**
COMP 260
**

Advanced
Algorithms

SPRING
2016

**Instructor:** Lenore Cowen

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

**Office Hours:** TBA

**Lectures:** Mondays, 6:30pm in Halligan 111B

** Note: No Class Monday, Feb 15 (President's day), Monday, March 21 (Tufts Spring Break) or Monday, April 11 (Prof. Cowen out of town).
Because of the Mon, April 11 holiday, we WILL Hold class on Monday, April 18 (Patriot's Day). **

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

OLD

Jan 25: Lecture 1 (Stable Matching/Bipartite perfect matching/Review of P and NP)

February 1: Lecture 2 (Max flow/min cut)

Feb 8: Lecture 3 [HW1 is due] (Metric TSP/begin knapsack)

Feb 15: NO CLASS/PRESIDENTS DAY

Feb 22: Lecture 4 (Finish knapsack/K center) [HW2 handed out]

Feb 29: Lecture 5 (Intro to randomized algorithms/mincut/maxcut)

March 7: Lecture 6 [HW2 is due] (Set Cover)

March 14: Lecture 7 (Scheduling)

March 21: No class: Tufts Spring Break

March 28: Lecture 8 (Online Algorithms I)

April 4: Lecture 9 [HW3 is due] (Online Algorithms II)

April 11: No class: Prof. Cowen away

April 18: Lecture 10 [extra class: we meet even though it is a Tufts holiday] (Semidefinite programming and MaxCut)

April 25: Lecture 11

May 2: Lecture 12

**Homework Assignments:**
HW1 (due Feb 1)

HW2 (due March 7)

HW3 (due April 3)

**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: More on metric TSP. There has recently been substantial progress on the $s$-$t$ path version of TSP using a best of many version of Christofides' algorithm, considering multiple spanning trees: the paper is:
An, H.C., Kleinberg, R. and Shmoys, D.B., 2015. Improving Christofides' algorithm for the s-t path TSP. Journal of the ACM (JACM), 62(5), p.34.
or you can read the preprint on arXiv. The bound of the golden ratio that they show on this approximation was then imroved by Sebo, then by Vygen, and the current best bound is now at 1.566, only slightly worse than the cycle case of Chritofides algorithm: (see
Gottschalk, C. and Vygen, J., 2015. Better $ s $-$ t $-Tours by Gao Trees. arXiv preprint arXiv:1511.05514. )

Lecture 5: The Karger-Stein paper is here:
A new approach to the minimum cut problem JACM, Volume 43, Issue 4, July 1996.
Lecture 7: Some scheduling papers:
Hall, Schulz, Shmoys and Wein
and also Schmoys, Stein and Wein, Job Shop scheduling