Analysis of Algorithms

This course covers recent topics in algorithms research: What you need to know to do research in this area, and probably didn't learn from your undergraduate algorithms class. It meets Mondays, Wednesdays, and Fridays, 2:00-2:50, in MSTB 110. Coursework will consist of weekly homework sets and a final exam.

Previous offerings of this course have focused on randomized algorithms (Winter 2012 and Spring 2014) and approximation algorithms (Spring 2015). For this offering we will focus on computational hardness assumptions beyond P ≠ NP including 3SUM, triangle-finding and shortest paths, the exponential time hypothesis, and unique games.

Additionally, we will not be meeting for January 27 – February 3 (four lectures).

Rough schedule, to be made more detailed as the quarter progresses:

**Week 1:**- Introduction: Why do algorithms have the time bounds they do?
- The subset sum problem (see also: Koiliaris and Xu, and Section 3 of Woeginger).
- The 3SUM problem.
- Models of computation: the real RAM and the word RAM.
- Homework 1, due at the start of class Friday, January 20.
**Week 2:**- Holiday Monday (Martin Luther King Jr. Day)
- Slightly-subquadratic word RAM and real RAM algorithms for 3SUM.
**Week 3:**- Subcubic equivalences between path, matrix and triangle problems
- Faster min-plus matrix multiplication and its applications in dynamic programming
- Connections between triangle finding and 3SUM
- Homework 2, due at the start of class Friday, February 10.
**Week 4:**- (No lectures.)
**Week 5:**- Backtracking algorithms for NP-complete problems (example: 3-coloring)
- Random walks in solution space (original paper; lecture notes)
- The Bellman–Held–Karp dynamic programming algorithm for the traveling salesman problem
- Homework 3, due at the start of class Friday, February 17.
**Week 6:**- Inclusion-exclusion for graph coloring
- Parameterized complexity and fixed parameter tractability; kernelization and vertex cover
- Longest paths and color coding
**Week 7:**- Holiday Monday (President's Day); no homework due this week
- Graph parameters: bidimensionality, well-quasi-ordering, and Courcelle's theorem
- The exponential time hypothesis
- Homework 4, due at the start of class Friday, March 3.
**Week 8:**- Greedy approximation for vertex cover and set cover (Vazirani,
*Approximation Algorithms*, Chapters 1 & 2). - Approximation schemes and dynamic programming for knapsack and bin packing (Vazirani, Chapters 8 & 9).
- Linear programming relaxation, LP approximation and kernelization for vertex cover, and the integrality gap (Vazirani 12.3.1 and 14.3)
- Homework 5, due at the start of class Friday, March 10: Vazirani (linked edition), exercises 1.4 (greedy not good for vertex cover), 2.2 (local search for max cut), 8.1 (greed is bad for knapsack), 9.9 (bin covering).
**Week 9:**- LP approximation for set cover, randomized rounding, and derandomization by conditional estimation (Vazirani 14.2, 16.2); Young 1995
- LP duality (Vazirani 12); minimax for zero-sum games; Yao's principle
- LP algorithms: the simplex and ellipsoid methods
- Homework 6, due at the start of class Friday, March 17: Vazirani 12.3 (dual of equality constraints), 14.4 (tight example for weighted vertex cover), 14.5 (better approximate vertex cover for k-colored graphs), and 16.3 (conditional-expectation derandomization of LP relaxation for MAX SAT).
**Week 10:**- Semidefinite approximation, inapprobility, and the unique games conjecture