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.
- You can take a look at last year's exam paper
- 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.
We have published Last year's Survey report
based on feedback from 2016/17 students. I have also written
a response to this, describing
improvements to be made this year.
- (May 18th) I have uploaded solutions
to coursework 1, as it is getting late to pick things up from
- (May 14th) I have added a "what to learn" page
here, to clarify what is examinable.
- (Apr 25th) I returned the marked coursework (cwk2) to the ITO,
and also left a stack of printed-out solutions/marking-scheme
there. Please pick a copy up.
- Instructor: Mary
- Lectures: 11:10-12:00, Tuesdays and Fridays, in
50 George Square, G.05.
- 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 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)
- Lectures 1-4 (January 16, 19, 23, 26) Introduction. Elementary
examples: identity testing, verifying matrix multiplication, randomized
min-cut and max-cut. (Chapter 1 of [MU]).
lecture1-4.pdf, board photos (jpg)
3, 4 on
testing polynomial identity.
lecture2-4.pdf on Matrix
board photo (jpg) continuing Matrix
Multiplication verification, introducing Min Cut.
mp4(slides+voice), analyzing Karger's
Min Cut; simple 2-appx for Max Cut.
- Lectures 5 and 6 (January 30, February 2)
(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]).
- Lectures 7 and 8 (February 6, 9) Chernoff Bounds
(from Chapter 4 of [MU]):
- Lecture 9 (February 13) Balls in Bins
(from Chapter 5 of [MU]):
- Lectures 10-12 (February 16 and thereafter)
``The Probabilistic Method, and the Lovasz Local Lemma"
(rearranged and typos corrected)
- Lectures 13 and 14 (March 27 and April 3)
Markov chain basics, application to 2-SAT (first half Chapter 7)
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:
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.