| Date |
Title |
Topics |
Reading (reading guide) |
|
|
|
|
|
| 5/11 |
Intro, Big-O, RAM model |
Course overview, Asymptotic notation, RAM model
slides
|
R: Chapters 1 and 2
or
CLRS 4th or 3rd: Chapters 1–3
|
| |
|
|
|
| |
|
Graph algorithms |
|
| 5/14 |
Minimum spanning trees I |
Minimum spanning tree problem, Prim's algorithm, Cut Property Theorem
|
KT: Section 4.5
or R: Chapter 15 (skip Sections 15.6 and 15.8)
or CLRS 4th: Chapter 21 or CLRS 3rd: Chapter 23
|
| 5/18 |
NO CLASS |
Victoria Day
|
|
| 5/21 |
Minimum spanning trees II |
Cut Property Theorem, Prim's algorithm, Kruskal's algorithm
slides (these don't cover correctness proofs)
|
|
|
|
|
|
| 5/25 |
Union-Find I
|
Dynamic connectivity problem, Union-Find
slides (mostly examples)
|
R: Section 15.6
or
KT: 4.6
or
CLRS 4th: Sections 19.1–19.3 or CLRS 3rd: Sections 21.1–21.3
|
| 5/28 |
Union-Find II
Shortest paths I |
Weighted Quick-Union, Path compression
Single-source shortest paths problem
slides (for both single-source and all-pairs shortest paths)
|
R: Chapter 9
or
CLRS 4th: Chapter 22 (everything except for Section 22.4)
or CLRS 3rd: Chapter 24 (everything except for Section 24.4)
|
| 6/1 |
Shortest paths II |
DFS-based solution for DAGs
|
|
| 6/4 |
Shortest paths III |
Dijkstra's algorithm, BFS solution for unweighted graphs
Bellman-Ford algorithm
|
R: Chapter 18
or CLRS 4th: Sections 23.1 and 23.2
or CLRS 3rd: Sections 25.1 and 25.2
|
| |
|
|
|
| 6/8 |
Shortest paths IV
|
All-pairs shortest paths problem, Floyd-Warshall algorithm
|
|
| 6/11 |
Network flows I |
Flow Networks, Max-Flow problem, Min-Cut problem
Residual graph
slides (from start to end of network flows)
|
KT: Sections 7.1-7.2
|
|
|
Midterm 1 - Monday, June 15th
|
|
| 6/18 |
Network flows II |
Augmenting paths, Ford-Fulkerson algorithm
Analysis of Ford-Fulkerson algorithm
|
CLRS 4th: Sections 24.1 - 24.2 (for analysis of Edmonds-Karp)
or CLRS 3rd: Sections 26.1 - 26.2 (for analysis of Edmonds-Karp)
|
| 6/22 |
Network flows III
|
Analysis of Ford-Fulkerson algorithm continued
Max-Flow Min-Cut Theorem,
Edmonds-Karp
|
|
| 6/25 |
Dynamic programming |
Weighted interval scheduling, Knapsack
slides
|
R: Chapter 16
or
KT: 6.1–6.2 and 6.4
|
| 6/29 |
No class - Nishant at a conference
|
|
|
| 7/2 |
NO CLASS |
Reading break
|
|
| 7/6 |
Selecting the kth smallest element
|
Quickselect with median of medians pivot
slides
|
Avrim Blum's notes: Sections 4.1 (stop before Theorem 4.1) and 4.3
or
CLRS 4th or 3rd: Sections 9.1 and 9.3
or
R: Section 6.1.1–6.1.4 and 6.3–6.4
|
| |
|
Randomized Algorithms |
|
| 7/9 |
Randomized Quickselect |
Basic probability
Randomized Quickselect
|
• Luca
Trevisan's notes: Sections 1 and 2 (Basic probability)
• Randomized analysis handout
|
| 7/13 |
Randomized Quicksort
|
Randomized Quicksort
|
|
|
|
Midterm 2 - Thursday, July 16th
|
|
| 7/20 |
Hashing I
|
Direct-address tables, Hash tables: slides
|
R: Chapter 12 (Sections 12.5 is recommended; 12.6 is optional)
or CLRS 4th: Chapter 11
(11.3.2–11.3.4 is recommended; 11.5.2 is optional)
or CLRS 3rd: Chapter 11
(11.3.3 is recommended; 11.5 is optional)
|
| |
|
Complexity |
|
| 7/23 |
Hashing II
Complexity I
|
Average-case analysis, Universal hashing, Open addressing
Computationally hard problems, Reductions: slides
|
R: Chapter 19
R: Chapter 22 (up to and including Section 22.5)
R: Chapter 23 (Sections 23.5 is optional)
|
| 7/27 |
Complexity II |
P, NP, and NP-Hardness
|
|
| 7/30 |
Complexity III
|
NP-Hardness, NP-Completeness
|
| — |
Extra material (will be moved):
Greedy algorithms
Longest common subsequence problem
|
Interval partitioning, Scheduling to minimize lateness
Longest common subsequence problem
|
|