Lectures

Lectures will generally be available on-line shortly after the class meets. Book sections indicated do not exactly match the lectures, but provide a reference for related material. Some slides taken from the Kevin Wayne slides accompanying the textbook.

Week 1:
• Introduction and Review - pdf: 2 per page, 6 per page
  In the book: Preface, 2.1, 2.2, 2.4, 3.1
• Graphs - pdf: 2 per page, 6 per page
  In the book: 3.2 - 3.6
• Greedy Algorithms (Intro, Interval Scheduling, and Shortest Path) - pdf: 2 per page, 6 per page
  In the book: 4.1, some of 4.4
• Greedy Algorithms (Shortest Path, Minimum Spanning Tree, and Union-Find) - pdf: 2 per page, 6 per page
  In the book: 4.4, 4.5, and 4.6
• Greedy Algorithms (MST, Union-Find, Clustering, and Huffman Coding) - pdf: 2 per page, 6 per page
  In the book: 4.6, 4.7, and 4.8
  

Week 2:
• Divide and Conquer (MergeSort, Inversion Counting, and Closest Pair of Points)- pdf: 2 per page, 6 per page
  In the book: 5.1, 5.3, and 5.4
• Divide and Conquer (Closest Pair of Points and Multiplication) - pdf: 2 per page, 6 per page
  In the book: 5.4 and 5.5
• Divide and Conquer (Matrix Multiplication) - pdf: 2 per page, 6 per page
  (Not in the book)
• Dynamic Programming (Weighted Interval Scheduling and Knapsack Problem) - pdf: 2 per page, 6 per page
  In the book: 6.1 and 6.4
• Dynamic Programming (Knapsack Problem and Sequence Alignment) - pdf: 2 per page, 6 per page
  In the book: 6.4 and 6.6

Week 3:
• Network Flow Introduction - pdf: 2 per page, 6 per page
  In the book: 7.1 and 7.2
• Network Flow (Capacity Scaling and Bipartite Matching) - pdf: 2 per page, 6 per page
  In the book: 7.3 and 7.5
• Network Flow Applications (Extensions and Airline Scheduling) - pdf: 2 per page, 6 per page
  In the book: 7.7 and 7.9

Week 4:
• Intractability Introduction (Poly-time Reductions) - pdf: 2 per page, 6 per page
  In the book: 8.1 and 8.2
• NP and NP-Complete - pdf: 2 per page, 6 per page
  In the book: 8.3 and 8.4
• NP-Complete Problems (Sequencing Problems) - pdf: 2 per page, 6 per page
  In the book: 8.5
• NP-Complete Problems (Partitioning and Numerical Problems) - pdf: 2 per page, 6 per page
  In the book: 8.6, 8.7, 8.8, and 8.10
• Equivalence Proofs - pdf: 2 per page, 6 per page
  (Not in the book)

Week 5:
• Approximation Algorithms Introduction (Load Balancing) - pdf: 2 per page, 6 per page
  In the book: 11.1
• Approximation Algorithms (k-Center Problem) - pdf: 2 per page, 6 per page
  In the book: 11.2
• Approximation Algorithms, the Pricing Method and IPs/LPs (Vertex Cover) - pdf: 2 per page, 6 per page
  In the book: 11.4 and 11.6
• Approximation Algorithms, Linear Programming and Dynamic Programming with Rounding (Knapsack Problem) - pdf: 2 per page, 6 per page
  In the book: 11.6 and 11.8

Week 6:
• Randomized Algorithms (Global Minimum Cut and Closest Pair of Points) - pdf: 2 per page, 6 per page
  In the book: 13.2 and 13.5
• Randomized Algorithms (Closest Pair of Points) and other topics - pdf: 2 per page, 6 per page
  In the book: 13.5, 9.1, 12.1, and Epilogue
• Exam Review - pdf: 2 per page, 6 per page