Memoization vs dynamic programming

memo-dyn.txt

Memoization is fundamentally a top-down computation and dynamic
programming is fundamentally bottom-up.  In memoization, we observe
that a computational *tree* can actually be represented as a
computational *DAG* (the single most underrated data structure in
computer science); we then use a black-box to turn the tree into a
DAG.  But it allows the top-down description of the problem to remain
unchanged.

In dynamic programming, we make the same observation, but construct
the DAG from the bottom-up.  That means we have to rewrite the
computation to express the delta from each computational tree/DAG node
to its parents.  We also need a means for addressing/naming those
parents (which we did not need in the top-down case, since this was
implicit in the recursive call stack).  This leads to inventions like
dynamic programming tables, but people often fail to understand why
they exist: it's primarily as a *naming mechanism* (and while we're at
it, why not make it efficient to find a named element, ergo arrays).

In both cases, there is the potential for space wastage.  But in the
case of memoization, it is very difficult to get rid of this (you
*could* have custom, space-saving memoizers, as Stephen says, but then
the programmer has to take the risk of using the wrong one...which to
me destroys the beauty of memoization in the first place).  In DP it's
easier to save space because you can just look at the delta function
to see how far "back" it reaches; beyond there lies garbage, and you
can come up with a cleverer representation that stores just the
relevant part of the fringe.  The iterative fibonacci is the extreme
case of this, where an inductive variables play the role of the entire
DP "table".

In my class, we work through some of the canonical DP algorithms as
memoization problems instead, just so when students later encounter
these as "DP problems" in algorithms, they can be wise-asses about it.
(There are innumerable things wrong with the way DP is presented by
algorithms teachers, but hey, what do you expect.)

Trade-offs:

Memo:

- leaves computational description unchanged (black-box)
- avoids unnecessary sub-computations
 (ie, automatically saves time)
- hard to save space
- always check whether a sub-computation has already been
 done before doing it (ie, always incur a small cost)
- time complexity depends on picking a smart computation name
 lookup strategy

DP:

- forces change in desription; may introduce errors
- cannot avoid unnecessary sub-computations
 (ie, impossible to save time)
- can more easily save space
- no need to check whether a computation has been done before
 doing it (ie, no cost of a check)
- space complexity depends on picking a smart data storage strategy

So, I teach my students: first write the computation, observe whether
it fits the DAG pattern; if it does, use memoization.  Only if the
space proves to be a problem and a specialized memo strategy won't
help -- or, even less likely, the cost of "has it already been
computed" is also a problem -- should you think about converting to DP
-- and then, do so in a methodical way.  Every subsequent programmer
who has to maintain your code will thank you.

QUIZ: Here's what I ask at the end of my memo/DP lectures:

Memoization is an optimization of a top-down, depth-first computation
for an answer.  DP is an optimization of a bottom-up, breadth-first
computation for an answer.  We should naturally ask, what about

- top-down, breadth-first
- bottom-up, depth-first

(a) Do we already have names for these without realizing it?, or
(b) Have we been missing one or two important tricks?, or
(c) Is there a reason we don't have names for these?

Shriram
________________________
PLT Educators talk list:
http://lists.racket-lang.org/plt-edu-talk