Site menu:

CS 761: Randomized Algorithms

This is an introductory graduate course on the use of randomness in computations and combinatorics. The aim is to provide a solid background for researchers to use probabilistic tools in computer science, engineering, or mathematics.

Lecture: Tuesdays and Thursdays, 12:00-1:20, DC 2568 EV1 350
Instructor: Lap Chi Lau
Office hour: Thursdays, 1:30-2:30, DC 3120
TA: Hong Zhou
Piazza page:

We will introduce the basic probabilistic tools and probabilistic methods, and apply these techniques in various different settings. The following is a tentative schedule.

Reference: Mitzenmacher and Upfal, Probability and Computing, Cambridge, 2005.
Reference: Motwani and Raghavan, Randomized Algorithms, Cambridge, 1995.
Reference: Alon and Spencer, The Probabilistic Method, Wiley, 2008.
Notes: Course notes 2013, Course notes 2011.