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:	Tuesdays and Thursdays, 10:30-12:00, online.
Instructor:	Lap Chi Lau
Office hours:	Tuesdays and Thursdays, 1:00-2:00, online.
Tutors:	Sheik Shameer Sheik Saleem, Kam Cheun (Alex) Tung, Ji Xin, Hong Zhou
TA office hours:
Piazza page:	piazza.com/uwaterloo.ca/spring2020/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.

tail inequalities, graph sparsification, dimension reduction.
balls and bins, hashing, data streaming.
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, hitting time, spectral sparsification.

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

linear programming, iterative rounding.
duality theorem, multiplicative 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: