Selective books, lectures and practice
Use local lessons first. Full-book reading is not required; no purchase or book conversion is needed.
- Jeff Erickson, Algorithms: Chapter 12, NP-Hardness. Focus on reduction definitions, the distinction between hardness and completeness, Independent Set/Clique/Vertex Cover, and pseudopolynomial algorithms. Treat 3-SAT completeness as an external starting theorem; reconstruct the local reduction chain yourself.
- MIT 6.006, Lecture 19: Complexity: an optional alternative explanation of problem classes and reductions. Watch to repair a specific confusion, then solve a changed example without the lecture.
- Erickson’s approximation notes, section J.5, Vertex Cover Redux: compare selecting both endpoints with the local matching-certificate proof. This is a separate set of lecture notes, not a chapter of the main book.
- Reuse Module 3’s matching definitions and Module 4’s knapsack state/cost analysis. A maximal matching is enough for the local approximation proof; maximum bipartite matching is a different task.
Within the 13–18 hour teaching/practice allowance, spend roughly 4–5 hours on definitions/encodings, 4–6 on reduction constructions, and 5–7 on certificates/approximation/solver selection. Complete all six local practice tasks and the concept drills. Optional textbook exercises add depth: record exact section/problem labels from your edition rather than relying on invented page numbers. Solutions to local practice and assessment are supplied for calibration after an attempt.
Local lessons, examples and lab code are original. Source links were checked on 2026-10-22. The textbook and course are references, not evidence that this module has undergone external review.
Language and computational limits
The required automata/computability bridge supplies original lessons, a runnable experiment, selective MIT notes and AC1–AC4. All four gates must reach 2 independently in addition to CA1–CA6. Its additional 20–30 hours are included in the revised 45–65-hour module total.