Module: Dynamic Programming

Cut rod problem, longest common subsequence, matrix-chain multiplication, knapsack problem, optimal substructure.

Learning Outcomes

Apply dynamic programming to problem solving, including

Solve simple optimization problems using dynamic programming techniques.

Readings

Introduction to dynamic programming

Example of dynamic programming using the cut rod problem.

Screencast Suthers 24 min

Dynamic programming using steps and LCS

Example of dynamic programming using steps and LCS.

Screencast Suthers 17 min

Dynamic programming using LCS (continued)

Example of dynamic programming using LCS.

Screencast Suthers 18 min

Dynamic programming applications, substructure, and summary

Summary of dynamic programming.

Screencast Suthers 18 min

CLRS 15 - Dynamic Programming

Rod cutting, matrix-chain multiplication, elements of DP, longest common subsequence, optimal BSTs

Textbook 55 pages

Sedgewick 37 - Dynamic Programming

Knapsack problem, matrix chain product, optimal BSTs, shortest paths, time and space requirements

Textbook 14 pages

Notes on dynamic programming

Derivations of dynamic programming

Notes

Experiential Learning

Dynamic programming sample problem: matrix chain multiplication

Apply dynamic programming principles again

Homework