Instructor: Kamesh Munagala
Time/Place: Physics 130, Wed/Fri 1:25 - 2:40
TA: Govind S. Sankar
Randomization is a key technique used in a variety of computational settings - in fact, its use is so ubiquitous that it is hard to be a computer scientist without appreciating the power of randomness. Randomization not only has practical applications, but also leads to mathematically elegant proofs. This course will cover a bit of both aspects. We will try to be comprehensive in presenting basic techniques, and will illustrate each technique with some practically motivated examples. These techniques will include linearity of expectation, concentration of measure and martingales, and Markov chains and mixing times, as well as many applications of these techniques.
Both these books cover most of the material I will present. The first book is more comprehensive (but terse), while the second presents material more gently.
[MR] Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan.
[MU] Probability and Computing by Michael Mitzenmacher and Eli Upfal
I have summarized the material into these notes. I'd appreciate it if you can point out errors/omissions.
[DP] Concentration of measure for the analysis of randomized algorithms by D. Dubhashi and A. Panconesi.
Some nice slides for the material in the [MU] book.
Randomized Algorithms course at CMU
Lecture notes by J. Aspnes (Yale)