# CS356 Approximation and Randomised Algorithms

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.

## Learning Outcomes

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.

## Content

• - 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

15 CATS (7.5 ECTS)
Term 2

Organiser:
Dr Sayan Bhattacharya

Syllabus

Online material