• Lectures: Tue/Thu 12:00-1:20, GHC 4401 (Rashid Auditorium)
    • Instructors: Anupam Gupta (anupamg@cs, GHC 7203), David Woodruff (dwoodruf@cs, GHC 7217)
    • TAs: Alice Rao (alrao), Can Bostanci (cbostanc), Eric Zhu (ericzhu), George Lu (gclu), Josh Korn (jkorn), Sean Zhang (xiaoronz), Shalom Yiblet (syiblet), Tanvi Bajpai (tbajpai)

  • Recitations (all on Friday)
    • A: 9:30 (DH 1211): Tanvi
    • B: 10:30 (DH 1211): Sean
    • C: 11:30 (DH 1211): Josh
    • D: 12:30 (BH 237B): George
    • E: 1:30 (GHC 4102): Eric
    • F: 2:30 (WeH 5421): Shalom

  • Office Hours: (subject to revisions in the calendar at the bottom of the page. Please check!)
    • Anupam Gupta: Monday 5-6pm, GHC 7203
    • David Woodruff: Tuesday 4-5pm, GHC 7217
    • Alice Rao: Wednesday 5pm-6:30pm, GHC 4126
    • Can Bostanci: Monday 8-9:30pm, GHC 4303
    • Eric Zhu: Monday 6:30-8pm, GHC 4303
    • George Lu: Monday 6:30-8pm, GHC 4303
    • Josh Korn: Tuesday 6:30-8pm (9pm only weeks when HW is due), GHC 5th Floor, Carrel 1
    • Shalom Yiblet: Thursday 5-6:30pm, GHC 5th Floor, Carrel 1
    • Tanvi Bajpai: Tuesday 8-9pm, GHC 5th Floor, Carrel 1; Sunday 11am-12:30pm, GHC 4101
    • Sean Zhang: Tuesday 5-6:30pm, GHC 5th Floor, Carrel 1

  • Other directions:
    • Office hours will be listed in the calender at the bottom of this page.
    • We'll use Canvas for course management, as well as for weekly online quizzes.
    • Please ask/answer questions on Piazza
    • Use gradescope (Entry code: 9N8ZWJ) for written HWs and autolab for programming HWs.
    • 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
Tue 16-Jan (A) Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. (notes) (handout on recurrences) [Ch 9/Ch 2.4]
Thu 18-Jan (D) Lec2: Concrete models and tight upper/lower bounds. (slides) (notes from previous year) [Ch 8.1/Ch 2.3] Q1
Fri 19-Jan Rec1: big-O, recurrences, probability, and concrete models (worksheet) (solutions) H1 out, Solutions
Tue 23-Jan (A) Lec3: Amortized Analysis I: A simple amortized dictionary data structure. (notes) [Ch 17/-]
Thu 25-Jan (A) Lec4: Amortized Analysis II: Union-find (with appendix on MSTs). (notes, updated) [Ch 21/5.1.3,5.1.4] Q2
Fri 26-Jan Rec2: Amortized Analysis (worksheet) (solutions)
Tue 30-Jan (D) Lec5: Hashing I: Universal and Perfect Hashing. (slides) (notes from previous year) [Ch 11/Ch 1.5] H1 due, H2 out, Solutions
Thu 1-Feb (D) Lec6: Hashing II: Streaming Algorithms (slides) (notes from previous year) Q3
Fri 2-Feb Rec3: UF and Hashing (worksheet) (solutions)
Tue 6-Feb (D) Lec7: Hashing III: Fingerprinting and other applications (slides) (notes from previous year) [H2 orals]
Thu 8-Feb (A) Lec8: Dynamic Programming I (notes) Q4
Fri 9-Feb Rec4: Streaming, Fingerprinting, DPs (worksheet) (solutions)
Tue 13-Feb (A) Lec9: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall) (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6] H3 out, Solutions
Thu 15-Feb Midterm Exam
Fri 16-Feb Rec5: DPs and Shortest paths (worksheet) (solutions)
Tue 20-Feb (A) Lec10: Network Flows I: Flows and Matchings (notes)
Thu 22-Feb (A) Lec11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows (notes) [Ch 26/7.2-7.3] H3 in, H4 out, Solutions
Fri 23-Feb Rec6: flows and matchings (worksheet) (solutions) Q5
Tue 27-Feb (D) Lec12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms (slides) (Notes from previous years)
Thu 1-Mar (D) Lec13: Linear Programming I: Basics (slides) (Notes from previous years) [Ch 29/Ch 7.1,7.6] Q6
Fri 2-Mar Rec7: zero-sum games and LPs (worksheet) (solutions)
Tue 6-Mar (D) Lec14: Linear Programming II: Simplex, Seidel's 2D algorithm (slides) (Notes from previous years) H4 orals [T-F]
Thu 8-Mar (D) Lec15: Linear Programming III: Duality (slides) (Notes from previous years) Q7
Fri 9-Mar Mid-semester Break (worksheet) (solutions)
Tue 13-18 Spring Break
Tue 20-Mar (A) Lec16: NP-completeness (notes) [Ch 34/Ch 8] H5 out, Solutions
Thu 22-Mar (A) Lec17: Approximation Algorithms. (notes) [Ch 35/Ch 9.2] Q8
Fri 23-Mar Rec8: NP-comp and approx (worksheet) (sols)
Tue 27-Mar (A) Lec18: Online Algorithms. (notes)
Thu 29-Mar (A) Lec19: The Multiplicative Weights Algorithm (notes) Q9
Fri 30-Mar Rec9: Approx and Online Algorithms and exam prep. (worksheet) (sols)
Tue 3-Apr (A) Lec20: The Gradient Descent Framework (notes) H5 due
Thu 5-Apr Midterm Exam
Fri 6-Apr Rec10: MW and GD (worksheet) (sols) H6 out, Sols
Tue 10-Apr (A) Lec21: Game Theory II: Auctions, VCG Mechanism, and other Mechanisms (notes)
Thu 12-Apr (A) Lec22: Game Theory III and Matching II: Matching Markets and a Pricing Algorithm (notes) Q10
Fri 13-Apr Rec11: Game theory (worksheet) (sols)
Tue 17-Apr (D) Lec23: Graph Compression (slides) (notes) H6in, H7 out
Thu 19-Apr Carnival
Fri 20-Apr Carnival
Tue 24-Apr (D) Lec24: Sketching I (slides) (notes)
Thu 26-Apr (D) Lec25: Sketching II - Graph Sketching (slides) (notes) Q11
Fri 27-Apr Rec12:Graph Compression and Sketching ( worksheet ) (solutions)
Tue 1-May (A/D) Lec26: The Algorithmic Magic of Polynomials (notes) H7 orals [T-F], Sols
Thu 3-May (A/D) Lec27: Recap and Review (notes) Q12
Fri 4-May Rec13: Course recap
Mon 7 May Final: 8:30-11:30am, Mcconomy (CMU Hub)

Course Calendar