DAGs can be used to solve any problem in CS proove me wrong
DAGs can be used to solve any problem in CS proove me wrong
fizzbuzz version or gtfo
P=NP
"Draw a graph containing a 3 node cycle"
> graph
> 3 node
Short path algorithm on Non-DAG
But yep DAG mapping any recursive function
What's wrong with that you retard
>google for "dag fizzbuzz"
>this thread is already in the 8th and 9th results
what the fuck
that's the power of Sup Forums my dude
digraph {
A -> B[label="1"];
B -> C[label="3"];
B -> D[label="2"];
B -> E;
C -> E[label="4"];
D -> E[labe="2"];
E -> F[label="3"];
G -> D[label="1"];
C -> D[label="1",color=red];
D -> A[label="2",color=red];
}
where is the fizzbuzz tho?
you'd need a stack as well. DAG could be a finite state machine, which isn't turing complete.
an example problem: identify strings of the form (a^x)(b^x)(c^x) where a^x is a repeated x times and juxtaposition is concatenation. e.g. "", "abc", "aabbcc", "aaabbbccc"
What if there is a relationship that isn't linear?
digraph {
A[label="n//3"];
B[label="n//5"];
C[label="n//5"];
Start -> A;
A -> B[label="false"];
B -> "toString(n)"[label="false"];
B -> "Buzz"[label="true"];
A -> C[label="true"];
C -> "Fizz"[label="false"];
C -> "FizzBuzz"[label="true"];
}
o shit it's the third result right now
Great work!
We made it to #1. Congrats everyone
i proved you wrong though
that looks more like a flowchart
Calculate the sum of all prime numbers below two million in less than one second.
Implement an algorithm that solves the travelling salesman problem in polynomial time.
Three 1-node DAGs placed inside a circularly linked list.
Halting problem. /thread
It's a digraph, and only two on the node pairs have bidirectional edges.
Graph with a single node of value 142913828922. This is also O(1)
A regular linked list containing:
>A circular linked list with two 1-node DAGs
>A 1-node DAG
NP on me
NP me on
Not you can't really argue /that's/ using only DAGs. You might as well implement a great data structure, which would be the only sane API to express what I'm describing anyway.
Listen to this OP, you also need a stack.
Here's another example: detect whether the input string is a palindrome.
Also are we just doing your homework?