• 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 (D) Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees. (notes) (handout on recurrences) [Ch 9/Ch 2.4]
Thu 19-Jan (D) 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 (worksheet) (solution) H1 out
Tue 24-Jan (D) Lec3: Amortized Analysis I: Binary Counters, Growing and Shrinking a Table (notes) [Ch 17/-]
Thu 26-Jan (D) Lec4: Amortized Analysis II: Splay Trees (notes) Q2
Fri 27-Jan Rec2: Amortized Analysis (worksheet) (solution)
Tue 31-Jan (A) Lec5: Amortized Analysis III: Union-find (with appendix on MSTs). (notes) [Ch 21/5.1.3,5.1.4] H1 sol, H2 out
Thu 2-Feb (A) Lec6: Hashing I: Universal and Perfect Hashing. (notes) [Ch 11/Ch 1.5] Q3
Fri 3-Feb Rec3: UF and Hashing (worksheet) (solution)
Tue 7-Feb (A) Lec7: Hashing II: Streaming Algorithms (notes) H2 sols
(signup sheet)
Thu 9-Feb (A) Lec8: Hashing III: Fingerprinting and other applications (notes) Q4
Fri 10-Feb Rec4: Streaming and Fingerprinting (worksheet) (solution) H3 out
Tue 14-Feb (A) Lec9: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms (notes)
Thu 16-Feb Midterm Exam
Fri 17-Feb Rec5: zero-sum games (worksheet) (solutions)
Tue 21-Feb (D) Lec10: Dynamic Programming I: (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6]
Thu 23-Feb (D) Lec11: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall), and TSP (subset DP). (notes) H3 sol
Fri 24-Feb Rec6: DPs and shortest paths (worksheet) (solution) H4 out, Q5
Tue 28-Feb (D) Lec12: Network Flows I: Flows and Matchings (notes) [Ch 26/7.2-7.3]
Thu 2-Mar (D) Lec13: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Dinic's Alg and Blocking Flows (notes) Q6
Fri 3-Mar Rec7: flows (worksheet) (sols)
Tue 7-Mar (D) Lec14: Linear Programming I: Basics (notes) [Ch 29/Ch 7.1,7.6] H4 orals [7-10 Mar](signup sheet)
Thu 9-Mar (A) Lec15: Linear Programming II: Simplex, Seidel's 2D algorithm? (notes) H4 sol,H5 out, Q7
Fri 10-Mar Mid-semester Break
13-18 Spring Break
Tue 21-Mar (A) Lec16: Linear Programming III: Duality (notes)
Thu 23-Mar (A) Lec17: NP-completeness (notes) Q8
Fri 24-Mar Rec8: LPs, NP-comp and test prep (worksheet) (sols)
Tue 28-Mar (A) Lec18: Approximation Algorithms. (notes) [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 (A) Lec19: Game Theory II: Auctions, VCG Mechanism, and other Mechanisms
Thu 6-Apr (A) Lec20: Game Theory III and Matching II: Matching Markets and a Pricing Algorithm Q9
Fri 7-Apr Rec10: Auctions, Matching markets
Tue 11-Apr (D) Lec21: Powerful Arrays: SegTrees and Fenwick Trees
Thu 13-Apr (D) Lec22: Online Algorithms. Q10
Fri 14-Apr Rec11: seg trees and online
Tue 18-Apr (A) Lec23: The Multiplicative Weights Algorithm H6 due, H7 out
Thu 20-Apr Carnival
Fri 21-Apr Carnival
Tue 25-Apr (D) Lec24: Computational Geometry I --- Intro and Convex Hull
Thu 27-Apr (D) Lec25: Computational Geometry II --- Sweepline algorithms Q11
Fri 28-Apr Rec12: MW, comp.geom.
Tue 2-May (A) Lec26: High-Dimensional 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
Tue May 9 Final: 5:30-8:30pm, location TBD (CMU Hub)

Course Calendar