• Lectures: Tue/Thu 12:00-1:20, DH (Doherty Hall) 2315
    • Instructors: Carl Kingsford (carlk@cs, GHC 7719), Danny Sleator (sleator@cs, GHC 8113)
    • TAs: Naama Ben-David, Can Bostanci, Laurie Jin, Bryan Lee,
      George Lu, Matthew Savage, Ziyang Wang, Katrina Yang

  • Recitations (all on Friday)
    • A: 9:30 (WEH 5320): Naama Ben-David
    • B: 10:30 (DH 1117): Laurie Jin
    • C: 11:30 (GHC 4211): Can Bostanci
    • D: 12:30 (GHC 4211): Bryan Lee
    • E: 3:30 (WEH 5310): Matthew Savage
    • F: 4:30 (GHC 4102): George Lu

  • Office hours (subject to revisions in the calendar at the bottom of the page. Please check that.):
    • Danny Sleator: Friday 13:15-15:00, GHC 8113
    • Carl Kingsford: Wednesday 13:30-15:00, GHC 7719
    • Naama Ben-David: Thursday 15:30-17:00, Table 4 Citadel Commons (GHC 5th Floor)
    • Can Bostanci: Thursday 13:30-15:30, Table 1 Citadel Commons (GHC 5th Floor)
    • Laurie Jin: Tuesday 16:30-18:00, Table 1 Citadel Commons (GHC 5th Floor)
    • Bryan Lee: Thursday 17:00-18:30, Carrel 4 Citadel Commons (GHC 5th Floor)
    • George Lu: Friday 17:30-19:30, Carrel 4 Citadel Commons (GHC 5th Floor)
    • Matthew Savage: Monday 17:00-18:30, Carrel 4 Citadel Commons (GHC 5th Floor)
    • Ziyang Wang: Monday 13:00-14:30, Table 1 Citadel Commons (GHC 5th Floor)
    • Katrina Yang: Saturday 18:00-20:00, Carrel 4 Citadel Commons (GHC 5th Floor)

  • Other directions:
    • Ask/answer questions on Piazza
    • Use Gradescope to submit written homework solutions (use entry code M2RRXY if necessary)
    • Use Autolab to submit programming assignments (and check grades).
    • Use Moodle to do quizzes.
    • 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 Reading HWs
Tue Aug 29 (D) Lec 1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees (notes) (handout on recurrences) [Ch 9/Ch 2.4]
Thu Aug 31 (C) Lec 2: Concrete models and tight upper/lower bounds (notes) [Ch 8.1/Ch 2.3]
Fri Sep 1 Reci 1: Lower and Upper Bounds (worksheet + solutions) HW1 Out
Tue Sep 5 (D) Lec 3: Amortized Analysis I: Binary Counters, Growing and Shrinking a Table (notes) [Ch 17/-]
Thu Sep 7 (D) Lec 4: Amortized Analysis II: Splay Trees (notes) (Splay tree demo)
Fri Sep 8 Reci 2: Amortized analysis (worksheet, solutions) HW1 Due
Tue Sep 12 (D) Lec 5: Powerful Arrays: SegTrees and Fenwick Trees (notes) HW2 Out
Thu Sep 14 (C) Lec 6: Hashing I: Universal and Perfect Hashing (notes) [Ch 11/-]
Fri Sep 15 Reci 3: Hashing, Basic Probability, and SegTrees (worksheet, solution) [Ch 5/-]
Tue Sep 19 (C) Lec 7: Hashing II: Streaming Algorithms (heavy hitters) (notes)
Thu Sep 21 (C) Lec 8: Hashing III: Fingerprinting and other applications (notes) [Ch. 32.2]
Fri Sep 22 Reci 4: Streaming and hashing (worksheet, solutions) HW2 Due (solution)
Tue Sep 26 (C) Lec 9: Classic String Matching: Knuth-Morris-Pratt (KMP) and Boyer-Moore (notes) [Ch. 32] HW3 Out
Thu Sep 28 (C) Lec 10: Suffix trees and arrays (notes)
Fri Sep 29 Reci 5: Fingerprint Oracle and Computing Suffix Arrays (worksheet, solutions)
Tue Oct 3 Midterm #1
Thu Oct 5 (D) Lec 11: DFS and Strong Components (notes) [Ch 22.3,22.5 / Ch 3]
Fri Oct 6 Reci 6: Graph algorithms (worksheet, solutions)
Tue Oct 10 (D) Lec 12: Dynamic Programming I: (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6] HW3 Due (solution);
HW4 Out
Thu Oct 12 (D) Lec 13: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall), and TSP (subset DP) (notes)
Fri Oct 13 Reci 7: Dynamic programming (worksheet, solutions)
Tue Oct 17 (C) Lec 14: Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms (notes)
Thu Oct 19 (D) Lec 15: Network Flows I: Flows and Matchings (notes) [Ch 26/7.2-7.3]
Fri Oct 20 Midsem break; No recitation HW4 Due (solution)
Tue Oct 24 (D) Lec 16: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Dinic's Alg and Blocking Flows (notes) HW5 Out
Thu Oct 26 (C) Lec 17: Linear Programming I: Basics (notes) [Ch 29/Ch 7]
Fri Oct 27 Reci 8: Flows (worksheet, solutions)
Tue Oct 31 (C) Lec 18: Linear Programming II: Algorithms, e.g. Seidel's 2D algorithm (notes) (bonus optional material: Simplex Algorithm, Code) [Ch 29/Ch 7]
Thu Nov 2 (D) Lec 19: Linear Programming III: Duality (notes) [Ch 29.4]
Fri Nov 3 Reci 9: Linear programming (worksheet, solutions) HW5 Due 11/5(solution)
Tue Nov 7 Midterm #2
Thu Nov 9 (D) Lec 20: Computational Geometry I --- Intro and Convex Hull (notes) [Ch 33.1-33.3] HW6 Out
Fri Nov 10 CMU 50th Anniversery --- no recitation
Tue Nov 14 (C) Lec 21: Computational Geometry II --- Sweepline algorithms (notes)
Thu Nov 16 (C) Lec 22: Computational Geometry III --- Closest Pair (notes) [33.4]
Fri Nov 17 Reci 10: Computational Geometry (worksheet, solutions)
Tue Nov 21 (C) Lec 23: NP-completeness (notes) [Ch 34/Ch 8]
Wed Nov 22 HW6 Due
Thu Nov 23 Thanksgiving --- no class
Tue Nov 28 (C) Lec 24: Approximation Algorithms (notes) [Ch 35/Ch 9.2] HW7 Out
Thu Nov 30 (D) Lec 25: Online Algorithms (notes)
Fri Dec 1 Reci 11: NP-completeness (worksheet, solutions)
Tue Dec 5 (D) Lec 26: The Multiplicative Weights Algorithm (notes)
Thu Dec 7 (CD) Lec 27: Fibonacci Heaps (notes) HW7 Due
Fri Dec 8 Reci 12: Multiplicative Weights, and Review (worksheet, solutions)

Course Calendar