• 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