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