Department of Computer Science and Technology

Course pages 2019–20

Subsections


Unit: Probability and Computation

This course is only taken by Part II 75% students.

Lecturers: Dr. T.M. Sauerwald, Dr. N. Rivera, Dr. J. Sylvester, Dr. L. Zanetti

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: Introduction and review of probability theory: Review of probability theory: Random variables, Independence, Markov and Chebychev inequalities. Basic Randomised Algorithms
  • Concentration Inequalities: How to derive Chernoff bounds, Applications to load balancing and quick-sort. Extensions of Chernoff bounds.
  • Random walks and Markov chains: Transition matrices, Stationary distribution and Convergence. Mixing time and total variation distance. Applications of Markov chains such as Connectivity testing, Solving 2-SAT, Sampling from unknown distributions and MCMC.
  • Spectral Analysis of Random Walks: Convergence Rate, Cheeger’s Inequality, Applications including Graph Clustering.
  • Advanced Randomised Algorithms: Sublinear-Time Algorithms, Matrix Verification, Random Projection and Dimensionality Reduction.

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.