| Date |
Title |
Topics |
Reading |
|
|
|
|
|
| 9/4 |
Intro, Big-O, RAM model |
Course overview, Asymptotic notation, RAM model
slides
|
CLRS 4th or 3rd: Chapters 1–3
|
| |
|
|
|
| |
|
Graph algorithms |
|
| 9/8 |
Minimum spanning trees I |
Minimum spanning tree problem, Kruskal's algorithm, Prim's algorithm
|
KT: Section 4.5 or CLRS 4th: Chapter 21 or CLRS 3rd: Chapter 23
|
| 9/11 |
Minimum spanning trees II |
Kruskal's algorithm, Prim's algorithm
slides
|
KT: 4.6 or CLRS 4th: Sections 19.1–19.3 or CLRS 3rd: Sections 21.1–21.3
|
|
|
|
|
| 9/15 |
Union-Find I
|
Dynamic connectivity problem, Union-Find
slides
|
|
| 9/18 |
Union-Find II
Shortest paths I |
Weighted Quick-Union, Path compression
Single-source shortest paths problem: slides
|
CLRS 4th: Chapter 22 (everything except for Section 22.4)
or CLRS 3rd: Chapter 24 (everything except for Section 24.4)
|
| 9/22 |
Shortest paths II |
Single-source shortest paths problem, DFS-based solution, Dijkstra's algorithm
slides
|
|
| 9/25 |
Shortest paths III |
Dijkstra's algorithm, BFS solution
Bellman-Ford algorithm
slides
|
|
| |
|
|
|
| 9/29 |
Shortest paths IV
Network flows I |
All-pairs shortest paths problem, Floyd-Warshall algorithm
Flow networks
|
KT: Sections 7.1-7.2
|
| 10/2 |
Network flows II |
Max-Flow problem, Min-Cut problem, Residual graph
|
|
| 10/6 |
Network flows III |
Augmenting paths, Ford-Fulkerson algorithm
Analysis of Ford-Fulkerson algorithm
slides
|
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)
|
|
|
Midterm - Thursday, October 9th
|
|
| 10/13 |
NO CLASS |
Thanksgiving
|
|
| 10/16 |
Network flows IV
|
Analysis of Ford-Fulkerson algorithm continued
Max-Flow Min-Cut Theorem,
Edmonds-Karp
|
|
| 10/20 |
Network flows V |
Edmonds-Karp
|
|
| |
|
Randomized Algorithms |
|
| 10/23 |
Selecting the kth smallest element
|
Quickselect with median of medians pivot:
slides
|
• CLRS 4th or 3rd: Section 9.3
• Avrim Blum's notes: Section 4.3
|
| 10/27 |
Randomized Quickselect and Quicksort |
Basic probability:
slides
Randomized Quickselect and Quicksort:
slides
|
• Luca
Trevisan's notes: Sections 1 and 2 (Basic probability)
• Randomized analysis handout
• KT: Section 13.5
or
CLRS 4th or 3rd: Chapter 7
|
| 10/30 |
Randomized Quickselect and Quicksort
|
Randomized Quickselect (continued) and Randomized Quicksort
|
|
| 11/3 |
Randomized Quicksort
Hashing I
|
Randomized Quicksort (continued)
Direct-address tables, Hash tables
|
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)
|
| 11/6 |
Hashing II |
Average-case analysis, Universal hashing, Open addressing: slides
|
|
| 11/10 |
NO CLASS |
Reading break
|
|
| |
|
Algorithms |
|
| 11/13 |
Dynamic programming
|
Weighted interval scheduling, Knapsack
|
KT: Sections 6.1-6.4
CLRS 4th: Section 14.4
or CLRS 3rd: Section 15.4
|
| 11/17 |
Amortized Analysis I |
Aggregate analysis, Accounting method
Accounting method (Dynamic tables)
|
CLRS 4th: Chapter 16
or CLRS 3rd: Chapter 17
|
| 11/20 |
Amortized Analysis II
String search I |
Accounting method (Dynamic tables)
Substring search problem, Rabin-Karp algorithm
|
CLRS 4th: Chapter 32 (32.4 and 32.5 are optional)
or CLRS 3rd: Chapter 32 (32.4 is optional)
|
| 11/24 |
String search II
|
Knuth-Morris-Pratt algorithm
|
|
| 11/27 |
Greedy algorithms |
Interval scheduling, Interval partitioning, Scheduling to minimize lateness
|
KT: Sections 4.1-4.3 (but 4.3 is optional)
|
| 12/1 |
Slack |
|
|