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, 10:00-11:20, MC 4042.
Instructor:	Lap Chi Lau
Office hours:	Mondays and Wednesdays, 11:30-12:30, DC 3120.
Tutors:	Alex Tung, Robert Wang.
TA office hours:	Alex Tung, Fridays, 10-11, DC 3139. Robert Wang, Thursdays, 5-6, DC 3139..
Piazza page:	piazza.com/uwaterloo.ca/spring2022/cs466666
Course outline:	[pdf]

We will study probabilistic techniques and linear algebraic techniques in algorithmic design.

Randomized Algorithms - Probabilistic tools have become indispensible in algorithm design.

Chernoff bounds, graph sparsification, dimension reduction.
balls and bins, hashing, data streaming.
polynomial identity testing, parallel matching, network coding.
probabilistic methods, local lemma.
random walks, Markov chain Monte Carlo.

Spectral Analysis - We will study how eigenvalues and eigenvectors can be used to design and analyze algorithms, from random walks to graph partitioning to solving linear equations.

spectral graph theory, mixing time.
Cheeger's inequality, local graph partitioning.
electrical networks, random walks.
spectral sparsification.
multiplicative update methods, maximum flow.

References: Notes will be provided. See my previous notes on CS 466 Spring 2020, CS 466 Spring 2019, CS 466 Spring 2018 to get a good idea of the topics to come. The following are two reference books.

Probability and Computing, by Mitzenmacher and Upfal
Spectral and Algebraic Graph Theory, by Dan Spielman

Site menu: