Week 1 (Mar 31 – Apr 3)
The first class is on Thursday of April 2nd.
Introduction to Algorithms
- Stable marriage
Reading
- KT 1.1
- Man-optimality proof
Week 2 (Apr 6 – 10)
Introduction to Algorithms
- Overview of algorithm design
- GCD algorithm
Greedy Algorithms
- Interval scheduling
Reading
- KT 4.1
Week 3 (Apr 13 – 17)
Greedy Algorithms
- Scheduling to minimize lateness; to maximize profit
- Minimum spanning trees
Reading
- KT 4.2
- Max Profit Scheduling
- KT 4.5
- KT 4.6
Week 4 (Apr 20 – 24)
Greedy Algorithms
- Shortest Paths
Graph Algorithms
- BFS
- DFS
- Edge connectivity
Reading
- KT 4.4
- KT 3.4
- Properties of DFS from CLRS
- Notes on bridges
Week 5 (Apr 27 – May 1)
Graph Algorithms
- Strong connectivity
Reading
Week 6 (May 4 – 8)
Dynamic Programming
- Weighted Interval Scheduling
- Knapsack
- Bellman-Ford
- Floyd-Warshall
Reading
- KT 6.1
- KT 6.8
- CLRS notes on Floyd-Warshall
Week 7 (May 11 – 15)
Dynamic Programming
- Segmented Least Squares
- Negative cycles
- Sequence alignment
Reading
- KT 6.3
- KT 6.5 – 6.7
Week 8 (May 18 – 22)
Network Flows
- Bipartite Matching
- Network flow application
Reading
- KT 7.5
Week 9 (May 25 – 29)
NP-completeness
- Reduction
- NP-completeness
Reading
- KT 8.1
- KT 8.2
- NP-completeness handout