CS 263, Winter 2017:
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