• Lectures: Tue/Thu 12:00-1:20, DH 2315
    • Instructors: Danny Sleator (sleator@cs, GHC 8113), Carl Kingsford (carlk@cs, GHC 7719)
    • TAs: Ian J Chiu (ichiu@andrew), Dustin Liu (kaigel@andrew), George Lu (gclu@andrew), Stephen Clark (saclark@andrew), Uday Uppal (uuppal@andrew), Millie (Weimiao) Chen (weimiaoc@andrew), Pedro Miguel Reis Bento Paredes (preisben@cs)

  • Recitations (all on Friday)
    • A: 9:30 (PH 226A): Uday
    • B: 10:30 (WEH 5421): Ian
    • C: 11:30 (WEH 4709): Pedro
    • D: 12:30 (GHC 4211): Stephen
    • E: 1:30 (POS 146): Millie
    • F: 3:30 (GHC 4102): Dustin
    • G: 4:30 (GHC 4102): George

  • Office Hours: (subject to revisions in the calendar at the bottom of the page. Please check!)
    • Danny Sleator: Thursdays, 2:30-4:30pm, GHC 8113
    • Carl Kingsford: Wednesdays, 1:30-3pm, GHC 7719
    • Uday: Tue 6:30-8:30pm GHC 6002
    • Stephen: Tues 5-7pm GHC 6002
    • Ian: Wed 6-8pmi GHC 7101
    • George: Mon 4:30-6:30 NSH 1505
    • Dustin: Fri 4:30-6:30 GHC 6002
    • Millie: Sun 10am-noon GHC Citadel Commons

  • Other directions:


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 and Quizes
Tue Aug 28 (CD) Lec 1: Intro & Linear time selection (notes) (handout on recurrences) [Ch 9/Ch 2.4]
Thr Aug 30 (C) Lec 2: Concrete Models (notes) [Ch 8.1/Ch 2.3] Quiz 1: Linear selection, Concrete models
Fri Aug 31 Reci 1: Lower and Upper Bounds (worksheet) HW1 Out: Selection, Concrete, Big-O
Tue Sep 4 (D) Lec 3: Amortized Analysis 1 (notes) [Ch 17/-]
Thr Sep 6 (D) Lec 4: Amortized Analysis 2: Splay Trees (notes) (Splay tree demo) Quiz 2: Amortized analysis
Fri Sep 7 Reci 2: Amortized Analysis (worksheet)
Sat Sep 8 HW1 Due. HW2 Out: Amortized analysis, Hashing
Tue Sep 11 (C) Lec 5: Hashing 1: Universal Hashing (notes) [Ch 11/Ch 1.5]
Thr Sep 13 (C) Lec 6: Hashing 2: Streaming (Heavy Hitters) (notes) Quiz 3: Hashing
Fri Sep 14 Reci 3: Hashing and Probability Review (worksheet)
Tue Sep 18 (C) Lec 7: Hashing 3: Fingerprinting (notes) HW2 Orals W-F
Thr Sep 20 (D) Lec 8: Dynamic Programming I (notes) Quiz 4: Hashing + DP
Fri Sep 21 Reci 4: Streaming and Hashing (worksheet) HW3 Out: Hashing, Dynamic Programming
Tue Sep 25 (D) Lec 9: Dynamic Programming II (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6]
Thr Sep 27 (D) Lec 10: Network Flow I (notes) Quiz 5: DP + NF
Fri Sep 28 Reci 5: Dynamic Programming (worksheet) HW3 Due
Tue Oct 2 MIDTERM #1 (Selection, Concrete Models, Amortized, Hashing, DP)
Thr Oct 4 (D) Lec 11: Network Flow II (notes) [Ch 26/7.2-7.3]
Fri Oct 5 Reci 6: Network Flow (worksheet) HW4 Out: Network Flow, Game Theory
Tue Oct 9 (C) Lec 12: Game Theory (notes)
Thr Oct 11 (C) Lec 13: Linear Programming I (Basics) (notes) [Ch 26/7.2-7.3] Quiz 6: Network Flow + LP
Fri Oct 12 Reci 7: Linear Programming (worksheet)
Tue Oct 16 (C) Lec 14: Linear Programming II (Simplex & Seidel's) (notes and simplex) HW4 Orals: T-H
Thr Oct 18 (C) Lec 15: Linear Programming III Duality (notes) AND NP-completeness (slides) [Ch 26/7.2-7.3] Quiz 7: LP
Fri Oct 19 NO RECITATION - Mid-semester break
Tue Oct 23 (D) Lec 16: Online Algorithms (notes) HW5 Out: Linear Programming, Online
Thr Oct 25 (D) Lec 17: Multiplicative Weights (notes) Quiz 8: Online + MW
Fri Oct 26 NO RECITATION - President Inauguration Day(worksheet)
Tue Oct 30 (C) Lec 18: Approximation Algorithms (notes)
Thr Nov 1 (D) Lec 19: Depth-First-Search and Strong Components (notes) [Ch 26/7.2-7.3] Quiz 9: NP-completeness + approx
Fri Nov 2 Reci 8: Online Algs and Multiplicative Weights (worksheet) HW5 Due;
Tue Nov 6 MIDTERM #2 (Flow, Games, LP, NP, Approx, Online, Multiplicative Weights)
Thr Nov 8 (D) Lec 20: Powerful Arrays (SegTrees, Fenwick Trees) (notes) HW6 Out: Approx, DFS, Segtrees
Fri Nov 9 Reci 9: NP and Approximation algorithms (worksheet)
Tue Nov 13 (D) Lec 21: Computational Geometry I (Convex Hull) (notes)
Thr Nov 15 (C) Lec 22: Computational Geometry II (Sweepline) (notes) Quiz 10: Segtrees, Comp Geometry
Fri Nov 16 Reci 10: Computational Geometry (worksheet)
Tue Nov 20 (C) Lec 23: Computational Geometry III (Closest Pair) (notes) HW6 Due
Thr Nov 22 Thanksgiving - No Class
Fri Nov 23 Thanksgiving - No recitation
Tue Nov 27 (C) Lec 24: Suffix Trees and Arrays (notes) HW7 Out: Comp Geometry, Suffix Trees
Thr Nov 29 (C) Lec 25: BWT and compression (notes) Quiz 11: Comp Geo, Suffix Trees, BWT
Fri Nov 30 Reci 11: String algorithms (worksheet)
Tue Dec 4 (D) Lec 26: Suffix array construction (notes)
Thr Dec 6 (D) Lec 27: Fibonacci Heaps (notes) Quiz 12: Compression and fib heaps
Fri Dec 7 Reci 12: Final Review HW7 Orals W-F

Course Calendar