This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. We will also discuss a bit of Complexity Theory (which looks at the intrinsic difficulty of computational problems) as well as some String Algorithms, Computational Geometry, and Machine Learning.
By the end of this course, you should be able to:
| Day | Date | Inst | Topics Covered | Notes and Readings | HWs |
|---|---|---|---|---|---|
| Tue | Aug 30 | (D) | Lec 1: Intro & Linear-time Selection (randomized and deterministic); recursion trees. (notes) (recurrences appendix) | [Ch 9/Ch 2.4] | |
| Thu | Sep 1 | (C) | Lec 2: Concrete Models, Upper/Lower Bounds (notes) | [Ch 8.1/Ch 2.3] | |
| Fri | Sep 2 | Reci 1: Lower and Upper Bounds (worksheet) | [Ch 3-4/Ch 0,2.2] | HW1 Out | |
| Tue | Sep 6 | (D) | Lec 3: Amortized Analysis I: Bankers, Physicists, and Data Structures (notes) | [Ch 17/-] | |
| Thu | Sep 8 | (D) | Lec 4: Amortized Analysis II: Splay trees (notes) | ||
| Fri | Sep 9 | Reci 2: Amortized analysis (wksheet) (solutions) | [Ch 5/] | HW1 Due | |
| Sat | Sep 10 | HW2 Out | |||
| Tue | Sep 13 | (C) | Lec 5: Union-find (with appendix on MSTs) (notes) | HW1 Soln | |
| Thu | Sep 15 | (C) | Lec 6: Hashing: Universal and Perfect Hashing (notes) | ||
| Fri | Sep 16 | Reci 3: Hashing and Basic Probability (wksheet) (solutions) | |||
| Tue | Sep 20 | (C) | Lec 7: Streaming Algorithms I: Heavy Hitters (notes) | ||
| Thu | Sep 22 | (C) | Lec 8: Streaming algorithms II: locality sensitive hashing, Bloom filters (notes) | ||
| Fri | Sep 23 | Reci 4: Streaming + hashing (wksheet) | [Ch 5/Ch 1.5] | ||
| Tue | Sep 27 | (D) | Lec 9: Dynamic Programming I (notes) | [Ch 15, 24.1, 25.1-25.2/Ch 6] | HW2 Soln |
| Thu | Sep 29 | Midterm 1 | Solutions | ||
| Fri | Sep 30 | Reci 5: Dynamic Programming (wksheet) | HW3 | ||
| Tue | Oct 4 | (D) | Lec 10: Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall) (notes) | ||
| Thu | Oct 6 | (C) | Lec 11: Fingerprinting and Substring Searches (notes) | [Ch. 32] | |
| Fri | Oct 7 | Reci 6: More DP/shortest paths (wksheet) | |||
| Tue | Oct 11 | (C) | Lec 12: Suffix trees and arrays I: applications (notes) | [??] | HW3 Due (Solutions) |
| Thu | Oct 13 | (C) | Lec 13: Suffix trees and arrays II: constructing (notes suffix array code) | ||
| Fri | Oct 14 | Reci 7: Suffix trees and arrays (wksheet) | HW4 | ||
| Tue | Oct 18 | (D) | Lec 14: Network Flows I (notes) | [Ch 26/7.2-7.3] | |
| Thu | Oct 20 | (D) | Lec 15: Network Flows II: Edmonds-Karp 1/2, blocking flows, min-cost flows (notes) | HW4 Due | |
| Fri | Oct 21 | No Recitation () | |||
| Mon | Oct 24 | HW5 | |||
| Tue | Oct 25 | (D) | Lec 16: Linear Programming I: basics (notes) | [Ch 29/Ch 7.1,7.6] | |
| Thu | Oct 27 | (D) | Lec 17: Linear Programming II: A 2D LP Algorithm (notes) | [Ch 29/Ch 7.4] | |
| Fri | Oct 28 | Reci 8: Flows (worksheet) | |||
| Mon | Oct 31 | ||||
| Tue | Nov 1 | (D) | Lec 18: Linear Programming III: Duality (notes) | HW5 Due; HW5 Solns | |
| Thu | Nov 3 | Midterm 2 | |||
| Fri | Nov 4 | Reci 9: LP (worksheet) | |||
| Tue | Nov 8 | (C) | Lec 19: NP Completeness I (definition; Independent Set, Hamiltonian Path) (notes) | [Ch 34/Ch 8] | HW6 |
| Thu | Nov 10 | (C) | Lec 20: Approximation algorithms I: (VC, makespan, traveling salesperson) (notes) | [Ch 35/Ch 9] | |
| Fri | Nov 11 | Reci 10: NP-completeness and Approximations (worksheet) | |||
| Tue | Nov 15 | (C) | Lect 21: Approximation algorithms II (LP and randomized rounding) (notes) | ||
| Thu | Nov 17 | (D) | Lec 22: Experts and Weighted Majority Algorithms (notes) | ||
| Fri | Nov 18 | Reci 11: Approximation algorithms (worksheet) | |||
| Tue | Nov 22 | (D) | Lec 23: Powerful Arrays: SegTrees and Fenwick Trees (notes) | HW6 Due; HW6 Solns | |
| Thu | Nov 24 | Happy Thanksgiving! | HW7 | ||
| Tue | Nov 29 | (D) | Lec 24: Online Algorithms (notes) | ||
| Thu | Dec 1 | (D) | Lec 25: Computational Geometry I: Intro and Convex Hull (notes) | [Ch 33/-] | |
| Fri | Dec 2 | Reci 12: Online algorithms + comp geo (worksheet) | |||
| Tue | Dec 6 | (CD) | Lec 26: Computational Geometry II: Sweep-Line and Segment Intersections (notes) | [Ch 33/-] | HW7 Due; HW7 Solns |
| Thu | Dec 8 | (D) | Lec 27: Point Location Data Structures (notes) | ||
| Fri | Dec 9 | Reci 13: No Recitation () | |||
| Fri | Dec 16 | 5:30 | Final Exam: CUC McConomy |