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