Lecture: Tu/Th 9:30 am - 11:00 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Week | Date | Lecture | Reading | Section | Videos | Assignments |
---|---|---|---|---|---|---|
1 |
Tu 1/18 |
Introduction, big-O notation, arithmetic webcast |
DPV §0 , §1.1 | |||
Th 1/20 |
Divide-and-Conquer (Part I) webcast |
DPV §2.1 , §2.2 , §2.3 | ||||
2 |
Tu 1/25 |
Divide-and-Conquer (Part II) webcast |
DPV §2.4 , §2.5 , §2.6 |
|
||
Th 1/27 |
Fast Fourier Transform webcast |
DPV §2.6 | ||||
3 |
Tu 2/1 |
Decompositions of graphs |
DPV §3 |
|
||
Th 2/3 |
Paths in graphs (Part I) |
DPV §4.1 , §4.2 , §4.3 , §4.4 | ||||
4 |
Tu 2/8 |
Paths in graphs (Part II) Prof. Wright's notes |
DPV §4.4 , §4.5 , §4.6 , §4.7 |
|
||
Th 2/10 |
Greedy Algorithms Prof. Wright's notes |
DPV §5 , §5.4 | ||||
5 |
Tu 2/15 |
Minimum Spanning Trees Prof. Wright's notes |
DPV §5.1 |
|
||
Th 2/17 |
Union Find Prof. Wright's notes |
DPV §5.1.4 | ||||
6 |
Tu 2/22 |
Dynamic Programming (Part I) Prof. Wright's notes |
DPV §6 |
|
||
Th 2/24 |
Dynamic Programming (Part II) Prof. Wright's notes |
DPV §6 | ||||
7 |
Tu 3/1 |
Dynamic Programming (Part III) Prof. Wright's notes |
DPV §6 |
|
||
Th 3/3 |
Dynamic Programming (Part IV) Prof. Raghavendra's notes |
DPV §7.1 | ||||
8 |
Tu 3/8 |
Linear Programming Prof. Raghavendra's notes |
DPV §7.2 | |||
Th 3/10 |
Network Flow + Bipartite Matching Prof. Raghavendra's notes |
DPV §7.4 | ||||
9 |
Tu 3/15 |
Duality + Zero-Sum Games Prof. Raghavendra's notes |
DPV §7.5 | |||
Th 3/17 |
Multiplicative Updates Prof. Raghavendra's notes |
notes | ||||
10 |
Tu 3/22 |
Spring Break |
||||
Th 3/24 |
Spring Break |
|||||
11 |
Tu 3/29 |
Reductions, Bipartite Matching Prof. Raghavendra's notes |
DPV §7.3 | |||
Th 3/31 |
Search Problems Prof. Raghavendra's notes |
DPV §8.1 | ||||
12 |
Tu 4/5 |
Midterm 2 |
||||
Th 4/7 |
NP-Completeness Prof. Raghavendra's notes |
DPV §8.2 , §8.3 | ||||
13 |
Tu 4/12 |
Coping with NP-completeness Prof. Raghavendra's notes |
DPV §9 |
|
||
Th 4/14 |
Streaming Prof. Raghavendra's notes |
DPV §1.2 , §1.3 notes | ||||
14 |
Tu 4/19 |
Sketching, Streaming Prof. Wright's notes |
DPV §1.5 |
|
||
Th 4/21 |
Cancelled |
|||||
15 |
Tu 4/26 |
Randomized Algorithms Prof. Wright's notes |
DPV §1.3 notes §3 |
|
||
Th 4/28 |
Quantum Algorithms Prof. Wright's notes (Part 1)Prof. Wright's notes (Part 2) |