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.
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
- Lecture 1 (January 14) Introduction. Elementary examples: identity testing, verifying matrix multiplication, randomized min-cut. (Chapter 1 of [MU]).
- Lecture 2 (January 21) 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.1-3.3 of [MU]).
- Lecture 3 (January 28) Analysis of Randomized Quicksort and Randomized Median. (Sections 2.5 and 3.4 of [MU]).
- Lecture 4 (February 4) Chernoff Bounds. (Sections 4.1-4.4 of [MU]).
- Lecture 5 (February 11) Balls and Bins. (Sections 5.1-5.4 of [MU]).
- Lecture 6 (February 25) Balls and Bins Continued. The Probabilistic Method. (Sections 6.1-6.4 of [MU]).
- Lecture 7 (March 4) The Second Moment Method (Sections 6.5, 6.7 of [MU]).
- Lecture 8 (March 11) Lovasz Local Lemma (Section 6.7 of [MU]).
- Lecture 9 (March 18) Markov Chains (Sections 7.1-7.3 of [MU]).
- Problem Set 1 (Handed out February 18th; due on March 7th; marks returned by March 21st.). ps1.pdf.
- Problem Set 2 (Handed out March 14th; due on March 28th; marks returned by April 7th.). ps2b.pdf.
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.