Material Covered

The list is intended as a guide. Dates may not exactly match the times the material was discussed; some of the topics were not taught, but mentioned as things you have learned, or should read on your own. If you notice something missing, please let us know.

  • 1/4 Chapter 1: section 1.1
  • 1/6 Chapter 2, except 2.5; section 3.1
  • 1/9 Greedy Algorithms. Section 4.1
  • 1/11 More Greedy algs: Minimum Spanning Trees. (review of Section 3.1 on trees) Section 4.5
  • 1/13 Heaps. Shortest paths on graphs. Dijkstra's Algorithm. (4.4)
  • 1/16 MLK day (no class)
  • 1/18 Implementing Dijkstra's Algorithm. Divide and Conquer. Solving recurrences. Heuristic: try to divide into equal parts. (5.1, 5.2)
  • 1/20 Sequence Alignment
  • 1/23 Sequence Alignment: backwards solution, finding the alignment using little space
  • 1/25 More Dynamc Programming: Optimal Matrix Multiplication Sequence. (with a "cultural excursion" talking about Strassen's Matrix Multiplication Algorithm).
    This material is covered in the Dasgupta et al Algorithms book in Section 6.5.
  • 1/27 More about Dynamic Programming: Top Dwon vs Bottom Up
  • 1/30 Network Flows: problem formulation. Maximal flow solutions (blocking flows) are not optimal.
  • 2/1 Ford-Fulkerson Algorithm. Residual Graphs.
  • 2/3 Max Flow Min Cut Thm through Ford Fulkerson
  • 2/6 Network Flows: scaling O(mC) and O(m^2 logC) algorithms
  • 2/8 Midterm
  • 2/10 No class (College break)
  • 2/13 Applications of Max Flow: Bipartite Matching, Augmenting Paths and Hall's Theorem
  • 2/15 Extensions: multiple sources, multiple sinks. Feasible circulations
  • 2/17 Circulations with lower bounds on flows on edges. Image Segmentation
  • 2/20 Randomized Algorithms: Contention in distributed computation.
  • 2/22 Randomized Access to resource (Sec 13.2), Karger's Agorithm for Global Min Cut
  • 2/24 Randomized median, quicksort. Randomized Max 3-SAT
  • 2/27 Polytime reductions. The class NP
  • 2/29 NP hardness, NP-completeness. SAT, Vertex Cover, Independent Set.
  • 3/2 NP-completeness proofs: 3-SAT, Hamiltonian Cycle (Hamiltonian Path, TSP)