Week of | Chapter | Description |
March 30 | 1, 2, 4 | Introduction: iteration, recursion, loop invariant | 8 | Quick Sort: strategies, average case analysis | 10 | Medians and Order Statistics |
April 6 | 9 | Sorting: lower bounds |
9 | Sorting in Linear Time | 18 | Amortized Analysis |
April 13 | 20 | Priority Queues revisited: Binomial Heaps | 21 | Fibonacci Heaps |
April 20 | 22 | Disjoint Sets (Union/Find) | 22.3 | Union by rank, Find with path compression |
22.4 | Amortized complexity analysis of Union/Find | |
April 27 | 1-10, 20-22 | Midterm Exam | April 27 | 16 | Dynamic Programming: Matrix Chain Product |
16.3 | Longest Common Subsequence | 16.4 | Polygon Triangulation | May 4 | 23 | Graph Algorithms: Representations | 23.2-3 | Breadth-first and Depth-first Traversals | 23.4-5 | Topological Sort and Connected Components |
May 11 | 24 | Minimum Spanning Trees | 24.2 | Algorithms of Kruskal and Prim |
May 18 | 25 | Single Source Shortest Paths | 25.2 | Dijkstra's Algorithm | 26 | All-Pairs Shortest Paths |
May 25 | 34 | String Matching | 34.3-4 | Knuth-Morris-Pratt Algorithmno |
June 1 | Spillage, Review and Discussion | |
June 10 | comprehensive | Final Exam at 15:15 Wednesday |