Schedule

Please keep in mind that this is preliminary and will change. The chapter numbers are from [CLRS/DPV].

HW1 Grade Dist.
Day Date    Inst Topics Covered Notes and Readings HWs/Quizzes
Tue 02-Feb (DW) Lec 01: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees
slides, notes, video, handout on recurrences
[Ch 9/Ch 2.4] HW1 Out and Programming Tips
Thu 04-Feb (DW) Lec 02: Concrete models and tight upper/lower bounds
slides, notes, video
[Ch 8.1/Ch 2.3] Q1
Fri 05-Feb Rec 01: big-O, recurrences, probability, and concrete models     worksheet   solutions
Tue 09-Feb (DS) Lec 03: Amortized Analysis    notes, video [Ch 17/-]
Thu 11-Feb (DS) Lec 04: Splay Trees    notes, video, review Q2
Fri 12-Feb Rec 02: Amortized Analysis and Splay Trees   worksheet (solutions)
Tue 16-Feb (DW) Lec 05: Hashing I: Universal and Perfect Hashing slides, notes, video [Ch 11/Ch 1.5] HW2 Out
Thu 18-Feb (DW) Lec 06: Hashing II: Streaming Algorithms slides, notes, video Q3
Fri 19-Feb Rec 03: Hashing and Streaming worksheet   solutions
Tue 23-Feb No Classes
Thu 25-Feb (DW) Lec 07: Hashing III: Fingerprinting and other applications slides, notes, video Q4
Fri 26-Feb Rec 04: Fingerprinting worksheet solutions
Tue 2-Mar (DS) Lec 08: Dynamic Programming I   notes  video
Thu 4-Mar Midterm Exam HW3 out
Fri 5-Mar Rec 05: DPs worksheet solutions
Tue 9-Mar (DS) Lec 09: Dynamic Programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall)   notes video-2020 video-2021 [Ch 15, 24.1, 25.1-25.2/Ch 6]
Thu 11-Mar (DS) Lec 10: Network Flows I: Flows and Matchings notes video Q5
Fri 12-Mar Rec 06: DPs and Network Flows worksheet solutions
Mon 15-Mar HW3 Due, HW4 Out
Tue 16-Mar (DS) Lec 11: Network Flows II: Advanced Flow Algorithms notes video implementation video code1 code2 code3 [Ch 26/7.2-7.3]
Thu 18-Mar (DW) Lec 12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms slides, notes, 2-row games, video Q6
Fri 19-Mar Mid-semester Break     rec 07 worksheet   rec 07 solutions
Tue 23-Mar (DW) Lec 13: Linear Programming I: Basics slides, notes, video [Ch 29/Ch 7.1,7.6]
Thu 25-Mar (DW) Lec 14: Linear Programming II: Simplex, Seidel's 2D algorithm slides, notes, video Q7, HW4 Due, HW5 Out
Fri 26-Mar Rec 08: LPs and Seidel's Algorithm worksheet solutions
Tue 30-Mar (DW) Lec 15: Linear Programming III: Duality slides, notes, video
Thu 1-Apr (DS) Lec 16: Approximation Algorithms notes, slides video, Q8
Fri 2-Apr Rec 09: LP Duality and Approximation Algorithms worksheet solutions
Tue 6-Apr (DS) Lec 17: Online Algorithms notes (video(2020)) HW5 Due
Thu 8-Apr Midterm Exam HW6 out
Fri 9-Apr Rec 10: Online Algorithms and Midterm Discussion worksheet
Tue 13-Apr (DW) Lec 18: Multiplicative Weights Algorithm notes, slides, panopto
Thu 15-Apr No Classes
Fri 16-Apr No Classes
Tue 20-Apr (DS) Lec 19: Computational Geometry I: Geometric Primitives and Convex Hull
Thu 22-Apr (DS) Lec 20: Computational Geometry II -- Sweepline and SegTrees Q9, HW6 Due, HW7 Out
Fri 23-Apr Rec 11: Multiplicative Weights and Computational Geometry
Tue 27-Apr (DS) Lec 21: Computational Geometry III -- Closest Pair
Thu 29-Apr (DW) Lec 22: Strassen and Karatsuba's Algorithms notes, slides Q10
Fri 30-Apr Rec 12: Computational Geometry and Multiplication
Tue 4-May (DS) Lec 23: Fast Fourier Transform, and Applications
Wed 5-May HW7 Due
Thu 6-May (DW) Lec 24: The Algorithmic Magic of Polynomials Q11
Fri 7-May Rec 13: FFT and Polynomials

Course Calendar