Schedule

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

Day Date    Inst Topics Covered Notes and Readings HWs/Quizzes
Tue 14-Jan (DW) Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees.
slides, notes from previous year, handout on recurrences
[Ch 9/Ch 2.4] HW1 Out and Programming Tips HW1 Solutions
Thu 16-Jan (DW) Lec2: Concrete models and tight upper/lower bounds.
slides, notes from previous year, comic 1, comic 2
[Ch 8.1/Ch 2.3] Q1
Fri 17-Jan Rec1: big-O, recurrences, probability, and concrete models     worksheet   solutions
Tue 21-Jan (DS) Lec3: Amortized Analysis    notes [Ch 17/-]
Thu 23-Jan (DS) Lec4: Splay Trees    notes, video Q2
Fri 24-Jan Rec2: Amortized Analysis and Splay Trees (worksheet) (solutions)
Tue 28-Jan (DW) Lec5: Hashing I: Universal and Perfect Hashing. slides, notes from previous year, video [Ch 11/Ch 1.5] HW2 Out
Thu 30-Jan (DW) Lec6: Hashing II: Streaming Algorithms slides, notes from previous year, video Q3
Fri 31-Jan Rec3: Hashing and Streaming (worksheet) (solutions)
Tue 4-Feb (DW) Lec7: Hashing III: Fingerprinting and other applications slides, notes from previous year, video [H2 orals (T-F)] HW 2 Solutions
Thu 6-Feb (DS) Lec8: Dynamic Programming I   notes  video Q4
Fri 7-Feb Rec4: Streaming, Fingerprinting, Dynamic Programming (worksheet) (solutions)
Tue 11-Feb (DS) Lec9: Dynamic Programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall)   notes, video [Ch 15, 24.1, 25.1-25.2/Ch 6] HW3 out
HW3 Solutions
Thu 13-Feb Midterm Exam
Fri 14-Feb Rec5: DPs, Shortest paths (worksheet) (solutions)
Tue 18-Feb (DS) Lec10: Network Flows I: Flows and Matchings notes video
Thu 20-Feb (DS) Lec11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows notes video [Ch 26/7.2-7.3] Q5
Fri 21-Feb Rec6: flows and matchings (worksheet) (solutions)
Tues 25-Feb (DW) Lec12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms slides, notes, video HW4 Out
HW4 Solutions
Thur 27-Feb (DW) Lec13: Linear Programming I: Basics slides, notes < video [Ch 29/Ch 7.1,7.6] Q6
Fri 29-Feb Rec7: flows and zero-sum games and LP (worksheet) (solutions)
Tues 3-Mar (DW) Lec14: Linear Programming II: Simplex, Seidel's 2D algorithm slides, notes, video
Thur 5-Mar (DW) Lec15: Linear Programming III: Duality slides, notes, video Q7
Fri 6-Mar Mid-semester Break HW5 out
HW5 Solutions
Tue
Thu Spring Break
Fri
Tues 17-Mar Class canceled [Ch 34/Ch 8]
Thur 19-Mar (DS) Lec16: NP-Completeness. notes, slides, panopto-video, zoom-video
Fri 20-Mar Rec8: NP-completeness (worksheet) (solutions)
Tues 24-Mar (DS) Lec17: Approximation Algorithms. (notes) (slides) (panopto-video) (zoom-video)
Thurs 26-Mar (DS) Lec18: Online Algorithms. (notes) (panopto-video) (zoom-video)
Fri 27-Mar Rec9: Approximation and Online Algorithms. (worksheet) (sols) HW 5 Due 3/28
Tues 31-Mar Midterm Exam
Thu 2-Apr (DW) Lec19: Graph Compression slides, notes, panopto video HW6 out
HW6 Solutions
Q8
Fri 3-Apr Rec10: Graph Compression (worksheet) (solutions)
Tues 7-Apr (DS) Lec20: Multiplicative Weights Algorithm (notes) (video) (panopto)
Thu 9-Apr (DS) Lec21: Computational Geometry I: Geometric Primitives and Convex Hull (notes) (video) (panopto) Q9
Fri 10-Apr Rec11: Multiplicative Weights and Computational Geometry (worksheet) (solutions)
Tue 14-Apr (DS) Lec22: Computational Geometry II -- Sweepline and SegTrees (Sweepline notes) (SegTree notes) (video) (panopto)
Thu 16-Apr (DS) Lec23: Computational Geometry III -- Closest Pair (notes) (Smallest Enclosing Circle 1) (SEC2) (video) (panopto) Q10
Fri 17-Apr Rec12: Computational Geometry (worksheet) (solutions) HW 6 Due 4/17
Programming Due 4/19
Tue 21-Apr (DW) Lec24: Strassen and Karatsuba's Algorithms notes, slides, panopto video HW 7 out (square hints)
HW 7 Sols
Thu 23-Apr (DW) Lec25: The Algorithmic Magic of Polynomials notes, slides, panopto video Q11
Fri 24-Apr Rec13: Multiplication Algorithms and Polynomials
Tue 28-Apr (DW) Lec26: The Fast Fourier Transform Avrim's text file notes, Gary's pdf file notes, slides, panopto video
Thu 30-Apr (DW) Lec27: Algorithmic Applications of Embeddings slides, notes, panopto video Q12
Fri 1-May Rec14: FFT, Embeddings, and Course recap (worksheet) (solutions)
Tue 5-May Final 8:30 am -- 11:30 am (CMU Hub)

Course Calendar