**
COMP 260
**

Advanced
Algorithms

SPRING
2019

**Instructor:** Lenore Cowen

Halligan 107A; 627-5134; cowen AT cs.tufts.edu ;

**Office Hours:** TBA

**Lectures:** Tuesdays, 6:30pm in Lane Hall Room 100A

** Note: No Tuesday, 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 2018. 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 22: Lecture 1: Review of P and NP, Bipartite perfect matching, stable matching:

January 29: Lecture 2: Max Flow/Min Cut ( Scribe notes )

February 5: Lecture 3: Approximation algorithms for Metric TSP ( Scribe notes ) and K-center ( Scribe notes )

February 12: Lecture 4: Approximation algorithm for knapsack ( Scribe notes )

February 19 Lecture 5: Approximation algorithms for Set Cover and mincut
( Scribe notes )

February 26 Lecture 6: Primal-Dual paradigm for LP and minweight bipartite perfect matching and set cover revisited ( Scribe notes )

March 5 Lecture 7: Introduction to Online Algorithms ( Scribe notes )

March 12 Lecture 8: Paging continued and approximate load balancing and scheduling

March 19: NO LECTURE SPRING BREAK!

March 26 Lecture 9: Intro to Semi-Definite Programming and Max Cut

April 2 Lecture 10: Graph coloring; Approximate 3-coloring

April 9 Lecture 11: Intro to Parallel Algorithms

April 16 Lecture 12:

April 23 Lecture 13: (Last class)

**Homework Assignments:**
HW1 (due Tuesday, February 5 in class) and here is the Latex source

HW2 (due Tuesday, February 19 in class) and here is the Latex source which requires this figure file

HW3 (due Tuesday, March 26 in class) and here is the Latex source

HW4 (due Tuesday, April 4 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.