Randomness and Computation

Spring 2014




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:

Lectures

Coursework

Guidelines

Please read the following guidelines regarding coursework: