Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas.
Prerequisites: Mathematical maturity; exposure to undergraduate material in Algorithms, and in Discrete Probability and Combinatorics. If you are not sure whether your background suffices, please see us.
Method of Evaluation: Grading will be based on (approximately bi-weekly) homework assignments, class participation and a take-home final. As part of class participation, each student (possibly in teams) will do a short project/presentation on a topic chosen in consultation with the instructors.
Textbook: Randomized Algorithms, Motwani and Raghavan. Other very nice books in the area include:
- Probability and computing: randomized algorithms and probabilistic analysis , Mitzenmacher and Upfal
- The Probabilistic Method, Alon and Spencer
- Approximation Algorithms, Vazirani
Material will be supplemented by handouts and papers.
Topics: A tentative list of topics includes:
- Basic Concepts: basic inequalities, the probabilistic method
- Elementary applications: Hashing, fingerprinting, identity testing
- Random walks: cover times, Markov chains, resistive networks
- Large Deviations: Chernoff bounds, martingales, applications
- Derandomization and limited independence
- Applications of these techniques to algorithms, including approximation and online algorithms.