COMP 260
Advanced Algorithms
SPRING 2025

Instructor: Lenore Cowen
Joyce Cummings Center; 627-5134; cowen AT cs.tufts.edu ;
Office Hours: Typically 2-3pm on Monday and Wednesday
Lectures: Mondays/Wednesdays 3pm-4:15pm in JCC 302

See the private page here for the code to add yourself to Gradescope to submit your homework assignments.

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 2023.

Here is a Template for scribe notes with instructions for first-time Latex users We can also supply this as an overleaf project-- just ask.

You can find the scribe notes for the class here: http://www.cs.tufts.edu/comp/260/private/

  • Week 0/1: January 15 and 22 Review of P and NP, Bipartite perfect matching and Stable Matching

  • Week 2: January 27 and 29 Approximation algorithms for Metric TSP , HW 1 due

  • Week 3: Feb 3 and Feb 5 Knapsack I and II

  • Week 4: Feb 10 and 12 Ford-Fulkerson Algorithm for Max Flow/Min Cut; HW1 due

  • Week 5: Feb 19 and 20 Intro to Randomaized Algorithms, Min Cut, MaxCut

  • Week 6: Feb 24 and 26 k-Center. Begin scheduling

  • Week 7: March 3 and March 5 Set Cover, HW2 due

  • Week 8: March 10 and March 12:

  • No classes: March 17 and March 19: Spring break

  • Week 9: March 31 and April 2: Intro to Online Algorithms

  • Week 10: April 7 and April 9: Finish Online lecture and k-Center

  • Week 11: April 14 and April 16: Max Cut Revisited and Approx 3 Coloring

  • Week 12: April 21 and April 23: Patriot's Day and TBA

  • Week 13: April 28 Last Class
    Homework Assignments: The code to add yourself to Gradecope for this class to submit electronically is handed out in class or available on the private portion of this website.

    HW1 (due Thurs, Jan 30 at 10pm) and here is the Latex source

    HW2 (due Thurs, March 6 at 10pm) and here is the Latex source where you will also need This figure to compile the latex source.

    HW3 (due Thursday, April 10 at 10pm) and here is the Latex source

    HW4 (due Monday, April 28 at 10pm)

    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.