Randomness and Computation
Spring 2017
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.
News
 (May 8th) I have added a "what to learn" page
here, to clarify what is examinable.
 Our course is on "nb@mit.edu" and I will be uploading
all the slides (with annotations) today (8th May).
I've added a updated copy of cwk 2 there, with annotations.
The link to log in is https://nb.mit.edu
(and it is now working with Firefox as well as Safari and Chrome).
 Office hours preexam are 1112:30 each morning.
 The feedback for Coursework 2 has
now been returned to students (Monday 10th at the ITO, direct
emails sent Tuesday 11th).
The solutions/markingscheme are here.
 The solutions for Coursework 1
are here.
Course Information
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
Lectures
 Lectures 14 (January 17, 20, 24, 27) Introduction. Elementary
examples: identity testing, verifying matrix multiplication, randomized
mincut. (Chapter 1 of [MU]). lecture1.pdf,
lecture14.pdf
lecture2.pdf,
lecture24.pdf,
lecture3.pdf,
lecture34.pdf
lecture4.pdf,
lecture44.pdf
 Lectures 5 and 6 (January 31, Feb 3) Review of
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]).
lecture5.pdf,
lecture54.pdf,
lecture6.pdf,
lecture64.pdf
 Lectures 7 and 8 (February 7, 10) Chernoff
Bounds. (Sections 4.14.4 of [MU]).
lecture7.8.pdf,
lecture7.84.pdf.
 Lectures 9 and 10 (February 14 and 17) Balls and Bins.
(Sections 5.15.4 of [MU]). lecture9.10.pdf,
lecture9.104.pdf.
 Lectures 11 and 12 (February 28, March 3) Hamilton
cycles in random graphs (Section 5.6 of [MU])
lecture11.12.pdf,
lecture11.124.pdf.
 Lecture 13 (March 7)
The Probabilistic Method, derandomization via conditional
expectations. (Sections 6.16.4 of [MU]).lecture13.pdf,
lecture134.pdf.
 "tutorial" (March 10)
I will take questions about Coursework 1 (you'll have feedback
by now) and endofprintout questions.
 Lectures 14 and 15 (March 14 and 17)
Markov chain basics (first half Chapter 7)
lecture14.pdf,
lecture144.pdf;
lecture15.pdf,
lecture154.pdf.
 Lectures 16 and 17 (March 21 and 24)
The Monte Carlo method (some of Chapter 10)
lecture16.pdf,
lecture164.pdf;
lecture17.pdf,
lecture174.pdf
 Lectures 18, 19, 20 (March 28 and 31)
Mixing time bounds for Markov chains (Chapter 11),
lecture18.pdf,
lecture184.pdf
lecture19.pdf,
lecture194.pdf
 "tutorial" (April 4)
Coursework
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.