• 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