Approximation and Randomised Algorithms

模块目标

Produce ratio proofs and probability bounds that name the algorithm, the random bits, and the event whose probability is claimed.

课程大纲

1. 01 Approximation ratio and hardness reminders 25h

   学习结果 Define ρ-approximation and say what a hardness result does and does not rule out.

   形成性检查 四选一检查

2. 02 Greedy approximation (matching 2-approx) 25h

   学习结果 Prove that both endpoints of a maximal matching give a vertex-cover 2-approximation, or give a tight example for that matching argument.

   形成性检查 书面推导

3. 03 LP relaxation and rounding 25h

   学习结果 Write a relaxation, a rounding rule, and a ratio that uses the fractional optimum.

   形成性检查 书面推导

4. 04 Monte Carlo and Las Vegas 25h

   学习结果 Distinguish zero-error randomised runtime from bounded-error output, with an example of each.

   形成性检查 四选一检查

5. 05 Concentration: Markov, Chebyshev, Chernoff 30h

   学习结果 Derive a Chernoff tail for a sum of independent bounded indicators and apply it to a stated algorithm.

   形成性检查 书面推导

6. 06 Hashing and fingerprinting 20h

   学习结果 Bound collision probability for a stated hash family and say when independence hypotheses are used.

   形成性检查 书面推导

7. 07 Streaming sketches (introduction) 20h

   学习结果 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.

   形成性检查 反例

8. 08 Course synthesis 30h

   学习结果 Write one complete argument: algorithm, approximation or error, probability, and remaining hardness.

   形成性检查 书面推导

学习结果

For a stated NP-hard problem or Monte Carlo task, give an algorithm, a ratio or error bound, and the probabilistic model used.

学科技能

Approximation ratio, LP rounding, Chernoff bounds, Markov/Chebyshev, Monte Carlo versus Las Vegas.

可迁移技能

Separate a high-probability claim from a worst-case guarantee; do not treat a random example as a proof.