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 |
|
|