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 |
Jan 11 |
(D) |
Lec 1: Intro &
Linear-time Selection
(randomized and deterministic); recursion
trees. (notes,
video) |
[Ch 9/Ch 2.4]
|
|
| Tue |
Jan 12 |
|
Reci 1: Asymptotic analysis,
solving recurrences. (notes) (worksheet) |
[Ch 3-4/Ch 0,2.2]
|
|
| Wed |
Jan 13 |
(A) |
Lec 2: Concrete Models, Upper/Lower Bounds
(notes)
(video)
|
[Ch 8.1/Ch 2.3]
|
H1 out |
| Thu |
Jan 14 |
|
|
|
Q1 due midnight |
| Mon |
Jan 18 |
|
MLK Day Holiday! |
|
|
| Tue |
Jan 19 |
|
Reci 2: Lower/upper bounds, probability (wksheet) |
[Ch 5/]
|
|
| Wed |
Jan 20 |
(D) |
Lec 3: Amortized Analysis I: A simple amortized dictionary data
structure (notes)
Formal Potential Functions
(notes)
(video)
|
[Ch 17/-]
|
|
| Mon |
Jan 25 |
(D) |
Lec 4: Amortized Analysis II: Splay trees
(notes)
|
|
Q2 |
| Tue |
Jan 26 |
|
Reci 3: Amortized analysis (wksheet) |
|
|
| Wed |
Jan 27 |
(A) |
Lec 5: Union-find (with appendix on MSTs).
(notes)
|
[Ch 21/5.1.3,5.1.4]
|
H1 soln, H2 out |
| Mon |
Feb 1 |
(A) |
Lec 6: Hashing: Universal and Perfect Hashing
(notes)
|
[Ch 11/Ch 1.5]
|
Q3 |
| Tue |
Feb 2 |
|
Reci 4: Hashing and Basic Probability
(wksheet)
|
[Ch 5/Ch 1.5]
|
|
| Wed |
Feb 3 |
(A) |
Lec 7: Algorithms for Big Data: Streaming Algorithms
(notes)
|
|
|
| Mon |
Feb 8 |
(A) |
Lec 8: Fingerprinting and Substring Searches
(notes)
|
|
Q4 |
| Tue |
Feb 9 |
|
Reci 5: Hashing and Streaming
(wksheet)
|
|
H2 soln |
| Wed |
Feb 10 |
(D) |
Lec 9: Dynamic Programming I
(notes)
|
[Ch 15, 24.1, 25.1-25.2/Ch 6]
|
|
| Mon |
Feb 15 |
(D) |
Lec 10: Quarterly Exam + Dynamic Programming II: shortest paths (Bellman-Ford, matrix, Floyd-Warshall)
(notes)
|
|
|
| Tue |
Feb 16 |
|
Reci 6: Dynamic Programming
(wksheet)
|
|
H3 out |
| Wed |
Feb 17 |
(A) |
Lec 11: Game Theory I: Minimax Optimality, and Connections to Algorithms
(notes)
|
[-/Ch 7.5]
|
|
| Mon |
Feb 22 |
(D) |
Lec 12: Network Flows I
(notes)
|
[Ch 26/7.2-7.3]
|
Q5 |
| Tue |
Feb 23 |
|
Reci 7: Flows, Zero-sum games
(wksheet)
|
|
|
| Wed |
Feb 24 |
(D) |
Lec 13: Network Flows II: Edmonds-Karp 1/2, blocking flows,
min-cost flows
(notes)
|
|
H3 soln |
| Mon |
Feb 29 |
|
Midterm |
|
|
| Tue |
Mar 1 |
|
Reci 8: Flows
(worksheet)
|
|
|
| Wed |
Mar 2 |
(D) |
Lec 14: Linear Programming I: basics
(notes)
|
[Ch 29/Ch 7.1,7.6]
|
H4 out |
|
|
|
|
|
|
|
Mar 7-12 |
|
Spring Break Holiday!!! |
|
|
|
|
|
|
|
|
| Mon |
Mar 14 |
(A) |
Lec 15: Linear Programming II: Recap, Seidel's algorithm
(notes, 2D-LP)
|
[Ch 29/Ch 7.4]
|
Q6 |
| Tue |
Mar 15 |
|
Reci 9: Linear Programming
(worksheet)
|
|
|
| Wed |
Mar 16 |
(A) |
Lec 16: Linear Programming III: Duality
(notes combined with Lec15,
notes v2.0 with revised duality intuition)
|
|
H4 sol, H5 out |
| Mon |
Mar 21 |
(A) |
Lec 17: Linear Programming IV (and Machine Learning I): The
Perceptron Algorithm
(notes)
|
|
Q7 |
| Tue |
Mar 22 |
|
Reci 10: LPs and perceptron
(worksheet)
|
|
|
| Wed |
Mar 23 |
(A) |
Lec 18: NP Completeness
(notes)
|
[Ch 34/Ch 8]
|
|
| Mon |
Mar 28 |
(A) |
Lec 19: Approximation Algorithms
(notes)
|
[Ch 35/Ch 9.2]
|
Q8 |
| Tue |
Mar 29 |
|
Reci 11: NP-completeness and Approximations
(worksheet)
|
|
H5 sols (partial) |
| Wed |
Mar 30 |
(A) |
Lec 20: Machine Learning II: The Multiplicative Weights Framework
(notes, old slides, survey).
|
|
|
| Mon |
Apr 4 |
(A) |
Lec 21: Quarterly Exam + Game Theory
II: Auctions and
the VCG Mechanism
(notes).
|
|
|
| Tue |
Apr 5 |
|
Reci 12: MW and Auction Mechanisms and VCG
(worksheet)
|
|
H6 out |
| Wed |
Apr 6 |
(A) |
Lec 22: Game Theory III: Matching Markets and a Pricing
Algorithm. (notes).
|
|
|
| Mon |
Apr 11 |
(D) |
Lec 23: Online Algorithms
(notes)
|
|
Q9 |
| Tue |
Apr 12 |
|
Reci 13: Matching Markets, Online Algorithms
(worksheet)
|
|
|
| Wed |
Apr 13 |
(D) |
Lec 24: Computational Geometry I: Intro and Convex Hull
(notes)
|
[Ch 33/-]
|
H6 sols |
|
|
|
Carnival!!! |
|
|
| Mon |
Apr 18 |
(D) |
Lec 25: Computational Geometry II: Closest Pairs
(notes)
|
[Ch 33/-]
|
H7 out
|
| Tue |
Apr 19 |
|
Reci 14: CG. (worksheet)
|
|
|
| Wed |
Apr 20 |
(D) |
Lec 26: Computational Geometry III: Sweepline Algorithms
(notes)
|
[Ch 33/-]
|
|
| Mon |
Apr 25 |
(D) |
Lec 27: Point Location Data Structures
(notes)
|
|
Q10 |
| Tue |
Apr 26 |
|
Reci 15: Comp.geom.
(worksheet) |
|
H7 sols |
| Wed |
Apr 27 |
(A) |
Lec 28: The Power of Polynomials
(notes), and Course Summary
|
[-/Ch 2.6.1]
|
|
| Thu |
May 5 |
|
Final: 8:30-11:30am, location
4401 (SV B23 room 211) (CMU Hub) |
|
|