Lecture: TuTh 12:30 PM - 1:59 PM
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 8/22 |
No Lecture |
|||
Th 8/24 |
Introduction, Big-O Notation, Arithmetic blankannotated recording posted! |
DPV §0 , §1.1 | |||
2 |
Tu 8/29 |
Divide-and-Conquer (Part I) blankannotated recording posted! |
DPV §2.1 , §2.2 , §2.3 | ||
Th 8/31 |
Divide-and-Conquer (Part II) blankannotated recording posted! |
DPV §2.4 , §2.5 , §2.6 | |||
3 |
Tu 9/5 |
Fast Fourier Transform (Part I) slidesrecording posted! |
DPV §2.6 | ||
Th 9/7 |
Fast Fourier Transform (Part II) slidesrecording posted! |
DPV §2.6 | |||
4 |
Tu 9/12 |
Graphs and DFS blankannotations unavailable, refer to recording recording posted! |
DPV §3.1 , §3.2 , §3.3 | ||
Th 9/14 |
Strongly Connected Components blankannotations unavailable, refer to recording recording posted! |
DPV §3.4 | |||
5 |
Tu 9/19 |
Paths in Graphs blank (updated!)annotated recording posted! |
DPV §4.1 , §4.2 , §4.3 , §4.4 | ||
Th 9/21 |
Greedy Algorithms blankannotated recording posted! |
DPV §5 | |||
6 |
Tu 9/26 |
Minimum Spanning Trees |
DPV §5.1 | ||
Th 9/28 |
Dynamic Programming (Part I) |
DPV §6 | |||
7 |
Tu 10/3 |
Midterm 1 |
|||
Th 10/5 |
Dynamic Programming (Part II) |
DPV §6 | |||
8 |
Tu 10/10 |
Linear Programming |
DPV §7.1 | ||
Th 10/12 |
Network Flow (Part I) |
DPV §7.2 | |||
9 |
Tu 10/17 |
Network Flow (Part II) |
DPV §7.2 | ||
Th 10/19 |
Zero-Sum Games |
DPV §7.5 | |||
10 |
Tu 10/24 |
Multiplicative Weights |
|||
Th 10/26 |
Reductions, Bipartite Matching |
DPV §7.3 | |||
11 |
Tu 10/31 |
Search Problems |
DPV §8.1 | ||
Th 11/2 |
NP-Completeness |
DPV §8.2 , §8.3 | |||
12 |
Tu 11/7 |
Midterm 2 |
|||
Th 11/9 |
Coping with NP-Completeness |
DPV §9 | |||
13 |
Tu 11/14 |
Randomized Algorithms |
DPV §1.3 | ||
Th 11/16 |
Hashing |
DPV §1.5 | |||
14 |
Tu 11/21 |
Sketching, Streaming |
|||
Th 11/23 |
Thanksgiving Break |
||||
15 |
Tu 11/28 |
Sketching, Streaming |
|||
Th 11/30 |
Special Topic |