Lecture: MWF 11:00 am - 11:59 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
The lectures playlist can be found here on Youtube (to be updated) and bCourses Media Gallery (CalNet CAS required). Please refer to the playlist for the most up-to-date lectures available.
Please be informed that access to the majority of solutions on this website necessitates authentication through CalNet CAS. Should you require access to these restricted materials but do not possess a CalNet ID, kindly contact us for further assistance.
Week | Date | Lecture | Reading | Section | Assignments |
---|---|---|---|---|---|
1 |
M 1/16 |
Martin Luther King, Jr. Day |
|||
W 1/18 |
Introduction, big-O notation, arithmetic Whiteboard |
DPV §2.1 , §2.2 | |||
F 1/20 |
Integer multiplication, Recurrence relations, Master theorem Whiteboard |
||||
2 |
M 1/23 |
Matrix multiplication Whiteboard |
DPV §2.5 | ||
W 1/25 |
Median finding Whiteboard |
DPV §2.3 , §2.4 | |||
F 1/27 |
Polynomial multiplication, Coefficient/value representation Whiteboard |
DPV §2.6 | |||
3 |
M 1/30 |
Complex numbers, roots of unity, Fourier transform Whiteboard |
DPV §2.6 | ||
W 2/1 |
Fast Fourier transform Whiteboard |
DPV §2.6 | |||
F 2/3 |
Depth first search, Topological sort |
DPV §3 | |||
4 |
M 2/6 |
DFS continued, Topological Sort Whiteboard |
DPV §3 | ||
W 2/8 |
Strongly connected components |
DPV §3 | |||
F 2/10 |
Paths in graphs |
DPV §4 | |||
5 |
M 2/13 |
Greedy Algorithms |
DPV §5 , §5.4 | ||
W 2/15 |
Minimum Spanning Trees |
DPV §5.1 | |||
F 2/17 |
Minimum Spanning Trees |
DPV §5.1 | |||
6 |
M 2/20 |
Union Find |
DPV §5.1.4 | ||
W 2/22 |
Dynamic Programming (Part I) |
DPV §6 | |||
F 2/24 |
Dynamic Programming (Part II) |
DPV §6 | |||
7 |
M 2/27 |
Midterm 1 |
DPV §6 | ||
W 3/1 |
Dynamic Programming (Part III) |
DPV §6 | |||
F 3/3 |
Dynamic Programming (Part IV) |
DPV §6 | |||
8 |
M 3/6 |
Dynamic Programming (Part V) |
DPV §6 | ||
W 3/8 |
Linear Programming |
DPV §7.2 | |||
F 3/10 |
Simplex Algorithm |
DPV §7.6 | |||
9 |
M 3/13 |
Network Flow, Bipartite Matching |
DPV §7.2 | ||
W 3/15 |
Duality, Zero-Sum Games |
DPV §7.4 | |||
F 3/17 |
Duality, Zero-Sum Games |
DPV §7.5 | |||
10 |
M 3/20 |
Multiplicative Updates Notes |
DPV §7.3 | ||
W 3/22 |
Reductions, Bipartite Matching |
DPV §7.3 | |||
F 3/24 |
Search Problems |
DPV §8.1 | |||
11 |
M 3/27 |
Spring Recess |
|||
W 3/29 |
Spring Recess |
||||
F 3/31 |
Spring Recess |
||||
12 |
M 4/3 |
NP-Completeness |
DPV §8.2 | ||
W 4/5 |
Midterm 2 |
||||
F 4/7 |
Reductions |
DPV §8.3 | |||
13 |
M 4/10 |
Reductions |
DPV §8.3 | ||
W 4/12 |
Coping with NP-completeness |
DPV §9 | |||
F 4/14 |
Coping with NP-completeness |
DPV §9 | |||
14 |
M 4/17 |
Coping with NP-completeness |
DPV §9 | ||
W 4/19 |
Randomized Algorithms Notes |
DPV §1.3 , §1.5 | |||
F 4/21 |
Streaming Notes |
||||
15 |
M 4/24 |
Sketching, Streaming Notes |
|||
W 4/26 |
Sketching, Streaming Notes |
||||
F 4/28 |
Special Topics |