AX26-CS-201 · 2026-27
Approximation and Randomised Algorithms
Analyse approximation ratios and randomised procedures with explicit algorithms, expectation or concentration, and a clear statement of what NP-hardness still forbids.
- Estimated study
- 200 hours
- Level
- Undergraduate level
- Topics
- 8
Course topics
- 01Approximation ratio and hardness reminders
- 02Greedy approximation (matching 2-approx)
- 03LP relaxation and rounding
- 04Monte Carlo and Las Vegas
- 05Concentration: Markov, Chebyshev, Chernoff
- 06Hashing and fingerprinting
- 07Streaming sketches (introduction)
- 08Course synthesis
Detailed syllabus and learning aims
Module aims
Produce ratio proofs and probability bounds that name the algorithm, the random bits, and the event whose probability is claimed.
Course outline
-
01 Approximation ratio and hardness reminders 25h
Learning result Define ρ-approximation and say what a hardness result does and does not rule out.
Formative check Four-option check
-
02 Greedy approximation (matching 2-approx) 25h
Learning result Prove that both endpoints of a maximal matching give a vertex-cover 2-approximation, or give a tight example for that matching argument.
Formative check Written derivation
-
03 LP relaxation and rounding 25h
Learning result Write a relaxation, a rounding rule, and a ratio that uses the fractional optimum.
Formative check Written derivation
-
04 Monte Carlo and Las Vegas 25h
Learning result Distinguish zero-error randomised runtime from bounded-error output, with an example of each.
Formative check Four-option check
-
05 Concentration: Markov, Chebyshev, Chernoff 30h
Learning result Derive a Chernoff tail for a sum of independent bounded indicators and apply it to a stated algorithm.
Formative check Written derivation
-
06 Hashing and fingerprinting 20h
Learning result Bound collision probability for a stated hash family and say when independence hypotheses are used.
Formative check Written derivation
-
07 Streaming sketches (introduction) 20h
Learning result State a sketch, its space and a failure probability; for a specified sketch where independence matters, construct and check a counterexample after dropping that hypothesis.
Formative check Counterexample
-
08 Course synthesis 30h
Learning result Write one complete argument: algorithm, approximation or error, probability, and remaining hardness.
Formative check Written derivation
Learning results
For a stated NP-hard problem or Monte Carlo task, give an algorithm, a ratio or error bound, and the probabilistic model used.
Subject skills
Approximation ratio, LP rounding, Chernoff bounds, Markov/Chebyshev, Monte Carlo versus Las Vegas.
Transferable skills
Separate a high-probability claim from a worst-case guarantee; do not treat a random example as a proof.