This course meets Monday, Wednesday, and Fridays, 3:00 - 3:50 in Bren 1429. Coursework will consist of weekly homeworks, graded during the class period on which they are due, and a final exam. Group work on homeworks is permitted and encouraged. Knowledge of a previous course in the design and analysis of algorithms (such as the CS 161 or CS 260 courses taught at UCI) is expected, but otherwise all CS graduate students are welcome.

The textbook for this course will
be *Approximation
Algorithms*, by Vijay Vazirani.
The tentative schedule of topics is to go through the chapters of this book at a rate of approximately one chapter per lecture.

Tentative schedule:

- Week 1: Chapters 1-2 (combinatorial algorithms). Homework, due in class Friday, Jan 16: Exercises 1.1, 1.3, 2.8, 2.14.
- Week 2: Chapters 3-5 (combinatorial algorithms). Homework, due in class Friday, Jan 23: Exercises 3.2, 3.5, 4.7, 5.1
- Week 3: Holiday Monday. Chapters 6-7 (combinatorial algorithms).
- Week 4: Chapters 8-10 (approximation schemes). Homework, due in class Friday, Jan 30: (1) Exercise 3 of this blog post. (2) Find a counterexample to the "clearly" equality on page 56, mentioned in the footnote of the blog post. (3,4) Exercises 6.1, 7.1.
- Week 5: Chapters 11-12 (geometric approximation; linear programming duality); minimax and Yao's principle. Homework, due in class Friday, Feb 6: 8.1, 8.3, 9.9, 10.2
- Week 6: Chapters 13-15 (LP-based approximation for set
cover; method
of conditional expectations as
an explanation
for greedy set cover). Homework, due in
class Friday, Feb 13: 11.3, 12.3, 12.7; Problem 4: use Yao's principle
and
the decision
tree lower bound for comparison sorting to prove that every
randomized comparison-based sorting algorithm must use
Ω(n log n) comparisons to sort n items. (Hint: in a
binary tree with k leaves, the average distance to a leaf is at least
log
_{2}k.) - Week 7: Holiday Monday. Chapters 16 & 26 (Max sat and semidefinite programming). Homework, due in class Friday, Feb 20: 14.4, 14.5, 15.3, 15.5.
- Week 8: Chapters 27-29 (lattices, counting, and inapproximability). Homework, due in class Friday, Feb 27: 16.1, 16.7, 26.5, 26.13
- Week 9: Additional topics: volume of convex bodies; unique games. Homework, due in class Friday, Mar 8: 27.6, 28.6, 28.8, 29.1.
- Week 10: No class.