- i. Complexity Theory and NP-Hardness: classes and their (corrected) relations, reductions with a tested 3-SAT example, the NP-complete catalogue, easy–hard pairs, FPT and kernels, lower bounds.
- ii. Approximation Algorithms: ratios and hardness, greedy guarantees, LP and randomized rounding, the knapsack FPTAS, Christofides, Goemans–Williamson.
- iii. Theoretical Algorithms Catalog: AKS to Wu–Manber by area, with what to write instead and tested Lucas–Lehmer, Toom-3, Good–Thomas, Rader, Two-Way and Wu–Manber.
- iv. Automata and Formal Languages: the Chomsky hierarchy, DFA/NFA minimization (tested), the pumping lemma, CYK parsing (tested), and why the halting problem is undecidable.
- v. Cryptography Fundamentals: RSA and Diffie–Hellman with proofs of correctness, what makes a hash function cryptographically safe versus CP-safe, and the unproven hardness assumptions everything rests on.
- vi. Quantum Computing Basics: qubits and superposition, Grover’s quadratic search speedup (provably optimal) and Shor’s period-finding attack on RSA/Diffie–Hellman, and what quantum computing does and doesn’t change for NP-hardness.
- vii. Parallel and Distributed Computing Theory: the PRAM model, work-span analysis and Brent’s scheduling theorem, Byzantine consensus’s bound, and the MapReduce model.