Complexity Analysis and Correctness

Two questions haunt every serious program. Is it fast enough? — will it still finish when the input is a million times bigger? And is it right? — not "did it pass the tests", but is it guaranteed to produce the correct answer on every input the specification allows? This master's-level course takes both questions to graduate depth, and shows that they are two faces of the same discipline: reasoning rigorously about what a computation does and what it costs.

The first half — complexity analysis — builds the machinery for measuring cost: asymptotics and recurrences, amortised and probabilistic analysis, the complexity classes P, NP, the polynomial hierarchy and PSPACE, NP-completeness and the art of reductions, and — when a problem is provably intractable — approximation, parameterised and exact-exponential algorithms, and matching lower bounds. The second half — correctness — builds the machinery for proof: Hoare logic and loop invariants, weakest preconditions and the guarded-command calculus, termination and total correctness, type soundness and the Curry–Howard correspondence, separation logic, and the automatic verification of temporal properties by model checking.

It assumes an undergraduate grounding in algorithms and automata, a little logic, and comfort with proof by induction.

Part A — Complexity Analysis

Module 1 — Models and asymptotics

  1. Big-O Notation — the informal starting point.

Module 2 — Recurrences

  1. Divide and Conquer — where recurrences come from.

Module 3 — Probabilistic and amortised analysis

Part B — Complexity Theory

Module 4 — Complexity classes and the hierarchy

  4. Complexity Classes: P, NP, PSPACE
  5. Space Complexity and the Hierarchy

Module 5 — NP-completeness and reductions

  2. NP-Completeness and Reductions

Module 6 — Beyond NP

Module 7 — Coping with intractability

Module 8 — Lower bounds

Part C — Correctness and Verification

Module 9 — Program correctness and Hoare logic

Module 10 — Predicate transformers and termination

Module 11 — Verification, types and proofs

Module 12 — Temporal logic and model checking

Begin → Models of Computation and Cost