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 4045.
Instructor:	Lap Chi Lau
Office hours:	Mondays and Wednesdays, 11:30-12:30, DC 3120.
Tutors:	Pak Hay Chan, Akshay Ramachandran, Kaiyu Wu.
TA office hours:	Pay Hay Chan, Thursdays, 2-3, DC 3129. Akhsay Ramachandran, Fridays, 1-2, DC 3128.
Piazza page:	piazza.com/uwaterloo.ca/spring2018/cs466666
Course outline:	[pdf]

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

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

Chernoff bounds, graph sparsification.
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, Laplacian solver.

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

linear programming, iterative rounding.
duality theorems, primal-dual methods.
multiplicative update methods, maximum flow.

References: Notes will be provided. See my previous notes on Graduate Algorithms to get a good idea of the topics to come. The following is a list of main references. See my previous 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: