Dynamic Programming
Let’s say you have an optimization problem that makes use of a cost function that needs to be computed over a set of discrete variables. For the sake of argument, assume that there is some sort of sub-structure or symmetry. How would you speed up the computation?
The simplest approach would be to build some sort of table for values
that have been computed already. Then, instead of reevaluating the
function each time, you can simply do a 
lookup.
The element of surprise here (atleast for me) is that this is called Dynamic Programming. I’m sure a lot of you have been using tricks like these for ages, but didn’t know what it was called. This new found knowledge has given me two things: keywords to search and preventing the NIH syndrome.
Consider a program to generate the Fibonacci sequence:
// lang lisp
(defun fib(x)
(cond ((= x 0) '0)
((= x 1) '1)
(t (+ (fib (- x 1)) (fib (- x 2)))))
)
The simple code snippet seems to work really well, but it has two
problems. The first problem obviously is the exponential growth in the
return values of the algorithm. Using the standard integer data type
will overflow at about 44 [[This is not a problem in lisp, which will autoconvert to BinInt.]]. Secondly, the recursive nature of the
algorithm necessitates computation of the same substructure over and
over. This is evident in the following backtrace from emacs, calling
fib with 6:
(0 1 2 1 0 1 2 3 4 1 0 1 2 3 0 1 2 1 0 1 2 3 4 5 6)
A lookup table, known as memoizing, will not solve the first problem, but will improve computation time considerably. This is pretty exciting stuff! Quickly skimming through some papers online led me to dynamic programming approaches in bioinformatics, control and information theory, signal processing (Viterbi algorithm), and ofcourse operations research.