The final exam is in 205 MLH from 7:30 am to 9:30 am on Tuesday, May 13th. You are welcome to use your books (including photocopied material) and notes during the exam.

The topics for the exam will be:

• Matching:
  • unweighted bipartite matching
  • weighted bipartite matching
  • duality between maximum weighted bipartite matching and minimum edge cover
  • Hungarian algorithm for maximum weighted bipartite matching

• Linear Programming
  • LP formulations of problems such as max-flow, shortest path, etc.
  • LP duality, strong and weak duality theorems
  • Strongly unimodular matrices and implications for LP

• NP-completeness
  • Polynomial time verification, the class NP
  • Polynomial reducibility, the class NP-hard, the class NP-complete
  • NP-completeness of problems such as CIRCUIT-SAT, SAT, 3CNF-SAT, VERTEX COVER, HAMILTONIAN CYCLE, CLIQUE, SUBSET SUM, etc.

• Approximation Algorithms
  • SET COVER: Deterministic rounding, Randomized rounding, Greedy method, Primal-dual method
  • Hardness of approximating TSP
  • FPTAS for Knapsack