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 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 |
Tu 1/16 |
1: Introduction, Big-O 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, Median-Finding 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, Zero-Sum Games |
DPV
§7.4
,
§7.5
|
||
Th 3/21 |
19: Review |
||||
11 |
Tu 3/26 |
Spring Recess |
|||
Th 3/28 |
Spring Recess |
||||
12 |
Tu 4/2 |
Midterm 2 |
|||
Th 4/4 |
20: Reductions, NP-Completeness |
DPV
§7.3
,
§8.1
|
|||
13 |
Tu 4/9 |
21: Reductions |
DPV
§8.2, 8.3
|
||
Th 4/9 |
22: Coping with NP-completeness |
DPV
§9
|
|||
14 |
Tu 4/23 |
23: Coping with NP-completeness |
DPV
§9
|
||
Th 4/25 |
24: TBD |
||||
15 |
Tu 4/30 |
25: TBD |
|||
Th 5/2 |
26: TBD |