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:
There will be one question on each of the 4 topics.
- 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
- 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