COMP 260
Advanced Algorithms
FALL 2021


Instructor: Lenore Cowen
Halligan 107A; 627-5134; cowen AT cs.tufts.edu ;
Office Hours: 10-10:30am Tuesday/Thursdays; or email for an appointment at another time.
Lectures: Tuesdays/Thursdays 10:30-11:45am in Halligan 111A

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 2020. The course page for 2020 is not available, but you can see the lecture notes for the 2018 version of the class 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.

New! I've been teaching a version of this class at Tufts since 2002, and have misplaced some of the old versions of the scribe notes deep in my old files. I would like to acknowledge all the old scribes in the current version of each lecture. But: I would need your help. So two things: 1) If you took an old version of the course with me, and you are willing to be acknowledged in the notes posted publicly on the Internet, please tell me which lecture(s), which year, and I will add your name. 2) If you no longer have your notes or don't wish your name posted, you don't need to do anything if you took the class before 2019 (your notes may still be shared with a future scribe, but we will not include your name when they are published). But: I'd love to hear from all students who took this class in previous years. Please email me to get back in touch.

  • Week 0/1: September 9 and 14: Review of P and NP, Bipartite perfect matching and Stable Matching

  • Week 1: September 14 and 16 Stable Matching and Ford-Fulkerson Algorithm for Max Flow/Min Cut

  • Week 2: September 21 and 23: Approximation Algorithms for the Traveling Salesman Problem: TSP Part I and TSP Part II



    Homework Assignments: Submit hardcopy or email the instructor for the code to add yourself to Gradecope for this class to submit electronically.

    HW1 (due Thursday, Sept. 23 in class) and here is the Latex source

    HW2 (due Thursday, Oct 7 in class) and here is the Latex source

    HW3 (due Tuesday, November 9 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.