News for hackers. Stuff that matters.

A comment on The Racket Blog: Dynamic Programming versus Memoization. Parent comment

Re:The Racket Blog: Dynamic Programming versus Memoization by ot on Sunday August 26, 2012 @10:20AM (#4435134)
That's wrong, not all connected DAGs are trees.

A DAG is a directed graph that has no (directed) loops. Consider the following:

     A
    / \
   v   v
  B     C
   \   /
    v v
     D
This is a DAG but not a tree, because it has an undirected loop but no directed loops.
[ Parent | on HN ]
Re:The Racket Blog: Dynamic Programming versus Memoization by nandemo on Sunday August 26, 2012 @11:38AM (#4435301)
You're totally right (I had a thinko and managed to miss the D in the DAG). My apologies for the misinformation.
[ Parent | on HN ]