Site menu:

CS 761: Randomized Algorithms

This is a graduate course on the use of randomness in computations and combinatorics. We study basic techniques in probabilistic analysis with classical and modern applications in theory of computing.

Lecture: Tuesdays and Thursdays, 11:00-12:20, DC 2568
Instructor: Lap Chi Lau
Office hour: Thursdays, 1:30-2:30, DC 3120
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 2018.