• Lectures: Mon/Wed 1:30-2:50, GHC 4401 (Rashid Auditorium)
    • Instructors: Anupam Gupta (anupamg@cs, GHC 7203), Danny Sleator (sleator@cs, GHC 8113)
    • TAs: Aakash Patel, Abhik Mondal, Andy Liu, Ben Spinelli, Bojian Han, Chris Ying, Matt Dee, Naomi Rubin

  • Recitations (all on Tuesday)
    • A: 9:30 (DH 1211): Aakash, Matt
    • B: 10:30 (DH 1211): Naomi
    • C: 11:30 (DH 1211): Chris
    • D: 12:30 (DH 1211): Andy
    • E: 1:30 (SH 222): Ben, Bojian
    • F: 11:00 PST (online, CMU-SV room 212): Abhik

  • Other directions:
    • Office hours will be listed in the calender at the bottom of this page.
    • Ask/answer questions on Piazza
    • Use gradescope to submit homework solutions (and autolab to check grades).
    • All videos at the Panopto site (use andrew ID to sign in).
    • Course Policies


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
Mon Jan 11 (D) Lec 1: Intro & Linear-time Selection (randomized and deterministic); recursion trees. (notes, video) [Ch 9/Ch 2.4]
Tue Jan 12 Reci 1: Asymptotic analysis, solving recurrences. (notes) (worksheet) [Ch 3-4/Ch 0,2.2]
Wed Jan 13 (A) Lec 2: Concrete Models, Upper/Lower Bounds (notes) (video) [Ch 8.1/Ch 2.3] H1 out
Thu Jan 14 Q1 due midnight
Mon Jan 18 MLK Day Holiday!
Tue Jan 19 Reci 2: Lower/upper bounds, probability (wksheet) [Ch 5/]
Wed Jan 20 (D) Lec 3: Amortized Analysis I: A simple amortized dictionary data structure (notes) Formal Potential Functions (notes) (video) [Ch 17/-]
Mon Jan 25 (D) Lec 4: Amortized Analysis II: Splay trees (notes) Q2
Tue Jan 26 Reci 3: Amortized analysis (wksheet)
Wed Jan 27 (A) Lec 5: Union-find (with appendix on MSTs). (notes) [Ch 21/5.1.3,5.1.4] H1 soln, H2 out
Mon Feb 1 (A) Lec 6: Hashing: Universal and Perfect Hashing (notes) [Ch 11/Ch 1.5] Q3
Tue Feb 2 Reci 4: Hashing and Basic Probability (wksheet) [Ch 5/Ch 1.5]
Wed Feb 3 (A) Lec 7: Algorithms for Big Data: Streaming Algorithms (notes)
Mon Feb 8 (A) Lec 8: Fingerprinting and Substring Searches (notes) Q4
Tue Feb 9 Reci 5: Hashing and Streaming (wksheet) H2 soln
Wed Feb 10 (D) Lec 9: Dynamic Programming I (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6]
Mon Feb 15 (D) Lec 10: Quarterly Exam + Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall) (notes)
Tue Feb 16 Reci 6: Dynamic Programming (wksheet) H3 out
Wed Feb 17 (A) Lec 11: Game Theory I: Minimax Optimality, and Connections to Algorithms (notes) [-/Ch 7.5]
Mon Feb 22 (D) Lec 12: Network Flows I (notes) [Ch 26/7.2-7.3] Q5
Tue Feb 23 Reci 7: Flows, Zero-sum games (wksheet)
Wed Feb 24 (D) Lec 13: Network Flows II: Edmonds-Karp 1/2, blocking flows, min-cost flows (notes) H3 soln
Mon Feb 29 Midterm
Tue Mar 1 Reci 8: Flows (worksheet)
Wed Mar 2 (D) Lec 14: Linear Programming I: basics (notes) [Ch 29/Ch 7.1,7.6] H4 out
Mar 7-12 Spring Break Holiday!!!
Mon Mar 14 (A) Lec 15: Linear Programming II: Recap, Seidel's algorithm (notes, 2D-LP) [Ch 29/Ch 7.4] Q6
Tue Mar 15 Reci 9: Linear Programming (worksheet)
Wed Mar 16 (A) Lec 16: Linear Programming III: Duality (notes combined with Lec15, notes v2.0 with revised duality intuition) H4 sol, H5 out
Mon Mar 21 (A) Lec 17: Linear Programming IV (and Machine Learning I): The Perceptron Algorithm (notes) Q7
Tue Mar 22 Reci 10: LPs and perceptron (worksheet)
Wed Mar 23 (A) Lec 18: NP Completeness (notes) [Ch 34/Ch 8]
Mon Mar 28 (A) Lec 19: Approximation Algorithms (notes) [Ch 35/Ch 9.2] Q8
Tue Mar 29 Reci 11: NP-completeness and Approximations (worksheet) H5 sols (partial)
Wed Mar 30 (A) Lec 20: Machine Learning II: The Multiplicative Weights Framework (notes, old slides, survey).
Mon Apr 4 (A) Lec 21: Quarterly Exam + Game Theory II: Auctions and the VCG Mechanism (notes).
Tue Apr 5 Reci 12: MW and Auction Mechanisms and VCG (worksheet) H6 out
Wed Apr 6 (A) Lec 22: Game Theory III: Matching Markets and a Pricing Algorithm. (notes).
Mon Apr 11 (D) Lec 23: Online Algorithms (notes) Q9
Tue Apr 12 Reci 13: Matching Markets, Online Algorithms (worksheet)
Wed Apr 13 (D) Lec 24: Computational Geometry I: Intro and Convex Hull (notes) [Ch 33/-] H6 sols
Mon Apr 18 (D) Lec 25: Computational Geometry II: Closest Pairs (notes) [Ch 33/-] H7 out
Tue Apr 19 Reci 14: CG. (worksheet)
Wed Apr 20 (D) Lec 26: Computational Geometry III: Sweepline Algorithms (notes) [Ch 33/-]
Mon Apr 25 (D) Lec 27: Point Location Data Structures (notes) Q10
Tue Apr 26 Reci 15: Comp.geom. (worksheet) H7 sols
Wed Apr 27 (A) Lec 28: The Power of Polynomials (notes), and Course Summary
[-/Ch 2.6.1]
Thu May 5 Final: 8:30-11:30am, location 4401 (SV B23 room 211) (CMU Hub)

Course Calendar