Randomness and Computation

Spring 2018

Alice in Randomland
One of the most remarkable developments in Computer Science over the past 30 years has been the realization that the ability of computers to toss coins can lead to algorithms that are more efficient, conceptually simpler and more elegant that their best known deterministic counterparts. Randomization has by now become a ubiquitous tool in computation.

This course will survey several of the most widely used techniques in this context, illustrating them with examples taken from algorithms, random structures and combinatorics. Our goal is to provide a solid background in the key ideas used in the design and analysis of randomized algorithms and probabilistic processes.

Students taking this course should have already completed a good Algorithms courses (with theoretical underpinnings), and have excellent Maths.

Course Information


We had/will-have tutorials between 12-1 on Wednesdays of week 4 (7th Feb), week 6 (28th Feb), week 8 (14th Mar), week 10 (28th Mar) and week 11 (4th Apr) .

Up to now, the location for the tutorials has been 1.203, Meeting Room 7 Bristo Square, but this may change (after checking the Doodle poll I sent out, it is clear Wed at 12 is the best day/time). The planned week 7 tutorial was cancelled because of the snow-cancelled lecture Friday 2nd (and the reading week before week 6); we may possibly add one in week 11.


Lecture recording is under the "Media Hopper" tab in Learn; also I have added direct links below (only started 4th lecture)


There will be two courseworks in total: the first will be marked and (formative) feedback returned, but will not contribute to the final mark. Deadlines will be:

Course Outline

Here is a rough outline of the course material:


Please read the following guidelines regarding coursework: