• 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: Tanvi Bajpai, Ainesh Bakshi, Weimiao (Millie) Chen, Yinglan Chen, Julia Hou, Rajesh Jayaram, Yijin Kang, Sheng Xu, Taisuke Yasuda, Shalom Yiblet, Stephanie You.

  • Recitations (all on Friday)
    • A: 9:30 (BH 237B): Rajesh Jayaram
    • B: 10:30 (BH 237B): Stephanie You
    • C: 11:30 (BH 237B): Julia Hou and Taisuke Yasuda
    • D: 12:30 (BH 237B): Tanvi Bajpai
    • E: 1:30 (WeH 5409): Ainesh Bakshi
    • F: 2:30 (WeH 5421): Shalom Yiblet
    • G: 3:30 (WeH 5421): Yinglan Chen and Sheng Xu
    • H: 4:30 (DH 1211): Yijin Kang

  • Office Hours: (subject to revisions in the calendar at the bottom of the page. Please check!)
    • Anupam Gupta: Monday 5-6pm, GHC 7203
    • Taisuke Yasuda: Monday 6-7:30pm, GHC 7501
    • Stephanie You: Monday 7:30-9pm, GHC 7501
    • David Woodruff: Tuesday 4-5pm, GHC 7217
    • Tanvi Bajpai and Yijin Kang: Tuesday 6-7:30pm, GHC 7501
    • Rajesh Jayaram: Wednesday 6-7:30pm, GHC 7501
    • Shalom Yiblet: Wednesday 7:30-9pm, GHC 7501
    • Ainesh Bakshi: Thursday 6:30-8pm GHC 6501
    • Sheng Xu: Thursday 7:30-9pm, GHC 6501
    • Julia Hou: Friday 4:30-6pm, GHC 4215
    • Weimiao (Millie) Chen: Saturday 4-5:30pm, Wean 4220 (except Apr 27, which is NSH 3001)
    • Tanvi Bajpai (Conceptual OH): Sunday 11:30-1pm, GHC 4215
    • Yinglan Chen: Sunday 2-3:30pm, GHC 4215

  • 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: MNP78G) for written HWs and autolab for programming HWs.
    • Course Policies


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 15-Jan (D) Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. slides, notes from previous year, handout on recurrences, video [Ch 9/Ch 2.4]
Thu 17-Jan (D) Lec2: Concrete models and tight upper/lower bounds. slides, updated notes, video, comic 1, comic 2 [Ch 8.1/Ch 2.3] Q1
Fri 18-Jan Rec1: big-O, recurrences, probability, and concrete models worksheet, solutions H1 out (and prog.tips), H1 Sols
Tue 22-Jan (A) Lec3: Amortized Analysis I: A simple amortized dictionary data structure. (notes, video) [Ch 17/-]
Thu 24-Jan (A) Lec4: Amortized Analysis II: Union-find (with appendix on MSTs). (notes, video) [Ch 21/5.1.3,5.1.4] Q2
Fri 25-Jan Rec2: Amortized Analysis (worksheet) (solutions) Bonus out
Tue 29-Jan (D) Lec5: Hashing I: Universal and Perfect Hashing. slides, notes from previous year, video [Ch 11/Ch 1.5] H1 due (on 1/30), H2 out, H2 Sols
Thu 31-Jan CMU classes canceled Q3
Fri 1-Feb Rec3: UF and Hashing (worksheet, solutions)
Tue 5-Feb (D) Lec6: Hashing II: Streaming Algorithms slides, notes from previous year, video [H2 orals (T-F)]
Thu 7-Feb (D) Lec7: Hashing III: Fingerprinting and other applications slides, notes from previous year, video Q4
Fri 8-Feb Rec4: Streaming, Fingerprinting worksheet (solutions)
Tue 12-Feb (A) Lec8: Dynamic Programming I (notes, video) H3 out
Thu 14-Feb (A) 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] Q5
Fri 15-Feb Rec5: DPs, Shortest paths (worksheet, solutions)
Tue 19-Feb Midterm Exam
Thu 21-Feb (A) Lec10: Network Flows I: Flows and Matchings (notes, video) Q6
Fri 22-Feb Rec6: flows and matchings H3 - deadline extended to Monday, 2/25. H4 out
Tue 26-Feb (A) Lec11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows (notes, video) [Ch 26/7.2-7.3]
Thu 28-Feb (D) Lec12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms video
Thu 28-Feb (D) Lec13: Linear Programming I: Basics [Ch 29/Ch 7.1,7.6] Q7
Fri 1-Mar Rec7: zero-sum games and LPs
Tue 5-Mar (D) Lec14: Linear Programming II: Simplex, Seidel's 2D algorithm H4 orals [M-Th]
Thu 7-Mar (D) Lec15: Linear Programming III: Duality Q8
Fri 8-Mar Mid-semester Break H5 out
Tue 11-17 Spring Break
Tue 19-Mar (A) Lec16: NP-completeness [Ch 34/Ch 8]
Thu 21-Mar (A) Lec17: Approximation Algorithms. [Ch 35/Ch 9.2] Q9
Fri 22-Mar Rec8: NP-comp and approx
Tue 26-Mar (A) Lec18: Online Algorithms. H5 due, H6 out
Thu 28-Mar (A) Lec19: The Multiplicative Weights Algorithm
Fri 29-Mar Rec9: Approx and Online Algorithms and exam prep.
Tue 2-Apr Midterm Exam
Thu 4-Apr (A) Lec20: The Gradient Descent Framework Q10
Fri 5-Apr Rec10: MW and GD
Tue 9-Apr (D) Lec21: Graph Compression H6 in, H7 out
Thu 11-Apr Carnival
Fri 12-Apr Carnival
Tue 16-Apr (D) Lec22: Sketching I
Thu 18-Apr (D) Lec23: Sketching II - Graph Sketching Q11
Fri 19-Apr Rec11: Graph Compression and Sketching
Tue 23-Apr (A) Lec24: Game Theory II: Auctions, VCG Mechanism, and other Mechanisms H7 orals [T-F]
Thu 25-Apr (A) Lec25: Game Theory III and Matching II: Matching Markets and a Pricing Algorithm Q12
Fri 26-Apr Rec12: Game theory
Tue 30-Apr (A) Lec26: The Algorithmic Magic of Polynomials
Thu 2-May (A/D) Lec27: Recap and Review Q13
Fri 3-May Rec13: Course recap

Course Calendar