Lecture: Tu/Th 3:30 - 5:00 pm, Dwinelle 155
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Week | Date | Lecture | Reading | Section | Assignments |
---|---|---|---|---|---|
1 |
Tu 1/21 |
Introduction, big-O notation, arithmetic webcast |
DPV §0 , §1.1 | ||
Th 1/23 |
Divide-and-Conquer Part I webcast |
DPV §2.1 , §2.2 , §2.3 | |||
2 |
Tu 1/28 |
Divide-and-Conquer Part II webcast |
DPV §2.4 , §2.5 , §2.6 | ||
Th 1/30 |
Fast Fourier Transform webcast |
DPV §2.6 | |||
3 |
Tu 2/4 |
Decompositions of graphs webcast |
DPV §3 | ||
Th 2/6 |
Paths in graphs Part I webcast |
DPV §4.1 , §4.2 , §4.3 , §4.4 | |||
4 |
Tu 2/11 |
Paths in graphs Part II webcast |
DPV §4.4 , §4.5 , §4.6 , §4.7 | ||
Th 2/13 |
Greedy Algorithms webcast |
DPV §5.4 | |||
5 |
Tu 2/18 |
Minimum Spanning Trees webcast |
DPV §5.1 | ||
Th 2/20 |
Midterm 1 on Th 2/20 (No lecture) | ||||
6 |
Tu 2/25 |
Union Find webcast |
DPV §5.1.4 | ||
Th 2/27 |
Dynamic Programming Part I notebook webcast |
DPV §6 | |||
7 |
Tu 3/3 |
Dynamic Programming Part II webcast |
DPV §6 | ||
Th 3/5 |
Linear Programming and Duality webcast |
DPV §7.1 , §7.4 | |||
8 |
Tu 3/10 |
Network Flow webcast |
DPV §7.2 | ||
Th 3/12 |
Network Flow webcast |
DPV §7.2 | |||
9 |
Tu 3/17 |
Zero-Sum Games webcast |
DPV §7.5 | ||
Th 3/19 |
Multiplicative Updates webcast |
notes | |||
10 |
Tu 3/24 |
Spring Break | |||
Th 3/26 |
Spring Break | ||||
11 |
Tu 3/31 |
Reductions, Bipartite Matching webcast |
DPV §7.3 |
|
|
Th 4/2 |
No Lecture (Time to work on the checkpoint) | ||||
12 |
Tu 4/7 |
Search Problems webcast |
DPV §8.1 |
|
|
Th 4/9 |
NP-Completeness webcast |
DPV §8.2 , §8.3 | |||
13 |
Tu 4/14 |
Coping with NP-Completeness webcast |
DPV §9 |
|
|
Th 4/16 |
Randomized Algorithms webcast |
notes | |||
14 |
Tu 4/21 |
Sketching, Streaming webcast |
notes |
|
|
Th 4/23 |
Lower Bounds webcast |
notes | |||
15 |
Tu 4/28 |
Hashing webcast |
DPV §1.5 |
|
|
Th 4/30 |
Special Topic webcast |