Randomness and Computation
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
- If you have not taken the
and Data Structures (ADS) course (or similar in another University),
you should take that first unless you are a very strong student.
- To get a feel for the material, you can take a look at the
2016/17 exam paper and/or the 2017/18 and 2018/19 papers.
There are also earlier papers on the library site (written by a
- All prospective students should do the
test I have created. When you have finished (it will take an hour and
half or maybe two) drop me a message asking for solutions. You
should be able to do about 70% of the questions without Googling
or needing help - say 10 of the 15 questions.
- Instructors: Mary
Cryan and Heng Guo
- 11:10-12:00 Tuesday in room 2.3 of the Lister Centre (5 Roxburgh Place).
- 11:10-12:00 Friday in room 1.3 of the Lister Centre (5 Roxburgh Place).
- Textbook: The required textbook for the course is ``Probability
and Computing: Randomized Algorithms and Probabilistic Analysis" by
Mitzenmacher and Upfal.
- Assessment: A written examination contributes 80% of the
final grade. The remaining 20% will be based on the second (pencil and
paper) homework exercise.
We planned to have 5 tutorials during the semester, on weeks
4, 6, 7, 8 and 10.
However week 8 was cancelled due to
the strike, and week 10 will move into week 11 (Thurs 2nd
and Fri 3rd April) and online
because of the Coronavirus shutdown.
We had two options, and students could attend
whichever they preferred:
Tutorial Sheets will be available on Learn.
- Tuesdays 12.10-13.00, G203 Teaching Room 2, Doorway 3,
- Wednesday 12.10-13.00, Lister Centre 1.4
Lecture recording will appear in Learn.
Slides below the gray line are from the last year. They will be
updated as we progress.
- Lectures 1-3 (January 14, 17, 21) Introduction. Elementary
examples: identity testing, verifying matrix multiplication, randomized
min-cut. (Chapter 1 of [MU]).
- Lectures 4 and 5 (January 24 and 28)
(random variables, independence, expectation, variance, moments).
Markov's inequality, Jensen's inequality, Chebyshev's inequality.
Application: Coupon collector's problem. (Sections 2.1, 2.2, 2.4
and 3.1-3.3 of [MU]).
- Lecture 6 (January 31) 2-approximation for Max-Cut;
de-randomization via conditional expectation
- Lectures 7 and 8 (February 4, 7) Chernoff Bounds
and applications (from Chapter 4 of [MU]):
Lectures 9 and 10 (February 11 and 14) Balls in Bins
(from Chapter 5 of [MU])
- Lectures 11-12 (February 25 and 28)
The Probabilistic Method
week 7: lost due to strike action
- week 8: lost due to strike action
- week 9: teaching "paused" due to University closure
Lecture 13 (March 24 (online))
The Lovasz Local Lemma
- Lectures 14-15 (April 1 and 2 (online))
Markov chain basics, application to 2-SAT (first half Chapter 7)
END OF TAUGHT/ASSESSED MATERIAL
Lectures 16-17: (uncovered due to strike)
Markov chain Monte Carlo, DNF counting, approximately counting
- Lectures 18-19: (uncovered due to strike)
Mixing-time of Markov chains.
There will be two courseworks in total: the
first will be marked and (formative) feedback returned, but will
not contribute to the final mark.
They will be available on Learn.
Here is a rough outline of the course material:
- Introduction: Las Vegas and Monte Carlo algorithms
- Elementary Examples: checking identities, fingerprinting
- Moments, Deviations and Tail Inequalities
- Balls and Bins, Coupon Collecting, stable marriage, routing
- Randomization in Sequential Computation
- Data Structures, Graph Algorithms
- Randomization in Parallel and Distributed Computation
- Algebraic techniques, matching, sorting, independent sets
- Randomization in Online Computation
- Online model, adversary models, paging, k-server
- The Probabilistic Method
- Threshold phenomena in random graphs, Lovasz Local Lemma
- Random Walks and Markov Chains
- Hitting and cover times, Markov chain Monte Carlo, mixing times
Please read the following guidelines regarding coursework:
Academic Conduct Policy: Students are expected to adhere to
the academic conduct policy of the University; this policy can be found in full
Late Coursework Policy: Please see here
for the late coursework policy of the School of Informatics.