Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley with John Wright and Nika Haghtalab, Fall 2023
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 |
1: Introduction, Big-O Notation, Arithmetic blankannotated recording posted! |
DPV §0 , §1.1 | |||
| 2 |
Tu 8/29 |
2: Divide-and-Conquer (Part I) blankannotated recording posted! |
DPV §2.1 , §2.2 , §2.3 | ||
|
Th 8/31 |
3: Divide-and-Conquer (Part II) blankannotated recording posted! |
DPV §2.4 , §2.5 , §2.6 | |||
| 3 |
Tu 9/5 |
4: Fast Fourier Transform (Part I) slidesrecording posted! |
DPV §2.6 | ||
|
Th 9/7 |
5: Fast Fourier Transform (Part II) slidesrecording posted! |
DPV §2.6 | |||
| 4 |
Tu 9/12 |
6: Graphs and DFS blankannotations unavailable, refer to recording recording posted! |
DPV §3.1 , §3.2 , §3.3 | ||
|
Th 9/14 |
7: Strongly Connected Components blankannotations unavailable, refer to recording recording posted! |
DPV §3.4 | |||
| 5 |
Tu 9/19 |
8: Paths in Graphs blank (updated!)annotated recording posted! |
DPV §4.1 , §4.2 , §4.3 , §4.4 | ||
|
Th 9/21 |
9: Greedy Algorithms blankannotated recording posted! |
DPV §5 | |||
| 6 |
Tu 9/26 |
10: Minimum Spanning Trees blankannotated recording posted! |
DPV §5.1 | ||
|
Th 9/28 |
11: More on MSTs and Set Cover blankannotated recording posted! |
DPV §5.1 , §5.4 | |||
| 7 |
Tu 10/3 |
Midterm 1 |
|||
|
Th 10/5 |
12: Dynamic Programming (Part I) blankannotated recording posted! |
DPV §6 | |||
| 8 |
Tu 10/10 |
13: Dynamic Programming (Part II) blankannotated recording posted! |
DPV §6 | ||
|
Th 10/12 |
14: Dynamic Programming (Part III) blankannotated recording posted! |
DPV §6 | |||
| 9 |
Tu 10/17 |
15: Linear Programming blankannotated recording posted! |
DPV §7.1 | ||
|
Th 10/19 |
16: Network Flow (Part I) slidesrecording posted! |
DPV §7.2 | |||
| 10 |
Tu 10/24 |
17: Network Flow (Part II) slides - dualityslides - ZSG recording posted! |
DPV §7.2 | ||
|
Th 10/26 |
18: Zero-Sum Games slides - ZSG part 2slides - P/NP recording posted! |
DPV §7.5 | |||
| 11 |
Tu 10/31 |
19: Reductions, Bipartite Matching slidesrecording posted! |
DPV §7.3 | ||
|
Th 11/2 |
20: Search Problems slidesrecording posted! |
DPV §8.1 | |||
| 12 |
Tu 11/7 |
Midterm 2 |
|||
|
Th 11/9 |
21: NP-Completeness slidesrecording posted! |
DPV §8.2 , §8.3 | |||
| 13 |
Tu 11/14 |
22: Coping with NP-Completeness slidesrecording posted! |
DPV §9 | ||
|
Th 11/16 |
23: Sketching, Streaming slidesfurther reading recording posted! |
DPV §1.5 | |||
| 14 |
Tu 11/21 |
24: Sketching and Streaming (Part II) slidesfurther reading recording posted! |
DPV §1.5 | ||
|
Th 11/23 |
Thanksgiving Break |
||||
| 15 |
Tu 11/28 |
25: Randomized Algorithms slidesrecording posted! |
DPV §1.3 | ||
|
Th 11/30 |
26: Special Topic (Quantum Algorithms!) |