Randomness and Computation
Spring 2020
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.
 If you have not taken the
Algorithms
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
past lecturer).
 All prospective students should do the
Self
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.
Course Information
 Instructors: Mary
Cryan and Heng Guo
 Lectures:
 11:1012:00 Tuesday in room 2.3 of the Lister Centre (5 Roxburgh Place).
 11:1012:00 Friday in room 1.3 of the Lister Centre (5 Roxburgh Place).
 Course
catalogue entry
 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.
Tutorials
We will have 5 tutorials during the semester, on weeks
weeks 4 (February 5th and 6th), 6, 7, 8 and 10. There are
two options, and you may attend whichever you prefer:
 Tuesdays 12.1013.00, G203 Teaching Room 2, Doorway 3,
Medical School
 Wednesday 12.1013.00, Appleton Tower 7.14
Lectures
Lecture recording will appear in Learn; also I will add
direct links to the lecture schedule).
 Lectures 13 (January 15, 18, 22) Introduction. Elementary
examples: identity testing, verifying matrix multiplication, randomized
mincut. (Chapter 1 of [MU]).
 Lectures 4 and 5 (January 25 and 29)
Discrete Probability
(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.13.3 of [MU]).
 Lecture 6 (February 1) 2approximation for MaxCut;
derandomization via conditional expectation
 Lectures 7 and 8 (February 5, 8) Chernoff Bounds
and applications (from Chapter 4 of [MU]):
 Lectures 9 and 10 (February 12 and 15) Balls in Bins
(from Chapter 5 of [MU])
 Lectures 1113 (February 26, March 1 and 5)
The Probabilistic Method, and the Lovasz Local Lemma
 Lectures 1415 (March 8 and 12)
Markov chain basics, application to 2SAT (first half Chapter 7)
 Lectures 1617: (March 15 and 18)
Markov chain Monte Carlo, DNF counting, approximately counting
Independent Sets
 Lectures 1819: (March 22 and 26)
Mixingtime of Markov chains.
Coursework
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:
 Coursework 1 (formative):
due 4pm, Thursday, 14th February
Feedback was returned on 7th March, solutions/markscheme
is here.
 Coursework 2 (summative):
due 4pm, Tuesday, 19th March.
Feedback was returned on 8th April, solutions/markscheme
is here.
Course Outline
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, kserver
 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
Guidelines
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
here.

Late Coursework Policy: Please see here
for the late coursework policy of the School of Informatics.