| 1 | Tu 1/16 | 1: Introduction, Big-O Notation, Arithmetic [slides] [slides (6up)] [recording posted!] | DPV §0 , §1.1 | | |
| 1 | Th 1/18 | 2: Integer Multiplication, Recurrence Relations, Master Theorem [slides] [slides (6up)] [recording posted!] | DPV §2.1 , §2.2 | | |
| 2 | Tu 1/23 | 3: Matrix Muliplication, Median-Finding [slides] [slides (6up)] [recording posted!] | DPV §2.3 , §2.4 , §2.5 | [Section 1,Solutions] [Section 1 walkthrough Asymptotic Complexity Comparisons / Asymptotics and Limits / Complex Numbers Review part 1 / Complex Numbers Review part 2 / Recurrence Relations ] | HW 1 due 1/29 |
| 2 | Th 1/25 | 4: Fast Fourier Transform (Part I) [slides] [slides (6up)] [recording posted!] | DPV §2.6 | | |
| 3 | Tu 1/30 | 5: Fast Fourier Transform (Part II) [slides] [slides (handout)] [recording posted!] | DPV §2.6 | [Section 2,Solutions] [Section 2 walkthrough Counting Inversions / Divide and Conquer / FFT Intro / Monotone Matrices ] | HW 2 |
| 3 | Th 2/1 | 6: Depth First Search, Topological Sort [slides] [slides (handout)] [recording posted!] | DPV §3 | | |
| 4 | Tu 2/6 | 7: Strongly Connected Components [slides] [recording posted!] | DPV §3 | [Section 3,Solutions] [Section 3 walkthrough Graph Traversal a / Graph Traversal b / Graph Traversal c / Not so Exciting Scheduling / Pattern Matching / Triple Sum ] | HW 3 </br> HW 3 walkthrough Homework 3 Q2 / Homework 3 Q3 / Homework 3 Q4 / Homework 3 Q5 |
| 4 | Th 2/8 | 8: Paths in Graphs [slides] [recording posted!] | DPV §4 [FFT Applications] | | |
| 5 | Tu 2/13 | 9: Greedy Algorithms, Huffman encoding [slides] [recording posted!] | DPV §5 , §5.2 | [Section 4,Solutions] [Section 4 walkthrough Dijikstras algorithm fails on negative edges / Discussion 4 Q4 / Discussion 4 Q5 / Running Errands / Waypoint ] | HW 4 |
| 5 | Th 2/15 | 10: Minimum Spanning Trees [slides] [prim’s proof] [recording posted!] | DPV §5.1 | | |
| 6 | Tu 2/20 | 11: Union Find, Horn Formulas [slides] [recording posted!] | DPV §5.1.4 , §5.3 | [Section 5,Solutions] | HW 5 |
| 6 | Th 2/22 | 12: Dynamic Programming (Part I) [slides] [recording posted!] | DPV §6.1 , §6.2 , §6.3 | | |
| 7 | Tu 2/27 | Midterm 1 on 2/26 | | [Section 6,Solutions] [Section 6 walkthrough Change Making / Dynamic Programming Introduction Fibonacci Numbers / lanting Trees / Longest Common Subsequence ] | HW 6 |
| 7 | Th 2/29 | 13: Dynamic Programming (Part II) [slides] [recording posted!] | DPV §6.3 , §6.4 | | |
| 8 | Tu 3/5 | 14: Dynamic Programming (Part III) [slides] [recording posted!] | DPV §6.6 | [Section 7,Solutions] [Section 7 walkthrough Balloon Popping Problem / Finding More Counterexamples / Optimal Set Covering / Tiring Resorts ] | HW 7 |
| 8 | Th 3/7 | 15: Dynamic Programming (Part IV) [slides] [recording posted!] | DPV §6.5 , §6.6 , §6.7 | | |
| 9 | Tu 3/12 | 16: Linear Programs, Simplex Algorithm [slides] [recording posted!] | DPV §7.1 | [Section 8,Solutions] [Section 8 walkthrough Egg Drop Revisited / Huffman and LP / LP Basics / Simplex Practice ] | HW 8 |
| 9 | Th 3/14 | 17: Network Flow, Bipartite Matching [slides] [recording posted!] | DPV §7.2 , §7.3 | | |
| 10 | Tu 3/19 | 18: Duality, Zero-Sum Games [slides] [recording posted!] | DPV §7.4 , §7.5 | [Section 9,Solutions] [Section 9 walkthrough Advertising / Fun Duality / Max Flow Min Cut and Duality / Residual in graphs / ZeroSum Games Short Answer ] | HW 9 |
| 10 | Th 3/21 | 19: Review [slides] [recording posted!] | | | |
| 11 | Tu 3/26 | Spring Recess | | | |
| 11 | Th 3/28 | Spring Recess | | | |
| 12 | Tu 4/2 | Midterm 2 | | | |
| 12 | Th 4/4 | 20: Reductions, NP-Completeness [slides] [recording posted!] | DPV §7.3 , §8.1 | [Section 10,Solutions] [Section 10 walkthrough Bad Reductions / Graph Coloring Problem / Optimization versus Search / Set Cover vs LP ] | HW 10 |
| 13 | Tu 4/9 | 21: Reductions [slides] [recording posted!] | DPV §8.2, 8.3 | [Section 11,Solutions] [Section 11 walkthrough A Reduction Warmup / California Cycle / Cycle Cover / NP or not NP that is the question / Runtime of NP ] | HW 11 |
| 13 | Th 4/11 | 22: Coping with NP-completeness [slides] [recording posted!] | DPV §9 | | |
| 14 | Tu 4/16 | 23: Coping with NP-completeness [slides] [recording posted!] | DPV §9 | [Section 12,Solutions] | HW 12 ,Coding |
| 14 | Th 4/18 | 24: Gradient Descent (Part I) [slides] [recording posted!] | GD Notes (sections 1-3) – updated 4/29 | | |
| 15 | Tu 4/23 | 25: Gradient Descent (Part II) [slides] [recording posted!] | GD Notes – updated 4/29 | Section 13 | HW 13 |
| 15 | Th 4/25 | 26: Gradient Descent (Part III), Multiplicative Weights | GD Notes – updated 4/29 | | |