Courses:

This is a graduate course on the design and analysis of algorithms, covering several advanced topics not studied in typical introductory courses on algorithms.

Prerequisites

Prerequisites include "Introduction to algorithms" (at the level of 18.410J/6.046J), linear algebra (at the level of 18.06 or 18.700), and mathematical maturity (since we'll be doing a lot of correctness proofs). The course is especially designed for doctoral students interested in theoretical computer science.

Requirements

There will be biweekly problem sets and students will also be expected to take turns to scribe lecture notes. It is thanks to the scribes that we can have a good set of lecture notes with many details.

Textbook

There is no textbook required for the course. Lecture notes are available for the current term as well as selected lecture notes from a previous term. Reference textbooks for each topic are listed in the readings section.

Course Outline

Here is a preliminary and non-exhaustive list of topics we will be or might be covering. This is subject to change at any time, partly based on the audience.

• Linear Programming
  • Geometry, Farkas' Lemma, Strong Duality
  • Complexity
  • Interior-point Algorithms
  • Ellipsoid Algorithm and Optimization vs. Separation
  • Extension to Conic Programming
    
    
• Network Flows
  • Maximum Flows, Min-cost Flows
  • Cycle Cancelling Algorithms
  • Strongly Polynomial-time Analysis
  • Minimum Cuts without Flows
    
    
• Approximation Algorithms
  • Limits to Approximability
  • Basic Techniques and Vertex Cover
  • Primal-dual Technique
  • Semidefinite Programming
  • Multicommodity Cut via Embedding Metric Spaces
  • Approximation Scheme for Euclidean TSP
    
    
• Data Structures
  • Van Emde Boas Queues
  • Splay Trees
  • Dynamic Trees