Algorithms/Dynamic Programming: Difference between revisions
From charlesreid1
No edit summary |
|||
| Line 3: | Line 3: | ||
==Skiena Chapter 8== | ==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 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, | |||
<math> | |||
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} | |||
</math> | |||
and the base cases: | |||
<math> | |||
\binom{p}{0} = 1 | |||
</math> | |||
<math> | |||
\binom{p}{1} = p | |||
</math> | |||
<math> | |||
\binom{p}{p} = 1 | |||
</math> | |||
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: | |||
<pre> | |||
for i = 1 to n: | |||
for j = 1 to i: | |||
calculate binomial coefficient | |||
</pre> | |||
=Resources= | =Resources= | ||
Revision as of 03:32, 8 August 2017
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 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