**
22C:153: About the Final Exam
**

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

There will be one question on each of the 4 topics.