| Date | Topic | Reading | Homework |
|---|---|---|---|
| Fri 9/10 |
Unit 1: Introduction Administrivia A Sneak Peek into Algorithms |
KT 1.2 | PS1 out |
| Tue 9/14 |
Unit 2: Divide and Conquer Sorting and Mergesort Asymptotic Notation |
KT 5.1, 2.1, 2.2, 2.4 | |
| Fri 9/17 |
Asymptotic Notation Recap Integer Multiplication: Karatsuba's algorithm Recurrence relations |
KT 5.2, 5.5 | |
| Tue 9/21 |
Recurrences: Master Theorem
Selection: Randomized Algorithm |
KT 13.5, 5.2 |
PS1 due PS2 out |
| Fri 9/24 |
Selection: Deterministic Algorithm Divide and Conquer Recap |
||
| Tue 9/28 |
Unit 3: Dynamic Programming Fibonacci Series Weighted Interval Scheduling |
KT 6.1, 6.2 | |
| Fri 10/1 |
Segmented Least Squares Knapsack |
KT 6.3, 6.4 |
PS2 due PS3 out 10/2 |
| Tue 10/5 |
Longest Common Subsequence Sequence Alignments |
KT 6.6 | |
| Fri 10/8 |
More DP examples | ||
| Tue 10/12 |
Unit 4: Greedy Algorithms Interval Scheduling |
KT 4.1 | |
| Fri 10/15 |
Huffman Coding Proof Strategies |
KT 4.8 | PS3 due |
| Tue 10/19 |
Midterm I (Units 1 through 3) | ||
| Fri 10/22 |
Unit 5: Graph Traversals Graph definitions Depth-first search, Topological Sort |
KT 3.1, 3.2, 3.5, 3.6 | PS4 out |
| Tue 10/26 |
Strongly connected components Breadth-first search |
KT 3.4, 3.5 | |
| Fri 10/29 |
Unit 6: Graph Optimization Shortest paths: Dijkstra's Algorithm |
KT 4.4 |
PS4 due PS5 out |
| Tue 11/2 |
Shortest paths: Dijkstra using PQs Shortest paths: Bellman-Ford | KT 2.5, 6.8 | |
| Fri 11/5 |
Minimum Spanning Trees: Introduction Minimum Spanning Trees: Prim |
KT 4.5 | |
| Tue 11/9 |
Minimum Spanning Trees: Kruskal Union-Find using linked lists (Kruskal) |
KT 4.5, 4.6 | |
| Fri 11/12 |
Unit 7: Network Flows Flows and cuts Ford-Fulkerson's algorithm |
KT 7.1-7.2 | PS5 due |
| Tue 11/16 |
Midterm II (Units 4 through 6) | ||
| Fri 11/19 |
Edmonds-Karp Applications of network flows |
KT 7.3, 7.5 | PS6 out |
| Tue 11/23 |
More Network flow applications | ||
| Fri 11/26 |
Thanksgiving (no class) | ||
| Tue 11/30 |
Unit 8: Randomized Algorithms | ||
| Fri 12/3 |
Unit 9: P, NP and NP-completeness Hard Decision Problems Polynomial-time Reductions |
KT 8.1-8.3 | |
| Tue 12/7 |
NP-completeness |
KT 8.4-8.7 | PS6 due |