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?