Weekly Readings (R), Lecture Notes (LN), and tutorials (TT)
-
Week 10:
R: CLRS Chapter 35
LN: Intro to Approximation Algorithms
LN: Intro to Inapproximability
LN: Minimum Makespan Job Scheduling
TT: Max-Cut Approximation
Week 8 and 9:
R: CLRS Chapter 34
LN: Intro to Complexity Theory: Definitions
LN: The Cook-Levin Theorem
LN: Reductions: 3-SAT to CLIQUE
LN: Reductions: 3-SAT to 3-COLOURING
TT: 3-SAT
TT: VERTEX COVER
Week 7:
R: CLRS Chapter 29
LN: Intro to Linear Programming
TT: Bipartite Matching
Week 6:
R: CLRS Sections 26.1 to 26.3
LN: Intro to Network Flows, Maximum Flow Problem
Max Flow-Min Cut Theorem
Bipartite Matching
TT: Flow & Cuts Practice
Week 5:
R: Sections 24.1 to 24.3, 25.2, and 26.1 on the CLRS
LN: Single Source Shortest Paths
All Pairs Shortest Paths
TT: Longest Path
Week 3 and 4:
R: Sections 16.3 in CLRS, 5.2 in DPV for Huffman Coding.
LN: Huffman Encoding.
R: Sections 15 in CLRS and 6 in DPV for Dynamic Programming.
LN: Weighted Interval Scheduling
Matrix Chain Multiplication
Minimum Weight Triangulation
TT: IS in a Permutation Model
Week 2:
R: Chapter 23 on the CLRS
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
Topic Outline
Here is a tentative topic outline for the course (this outline is reflected explicitly on the calendar below):
-
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