Lecture Topics
Topic |
Reading/Materials |
| Background, Asymptotic Analysis (8/28) | Homework 1 assigned, Chapter 0 |
| Integer Multiplication, Recurrence Relations, and the Master Theorem (8/31, 9/2, 9/7, 9/9, 9/12, 9/14, 9/16) | Chapter 1.1, 2.2 |
| Strassen's Algorithm for Matrix Multiplication (9/16) | Chapter 2.5 |
| Randomization, Linear Time Selection, and Optimal Sorting (9/19, 9/21, 9/23, 9/26, 9/28, 9/30, 10/3) | Chapter 2.3, 2,4 |
| Midterm Review/Midterm (10/7, 10/10) | Chapter 2.3, 2,4 |
| Graphs, Breadth-First Search and Depth-First Search (10/5, 10/17, 10/19, 10/21) | Chapter 3.1, 3.2, 4.1, 4.2, 4.3 |
| Shortest Paths in Weighted Graphs and Minimum Spanning Trees (10/24, 10/26, 10/28, 10/31) | Chapter 4.4, 4.5, 4.6, 5.1 |
| Greedy Algorithms: Data Compression and Interval Scheduling (11/2, 11/4, 11/7, 11/9, 11/11, 11/14) | Chapter 5.2 |
| Dynamic Programming: Weighted Interval Scheduling and 0-1 Knapsack (11/16, 11/18, 11/21) | Chapter 6.4 |
| Dynamic Programming: Edit Distance, Matrix Chain Multiplication and Shortest Paths (11/28, 11/30, 12/2) | Chapter 6.3, 6.5, 6.6 |
| NP-Completeness and Approximation Algorithms (12/5, 12/7, 12/9) | Chapter |
Template design by Andreas Viklund