COMP 260
Advanced Algorithms
SPRING 2019


Instructor: Lenore Cowen
Halligan 107A; 627-5134; cowen AT cs.tufts.edu ;
Office Hours: TBA
Lectures: Tuesdays, 6:30pm in Lane Hall Room 100A

Note: No Tuesday, March 19 (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 2018. 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.

  • January 22: Lecture 1: Review of P and NP, Bipartite perfect matching, stable matching:

  • January 29: Lecture 2: Max Flow/Min Cut ( Scribe notes )

  • February 5: Lecture 3: Approximation algorithms for Metric TSP ( Scribe notes ) and K-center ( Scribe notes )

  • February 12: Lecture 4: Approximation algorithm for knapsack ( Scribe notes )

  • February 19 Lecture 5: Approximation algorithms for Set Cover and mincut Scribe notes

  • February 26 Lecture 6: Primal-Dual paradigm for LP and minweight bipartite perfect matching and set cover revisited

  • March 5 Lecture 7: Introduction to Online Algorithms

  • March 12 Lecture 8: Pagin continued and approximate load balancing and scheduling

  • March 19: NO LECTURE SPRING BREAK!

  • March 26 Lecture 9:

  • April 2 Lecture 10:

  • April 9 Lecture 11:

  • April 16 Lecture 12:

  • April 23 Lecture 13:

  • April 30



    Homework Assignments:

    HW1 (due Tuesday, February 5 in class) and here is the Latex source

    HW2 (due Tuesday, February 19 in class) and here is the Latex source which requires this figure file

    HW3 (due Tuesday, March 26 in class) and here is the Latex source


    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: While there has been no improvement on Christofides algorithm for metric TSP in terms of approximation factor, there has been more recent approximation algorithms for metric TSP s-t path (i.e. you don't close the cycle) and some very recent work on nearly achieving the same approximation guarantee of Christofides algorithm with a better running time:

  • Lecture 4: A PTAS for the Multiple Knapsack problem (a generalization of Knapsak) was found by Chekuri and Khanna in 2006: C. Chekuri, S. Khanna, "A polynomial time approximation scheme for the multiple knapsack problem", SIAM Journal on Computing 35(3), 713-728.