Skip to main content

Complexity, Reductions and Approximation

Complete Modules 1–3 first: proof/cost models, basic data structures and graph contracts. Module 4’s knapsack discussion supplies a useful pseudopolynomial example; Module 5 is not a prerequisite. No calculus or statistical-inference prerequisite is introduced.

The earlier modules teach how to build algorithms. This module teaches how to defend a problem transformation, recognize the limits of an optimality claim, and choose a bounded alternative. Existing references to bit costs, matching and approximation remain useful; this sequence supplies the missing connected treatment.

Original complexity package: 25–35 focused hours: lessons and written practice 13–18, lab/project 8–11, independent assessment and delayed repair 4–6. These are author estimates awaiting pilots. Reuse the project appendix at semester review; do not count it twice.

Entry check and repair​

Before the new terminology, use a three-vertex path: list its edges, test whether the middle vertex touches every edge, and enumerate all subsets by size. Explain why checking a returned object differs from searching all candidates. The checks use prior graph representation, subsets, loops and proof/cost models. Consult entry calibration after your attempt; repair Modules 1–3 if needed. This uses the existing lesson/practice allowance.

Learning sequence​

  1. Problems, encodings and certificates.
  2. Reduction direction and both implications.
  3. P, NP and an explicit hardness chain.
  4. A provable two-approximation.
  5. Exact search, limits and unresolved answers.
  6. Choose a solver without overstating guarantees.

Then complete practice, guided lab, project and assessment. Use the reading guide and worked examples for targeted repair.

Completion and scope​

Pass CA1–CA6 independently. Preserve a reduction proof, feasible cover, matching lower bound, exact small-instance comparison and honest resource limit. General approximation schemes, SAT-solver engineering, Cook–Levin’s proof and a full computability course remain outside scope.

Status: authored candidate with executable checks; independent technical review and learner calibration pending. Free sources suffice; full-book reading is not required.

Required language and computability bridge​

Complete the automata and computability bridge after the reductions lesson. It adds 20–30 hours and AC1–AC4, making this module 45–65 hours. Original CA1–CA6 and their 25–35-hour package remain required; a full computability course remains outside scope.