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 |
|
| Tue |
15-Jan |
(D) |
Lec1: Intro & Admin. Linear-time Selection (randomized and deterministic); recursion trees.
slides,
notes from previous year,
handout on recurrences,
video
|
[Ch 9/Ch 2.4] |
|
| Thu |
17-Jan |
(D) |
Lec2: Concrete models and tight upper/lower bounds.
slides,
updated notes,
video,
comic 1,
comic 2
|
[Ch 8.1/Ch 2.3] |
Q1 |
| Fri |
18-Jan |
|
Rec1: big-O, recurrences, probability, and concrete models
worksheet,
solutions
|
|
H1 out
(and prog.tips), H1
Sols |
| Tue |
22-Jan |
(A) |
Lec3: Amortized Analysis I: A simple amortized dictionary data structure.
(notes, video)
|
[Ch 17/-] |
|
| Thu |
24-Jan |
(A) |
Lec4: Amortized Analysis II: Union-find (with appendix on MSTs).
(notes,
video)
|
[Ch 21/5.1.3,5.1.4] |
Q2 |
| Fri |
25-Jan |
|
Rec2: Amortized Analysis
(worksheet)
(solutions)
|
|
Bonus out |
| Tue |
29-Jan |
(D) |
Lec5: Hashing I: Universal and Perfect Hashing.
slides,
notes from previous year,
video
|
[Ch 11/Ch 1.5] |
H1 due (on 1/30), H2
out, H2 Sols |
| Thu
| 31-Jan
|
| CMU classes canceled
|
|
Q3 |
| Fri |
1-Feb |
|
Rec3: UF and Hashing
(worksheet,
solutions)
|
|
|
| Tue |
5-Feb |
(D) |
Lec6: Hashing II: Streaming Algorithms
slides,
notes from previous year,
video
|
|
[H2 orals (T-F)] |
| Thu |
7-Feb |
(D) |
Lec7: Hashing III: Fingerprinting and other applications
slides,
notes from previous year,
video
|
|
Q4 |
| Fri |
8-Feb |
|
Rec4: Streaming, Fingerprinting
worksheet
(solutions)
|
|
|
| Tue |
12-Feb |
(A) |
Lec8: Dynamic Programming I
(notes,
video)
|
|
H3 out , Solutions |
| Thu |
14-Feb |
(A) |
Lec9: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall)
(notes,
video)
|
[Ch 15, 24.1, 25.1-25.2/Ch 6] |
Q5 |
| Fri |
15-Feb |
|
Rec5: DPs, Shortest paths
(worksheet,
solutions)
|
|
|
| Tue |
19-Feb |
|
Midterm Exam |
|
|
| Thu |
21-Feb |
(A) |
Lec10: Network Flows I: Flows and Matchings
(notes,
video)
|
|
Q6 |
| Fri |
22-Feb |
|
Rec6: flows and matchings
(worksheet,
solutions)
|
|
H3 - deadline extended to Monday, 2/25. H4 out |
| Tue |
26-Feb |
(A) |
Lec11: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows
(notes,
video)
|
[Ch 26/7.2-7.3] |
H4 Solutions |
| Thu |
28-Feb |
(D) |
Lec12: Linear Programming 0 and Game Theory I: Zero-sum Games, Minimax Optimality, and Connections to Algorithms
slides,
notes,
video
|
|
Q7 |
| Fri |
1-Mar |
|
Rec7: flows and zero-sum games
worksheet,
partial solutions)
|
|
|
| Tue |
5-Mar |
(D) |
Lec13: Linear Programming I: Basics
slides,
notes,
video
|
[Ch 29/Ch 7.1,7.6] |
H4 orals [M-Th] |
| Thu |
7-Mar |
(D) |
Lec14: Linear Programming II: Simplex, Seidel's 2D algorithm
slides,
notes,
video,
previous year's recitation
|
|
Q8 |
| Fri |
8-Mar |
|
Mid-semester Break
|
|
H5 out, Solutions |
| Tue |
|
|
|
|
|
| Thu |
11-17 |
|
Spring Break |
|
|
| Fri |
|
|
|
|
|
| Tue |
19-Mar |
(D) |
Lec15: Linear Programming III: Duality
slides,
notes,
video
|
|
|
| Thu |
21-Mar |
(A) |
Lec16: NP-completeness
(notes, video)
|
[Ch 34/Ch 8] |
Q9 |
| Fri |
22-Mar |
|
Rec8: LPs and NP-comp
(worksheet)
(sols)
|
|
|
| Tue |
26-Mar |
(A) |
Lec17: Approximation Algorithms.
(notes, video)
|
[Ch 35/Ch 9.2] |
H5 due, H6 out, H6 sols
|
| Thu |
28-Mar |
(A) |
Lec18: Online Algorithms.
(notes, video)
|
|
|
| Fri |
29-Mar |
|
Rec9: Approx and Online Algorithms and exam prep.
(worksheet)
(sols)
|
|
|
| Tue |
2-Apr |
|
Midterm Exam |
|
|
| Thu |
4-Apr |
(A) |
Lec19: The Multiplicative Weights Algorithm
(notes, video)
| |
Q10 |
| Fri |
5-Apr |
|
Rec10: MW
(worksheet)
(sols)
|
|
|
| Tue |
9-Apr |
(A) |
Lec20: The Gradient Descent Framework
(notes, video) (worksheet)
|
|
H6 in, H7 out, solns
|
| Thu |
11-Apr |
|
Carnival |
|
|
| Fri |
12-Apr |
|
Carnival |
|
|
| Tue |
16-Apr |
(D) |
Lec21: Graph Compression
slides,
notes,
video
|
|
|
| Thu |
18-Apr |
(D) |
Lec22: Sketching and Nearest Neighbor Search
slides,
notes,
video
|
|
Q11 |
| Fri |
19-Apr |
|
Rec11: Graph Compression, Sketching, and Nearest Neighbor
worksheet,
sols
|
|
|
| Tue |
23-Apr |
(D) |
Lec23: Fast Algorithms for Linear Regression
slides,
notes (updated),
video
|
|
H7 orals [T-F]
|
| Thu |
25-Apr |
(A) |
Lec24: Linear Algebra review
notes,
video
|
|
Q12 |
| Fri |
26-Apr |
|
Rec12: CountSketch and Regression
worksheet
(solutions)
|
|
|
| Tue |
30-Apr |
(A) |
Lec25: Game Theory II: Auctions, VCG Mechanism, and other Mechanisms
(notes,
video)
|
|
bonus problem |
| Thu |
2-May |
(A/D) |
Lec26: The Algorithmic Magic of Polynomials, and Recap
(notes,
video)
review slides
|
|
Q13 |
| Fri |
3-May |
|
Rec13: VCG, polynomials and Course recap
worksheet
(solutions)
|
|
|
| Friday |
10 May |
|
Final: 5:30-8:30pm, DH 2210-DH 2315 (CMU Hub) |
|
|