COMP 260
Advanced Algorithms
SPRING 2020


Instructor: Lenore Cowen
Halligan 107A; 627-5134; cowen AT cs.tufts.edu ;
Office Hours: TBA
Lectures: Tuesdays/Thursdays 10:30-11:45am in Halligan 111B

Note: No classes Tuesday, March 17 and Thursday, 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 2019. 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.

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: January 16: Review of P and NP, Bipartite perfect matching. Scribe notes

  • Week 1: January 21 and 23: Stable Matching and FordProf. Lenore Cowen Bioinformatics-Fulkerson Algorithm for Max Flow/Min Cut Scribe notes.

  • Week 2: January 28 and 30: Edmonds-Karp Algorithm for Max Flow/Min Cut and Christofides Algorithm for Approximate Metric TSP ( Scribe notes)

  • Week 3: February 4 and 6: K-center (scribe notes) and Knapsack (scribe notes)

  • Week 4: February 11 and 13: FPTAS for Knapsack ( Scribe notes ) and Set Cover

  • Week 5: February 18: Guest Lecture by Mati Korman (No class Feb 20: Tufts in a Monday Schedule)

  • Week 6: February 24 and 26: Intro to Randomized Algorithms/Mincut and Maxcut



    Homework Assignments:

    HW1 (due Thursday, January 30 in class) and here is the Latex source

    HW2 (due Tuesday, February 25 in class) and here is the Latex source requires This figure

    HW3 (due Thursday, April 2 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.