COMP 260
Advanced Algorithms

Instructor: Lenore Cowen
Halligan 107A; 627-5134; cowen AT ;
Office Hours: TBA
Lectures: Tuesdays, 6:30pm in Halligan 111B

Note: No Tuesday, March 21 (Tufts Spring Break) or Tuesday, April 17 (Prof. Cowen out of town). Because of the Tuesday, April 17 holiday, we WILL Hold a makeup class on Tuesday, May 1.

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

Prerequisites: Comp 160 or permission of the instructor.

There is no text for this course.

The course was last taught in 2016. 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 23: Lecture 1: Review of P and NP, Bipartite perfect matching, stable matching: Scribe Notes: part I and Scribe Notes: part II

  • January 30: Lecture 2: (Max flow/min cut) Scribe notes

  • Feb 6: Lecture 3: Metric TSP and k-Center. Scribe Notes: part I and Scribe Notes: part II

  • Feb 13: Lecture 4: Knapsack Scribe notes

  • Feb 20: Lecture 5: Intro to randomized algorithms/mincut/maxcut Scribe notes

  • Feb 27: Lecture 6: Set Cover

  • March 6: Lecture 7: Set Cover and Maxcut Revisited Scribe notes

  • March 13: Lecture cancelled! Tufts closed for snow!


  • March 27: Lecture 8: Approximate Scheduling Scribe notes

  • April 3: Lecture 9: Online Algorithms I Scribe notes

  • April 10: Lecture 10: Online Algorithms II and Approximate Coloring Scribe notes

  • April 17: NO CLASS

  • April 24: Lecture 11: Parallel Algorithms

  • May 1: Lecture 12: Last Lecture

    Homework Assignments:

    HW1 (due Tuesday, February 6 in class)

    HW2 (due Tuesday, February 20 in class)

    HW3 (due Tuesday, March 13 in class)

    HW4 (due Tuesday, April 24 in class)

    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