Randomized Algorithms

CS 761

Site menu:

• Information
• Notes
• Homework
• Project

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:	piazza.com/uwaterloo.ca/spring2018/cs761

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

• linearity of expectations, tail inequalities.
• graph algorithms: color coding, min-cut, MST, graph sparsification.
• balls and bins, hashing, power of two choices, data streaming algorithms.
• algebraic techniques: parallel matching, network coding, matrix rank.
• probabilistic methods: first moment, second moment, entropy, local lemma.
• random walks, electrical networks.
• Markov chain: Monte Carlo method, mixing, coupling, approximate counting.
• geometry: dimension reduction, metric embeddings.
• linear algebra: spectral sparsification, Laplacian solver.
• derandomization: conditional probability, k-wise independence.
• complexity: interactive proofs, probabilistic checkable proofs.

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.

CS, Waterloo. Picture by Andrew Davidhazy. Web design by Andreas Viklund.