| 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
|
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
Network flows I
|
All-pairs shortest paths problem, Floyd-Warshall algorithm
Flow networks
|
KT: Sections 7.1-7.2
|
| 6/11 |
Network flows II |
Max-Flow problem, Min-Cut problem, Residual graph
|
|
|
|
Midterm 1 - Monday, June 15th
|
|
| 6/18 |
Network flows III |
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 IV
|
Analysis of Ford-Fulkerson algorithm continued
Max-Flow Min-Cut Theorem,
Edmonds-Karp
|
|
| 6/25 |
Network flows V |
Edmonds-Karp
|
|
| |
|
Randomized Algorithms |
|
| 6/29 |
Dynamic programming
(Guest lecture or recorded lecture)
|
Weighted interval scheduling, Knapsack
|
|
| 7/2 |
NO CLASS |
Reading break
|
|
| 7/6 |
Selecting the kth smallest element
|
Quickselect with median of medians pivot
|
|
| 7/9 |
Randomized Quickselect and Quicksort |
Basic probability
Randomized Quickselect and Quicksort
|
|
| 7/13 |
Randomized Quickselect and Quicksort
|
Randomized Quickselect (continued) and Randomized Quicksort
|
|
|
|
Midterm 2 - Thursday, July 16th
|
|
| 7/20 |
Randomized Quicksort
Hashing I
|
Randomized Quicksort (continued)
Direct-address tables, Hash tables
|
|
| 7/23 |
Hashing II |
Average-case analysis, Universal hashing, Open addressing
|
|
| |
|
Complexity |
|
| 7/27 |
Complexity / NP-Completeness I |
To Be Updated
|
|
| 7/30 |
Complexity / NP-Completeness II
|
To Be Updated
|
| — |
Extra material (will be moved):
Greedy algorithms
Longest common subsequence problem
|
Interval partitioning, Scheduling to minimize lateness
Longest common subsequence problem
|
|