COMP 260
Advanced Algorithms
SPRING 2004

Instructors: Lenore Cowen and Marta Arias
Halligan 237; 7-5134; cowen@cs.tufts.edu; marias@cs.tufts.edu
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.

Prerequisites: 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


    Homeworks:

  • Homework 1 (due Feb 11) or pdf file

  • Homework 2 (due March 31) or pdf file