• Lectures: Tue/Thu 12:00-1:20, GHC 4401 (Rashid Auditorium)
    • Instructors: Anupam Gupta (anupamg@cs, GHC 7203), Danny Sleator (sleator@cs, GHC 8113)
    • TAs: Dominick Direnzo, Kelly Yang, Matthew Lee, Preeti Gondi, Raymond Kang, William Xiao, Yihan Sun

  • Recitations (all on Friday)
    • A: 9:30 (DH 1211): Raymond Kang
    • B: 10:30 (DH 1211): Preeti Gondi
    • C: 11:30 (DH 1211): Matthew Lee
    • D: 12:30 (DH 1211): William Xiao
    • E: 1:30 (DH 1217): Dominick Direnzo

  • 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).
    • 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 17-Jan (A) Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. (notes) (handout on recurrences) [Ch 9/Ch 2.4]
Thu 19-Jan (A) Lec2: Concrete models and tight upper/lower bounds. (notes) [Ch 8.1/Ch 2.3] Q1 due 11:59pm
Fri 20-Jan Rec1: big-O, recurrences, probability and concrete models H1 out
Tue 24-Jan (D) Lec3: Amortized Analysis I: A simple amortized dictionary data structure. [Ch 17/-]
Thu 26-Jan (D) Lec4: Amortized Analysis II: Splay Trees Q2
Fri 27-Jan Rec2: Amortized Analysis
Tue 31-Jan (D) Lec5: Amortized Analysis III: Union-find (with appendix on MSTs). [Ch 21/5.1.3,5.1.4] H1 due, H2 out
Thu 2-Feb (A) Lec6: Hashing I: Universal and Perfect Hashing. [Ch 11/Ch 1.5] Q3
Fri 3-Feb Rec3: UF and Hashing
Tue 7-Feb (A) Lec7: Hashing II: Streaming Algorithms H2 orals [7-10Feb]
Thu 9-Feb (A) Lec8: Hashing III: Fingerprinting and other applications Q4
Fri 10-Feb Rec4: Streaming and Fingerprinting H3 out
Tue 14-Feb (A) Lec9: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms
Thu 16-Feb Midterm Exam
Fri 17-Feb Rec5: DPs
Tue 21-Feb (D) Lec10: Dynamic Programming I: [Ch 15, 24.1, 25.1-25.2/Ch 6]
Wed 22-Feb
Thu 23-Feb (D) Lec11: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall) H3 due, H4 out, Q5
Fri 24-Feb Rec6: shortest paths and zero-sum games
Tue 28-Feb (D) Lec12: Network Flows I: Flows and Matchings [Ch 26/7.2-7.3]
Thu 2-Mar (D) Lec13: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows Q6
Fri 3-Mar Rec7: flows
Tue 7-Mar (D) Lec14: Linear Programming I: Basics [Ch 29/Ch 7.1,7.6] H4 orals [7-10 Mar]
Thu 9-Mar (A) Lec15: Linear Programming II: Simplex, Seidel's 2D algorithm? H5 out, Q7
Fri 10-Mar Mid-semester Break
13-18 Spring Break
Tue 21-Mar (A) Lec16: Linear Programming III: Duality
Thu 23-Mar (A) Lec17: NP-completeness Q8
Fri 24-Mar Rec8: NP-comp and test prep
Tue 28-Mar (A) Lec18: Approximation Algorithms. [Ch 35/Ch 9.2] H5 due
Thu 30-Mar Midterm Exam
Fri 31-Mar Rec9: NP-comp and Approx H6 out
Tue 4-Apr (D) Lec19: Powerful Arrays: SegTrees and Fenwick Trees
Thu 6-Apr (D) Lec20: Online Algorithms. Q9
Fri 7-Apr Rec10: seg trees and online
Tue 11-Apr (D) Lec21: Computational Geometry I --- Intro and Convex Hull
Thu 13-Apr (D) Lec22: Computational Geometry II --- Sweepline algorithms Q10
Fri 14-Apr Rec11: CG
Tue 18-Apr (A) Lec23: The Multiplicative Weights Algorithm H6 due, H7 out
Thu 20-Apr Carnival
Fri 21-Apr Carnival
Tue 25-Apr (A) Lec24: Game Theory II: Auctions, VCG Mechanism, and other Mechanisms
Thu 27-Apr (A) Lec25: Game Theory III and Matching II: Matching Markets and a Pricing Algorithm Q11
Fri 28-Apr Rec12: MW, Auctions, Matching markets
Tue 2-May (A) Lec26: Dimension-free Optimization: Gradient Descent H7 orals [1-4 May]
Thu 4-May (A) Lec27: The Power of Polynomials (e.g., Matching), and Course Wrapup Q12
Fri 5-May Rec13: Course recap

Course Calendar