15-859(M): Randomized Algorithms

Course description: 

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 me.

Method of Evaluation: Grading will be based on a collection of homework assignments, class participation and possibly a take-home final. As part of class participation, each student (possibly in teams) will give a class presentation on a topic chosen in consultation with the instructor.

Textbook: There is no required text, but we will use material from the following books:

Material will be supplemented by handouts and papers.

Topics: A tentative list of topics includes:

Last updated: 08/27/2004