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.
David Eppstein,
ICS, UC Irvine.