Design and Analysis of Algorithms
Handouts
Slides
Randomized approximation algorithms for MAX 3-SAT
.
An approximation algorithm for set cover
.
Approximation algorithms for vertex cover
.
An approximation scheme for the knapsack problem
.
Tree decompositions
.
NP-completeness
.
Linear programming
The simplex method and duality
.
The fundamental theorem of linear programming, the weak duality theorem, and the strong duality theorem
.
(Updated 10/06)
Sample Exams
Sample exam 3
.
Sample exam 2
.
Exam 1, Fall 2008
.
Other
Handout on center selection
(by Mukul Bansal).
Last modified 6 October 2009.