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, or something listed as "covered" that wasn't, please let us know.

  • 1/8 Introduction. Informal Notes on testing whether a graph is Eulerian. Intro to Stable Matching.
  • 1/10 Stable Matching (Section 1.1). REMINDER: I assume you know all of Chapters 2 and 3!!
  • 1/13 Greedy Algorithms (Chapter 4). Knapsack problems (llustration), Interval Scheduling Problems (Sections 4.1 and 4.2 of the text).
  • 1/15 Minimum Spanning Trees--Prim and Kruskal Strategies. Shortest Paths -- Dijkstra (Sections 4.4, 4.5)
  • 1/17 Implementation issues. Heaps (Section 2.5). Union-Find Structures. (Section 4.6).
  • 1/20 No class. MLK Day
  • 1/22 Divide and Conquer. Recursion and recurrence relations. Mergesort. Integer Multiplication. Divide into equal parts. (Sections 5.1, 5.5 -- 5.2 covered in 271000)
  • 1/24 Dynamic Programming. Weighted Interval Scheduling. Memoization.Subset Sum and Knapsack. (Sections 6.1, 6.2, 6.4)
  • 1/27 Dynamic Programming. Sequence Alignment. Sequence Alignment in small space (Sections 6.6, 6.7)
  • 1/29 Shortest Paths. (Section 6.8)
  • 1/31 MIDTERM 1
  • 2/3 Network Flows: Definitions, Ford-Fulkerson (Section 7.1)
  • 2/5 Network Flow: MaxFlow MinCut Theorem and proof of correctness of Ford-Fulkerson (Sections 7.2, 7.3)
  • 2/7 Applications of Network Flow: Biprtite Matching, Edge-Disjoint Paths (Sections 7.5, 7.6)
  • 2/10 More Applications of Max-Flow: Circulations. Circulations with Lower Bounds, Baseball Elimination (Sections 7.7 and 7.12)
  • 2/12 Linear Programming. (Chapter 29 of Cormen) Standard and slack forms. Reducing combinatorial problems to LP
  • 2/14 LP: the simplex algorithm. (section 29.3 Cormen)
  • 2/17 LP: deciding feasibility and getting an initial feasible solution for simplex. Definition of dual problem.
  • 2/19 LP duality. Proof of Weak Duality Theorem. Consequences. Strong Duality Theorem andclassification of LP problems and their duals. (no proof of Strong Duality in class)
  • 2/21 Second Midterm
  • 2/24 Intuition about duality. (Matousek-Gaertner example). Price interpretation via dimensional analysis2/26 NP
  • 2/26 The class NP. Good (polynomial length) certificates. Examples of problems in NP: Vertex Cover, Independent Set.
  • 2/28 More NP-complete problems. Polynomial time reductions.
  • 3/3 3-SAT reduces to 3D Matching. The Garey ad Johnson lists.
  • 3/5 Circuit Satisfiability problem. It is NP-complete. Proof that Circuit Satisfiability reduces to 3-SAT (therefore zillions of NP-complete problems.) co-NP. Informal discussion of what to do with NP-completeness in real life: restrictions, approximation algorithms, local search, etc.
  • 3/7 Probabilistic Algorithms (Chapter 13). Section 13.1 (contention resolution -- we saw the 2-process version in class and did not spend time on the complete analysis, but you should look at it.) I assume you know the material in 13.3 (linearity of expectation). We covered Section 13.4, the 7/8 randomized approximation algorithm to MAX 3-SAT
  • 3/10 Randomized algorithm for Median (Section 13.5) Quicksort uses the same trick and the same analysis.
  • 3/12 Hashing (section 13.6). General talk (you're not responsible for it) on concepts: streaming algorithms, quantum algorithms.
    •