Instructors: Lenore Cowen and Marta Arias
Halligan 237; 7-5134; email@example.com;
Office Hours: M 6:00-6:50pm, or by appointment.
Lectures: Monday and Wednesday 6.50-8.15pm,in Halligan 106.
Description: If you loved your algorithms class and can't wait for
more, this is the class for you. In this pleasant and fun class, we
will look at some more modern algorithms, some beautiful algorithms
gems, and some areas of current research in algorithms. Topics will
include using randomness in the design and analysis of algorithms,
approximation algorithms, and online algorithms.
Comp 160 or permission of the instructor.
Text is Approximation Algorithms by Vijay Vazirani, Springer, 2003.
The course was last taught in 2002, with lecture notes here
This year's scribe notes:
Lecture 1 (ps) or (pdf) (Bipartite perfect matching)
Lecture 2 (ps) or (pdf) (Bipartite perfect matching/stable marriage)
Lecture 3 (pdf) (Max flow/min cut)
Lecture 4 (pdf) (Max flow/min cut (cont))
Lecture 5: TSP I (ps) or (pdf)
Lecture 6: TSP II (ps) or (pdf)
Lecture 7: Knapsack (ps) or (pdf)
Lecture 8: Knapsack II (ps) or (pdf)
Lecture 9: k-center (ps) or (pdf)
Lecture 10: Introduction to Randomized Algorithms (ps) or (pdf)
Lecture 11: Max Cut I
Lecture 12: Max flow/Min cut III
Lecture 13: Approximate Shortest Paths I (ps) or (pdf)
Lecture 14: Approximate Shortest Paths II
Lecture 15: Randomized Set Cover
Lecture 16: Greedy Set Cover and Compact Routing
Lecture 17: Primality Testing I
Lecture 18: Primality Testing II
Lecture 19: Online Algorithms I
Lecture 20: Online Algorithms II
Lecture 10: Online Algorithms III (ps) or (pdf)
Lecture 22: A .878 Approximation Algorithm for Max Cut
Lecture 23: Approximate Scheduling
Homework 1 (due Feb 11) or pdf file
Homework 2 (due March 31) or pdf file