Lecture: TuTh 3:30 PM  4:59 PM in Li Ka Shing 245
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
For this semester, we unfortunately currently no longer plan to publish lectures to YouTube. The lectures playlist can still be found on bCourses in the Media Gallery tab (CalNet CAS required). Please refer to the playlist for the most uptodate 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 
Tu 1/16 
1: Introduction, BigO Notation, Arithmetic slidesslides (6up) recording posted! 
DPV
§0
,
§1.1


Th 1/18 
2: Integer Multiplication, Recurrence Relations, Master Theorem slidesslides (6up) recording posted! 
DPV
§2.1
,
§2.2


2 
Tu 1/23 
3: Matrix Muliplication, MedianFinding slidesslides (6up) recording posted! 
DPV
§2.3
,
§2.4
,
§2.5

HW 1
due 1/29 

Th 1/25 
4: Fast Fourier Transform (Part I) slidesslides (6up) recording posted! 
DPV
§2.6


3 
Tu 1/30 
5: Fast Fourier Transform (Part II) slidesslides (handout) recording posted! 
DPV
§2.6


Th 2/1 
6: Depth First Search, Topological Sort slidesslides (handout) recording posted! 
DPV
§3


4 
Tu 2/6 
7: Strongly Connected Components slidesrecording posted! 
DPV
§3


Th 2/8 
8: Paths in Graphs slidesrecording posted! 
DPV
§4
FFT Applications 

5 
Tu 2/13 
9: Greedy Algorithms, Huffman encoding slidesrecording posted! 
DPV
§5
,
§5.2


Th 2/15 
10: Minimum Spanning Trees slidesprim's proof recording posted! 
DPV
§5.1


6 
Tu 2/20 
11: Union Find, Horn Formulas slidesrecording posted! 
DPV
§5.1.4
,
§5.3


Th 2/22 
12: Dynamic Programming (Part I) slidesrecording posted! 
DPV
§6.1
,
§6.2
,
§6.3


7 
Tu 2/27 
Midterm 1 on 2/26 

Th 2/29 
13: Dynamic Programming (Part II) slidesrecording posted! 
DPV
§6.3
,
§6.4


8 
Tu 3/5 
14: Dynamic Programming (Part III) slidesrecording posted! 
DPV
§6.6


Th 3/7 
15: Dynamic Programming (Part IV) slidesrecording posted! 
DPV
§6.5
,
§6.6
,
§6.7


9 
Tu 3/12 
16: Linear Programs, Simplex Algorithm slidesrecording posted! 
DPV
§7.1


Th 3/14 
17: Network Flow, Bipartite Matching slidesrecording posted! 
DPV
§7.2
,
§7.3


10 
Tu 3/19 
18: Duality, ZeroSum Games slidesrecording posted! 
DPV
§7.4
,
§7.5


Th 3/21 
19: Review slidesrecording posted! 

11 
Tu 3/26 
Spring Recess 

Th 3/28 
Spring Recess 

12 
Tu 4/2 
Midterm 2 

Th 4/4 
20: Reductions, NPCompleteness slidesrecording posted! 
DPV
§7.3
,
§8.1


13 
Tu 4/9 
21: Reductions slidesrecording posted! 
DPV
§8.2, 8.3


Th 4/11 
22: Coping with NPcompleteness slidesrecording posted! 
DPV
§9


14 
Tu 4/16 
23: Coping with NPcompleteness slidesrecording posted! 
DPV
§9


Th 4/18 
24: Gradient Descent (Part I) slidesrecording posted! 
GD Notes (sections 13)  updated 4/29


15 
Tu 4/23 
25: Gradient Descent (Part II) slidesrecording posted! 
GD Notes  updated 4/29


Th 4/25 
26: Gradient Descent (Part III), Multiplicative Weights 
GD Notes  updated 4/29
