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 |
Academic and Administrative Holiday |
|||
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 Whiteboard |
DPV §3 | |||
F 2/10 |
Paths in graphs Whiteboard |
DPV §4 | |||
5 |
M 2/13 |
Single Source Shortest Paths (continued) |
DPV §5 , §5.4 | ||
W 2/15 |
Greedy Algorithms Whiteboard |
DPV §5 | |||
F 2/17 |
Greedy Algorithms Whiteboard |
DPV §5 | |||
6 |
M 2/20 |
Academic and Administrative Holiday |
|||
W 2/22 |
Minimum Spanning Trees |
DPV §5.1 | |||
F 2/24 |
Minimum Spanning Trees Whiteboard |
DPV §5.1 | |||
7 |
M 2/27 |
Midterm 1 |
DPV §6 | ||
W 3/1 |
Dynamic Programming (Part I) Whiteboard |
DPV §6 | |||
F 3/3 |
Dynamic Programming (Part II) Whiteboard |
DPV §6 | |||
8 |
M 3/6 |
Dynamic Programming (Part III) |
DPV §6 | ||
W 3/8 |
Dynamic Programming (Part III continued) |
DPV §6 | |||
F 3/10 |
Linear Programming Whiteboard |
DPV §7.2 | |||
9 |
M 3/13 |
Algorithms to Linear Programming, Simplex Algorithm |
DPV §7.2 , §7.6 | ||
W 3/15 |
Network Flow, Bipartite Matching Whiteboard |
DPV §7.2 | |||
F 3/17 |
Network Flow(Continued), Duality Whiteboard |
DPV §7.2 | |||
10 |
M 3/20 |
Duality, Zero Sum Games Whiteboard |
DPV §7.4 , §7.5 | ||
W 3/22 |
Zero Sum Games (Continued), Multiplicative Updates NotesWhiteboard |
DPV §7.3 | |||
F 3/24 |
Zero Sum Games (Continued), Multiplicative Updates NotesWhiteboard |
DPV §7.3 | |||
11 |
M 3/27 |
Spring Recess |
|||
W 3/29 |
Spring Recess |
||||
F 3/31 |
Spring Recess |
||||
12 |
M 4/3 |
Search Problems, NP-Completeness Whiteboard |
DPV §8.1 , §8.2 | ||
W 4/5 |
Midterm 2 |
||||
F 4/7 |
Reductions Whiteboard |
DPV §8.3 | |||
13 |
M 4/10 |
Reductions Whiteboard |
DPV §8.3 | ||
W 4/12 |
Reductions Whiteboard |
DPV §8.3 | |||
F 4/14 |
Coping with NP-completeness Whiteboard |
DPV §9 | |||
14 |
M 4/17 |
Coping with NP-completeness, Approximation Whiteboard |
DPV §9 | ||
W 4/19 |
Approximation II Whiteboard |
DPV §9 | |||
F 4/21 |
Approximation III Whiteboard |
DPV §9 | |||
15 |
M 4/24 |
Approximation Wrap-Up, Sampling, Sketching, Streaming NotesWhiteboard |
|||
W 4/26 |
Sketching, Streaming Notes |
||||
F 4/28 |
Special Topics |