Algorithms/Dynamic Programming

Notes

Skiena Chapter 8

Fibonacci example

Skiena begins the chapter with the Fibonacci example.

Worst way to do Fibonacci calculation: using recursion

More efficient way to do Fibonacci calculation: cache the intermediate results

Most efficient way: specify the order of evaluation in such a way that the results that are needed are always available. No caching necessary. It's a bit trivial once you reach this point, but it is still dynamic programming - you're just specifying the order in which to evaluate the sub-problems so that you always have the information you need.

Binomial dynamic programming example

Skiena uses the binomial coefficient as an example of a problem with a single expression that can be evaluated, but that single expression will cause integer overflow.

Instead: use identity,

$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $

and the base cases:

$ \binom{p}{0} = 1 $

$ \binom{p}{1} = p $

$ \binom{p}{p} = 1 $

To implement this, we can build a table/array, which will contain Pascal's triangle...

Left column: m, top column: n

Now the order of operations is to fill in the edges of Pascal's triangle (the base cases) first

• Initialize column 0 = 1
• Initialize diagonal = 1

Now loop over each row and each column of the row to compute the binomial coefficient:

for i = 1 to n:
    for j = 1 to i:
        calculate binomial coefficient

Resources

MIT Open Courseware 6.006

Links to Videos

Dynamic programming 1: Fibonacci, shortest paths: https://www.youtube.com/watch?v=OQ5jsbhAv_M

Dynamic programming 2: Blackjack: https://www.youtube.com/watch?v=ENyox7kNKeY

Dynamic programming 3: Parenthesization, edit distance, knapsack: https://www.youtube.com/watch?v=ocZMDMZwhCY

Dynamic programming 4: guitars, tetris, super mario: https://www.youtube.com/watch?v=tp4_UXaVyx8

MIT Open Courseware 6.046

Links to Videos

The topic of dynamic programming is covered in the MIT 6.046 open courseware playlist: https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

The course begins with dynamic programming, by covering the divide and conquer approach for finding a convex hull: https://www.youtube.com/watch?v=EzeYI7p9MjU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=2

It continues with a divide and conquer approach for matrix algebra and Fast Fourier Transforms: https://www.youtube.com/watch?v=iTMn0Kt18tg&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=4

It then covers divide and conquer for van Emde Boas trees: https://www.youtube.com/watch?v=hmReJCupbNU&index=6&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

Recitation with more dynamic programming examples: https://www.youtube.com/watch?v=krZI60lKPek&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=12

Advanced dynamic programming: https://www.youtube.com/watch?v=Tw1k46ywN6E&index=14&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

Dynamic programming for all pairs, shortest paths: https://www.youtube.com/watch?v=NzgFUwOaoIw&index=15&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp