## Course Description

The powerful role played by randomness in computation has been
among the central discoveries in the foundations of computer
science over the last three decades. Randomized algorithms are
algorithms that make random choices as they proceed, and have
had a fundamental impact on several areas of computer science
(e.g., distributed algorithms, cryptography, resource allocation,
approximation algorithms). This course is an introduction to
randomized algorithms. It aims to teach rigorous methods to
design and analyze such algorithms, and to present some of
the key applications of randomization in diverse fields of
computer science such as distributed computing, resource allocation,
scheduling, and packet routing.

## Announcements

The room for this class has
been changed to A. V. Williams 1112.

The **mid-term** will be in class
on October 12th, from 10:15 AM to 12:15 PM. You can bring your own notes,
the class handouts and homework assignments,
and a copy of the Motwani-Raghavan book.

The **final** will be held in the classroom
on December 17th, from 4 PM to 7 PM. You can bring your own notes,
the class handouts and homework assignments,
and a copy of the Motwani-Raghavan book.

The original versions of some of the material below
had some errors/typos, which have now
been corrected. I thank Rajiv Gandhi, Daniel Khodorkovsky,
Ruggero Morselli, and
Arunchandar Vasan for pointing out these errors.

## Handouts

Handout 1: Basic course information

Handout 2: Basics regarding expectations and the
probabilistic method

Handout 3: Facts related to the Chernoff-Hoeffding
bounds

Handout 4: The Lov'asz Local Lemma and Packet
Routing

Handout 5: Pessimistic estimators

Handout 6: The vertex-connectivity of random graphs

## Homework Assignments that will be graded, Exams

Homework 1, due on October 5th

Homework 2, due on November 9th

Homework 3, due on December 7th

Mid-term exam

Final exam

## Project

Project (Due by the beginning of class on December 7, 2001)

## Ungraded Homework Assignments

Ungraded Homework 1

Ungraded Homework 2

Ungraded Homework 3