COMP 260
Advanced Algorithms
SPRING 2009


Instructor: Lenore Cowen
Halligan 237; 7-5134; cowen AT cs.tufts.edu ;
Office Hours: Friday, 9:30-10:30am or by appointment.
Lectures: Thursdays, 7:30pm in Halligan 111B

Note: No Class Thursday March 19. Tufts Spring Break!

Note: No Class Thursday, February 19. Tufts on a Monday schedule

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.

The public website for this class is at http://www.cs.tufts.edu/comp/260

The moodle website for this class is at https://www.eecs.tufts.edu/moodle/
(There is nothing there yet, but please check you can log in).

Prerequisites: Comp 160 or permission of the instructor.

Text is Algorithm Design by Kleinberg and Tardos. We will only follow it loosely.

The course was last taught in 2004, with lecture notes here

Here is a Template for scribe notes with instructions for first-time Latex users

This year's scribe notes:

  • Lecture 1 (Stable Matching/Bipartite perfect matching/Review of P and NP) and Lecture 1, Part II Note: notes here are from the 2004 lecture, and cover stable matching at the end, not at the beginning

  • Lecture 2 (Max Flow/Min Cut: Guest Lecture by Diane Souvaine)

  • Lecture 3 (Metric TSP) (Scribe: Derrick Rice)

  • Lecture 4 (Knapsack) (Scribe: Jordan Crouser}

  • Lecture 5 (K-center) Homework question (Scribe: Yang Wang)

  • Lecture 6 (Intro Randomized Algorithms) (Scribe: Adam Lewis)

  • Lecture 7 (Parallel MIS-- Guest Lecture by Ben Hescott) (Scribe: Jeremy Freeman)

  • Lecture 8 (Set Cover) (Scribe: Diana Tatar)

  • Lecture 9 (Online Algorithms -- Part I) (Scribe: John Trafton)

  • Lecture 10 (Online Algorithms -- Part II) (Scribe: Mark Pellegrini)

  • Lecture 11 (Primal-Dual Methods for Linear Programming) (Scribe: Andrew Fox)

  • Lecture 12 (Semi-Definite Programming for MaxCut and 3-coloring) (Scribe: Kristof Redei)

  • Lecture 13 (Back to MaxFlow/Edmonds-Karp) (Scribe: Wanyu Wang)