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
-
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