Algorithm Design and Analysis
CS 466/666, Fall 2016

CS 466/666: Algorithm Design and Analysis
Winter 2016

Fall 2016
Time: Tuesdays and Thursdays, 10:00-11:20am
Location: PAS 1229
Eric Blais
Office hours: Tuesdays, 11:30-12:30 in DC 3122
Teaching assistants
V. Abhinav Bommireddi, Nathan Harms
Office hours: Mondays, 1:30-2:30 in DC 2305
Piazza page
All announcements for the class will be posted on the Piazza page. The page will also be the central place for class discussions and for any questions about the lectures and assignments.

What is this course about?

Algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and application.


The assignments will be added here as they become available.

Problem set 1.
Available on September 15. Due on September 29. (LaTeX source)
Problem set 2.
Available on September 29. Due on October 13. (LaTeX source)
Problem set 3.
Available on October 20. Due on November 3. (LaTeX source)
Problem set 4.
Available on November 3. Due on November 17. (LaTeX source)
Problem set 5.
Available on November 21. Due on December 1. (LaTeX source)

List of topics

Here is a tentative list of topics that we will cover this semester.

Sampling algorithms
Matrix multiplication verification, Freivald's algorithm, Polynomial identity testing
Probabilistic data structures
Hashing and chaining, Bloom filters, Power of two choices
Dynamic data structures
Splay trees, Union find
Streaming algorithms
Approximate counting, Finding heavy hitters, approximating frequency moments
Dimension reduction
Johnson-Lindenstrauss lemma, Compressed sensing
Constraint satisfaction problems
Lovasz local lemma, Moser-Tardos algorithm
Linear programming
Minimum set cover, Multiplicative weight updates
Sublinear-time algorithms
Testing linearity, Testing properties of graphs
Graph sparsification
Minimum spanning trees, Karger's Min-Cut algorithm, Graphs as electrical networks
Distributed algorithms
Local computation, Maximal independent set, Maximum matching

Cover image: Pillars ©Mikael Hvidtfeldt Christensen.
Site designed with Bootstrap.