Topic Outline

Here is a tentative topic outline for the course:

   Greedy Algorithms - 2 weeks
   Dynamic Programming - 2 weeks
   Network Flows and Reductions - 2 weeks
   Linear Programming - 2 weeks
   Introduction to Complexity Theory - 2 weeks
   Approximation Algorithms and Randomization - 2 weeks

Weekly Readings (R), Lecture Notes (LN), and tutorials (TT)

Week 9 & 10:
  R: CLRS Section 35
  LN: Some inapproximability results
  LN: Weighted Vertex Cover with Edge Penalties
  LN: Introduction to Approximation Algorithms
  LN: Minimum Makespan Job Scheduling
  LN: Subset Sum is NP-complete
Week 9: - These are notes from 2014, I haven't had time to edit them so beware of silly mistakes.
  R: CLRS Section 34
  LN: 3-Colouring is NP-complete
  LN: SAT is NP-complete
  LN: Introduction to Complexity
Week 8:
  R: CLRS Section 29
  LN: Introduction to Linear Programming
Week 6:
  R: CLRS Sections 26.1 to 26.3
  LN: The Max Flow/Min Cut Theorem
  LN: Bipartite Matching
Week 5:
  R: CLRS Sections 26.1 to 26.3
  LN: Intro to Network Flows, Maximum Flow Problem
Week 4:
  R: Sections 15, 25.2
  LN: All Pairs Shortest Paths
Week 3:
  R: Sections 15, 24.1-24.3,
  LN: Weighted Interval Scheduling
  LN: Bellman Ford Algorithm
Week 2:
  R: CLRS 23 and 24.3
  LN: Dijkstra's Shortest Path Algorithm
  LN: Minimum Spanning Tree
Week 1:
  R: Allan Borodin's lecture 2 and Jeff Erickson's notes on Sections 7.2 and 7.3
  LN: Interval Scheduling
  TT: Minimum Spanning Tree - Prim's Algorithm.
  Notes to be posted next week when we cover Kruskal's algorithm