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. Some of the material is not in either of the two recommended textbook. For material that is in the books, For each section, I marked the chapters of the books used. The section numbers for the Kleinberg-Tardos book are from the 681 course packet. The corresponding numbers for last spring's 482 course packet are one more (as the section on Algorithmic primitives has been moved to the Appendix.)

• Greedy algorithms:
  • spanning trees, Steiner trees, matroids, arborescences, and multicast cost-sharing. (Using Kozen Lec1-2, and Kleinberg-Tardos Sec 2.4-2.5)
• Advanced data structures:
  • advanced heaps, self-organizing data-structures. (Using Kozen 8-13)
• 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. (Using Kleinberg-Tardos Chapter 5 and Section 10.6, and Kozen Lec. 14, and 16-20)
• Dynamic programming. 
  • basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width. (Using Kleinberg-Tardos 3.5-3.8 and 8.2-8.3)
• NP-completeness:
  • This topic is discussed extensively in the undergraduate course, CS 482. The coverage here will be briefer. (Using Kleinberg-Tardos Chapter 6.)
• Algorithms for hard problems
  • Approximation Algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, the use of linear programming. (Using Kleinberg-Tardos Chapter 9)
• Randomized Algorithms:
  • basic techniques from discrete probability, and applications to optimization, distributed computation, and packet routing. (Using Kleinberg-Tardos Chapter 11)