Algorithm Design and Analysis
CS 466/666, Fall 2017
- Mondays and Wednesdays, 1:00-2:20pm
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
- 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.
- Due on September 20. (LaTeX source)
- Problem set 2.
- Due on October 4.
- Problem set 3.
- Due on October 18.
- Problem set 4.
- Due on November 1.
- Problem set 5.
- Due on November 15.
- Problem set 6.
- Due on November 29.
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