CS466/666 - Algorithm Design and Analysis

CS466/666: Algorithm Design and Analysis

This is an advanced undergraduate / introductory graduate course on algorithm design for students in computer science, engineering, or mathematics.

Lecture:	Mondays and Wednesdays, 11:30-12:50, E2 1732.
Instructor:	Lap Chi Lau
Office hours:	Mondays and Wednesdays, 2:00-3:00, DC 3120.
Tutors:	Zhengkun Chen, Jian Deng, Hong Zhou.
TA office hours:	Hong Zhou, Thursdays and Fridays, 4:30-5:30, DC 2305.
Piazza page:	piazza.com/uwaterloo.ca/spring2019/cs466666
Course outline:	[pdf]

We will study various probabilistic techniques in algorithmic design.

linearity of expectation, tail inequalities.
graph algorithms: color coding, min-cut, MST, graph sparsification.
balls and bins, hashing, data streaming.
algebraic techniques: parallel matching, network coding.
probabilistic methods: first moment, second moment, local lemma.
random walks, electrical networks.
Markov chain: Monte Carlo method, mixing, coupling, approximate counting.

References: Notes will be provided. See my previous notes on CS 466 and CS 761 to have a good idea of the topics to come. The following are two main reference books for this course.

Probability and Computing, by Mitzenmacher and Upfal.
Randomized Algorithms, by Motwani and Raghavan.

Algorithm Design and Analysis

Site menu: