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
- Office hours are every Monday 3-4, every Tuesday 12-1.
- Coursework 1 is out now :) (due Monday 20th
February at 4pm). You should submit by 4pm on the 20th by
one of the following routes:
- in person to the ITO in Forrest Hill
- electronically submitting the file coursework1.pdf
using the following command (when logged in on DICE):
submit rc 1 coursework1.pdf
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
- Lectures 1-4 (January 17, 20, 24, 27) Introduction. Elementary
examples: identity testing, verifying matrix multiplication, randomized
min-cut. (Chapter 1 of [MU]). lecture1.pdf,
- Lectures 5 and 6 (January 31, Feb 3) Review of
(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 7, 10) Chernoff
Bounds. (Sections 4.1-4.4 of [MU]).
- Lectures 9 and 10 (February 14 and 17) Balls and Bins.
(Sections 5.1-5.4 of [MU]). lecture9.10.pdf,
- Lecture 11 (February 28) Hamilton cycles in random
graphs (Section 5.6 of [MU])
- Lectures 12 and 13 (March 3 and 7)
The Probabilistic Method, derandomization via conditional
expectations. (Sections 6.1-6.4 of [MU]).
- "tutorial" (March 10)
I will take questions about Coursework 1 (you'll have feedback
by now) and end-of-printout questions.
- Lectures 14 and 15 (March 14 and 17)
Markov chain basics (first half Chapter 7)
- Lectures 16 and 17 (March 21 and 24)
The Monte Carlo method (some of Chapter 9)
- Lectures 18, 19, 20 (March 28 and 31, April 4)
Mixing time bounds for Markov chains (Chapter 11)
- "tutorial" (April 7)
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.