Algorithm Design and Analysis
CS 466/666, Fall 2017

CS 466/666: Algorithm Design and Analysis
Fall 2017

Lectures
Mondays and Wednesdays, 1:00-2:20pm
MC 2054

Instructor
Eric Blais
eric.blais@uwaterloo.ca
Office hours: Th 12:00-1:00pm, DC 3122

Teaching assistants
V. Abhinav Bommireddi, Nathan Harms
Office hours: Tu 2:30pm-3:30pm, DC 2305

Syllabus
Here.

Piazza page
http://piazza.com/uwaterloo.ca/fall2017/cs466666/
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.


Assignments

The assignments will be added here as they become available.

Problem set 1.
Due on September 20. (LaTeX source)
Problem set 2.
Due on October 4. (LaTeX source)
Problem set 3.
Due on October 18. (LaTeX source)
Problem set 4.
Due on November 1. (LaTeX source)
Problem set 5.
Due on November 15. (LaTeX source)
Problem set 6.
Due on November 29. (LaTeX source)

List of topics

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

Randomized algorithms
Equality testing, Min-Cut, Polynomial identity testing
Approximation algorithms
Approximate counting, testing sortedness
Sketching algorithms
Hash functions, Bloom filters, graph sparsification, dimension reduction
Constraint satisfaction problems
Probabilistic method, Max-Cut, Algorithmic Lovasz Local Lemma
Amortized analysis
Splay trees, union find, regret minimization
Limits of efficient algorithms
Communication complexity, Fine-grained complexity

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