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


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 Slides 
DPV
§5.1.4
,
§5.3


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


7 
Tu 2/27 
Midterm 1 on 2/26 

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


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


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


9 
Tu 3/12 
16: Linear Programs, Simplex Algorithm slides 
DPV
§7.1


Th 3/14 
17: Network Flow, Bipartite Matching slides 
DPV
§7.2
,
§7.3


10 
Tu 3/19 
18: Duality, ZeroSum Games slides 
DPV
§7.4
,
§7.5


Th 3/21 
19: Review slides 

11 
Tu 3/26 
Spring Recess 

Th 3/28 
Spring Recess 

12 
Tu 4/2 
Midterm 2 

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


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


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


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


Th 4/18 
24: TBD 

15 
Tu 4/23 
25: TBD 

Th 4/25 
26: TBD 