Learning Resources
This module is populated from the local chunked books in library/raw/semester-02-algorithms/books. Use this page as a source map, not as an instruction to read everything.
Source Stack
| Book | Role | How to use it in this module |
|---|---|---|
| Introduction to Algorithms (CLRS, Ch. 14) | Primary rigorous source | Default escalation for optimal substructure, memoization/tabulation, rod cutting, matrix chain, LCS, optimal BST |
| The Algorithm Design Manual (Skiena, Ch. 8) | Primary applied source | War stories, edit distance, LIS, partitioning, triangulation, limitations of DP (TSP) |
| Competitive Programming (Halim) | Problem variety and advanced patterns | Use for classical examples, bitmask DP, digit DP, tree DP, and DAG-based DP |
| Algorithms (Sedgewick) | Supporting prose | Use for an alternate DP framing if CLRS/Skiena feels opaque |
| Grokking Algorithms (Bhargava) | Friendly re-entry | Use only when a chapter feels opaque and you need a gentle first pass on grid or Fibonacci DP |
Resource Map by Cluster
Cluster 1: DP Foundations
| Need | Best local chunk | Why |
|---|---|---|
| the cut-and-paste argument and substructure definition | CLRS 14.3 Elements of DP (Part 1) | Rigorous statement and justification of optimal substructure |
| overlapping subproblems and the recursion DAG | CLRS 14.3 Elements of DP (Part 2) | Best explanation of why naive recursion is exponential |
| rod cutting as the canonical first DP | CLRS 14.1 Rod cutting (Part 1) | Smallest non-trivial full DP with explicit states and reconstruction |
| memoization vs tabulation trade-offs | CLRS 14.3 Elements of DP (Part 3) | Explicit top-down vs bottom-up comparison |
| reconstruction from the table | CLRS 14.1 Rod cutting (Part 3) | Parent-array reconstruction shown in full |
| first gentle exposure | Grokking Algorithms: 9 DP (Part 1) | Use only if the CLRS chunk feels too dense |
Cluster 2: Linear and Sequence DP
| Need | Best local chunk | Why |
|---|---|---|
| Fibonacci memoization and rolling array | Skiena 8.1.2 Fibonacci by Caching | Clean worked example of space reduction |
LIS O(n^2) and O(n log n) | Skiena 8.3 Longest Increasing Sequence | Best operational explanation with both algorithms |
| LIS practice set | Competitive Programming: 3.5.2 Classical Examples (LIS) | Additional LIS problem variations |
| edit distance recurrence | Skiena 8.2.2 Edit Distance by DP | Primary walkthrough of the 2D recurrence |
| edit-distance reconstruction | Skiena 8.2.3 Reconstructing the Path | Best coverage of script-recovery |
| edit-distance variants | Skiena 8.2.4 Varieties of Edit Distance | Weighted and constrained versions |
| LCS as a two-sequence DP | CLRS 14.4 LCS (Part 1) | Rigorous two-sequence substructure derivation |
| knapsack classical DP | Skiena 13.10 Knapsack Problem | 0/1 knapsack with pseudo-polynomial analysis |
| subset sum / partition | Skiena 8.5 The Partition Problem | Related boolean-table DP useful as a warm-up |
| knapsack problem variety | Competitive Programming: 3.5.2 Classical Examples (Knapsack) | Coin change and knapsack variants |
Cluster 3: Grid, Interval, and Tree DP
| Need | Best local chunk | Why |
|---|---|---|
| first grid DP | Grokking Algorithms: 9 DP (Part 2) | Friendliest first pass on 2D table filling |
| grid path counting | Competitive Programming: 3.5.2 Classical Examples (Counting Paths) | Direct grid-DP recurrences |
| matrix chain multiplication | CLRS 14.2 Matrix Chain (Part 1) | Canonical interval DP, rigorously derived |
| matrix chain fill order | CLRS 14.2 Matrix Chain (Part 2) | Explicit interval-length loop |
| optimal BST | CLRS 14.5 Optimal BST (Part 1) | Weighted interval DP with expected-cost objective |
| minimum weight triangulation | Skiena 8.6.1 Min Weight Triangulation | Geometric variant of interval DP |
| tree DP with weighted independent set | Competitive Programming: 9.22 Max Weighted Independent Set | Cleanest tree-DP exposition available here |
Cluster 4: Bitmask and Digit DP
| Need | Best local chunk | Why |
|---|---|---|
| TSP as bitmask DP | Skiena 8.7 Limitations of DP (TSP) | Motivates Held-Karp and discusses its ceiling |
| advanced DP techniques including bitmask and digit | Competitive Programming: 8.3 More Advanced DP Techniques | Compact guided tour of bitmask, digit, and state-compression |
| common DP parameters catalog | Competitive Programming: 8.3.2 Common DP Parameters | Reference for state-design choices |
| MLE mitigation | Competitive Programming: 8.3.4 MLE: Balanced BST as Memo Table | When dense tables blow memory, use sparse memo |
Cluster 5: Greedy vs DP and Optimization Tradeoffs
| Need | Best local chunk | Why |
|---|---|---|
| activity selection as a clean greedy | CLRS 15.1 Activity Selection (Part 1) | Best first proof of greedy correctness via exchange |
| elements of the greedy strategy | CLRS 15.2 Elements of the Greedy Strategy (Part 1) | Greedy-choice property formalized |
| greedy vs DP trade-off | CLRS 15.2 Elements of the Greedy Strategy (Part 2) | Explicit comparison on knapsack variants |
| DP on DAGs and min path cover | Competitive Programming: 9.24 Min Path Cover on DAG | Shows DP as topological-order computation |
| choosing a paradigm | Skiena 10 How to Design Algorithms | Best prose on paradigm selection |
| friendly greedy walkthrough | Grokking Algorithms: 8 Greedy Algorithms | Use only if CLRS 15.1 feels too formal |
Exercise Support Chunks
Use these when the concept pages are understood but your implementation fluency is weak:
- Competitive Programming: 3.5 Dynamic Programming
- Competitive Programming: 3.5.2 Classical Examples (LIS)
- Competitive Programming: 3.5.2 Classical Examples (Knapsack)
- Competitive Programming: 3.5.2 Classical Examples (Coin Change)
- Competitive Programming: 3.5.3 Non-classical Examples
- Competitive Programming: 6.5 String Processing With DP
External Resources (Validated)
Only open these when you want a second voice on a stubborn concept. Do not browse them casually.
- Erik Demaine, MIT OCW 6.046J Design and Analysis of Algorithms -- the DP lectures in the Spring 2015 version are the best free lectures on DP as a unified paradigm. Use them for Clusters 1, 2, and 5.
- MIT OCW 6.006 Introduction to Algorithms (Spring 2020) -- the DP unit has the cleanest "SRTBOT" state-recurrence template; use for Cluster 1.
- CP-Algorithms DP pages -- the intro to DP and knapsack articles are solid written references for Clusters 1, 2, and 4.
- Competitive Programmer's Handbook (Antti Laaksonen) -- the free PDF at cses.fi has excellent concise DP chapters; pair with the CSES problem set.
- USACO Guide: Intro to DP -- the Gold DP module has well-chosen problems with editorials; useful for Cluster 2 and 3.
- TopCoder: Dynamic Programming -- From Novice to Advanced -- the classic TopCoder DP tutorial by Dumitru is still the best "tour of tricks" for Clusters 3 and 4.
- AtCoder Educational DP Contest -- the 26-problem contest is the de-facto practice set for every DP pattern covered here (linear, knapsack, LIS, grid, interval, tree, bitmask, digit); use it across all five clusters.
- MIT 6.006 Lecture 15: DP Part 1 (SRTBOT, Fib, DAGs) -- the recitation + lecture materials are the cleanest derivation of the DP-as-DAG framing; pair with Cluster 1 and Cluster 5's DAG concept.
- MIT 6.006 Lecture 16: DP Part 2 (LCS, LIS, coin change) -- the follow-up lecture covers sequence DPs; pair with Cluster 2.
- CP-Algorithms: Knapsack -- the knapsack article covers all three knapsack variants with implementation tips; pair with concept 08.
- CP-Algorithms: SOS DP -- the Sum-over-Subsets DP article is the reference for subset-enumeration DP beyond Held-Karp; pair with concepts 12 and 14.
- Codeforces: Digit DP tutorial -- the classic tutorial with
(pos, tight, leading_zero, extra)state is the cleanest introduction; pair with concept 13. - Wikipedia: Bellman equation -- Bellman equation gives the bridge from DP to reinforcement learning referenced in the Transfer sections; read once per cluster 5.
Use Rules
- If you are stuck on optimal substructure or the recurrence itself, go to CLRS Ch. 14 first.
- If the recurrence is clear but you cannot turn it into a working implementation, go to Skiena Ch. 8 (or the matching Competitive Programming chunk) for worked pseudocode.
- If you need volume and problem variety, go to Competitive Programming Ch. 3.5 and 8.3.
- If a chunk feels opaque, write your own version of the recurrence and a small trace before opening another chunk.
- If rereading is not fixing the problem, stop and implement the smallest concrete instance by hand.
- External resources are escalation only. Do not start from external pages before the concept page and local book chunks.