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 |
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 | Reci 8: Flows () | |||
Mon | Oct 24 | HW5 | |||
Tue | Oct 25 | (D) | Lec 16: Linear Programming I: basics () | [Ch 29/Ch 7.1,7.6] | |
Thu | Oct 27 | (D) | Lec 17: Linear Programming II: Recap, Seidel's algorithm (, ) | [Ch 29/Ch 7.4] | |
Fri | Oct 28 | Reci 9: LP and Flows () | |||
Mon | Oct 31 | HW5 Due | |||
Tue | Nov 1 | (D) | Lec 18: Linear Programming III: Duality ( combined with Lec15, with revised duality intuition) | ||
Thu | Nov 3 | Midterm 2 | |||
Fri | Nov 4 | Reci 10: LP () | |||
Tue | Nov 8 | (C) | Lec 19: NP Completeness I (definition; set cover, Vertex cover) () | [Ch 34/Ch 8] | HW6 |
Thu | Nov 10 | (C) | Lec 20: NP-completeness: II (sat, graph coloring, traveling salesperson) | [???] | |
Fri | Nov 11 | Reci 11: NP-completeness and Approximations () | |||
Tue | Nov 15 | (C) | Lect 21: Approximation algorithms I: (VC, makespan, traveling salesperson, etc.) | [???] | |
Thu | Nov 17 | (C) | Lec 22: Approximation algorithms II: (LP and randomized rounding) | [???] | HW6 Due |
Fri | Nov 18 | Reci 12: Approximation algorithms () | |||
Tue | Nov 22 | (D) | Lec 23: Machine Learning: The Multiplicative Weights Framework (notes, old slides, survey). | ||
Thu | Nov 24 | Happy Thanksgiving! | HW7 | ||
Tue | Nov 29 | (D) | Lec 24: Online Algorithms () | ||
Thu | Dec 1 | (D) | Lec 25: Computational Geometry I: Intro and Convex Hull () | [Ch 33/-] | |
Fri | Dec 2 | Reci 13: Online algorithms + comp geo () | |||
Tue | Dec 6 | (D) | Lec 26: Computational Geometry II: Closest Pairs () | [Ch 33/-] | HW7 Due |
Thu | Dec 8 | (D) | Lec 27: Point Location Data Structures () | ||
Fri | Dec 9 | Reci 14: Comp geo () | |||
Fri | Dec 16 | 5:30 | Final Exam: Location to be determined |