CS 263, Spring 2015: Analysis of Algorithms

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 log2k.)
• 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.