Spring 2013
Tentative schedule
| Date | Topic | Readings | Homework (out) | Homework (due) | |
| 1 | 2/6 | Overview | Chapter 1 | ||
| 2 | 2/8 | Measuring algorithm performance: Big O | Chapters 2, 3 | ||
| 3 | 2/13 | Recurrences and Master Theorem | Chapter 4.3, 4.4, 4.5 | HW1 | |
| 4 | 2/15 | Quicksort | Chapter 7 | ||
| 5 | 2/20 | Mergesort | Chapter 2.3 | ||
| 6 | 2/22 | Heapsort | Chapter 6 | HW2 | HW1 |
| 7 | 2/27 | Sorting in Linear Time | Chapter 8 | ||
| 8 | 3/1 | Selection: Max, Min, and Medians | Chapter 9 | ||
| 9 | 3/6 | Hash Tables | Chapter 11 | HW3 | HW2 |
| 10 | 3/8 | Binary Search Trees and 2-3 Trees | Chapter 12 and handout | ||
| 11 | 3/13 | Amortized analysis | Chapter 17 | ||
| 12 | 3/15 | Disjoint Sets | Chapter 21 | HW3 | |
| 13 | 3/20 | Review | |||
| 3/22 | Midterm | ||||
| 3/27 | Spring break (No lecture) | ||||
| 3/29 | Spring break (No lecture) | ||||
| 14 | 4/3 | Graph Respresentations, BFS, DFS | Chapter 22.1-3 | ||
| 15 | 4/5 | Topological Sort, SCC | Chapter 22.4, 22.5 | HW4 | |
| 16 | 4/10 | Minimum Spanning Trees: Prim Algorithm | Chapter 23.1 | ||
| 17 | 4/17 | Minimum Spanning Trees: Kruskal Algorithm | Chapter 23.2 | ||
| 18 | 4/19 | Single-Source Shortest Paths: Dijkstra's Algorithm | Chapter 24 | HW5 | HW4 |
| 19 | 4/24 | All-Pairs Shortest Paths: Floyd-Warsh algorithm | Chapter 25 | ||
| 20 | 4/26 | Dynamic Programming | Chapter 15.2-3 | ||
| 21 | 5/1 | NP-Completeness | Chapter 34 | HW6 | HW5 |
| 22 | 5/3 | NP-Completeness | Chapter 34 | ||
| 23 | 5/8 | Approximation Algorithms | Chapter 35 | ||
| 24 | 5/10 | Review | HW6 | ||
| TBA | Final Exam |