# Randomised Algorithms

**Principal lecturer:** Dr Thomas Sauerwald

**Taken by:** Part II CST 50%, Part II CST 75%

**Term:** Lent

**Hours:** 16

**Format:** Video lectures and in-person examples classes

**Suggested hours of supervisions:** 4

**Prerequisites:** Algorithms 1, Algorithms 2, Foundations of Computer Science, Introduction to Probability

**Exam:** Paper 8 Question 12; Paper 9 Question 12

**Past exam questions, timetable**

## Aims:

The aim of this course is to introduce advanced techniques in the design and analysis algorithms, with a strong focus on randomised algorithms. It covers essential tools and ideas from probability, optimisation and graph theory, and develops this knowledge through a variety of examples of algorithms and processes. This course will demonstrate that randomness is not only an important design technique which often leads to simpler and more elegant algorithms, but may also be essential in settings where time and space are restricted.

## Lectures:

**Introduction. **Course Overview. Why
Randomised Algorithms? A first Randomised Algorithm for the
MAX-CUT problem. [1 Lecture]

**Markov Chains and Mixing Times.** Random
Walks on Graphs. Application: Randomised Algorithm for the 2-SAT
problem. Mixing Times of Markov Chains. Application: Load
Balancing on Networks. [approx. 2 Lectures]

**Spectral Graph Theory and
Clustering.** Eigenvalues of Graphs and Matrices:
Relations between Eigenvalues and Graph Properties, Spectral
Graph Drawing. Spectral Clustering: Conductance, Cheeger's
Inequality. Spectral Partitioning Algorithm [approx. 2
Lectures]

**Linear Programming and
Applications.** Definitions and Applications.
Formulating Linear Programs. The Simplex Algorithm. Finding
Initial Solutions. How to use Linear Programs and Branch &
Bound to Solve a Classical TSP instance. [approx. 3 Lectures]

**Randomised Approximation
Algorithms.** Randomised Approximation Schemes.
Linearity of Expectations, Derandomisation. Deterministic and
Randomised Rounding of Linear Programs. Applications: MAX3-SAT
problem, Weighted Vertex Cover, Weighted Set Cover, MAX-SAT.
[approx. 2 Lectures]

**Concentration
Inequalities.** Moment-Generating Functions and
Chernoff Bounds. Extension: Method of Bounded Independent
Differences. Applications: Balls-into-Bins, Quick-Sort and Load
Balancing. [approx. 2 Lectures]

**Streaming and Online
Algorithms. **Introduction to Streaming. Approximate
Counting using Morris Algorithm. Online Learning using Experts:
Weighted Majority and Randomised Weighted Majority. [approx. 2
Lectures]

**Stochastic Bandits:** Greedy, Epsilon-Greedy,
UCB Algorithm. Outlook to Adversarial Bandits: EXP3 Algorithm
[approx. 2 Lectures]

## Objectives:

By the end of the course students should be able to:

- learn how to use randomness in the design of algorithms, in particular, approximation algorithms;
- learn the basics of linear programming, integer programming and randomised rounding;
- apply randomisation to various problems coming from optimisation, machine learning and data science;
- use results from probability theory to analyse the performance of randomised algorithms.

## Recommended reading

** Michael Mitzenmacher and Eli Upfal. Probability and
Computing: Randomized Algorithms and Probabilistic Analysis.,
Cambridge University Press, 2nd edition.*

** David P. Williamson and David B. Shmoys. The Design of
Approximation Algorithms, Cambridge University Press,
2011*

** Cormen, T.H., Leiserson, C.D., Rivest, R.L. and Stein,
C. (2009). Introduction to Algorithms. MIT Press (3rd ed.). ISBN
978-0-262-53305-8*