409 - Discrete Optimization - Spring 2022

Course information

Covered material

  1. Monday, Mar 28, 2022: Course logistics; Section 1.1 Algorithms and Complexity; Section 1.1.1 Complexity theory and NP-hardness
  2. Wednesday, Mar 30, 2022: Section 1.2 Graph Theory (undirected graphs)
  3. Friday, April 1, 2022: Section 1.2 Graph Theory (directed graphs) and Section 1.3 TSP
  4. Monday, April 4, 2022: Section 2 Minimum Spanning Trees (finished with Def of connected components)
  5. Wednesday, April 6, 2022: Section 2 Minimum Spanning Trees (finished)
  6. Friday, April 8, 2022: Shortest Paths (until beginning of correctness proof of Dijkstra's algorithm)
  7. Monday, April 11: Shortest Paths (correctness proof of Dijkstra's algorithm; Moore-Bellman-Ford algorithm)
  8. Wednesday, April 13: Correctness of Moore-Bellman-Ford. Detecting of negative cost cycles.
  9. Friday, April 15: Finding negative cost cycle. Introduction to Network Flows.
  10. Monday, April 18: Residual graphs, Ford-Fulkerson, s-t MinCut is upper bound on MaxFlow
  11. Wednesday, April 20: Proof of MaxFlow=MinCut Theorem. Edmonds-Karp algorithm
  12. Friday, April 22: Running time analysis of Edmonds-Karp
  13. Monday, April 25: Bipartite matchings, Koenigs Theorem
  14. Wednesday, April 27: Hall's Theorem. Started with linear programming chapter (polyhedra, convexity, convex hull)
  15. Friday, April 29: Cont. linear programming
  16. Monday, May 2: Farkas Lemma
  17. Wednesday, May 4: MIDTERM
  18. Friday, May 6: Strong Duality Theorem. Discussion of LP algorithms (skipped the section on the gradient-descent based method)
  19. Monday, May 9: Connection of LPs to discrete optimization. Integer programs and integer hull (skipped the direct proof of the integrality of the bipartite matching LP, Lemma 48)
  20. Wednesday, May 11: Intro to total unimodularity
  21. Friday, May 13: Criterion for checking TU'ness. Application to bipartite matching
  22. Monday, May 16: Application to flows. TUness of node-edge incidence matrices of directed graphs. TUness of matrices with consecutive-ones property
  23. Wednesday, May 18: Finished TU chapter. Begin Branch & Bound chapter.
  24. Friday, May 20: Finished B & B chapter. Started with matchings in general graphs
  25. Monday, May 23: Augmenting paths for matchings
  26. Wednesday, May 25: Contracting M-blossoms
  27. Friday, May 27: Finished chapter on matchings in non-bipartite graphs. Started chapter on Knapsack problem
  28. Monday, May 30: NO CLASS --- MEMORIAL DAY
  29. Wednesday, June 1: A dynamic program for Knapsack. A (1-epsilon)-approximation algorithm for Knapsack
  30. Friday, June 3: OFFICE HOUR IN JHN175

Problem sets

The solutions to the problem sets will be available later. You can check your points on the GradeScope webpage.

Midterm exam

Final exam

Text books

The lecture notes will contain all information given in the lecture and will be fully sufficient for the exams. However, for additional information, I recommend the following text books: 

Corrections to the lecture notes (since the March 23 version)