COMP 260
Advanced Algorithms
SPRING 2002


Instructor: Lenore Cowen, Halligan 237; 7-5134; cowen@eecs.tufts.edu
Office Hours: M 4:00--5:00pm, or by appointment.
Lectures: Monday and Wednesday 5.10-6.25pm,in Halligan 102.

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.

Scribe notes:

  • Lecture 1 (Bipartite perfect matching)
  • Lecture 2 (augmenting path alg/stable matching)
  • Lecture 3 (Christofides' Algorithm for TSP)
  • Lecture 4 (The Knapsack problem)
  • Lecture 5 (An fptas for knapsack)
  • Lecture 6 (Greedy approximation for Set Cover)
  • Lecture 7 (Online algorithms/Paging)
  • Lecture 8 (k-competitive paging)
  • Lecture 9 (A Randomized Competitive Paging Algorithm)
  • Lecture 10 (1/2-approx to Max Cut)
  • Lecture 11 (PRAM algorithm for MIS)
  • Lecture 12 (An LP-based algorithm for Set Cover)
  • Lecture 13 (k-center problem)
  • Lecture 14 (weighted k-center problem)
  • spring break
  • Lecture 15 (approximate unweighted apsp)
  • Lecture 16 (approximate unweighted apsp cont.)
  • Lecture 17 (approximate weighted apsp/compact routing
  • Lecture 18 (.878 approximation to max cut)
  • Lecture 19 (Intro to Linear Programming)
  • Lecture 20 (Linear Programming duality)
  • Lecture 21 (approximate scheduling)
  • Lecture 22 (vertex coloring planar graphs)

    Partial Bibliography: the following were used in preparation of lectures (will be extended and revised throughout the semester):
    West's graph theory book, Hochbaum's book, working notes from V. Vazarani, Goemans' notes, paper of Luby, more to come.

    Homeworks:

  • HW 1 due Feb 4
  • HW 2 due March 4
  • HW 3 due April 15 (deadline extended to 4/17)