Probability and Computing

"Randomness is too important to be left to chance."

About and Prerequisites

Randomness has become a fundamental tool in theoretical computer science. This course develops the probabilistic techniques that underpin the design, analysis, and understanding of randomization in algorithms and other related areas of theoretical computer science. The course is based primarily on the first text listed in the reference material.

Reference Material

  1. Mitzenmacher M, Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press; 2005.
  2. Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press; 1995.

Lectures

#000: Introduction | Video | Slides
#001: Events and Probability
g