COMP 260
Advanced Algorithms
SPRING 2023

Instructor: Lenore Cowen
Joyce Cummings Center; 627-5134; cowen AT cs.tufts.edu ;
Office Hours: Typically Thursday Mornings in Prof. Cowen's office but since some of you have 10:30 classes and some of you have noon classes, instead of setting an exact time, I will ask that you email in advance to tell me you're coming and we'll find a time that works for you. Office hours available at other times too: just email with your schedule.
Lectures: Tuesdays/Thursdays 1:30-2:45am in Lane Hall 100A

Please see Prof. Cowen's email for the passcode to add yourself to Gradescope if you want to submit your HWs electronically.

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

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

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

  • Week 0/1: January 19 Review of P and NP, Bipartite perfect matching

  • Week 1: January 24 and 26 Stable Matching and Ford-Fulkerson Algorithm for Max Flow/Min Cut

  • Week 2: Jan 31 and Feb 2: More Max Flow/Min Cut

  • Week 3: Feb 7 and 9 Approximation algorithms for Metric TSP

  • Week 4: Feb 14 and 16 Knapsack I and Knapsack II

  • Week 5: Feb 21 (no class Feb 23: Tufts on a Monday schedule) Intro to Randomized Algorithms

  • Week 6: Feb 28 and March 2 Removing randomness and Mincut

  • Week 7: March 7 and March 9

  • Week 8: March 14 and March 16: guest lectures

  • No classes: March 21 and March 23: Spring break

  • Week 9: March 28 and March 30

  • Week 10: April 4 and April 6

  • Week 11: April 11 and April 13

  • Week 12: April 18 and April 20

  • Week 13: April 25 and April 27
    Homework Assignments: Submit hardcopy or email the instructor for the code to add yourself to Gradecope for this class to submit electronically.

    HW1 (due Jan 31 (up to 10am Feb 1 with automatic grace period)) and here is the Latex source

    HW2 (due Feb 28 (up to 10am March 1 with automatic grace period) ) 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.