The course is organized around a few fundamental themes in the area of algorithms. The exact coverage in each of these areas is subject to change. Many of these themes appear in undergraduate algorithms courses, such as in CS 482. The coverage here will focus on more advanced topics, and will involve very little overlap with CS 482.

• Greedy algorithms:
  • spanning trees, Steiner trees, matroids, arborescences, and multicast cost-sharing.
• Advanced data structures:
  • advanced heaps, self-organizing data-structures.
• Network Flows:
  • maximum flows and minimum cuts, the preflow-push algorithm, minimum-cost flows, multicommodity flows, and applications to matching, scheduling, network routing and vision.
• Dynamic programming. 
  • basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width.
• NP-completeness:
  • This topic is discussed extensively in the undergraduate course, CS 482. The coverage here will be briefer.
• Algorithms for hard problems
  • Approximation Algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, the use of linear programming.
• Randomized Algorithms:
  • basic techniques from discrete probability, and applications to optimization, distributed computation, and packet routing.