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