| SES # | TOPICS | KEY DATES |
|---|---|---|
| L1 | Administrivia Introduction Analysis of Algorithms, Insertion Sort, Mergesort | Problem set 1 out |
| R1 | Correctness of Algorithms Horner's rule | |
| L2 | Asymptotic Notation Recurrences Substitution, Master Method | |
| L3 | Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication | |
| R2 | Recurrences, Sloppiness | |
| L4 | Quicksort, Randomized Algorithms | Problem set 1 due Problem set 2 out |
| R3 | Heapsort, Dynamic Sets, Priority Queues | |
| L5 | Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort | |
| L6 | Order Statistics, Median | |
| R4 | Applications of Median Bucketsort | |
| L7 | Hashing, Hash Functions | Problem set 2 due Problem set 3 out |
| L8 | Universal Hashing, Perfect Hashing | Homework lab tonight |
| R5 | Quiz 1 Review | Problem set 3 due |
| Q1 | Quiz 1, In-class | |
| R6 | Binary Search Trees, Tree Walks | |
| L9 | Relation of BSTs to Quicksort Analysis of Random BST | Problem set 4 out |
| L10 | Red-black Trees, Rotations, Insertions, Deletions | |
| R7 | 2-3 Trees, B-trees | |
| L11 | Augmenting Data Structures, Dynamic Order Statistics, Interval Trees | Problem set 4 due Problem set 5 out |
| L12 | Skip Lists | |
| R8 | Range Trees | |
| L13 | Amortized Algorithms, Table Doubling, Potential Method | Problem set 5 due Problem set 6 out |
| L14 | Competitive Analysis: Self-organizing Lists | |
| R9 | Competitive Analysis: Ski Rental, Randomized Competitive Algorithm | |
| L15 | Dynamic Programming, Longest Common Subsequence | Problem set 6 due Problem set 7 out |
| L16 | Greedy Algorithms, Minimum Spanning Trees | |
| L17 | Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search | Problem set 7 due Problem set 8 out |
| L18 | Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints | |
| R10 | Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths | |
| L19 | Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson | Problem set 8 due |
| L20 | Quiz 2 Review | |
| L21 | Ethics, Problem Solving (Mandatory Attendance) | Take-home quiz 2 handed out |
| Q2 | Quiz 2, In-class | Take-home quiz 2 due two days after Ses #Q2 |
| L22 | Advanced Topics | Problem set 9 out |
| L23 | Advanced Topics (cont.) | Homework lab tonight |
| R11 | Advanced Topics | Problem set 9 due |
| L24 | Advanced Topics (cont.) | |
| L25 | Advanced Topics (cont.) Discussion of Follow-on Classes | |
| Final Exam |