Department of Computer Science and Technology

Course pages 2018–19

Probability and Computation

Principal lecturers: Dr Thomas Sauerwald, Dr Nicolas Rivera, Dr John Sylvester, Dr Luca Zanetti
Taken by: Part II CST 75%

No. of lectures and practical classes: 16
Prerequisite courses: Algorithms, Foundations of Data Science.
Capacity: 30

Aims

The aim of this course is to introduce the design and analysis of randomised algorithms. It starts by introducing some essential tools and ideas from probability and graph theory, and develops this knowledge through analysing a variety of examples of randomised algorithms and processes. Ultimately the course demonstrates that randomness can be an elegant programming technique, and particularly helpful when time or space are restricted.

Lectures

  • Introduction and review of probability theory: Review of probability theory: Random variables, Markov chains, Markov’s inequality [1 lecture and Homework test]
  • Random walks and Markov chains: Mixing time and total variation distance, hitting and cover times. Applications of Markov chains including Connectivity testing, Solving 2-SAT, Sampling from unknown distributions, Coupling, Generating Random Permutations/Card shuffling [approx. 3 lectures]
  • Concentration Inequalities: How to derive Chernoff bounds, applications including load balancing and quick-sort, Martingales: optional stopping theorem, gambler’s ruin, random walks with drift, advanced tools: Azuma’s inequality, method of bounded differences, application to graph colouring, Dimensionality Reduction (if time permits) [approx. 4 lectures]
  • Spectral Analysis of Random Walks: Convergence Rate, Applications. [approx. 2 lecture].
  • Advanced Randomised Algorithms: Algorithms for Machine Learning, MAX-CUT, Streaming Algorithms, Distributed Algorithms [approx. 6 lectures]

Objectives

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

  • learn how to use randomness in the design of algorithms;
  • apply randomisation to various problems coming from optimisation, machine learning and distributed computing;
  • 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.