Dynamic programming is an optimization technique using divide and conquer, whereas memoization is an added optimization in the dynamic programming paradigm. An optimization we do while calculating fibonacci sequence is memoization, to prevent from going down the tree to the leaf every time.
Dynamic Programming versus Memoization
21–29 of 29 posts
Re: Dynamic Programming versus Memoization
#22My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.
A DAG has directed edges, whereas a tree does not. Also, a node in a tree can only have 1 parent. Here's an example of a DAG that can't be a tree because of the edge directions: http://en.wikipedia.org/wiki/File:Directed_acyclic_graph_3.s...
Trees are commonly directed. Single in edge per node is the important distinction.
Re: Dynamic Programming versus Memoization
#23Earlier quoted context omitted.
A DAG has directed edges, whereas a tree does not. Also, a node in a tree can only have 1 parent. Here's an example of a DAG that can't be a tree because of the edge directions: http://en.wikipedia.org/wiki/File:Directed_acyclic_graph_3.s...
Trees are commonly directed. Single in edge per node is the important distinction.
Right, but then we'd be talking about the difference between a "directed tree" and a DAG...or a "rooted tree" and a DAG. But yea, I'm sure grand-parent gets the point by now
Re: Dynamic Programming versus Memoization
#24My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.
In programming lingo a tree is usually a directed acyclic graph in which every node has exactly one incoming edge (one parent) except for the root node, which has no parents. A "cycle" in a directed graph is a loop that connects a node to itself along directed edges, so "acyclic" just means there aren't any loops. In this case, that means no circular dependencies among the computations.
There's also a mathematical definition of tree which is occasionally used in theoretical CS, so you have to be careful about getting them mixed up, but that kind of tree is an undirected acyclic graph. The kind of tree they're talking about in the article is directed, because it represents computational dependencies. (If A is connected to B, then either A depends on B or B depends on A. The dependency only goes one way.)
The defining difference between a tree and a directed acyclic graph is that a node in a DAG can have more than one incoming edge. So a DAG is like a tree in which nodes can have more than one parent. Here's the simplest illustration. I can't draw arrows, but imagine each edge being directed from top to bottom, so that A is the root of the tree:
A (a tree, therefore A (a DAG, but not a tree)
/ \ also a DAG ) / \
B C B C
/ \ /
D D
A
/ \
B C
/ / \
D E D
\ \
F F
A
/ \
B C
\ / \
D E
\
F
The idea of memoization is that each node in the tree should be the name of a computation, and the computation itself should be looked up by name. That way even if a name occurs multiple times in the tree, the computation it names will only occur once. The computations named "B" and "C" both depend on a computation named "D" which they will look up by name. They don't have to know they share a dependency, and they don't even have to reference the same copy of the name "D". This extra layer of indirection is the "black box of memoization" that implicitly turns the tree into a DAG to avoid replicating computations D and F.
Re: Dynamic Programming versus Memoization
#25Earlier quoted context omitted.
Trees are commonly directed. Single in edge per node is the important distinction.
Right, but then we'd be talking about the difference between a "directed tree" and a DAG...or a "rooted tree" and a DAG. But yea, I'm sure grand-parent gets the point by now
Yep, thanks. I realize that in graph theory trees aren't directed, but in programming, saying "tree" almost always implies a parent-child relationship (i.e, directedness).
I was missing that nodes in a DAG can have two "parents", that makes sense.
Re: Dynamic Programming versus Memoization
#26I think this neglects a performance consideration: dynamic programming is often simpler for a compiler to optimize, since it's generally a set of nested loops. Sometimes you can vectorize operations, but often you can just exploit locality to keep all the active set in l1 cache (not a compiler optimization per-se). Memoization, however, is much more of a black-box. Very few compilers will handle the branching present…
This won't help everywhere, but sometimes you can give the compiler a hint that a certain branch is less likely to be taken. The computation branch is going to be slower anyway, and only happen once, so tell the compiler to assume the lookup branch will be taken most of the time.
Re: Dynamic Programming versus Memoization
#27My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.
A tree is a DAG that is connected: if a and b are nodes of a tree, there is a path between a and b . But in general a DAG doesn't have to be connected. So all trees are DAGs but not all DAGs are trees: some are forests i.e. unions of trees.
A tree is a DAG that's simply connected.
Re: Dynamic Programming versus Memoization
#28My lack of a formal CS background is hurting me here. Could someone speak to the distinction between a tree and a DAG they make here? I was under the impression that the terms were more or less synonymous.
In programming lingo a tree is usually a directed acyclic graph in which every node has exactly one incoming edge (one parent) except for the root node, which has no parents. A "cycle" in a directed graph is a loop that connects a node to itself along directed edges, so "acyclic" just means there aren't any loops. In this case, that means no circular dependencies among the computations. There's also a mathematical de…
I should add: a consequence of allowing more than one incoming edge is that a DAG can have more than one "root," like this:
A B
\ /
C
Re: Dynamic Programming versus Memoization
#29This is a really interesting way to think about computations. I mostly think of memoization for I/O things like database lookups, or long computations. I'd never thought of it in comparison to dynamic programming algorithms.
> I'd never thought of it in comparison to dynamic programming algorithms. The blog post is using a different terminology. Memoization isn't part of dynamic programming - it's just that the top-down dynamic programming benefits from memoization. The top-down fibonacci is defined as fib(n) = fib(n-1) + fib(n-2) Since fib(n-1) and fib(n-2) are overlapping(they have to overlap for it to be an example of dynamic programm…
I don't know that the terminology is common (or correct), but I find it pretty useful. It also corresponds intuitively to the way people in practice use these terms. I say keep it.
TLDR for OP: in both "DP" and "memoization" you construct a name-value table for a given function. In "memoization" you construct it reactively, in "DP" proactively - where "reactively" means "lazily as we need it," and "proactively" means "any way that isn't reactively."
(A dag being just one way of storing this data structure. Generally it is just a cache of function results - which can be stored as a table, derivation graph, or whatever.)