Advanced Algorithms
Winter 2013, Carleton College

Basic Information

• Instructor: David Liben-Nowell
• Lecture: 3a, Weitz 233.
• Office Hours: see my homepage. Always feel free to email for an appointment if the scheduled times aren't good for you.

• This webpage was originally stored in Moodle, which does not have an easy capacity to publish a version of an old webpage for a course. Major thanks to Dave Musicant, whose Moodle-scraping tool I used to generated this page, which is an approximation of the original.

Course Materials:

Resources for scribes:

Week 1:

Monday (Calder):  logistics and review of asymptotics, problems, and complexity.

Assignment for Wednesday:  email me a proposed collaboration policy for the class.

Wednesday (Jack):  NP, P vs. NP, approximation algorithms, a 2-approximation for Vertex Cover.

Friday (Kathy):  a Hn-approximation for Set Cover

Week 2:

Monday (David):  set cover wrapup; shortest superstring.

Wednesday (Zach Walsh):  shortest superstrings via Set Cover.

Assignment for Friday:  review bipartite matching algorithms (using max flow).  

Also ps1 was distributed in class today (where we agreed to swap the numbers of problems #2 and #3, so that Max Cut is #3 and Superstrings is #2).

Friday (Joy):  min-cost perfect matching in bipartite graphs (Part I).

Week 3:

Monday (Morgan):  min-cost perfect matching in bipartite graphs (Part II).

Wednesday (Joe):  shortest superstrings, revisited.

Friday (Nate):  4-approximation for shortest superstring.

Week 4:

Monday (Daniel):  TSP.

Wednesday (Will):  3/2-approximating Metric TSP; online algorithms.

Friday (Zach Wood-Doughty):  randomized algorithms; quicksort.

Week 5:

Monday (Greg):  the drunken sailors; randomized quick sort; SAT begun.

Wednesday (Marcus):  algorithms for 3SAT.

Friday (Ken):  improving the analysis of Schoening's Algorithm; approximating MAXSAT.

Week 6:

Wednesday (Austin):  finishing SAT, derandomizing SAT, and complexity theory/randomization (see BPP, and ZPP, and RP/coRP).

Friday (Aiden):  global min cut: Karger.

Week 7:

Monday (Larkin):  global min cut:  Karger/Stein.

Wednesday (Andrew):  global min cut wrapup; linear programming.

Friday (Joy and Daniel):  linear programming, smoothed analysis.  Come on Monday with an LP for max flow.

Week 8:

Monday (Kathy and Zach Walsh):  linear programs for max flow, vertex cover, and set cover.

The final project will be: you read a paper with a group; your group presents in approximately 20 minutes the highlights of the problem and the solution.  (Details will follow once I have groups formed.)  Links to the papers that I propose follow. You may also propose an alternative.

By Thursday, 27 February at 5:00pm, email DLN with your preferences (ranked top 4 papers, at least, and anything else I should know about making groups [e.g., known absences]).  I will treat no response as having no preferences whatsoever.

Wednesday (Ken and Nathan):  LP for Set Cover; Max Cut.

Friday (Jack and David):  vector programs and SDPs.

Week 9:

Monday (Joe and Aiden), such as it was: Max Cut wrapup.

Wednesday (Marcus and Calder):  splay trees.

Friday (Will):  splay trees; van Emde Boas queues.

Week 10:

Monday:  project presentations.

• Sorting by Transpositions:  Joe, Calder, Austin, Morgan.
• Derandomizing SAT:  Marcus, Ken, Zach WD, David.
• PTAS for TSP:  Daniel, Aiden, Nathan.

Wednesday: project presentations; course evals; van Emde Boas wrapup.

• Matching in nonbipartite graphs:  Larkin, Greg, Zach W, Kathy.
• Correlation Clustering:  Andrew, Jack, Joy, Will.