Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.
Be able to implement solutions for simple optimization problems based upon dynamic programming techniques.
Example of dynamic programming using the cut rod problem.
Screencast Suthers 24 min
Example of dynamic programming using steps and LCS.
Screencast Suthers 17 min
Example of dynamic programming using LCS.
Screencast Suthers 18 min
Summary of dynamic programming.
Screencast Suthers 18 min
Rod cutting, matrix-chain multiplication, elements of DP, longest common subsequence, optimal BSTs
Textbook 55 pages
Knapsack problem, matrix chain product, optimal BSTs, shortest paths, time and space requirements
Textbook 14 pages
Apply dynamic programming principles again
Homework