Randomness and Computation
Spring 2015
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.
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
Lectures
 Lecture 1 (January 13) Introduction. Elementary examples: identity testing, verifying matrix multiplication, randomized mincut. (Chapter 1 of [MU]).
Slides.
 Lecture 2 (January 20) 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]).
 Lecture 3 (January 27) Analysis of Randomized Quicksort and Randomized Median. (Sections 2.5 and 3.4 of [MU]).
 Lecture 4 (February 3) Chernoff Bounds. (Sections 4.14.4 of [MU]).
 Lecture 5 (February 10) Balls and Bins. (Sections 5.15.4 of [MU]).
 Lecture 6 (February 24) The Probabilistic Method. (Sections 6.16.4 of [MU]).
Coursework
 Problem Set 1 (Handed out February 9th; due on February 27th; marks returned by March 9th.).
ps1.pdf.
 Problem Set 2 (Handed out March 10th; due on March 24th; marks returned by April 7th.).
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.