• 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, H1 out
Mon Sep 7 Labor Day Holiday!
Tue Sep 8 Reci 2: Lower/upper bounds, probability (handout) [Ch 5/]
Wed Sep 9 (B) Lec 3: Amortized Analysis and a simple amortized dictionary data structure (notes) [Ch 17/-]
Mon Sep 14 (B) Lec 4: Union-find (with appendix on MSTs). (notes) [Ch 21/5.1.3,5.1.4] Q2
Tue Sep 15 Reci 3: Amortized analysis (handout)
Wed Sep 16 (B) Lec 5: Hashing: Universal and Perfect Hashing (notes) [Ch 11/Ch 1.5] H1 soln, H2 out
Mon Sep 21 (G) Lec 6: Algorithms for Big Data: Streaming Algorithms (notes) Q3
Tue Sep 22 Reci 4: Hashing and Basic Probability (worksheet) [Ch 5/Ch 1.5]
Wed Sep 23 (G) Lec 7: Fingerprinting and Substring Searches (notes)
Mon Sep 28 (G) Lec 8: Quarterly Exam + Dynamic Programming I (notes) [Ch 15, 24.1, 25.1-25.2/Ch 6]
Tue Sep 29 Reci 5: Dynamic Programming (worksheet) H2 soln [T-R]
Wed Sep 30 (G) Lec 9: Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall) (notes) H3 out
Mon Oct 5 (G) Lec 10: Network Flows I (notes) [Ch 26/7.2-7.3] Q4
Tue Oct 6 Reci 6: Network Flows (worksheet)
Wed Oct 7 (G) Lec 11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows (notes)
Mon Oct 12 (B) Lec 12: Game Theory, Minimax Optimality, and Connections to Algorithms (notes, slides) Q5
Tue Oct 13 Reci 7: Flows, Zero-sum games (worksheet)
Wed Oct 14 (B) Lec 13: Linear Programming I: basics (notes) [-/Ch 7.5] H3 soln
Mon Oct 19 Midterm H4 out
Tue Oct 20 Reci 8: linear programming (worksheet)
Wed Oct 21 (B) Lec 14: Linear Programming II: Duality and Geometry (notes) [Ch 29/Ch 7.1,7.6]
Mon Oct 26 (B) Lec 15: Linear Programming III: Duality contd. (notes, more notes) [Ch 29/Ch 7.4] Q6
Tue Oct 27 Reci 9: Linear Programming (worksheet) H4 sols [T-R]
Wed Oct 28 (B) Lec 16: Linear Programming IV (and Machine Learning I): The Perceptron Algorithm (notes) H5 out
Mon Nov 02 (G) Lec 17: NP Completeness (notes) [Ch 34/Ch 8] Q7
Tue Nov 03 Reci 10: NP-completeness (worksheet)
Wed Nov 04 (G) Lec 18: Approximation Algorithms (notes) [Ch 35/Ch 9.2]
Mon Nov 09 (G) Lec 19: Online Algorithms I (notes) Q8
Tue Nov 10 Reci 11: Approximation and Online Algorithms, Review (worksheet)
Wed Nov 11 (B) Lec 20: Quarterly Exam + Online Algorithms II. (notes)
Thu Nov 12 H5 sols
Sun Nov 15 H6 out
Mon Nov 16 (B) Lec 21: Machine Learning II (notes) Q9
Tue Nov 17 Reci 12: Online Algorithms, Machine Learning (worksheet)
Wed Nov 18 (B) Lec 22: The Multiplicative Weights Framework (slides, some notes).
Mon Nov 23 (B) Lec 23: Auctions and the VCG Mechanism (notes). Q10
Tue Nov 24 Reci 13: No recitation, thanksgiving H6 sols
W Nov 25 Thanksgiving!! H7 out
Mon Nov 30 (G) Lec 24: Matching Markets and a Pricing Algorithm. (notes) Q11
Tue Dec 01 Reci 14: Auctions and Markets. (worksheet)
Wed Dec 02 (G) Lec 25: The Gradient Descent Framework. (notes)
Mon Dec 7 (B) Lec 26: Online Resource Allocation. (notes) Q12
Tue Dec 8 Reci 15: Gradient Descent and Online Allocation. (worksheet) H7 sols
Wed Dec 9 (B+G) Lec 27: The Power of Polynomials (notes), and Course Summary
Fri Dec 18 Final: 8:30-11:30am