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, 2:30-3:50, MC 1056.
Instructor:	Lap Chi Lau
Office hours:	Mondays and Wednesdays, 4:00-5:00, DC 1309.
Tutors:	Robert Wang
TA office hours:
Piazza page:	piazza.com/uwaterloo.ca/summer2026/cs466666
Course outline:	[pdf]

We will study modern techniques in algorithms design and analysis, including probabilistic techniques, linear algebraic techniques, and optimization techniques.

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

concentration inequalities, graph sparsification, dimension reduction.
k-wise independence, data streaming, graph sketching.
polynomial identity testing, parallel matching, network coding.
probabilistic methods, local lemma.

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

spectral graph theory, Cheeger's inequality.
random walks, mixing time.
electrical networks, spectral sparsification.

Linear Programming - A general and powerful approach for combinatorial optimization and approximation algorithms.

linear programming, duality theorems.
iterative rounding.
multiplicative weights update methods.

References: Notes will be provided. See my previous notes on Algorithm Design and Analysis to get a good idea of the topics to come. The following is a list of main references. See the project page for further references.

Probability and Computing, by Mitzenmacher and Upfal
Notes on Spectral Graph Theory by Dan Spielman.
The Design of Approximation Algorithms, by Williamson and Shmoys

Site menu: