COMP 260
Advanced Algorithms
SPRING 2011


Instructor: Lenore Cowen
Halligan 237; 7-5134; cowen AT cs.tufts.edu ;
Office Hours: TBA
Lectures: Thursdays, 6pm in Halligan 111A

Note: No Class Thursday, February 24 (Tufts on a Monday schedule) or Thursday, March 24 (Tufts Spring break).

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 website for this class is at http://www.cs.tufts.edu/comp/260

Prerequisites: Comp 160 or permission of the instructor.

There is no text for this course.

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

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

Please note that many of the scribe notes below were based also on scribe notes from previous year lectures.

  • Jan 20: Lecture 1 (Stable Matching/Bipartite perfect matching/Review of P and NP)

  • Jan 27: Lecture 2 (Max Flow/Min Cut) [HW1 is due]

  • Feb 3: Lecture 3 (Intro to Randomized Algorithms/Max Cut/MIS) [HW2 is due]

  • Feb 10: Lecture 4 (finish MIS/Metric TSP)

  • Feb 17: Lecture 5 (knapsack) [Hw3 is due]

  • No Class Feb 24 (Tufts on A Monday Schedule)

  • March 3: Lecture 6 (k-center Problem)

  • March 10: Lecture 7 (Set Cover) [Hw4 is due]

  • March 17: Lecture 8 (online algorithms)

  • March 24: No class: Tufts Spring Break

  • March 31: Lecture 9: Andrew Winslow Guest Lecture (Geometry)

  • April 7: Lecture 10 (Intro to SDP/max cut)

  • April 14: Lecture 11 : (Approximate coloring)

  • April 21: Lecture 12: Ben Hescott Guest Lecture (Complexity)

  • April 28: Lecture 13: (Low-Distortion Embeddings) [Hw5 is due]



    Homework Assignments:

    HW1 (due Jan 27)

    HW2 (due Feb 3)

    HW3 (due Feb 17)

    HW4 (due March 10)

    HW5 (due April 28)


    The Bleeding Edge:

    In this section we link to current research papers that are related to the topics of the lectures of this course.

  • Lecture 1: More on stable marriage. See recent work on Generalized Median Stable Matchings of Christine Cheng's on Her webpage

  • Lecture 3: Improved algorithms for Deterministic Distributed Delta + 1 coloring have recently been found, see Barenboim and Elkin's paper, preprint here to start.

  • Lecture 4: Has there finally been a breakthrough improvement on Christofides's approximation algorithm for metric TSP? See: http://blog.computationalcomplexity.org/2010/12/breakthrough-in-algorithms-improved.html with the following preprint by Gharan, Saberi and Singh.

  • Lecture 13: Lots and lots of activity on metric embeddings since that first LLR paper: a good starting point might be Metric Embeddings with Relaxed Guarantees by Chan, Dhammdhere, Gupta, Kleinberg and Slivkins.