Advanced Algorithms
Winter 2013, Carleton College

Basic Information

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.

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