Design and Analysis of Algorithms
Handouts
Slides
Linear programming
Basic definitions and the simplex method
.
(Updated 9/24/10)
Duality
.
(Updated 9/24/10)
NP-completeness
.
Approximation algorithms load balancing
.
An approximation algorithm for set cover
.
Approximation algorithms for vertex cover
.
(Updated 11/7/10)
An approximation scheme for the knapsack problem
.
Randomized approximation algorithms for MAX 3-SAT
.
Fixed-parameter algorithms: Vertex cover and forbidden minors
.
Tree decompositions
.
(Updated 12/6/10)
Sample Exams
Sample exam 2
.
Sample exam 3
.
Exam 1, Fall 2008
.
Exam 2, Fall 2008
.
Exam 3, Fall 2008
.
Other
Handout on center selection
(by Mukul Bansal).
Last modified 6 December 2010.