CMPSC 292A Randomized Algorithms

The goal of the class is to learn the basics of probability theory, how to reason rigorously about probability, to learn concentration inequalities (Markov, Chebyshev, Chernoff, ++) and know to apply those in the context of algorithm analysis and design.

Textbook: Randomized Algorithms by Mitzenmaher and Upfal (Second Edition). We will cover approximately the 7 first chapters, plus possibly additional readings. The precise syllabus will develop as we go along! See Q&A Lecture Schedule post for the approximate schedule.