Module 4: Dynamic Programming & Optimization
Primary books: The Algorithm Design Manual and Introduction to Algorithms. Use selective reading, not full-book completion, to repair specific gaps. The authored lessons are the main path; you do not need to read all source chapters front to back.
This module develops the ability to derive a state, prove its recurrence, recover a valid output and account for resources. It includes 17 concept lessons, 10 worked examples, 20 practice problems with separate feedback, five offline labs implementing eight operations, independent assessment and a budgeted scheduling capstone. Expected focused effort is 90–125 hours, approximately 9–13 weeks at 10 hours per week; this is an author estimate awaiting learner pilots.
Scope and prerequisites
Begin with the prerequisite diagnostic: recursion, induction, subsets, binary-search boundaries, topological order and asymptotic/bit-size reasoning from earlier modules. The diagnostic does not require prior DP mastery.
The core covers state sufficiency, counting/optimization decompositions, evaluation order, reconstruction, numeric/storage costs, sequence/capacity/grid/interval/tree states, subsets, digit bounds and greedy-versus-DP reasoning. A correct recurrence may still be exponential or pseudo-polynomial; overlap explains reuse benefits but is not a universal prerequisite for DP.
Affine alignment, Hirschberg reconstruction, profile tilings, richer optimal BSTs, advanced split optimizations and approximation methods are bounded depth options. Their names do not create extra required implementations or imply later coverage that has not been specified.
Concept map
Lessons
Work in order, checking the state, proof and drill on each page. A failed boundary case should be repaired before optimizing the implementation.
The additional State, Witness, and Resource Contracts page connects the lesson proofs to API design and independent verification.
Learning objectives
By completion, independently:
- Distinguish histories that may be merged from those requiring more state.
- Derive sound, complete recurrences and disjoint cases for counting.
- Set empty/impossible bases and prove a valid evaluation order.
- Choose memoization/tabulation with a correct cache lifetime and stack bound.
- Reconstruct and independently validate an optimal object, accepting valid ties.
- Count transitions, live storage and relevant numeric bits before scaling.
- Prove a greedy rule or show a counterexample under a stated objective.
- Adapt a solved problem to a new constraint and revise the proof and resource bound.
Practice and implementation
| Path | Required work |
|---|---|
| Worked examples | Ten derivations with changed-assumption checks |
| Foundations practice | P1–P5: states, transitions, caching, witnesses and bit costs |
| Sequence/grid practice | P6–P10: LIS, alignment, capacity, counting and unreachable states |
| Advanced clinic | P11–P20: intervals, trees, subsets, digits and algorithm selection |
| Guided labs | LIS, edit distance, knapsack, weighted intervals, matrix chain, tree independent set, TSP and digit sum |
| Implementation studio | Targeted repair and a bounded transfer option |
Keep attempts before opening practice solutions. Lab contracts require witness checks, small exhaustive oracles and source/proof review. Passing fixtures alone does not establish mastery.
Assessment and completion
Complete the eight-task independent assessment, then use the scoring key and competency rubric. Reach level 2 in every competency; do not average away an invalid state or witness. Complete the budgeted scheduling capstone, repair gaps and take a fresh transfer task after 7–14 days.
Keep a state/proof notebook, tested implementation package, output validation, resource record and assistance disclosure. There is no arbitrary required number of mistakes or promise that content completion establishes an elite percentile.
Suggested study sequence
| Block | Focused hours |
|---|---|
| Diagnostic, 17 lessons, contracts and targeted reading | 30–40 |
| Five guided implementation labs | 25–35 |
| P1–P20, solution review and repair | 20–28 |
| Independent assessment, remediation and delayed transfer | 8–12 |
| Scheduling capstone and review | 7–10 |
Total: 90–125 hours. Depth extensions add time. Record actual effort to improve the estimate; the instructor guide separates authored, executed, independently reviewed and learner-piloted evidence.
Further support
Mistake Clinic | Case Studies | Reading Guide | Learning Resources | Reference and Selective Reading | Instructor Guide