• Lectures: Mon/Wed 10:30-11:50, GHC 4401 (Rashid Auditorium)
    • Instructors: Avrim Blum (avrim@cs, GHC 8111), Anupam Gupta (anupamg@cs, GHC 7203)
    • TAs: Aakash Patel, Aram Ebtekar, Greg Kownacki, Ivan Wang, Matt Dee, Naomi Rubin, Terence An

  • Recitations (all in WeH 4709):
    • A: Tue 9:30: Gregory Kownacki (gkownack@andrew)
    • B: Tue 10:30: Aram Ebtekar (aebtekar@andrew)
    • C: Tue 12:30: Terence An (terencea@andrew) and Ivan Wang (icw@andrew)
    • D: Tue 1:30: Matt Dee (medee@andrew)
    • E: Tue 3:30: Aakash Patel (avpatel@andrew) and Naomi Rubin (nhrubin@andrew)

  • 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/Quizzes
Mon Aug 31 (G) Lec 1: Intro & Linear-time Selection (randomized and deterministic); recursion trees. (notes) [Ch 9/Ch 2.4]
Tue Sep 1 Reci 1: Asymptotic analysis, solving recurrences. (notes) (worksheet) [Ch 3-4/Ch 0,2.2]
Wed Sep 2 (B) Lec 2: Concrete Models, Upper/Lower Bounds (notes) [Ch 8.1/Ch 2.3] Q1, HW1 out
Mon Sep 7 Labor Day Holiday!
Tue Sep 8 Reci 2: Lower/upper bounds, probability [Ch 5/]
Wed Sep 9 (B) Lec 3: Amortized Analysis and a simple amortized dictionary data structure [Ch 17/-]
Mon Sep 14 (B) Lec 4: Union-find (with appendix on MSTs). [Ch 21/5.1.3,5.1.4] Q2
Tue Sep 15 Reci 3: Amortized analysis
Wed Sep 16 (B) Lec 5: Hashing: Universal and Perfect Hashing [Ch 11/Ch 1.5] H1 due
Mon Sep 21 (G) Lec 6: Hashing, Fingerprinting, etc. Q3
Tue Sep 22 Reci 4: Hashing and Basic Probability [Ch 5/Ch 1.5]
Wed Sep 23 (G) Lec 7: Algorithms for Big Data: Streaming Algorithms
Mon Sep 28 (G) Lec 8: Quarterly Exam + Dynamic Programming I [Ch 15, 24.1, 25.1-25.2/Ch 6]
Tue Sep 29 Reci 5: Dynamic Programming H2 orals [T-R]
Wed Sep 30 (G) Lec 9: Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall)
Mon Oct 5 (G) Lec 10: Network Flows I [Ch 26/7.2-7.3] Q4
Tue Oct 6 Reci 6: Network Flows
Wed Oct 7 (G) Lec 11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows
Mon Oct 12 (B) Lec 12: Network Flows III: Applications Q5
Tue Oct 13 Reci 7: More Flows
Wed Oct 14 (B) Lec 13: Linear Programming 0: Game Theory and Zero-sum Games [-/Ch 7.5] HW3 due
Mon Oct 19 Midterm
Tue Oct 20 Reci 8: Game theory, Zero-sum Games
Wed Oct 21 (B) Lec 14: Linear Programming I: basics [Ch 29/Ch 7.1,7.6]
Mon Oct 26 (B) Lec 15: Linear Programming II: Duality [Ch 29/Ch 7.4] Q6
Tue Oct 27 Reci 9: Linear Programming H4 orals[T-R]
Wed Oct 28 (B) Lec 16: Linear Programming III: Perceptron and Applications
Mon Nov 02 (B) Lec 17: Machine Learning Q7
Tue Nov 03 Reci 10: Perceptron and Learning
Wed Nov 04 (G) Lec 18: NP Completeness [Ch 34/Ch 8]
Mon Nov 09 (G) Lec 19: Approximation Algorithms I [Ch 35/Ch 9.2] Q8
Tue Nov 10 Reci 11: NP Completeness and Approximation Algorithms
Wed Nov 11 (G) Lec 20: Quarterly Exam + Approximation Algorithms II. [Ch 35/Ch 9.2]
Thu Nov 12 H5 due
Mon Nov 16 (B) Lec 21: Online Algorithms Q9
Tue Nov 17 Reci 12: Approximations and Online Algorithms
Wed Nov 18 (B) Lec 22: The Multiplicative Weights Framework.
Mon Nov 23 (B) Lec 23: Auctions and the VCG Mechanism. Q10
Tue Nov 24 Reci 13: Auctions H6 due
W Nov 25 Thanksgiving!!
Mon Nov 30 (G) Lec 24: Market Equilibria. Q11
Tue Dec 01 Reci 14: Auctions and Markets.
Wed Dec 02 (G) Lec 25: The Gradient Descent Framework.
Mon Dec 7 (B) Lec 26: Singular Value Decompositions. Q12
Tue Dec 8 Reci 15: Gradient Descent and SVDs. HW7 orals[T-R]
Wed Dec 9 (G) Lec 27: TBD
Xxx Dec XX Final

Course Calendar