CS356 15 CATS (7.5 ECTS) Term 2
Core - DM, Option - CS, Mathematics
The module aims to introduce students to the area of approximation and randomised algorithms, which often provide a simple and viable alternative to standard algorithms.
Students will learn the mathematical foundations underpinning the design and analysis of such algorithms
By the end of the module, students should:
- Understand and use suitable mathematical tools to design approximation algorithms and analyse their performance.
- Understand and use suitable mathematical tools to design randomised algorithms and analyse their performance.
- Learn how to design faster algorithms with weaker (but provable) performance guarantees for problems where the best known exact deterministic algorithms have large running times.
- - Linearity of expectation, moments and deviations, coupon collector's problem
- - Chernoff bounds and its applications
- - Balls into bins, hashing, Bloom filters
- - The probabilistic method, derandomization using conditional expectations
- - Markov chains and random walks
- - LP duality, relaxations, integrality gaps, dual fitting analysis of the greedy algorithm for set cover.
- -The primal dual method: Set cover, steiner forest
- - Deterministic rounding of LPs: Set cover, the generalized assignment problem
- - Randomized rounding of LPs: Set cover, facility location
- - Multiplicative weight update method: Approximately solving packing/covering LPs
If time permits, more topics can be covered such as Tail inequalities for martingales, SDP based algorithms, local search algorithms, PTAS for Euclidean TSP, metric embeddings, hardness of approximation, online algorithms or streaming.
- Mitzenmacher and Upfal. Probability and Computing. CUP
- Motwani and Raghavan. Randomized Algorithms. CUP
- Dubhashi and Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. CUP
- Williamson and Shmoys. The Design of Approximation Algorithms. CUP
- Vazirani. Approximation Algorithms. Springer
Two-hour examination (80%), Coursework (20%)
30 one-hour lectures plus 9 one-hour seminars