skip to primary navigationskip to content

Department of Computer Science and Technology

Undergraduate

Course pages 2021–22

# 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