Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley, Spring 2026
Lijie Chen, Umesh Vazirani
Lecture: TuTh 3:30pm - 5:00pm, Stanley 105
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Jump to current week
| Week | Date | Lecture | Resources | Readings | Discussion | Homework |
|---|---|---|---|---|---|---|
|
1 |
Tue 1/20 |
Introduction, Arithmetic Algorithms recording |
DPV §2.1 , §2.2 | |||
|
Thu 1/22 |
Fast Multiplication, Master Theorem, Median Finding recording |
DPV §2.3 , §2.4 | ||||
|
2 |
Tue 1/27 |
Fast Matrix Multiplication |
DPV §2.5 | |||
|
Thu 1/29 |
Graph Alogorithms, DFS, Topological Sort |
DPV §3 | ||||
|
3 |
Tue 2/3 |
BFS, Shortest Paths |
DPV §3 | |||
|
Thu 2/5 |
Greedy Algorithms (Part I) |
DPV §5 , §5.4 | ||||
|
4 |
Tue 2/10 |
Greedy Algorithms (Part II) |
DPV §5 , §5.4 | |||
|
Thu 2/12 |
Dynamic Programming (Part I) |
DPV §6 | ||||
|
5 |
Tue 2/17 |
Dynamic Programming (Part II) |
DPV §6 | |||
|
Thu 2/19 |
Dynamic Programming (Part III) |
DPV §6 | ||||
|
6 |
Tue 2/24 |
Backpropogation |
DPV §6 | |||
|
Thu 2/26 |
Midterm 1 (7 - 9 pm) |
|||||
|
7 |
Tue 3/3 |
Fast Fourier Transform (FFT) |
DPV §2.6 | |||
|
Thu 3/5 |
Fast Fourier Transform (FFT), Parallelism (Part I) |
DPV §2.6 | ||||
|
8 |
Tue 3/10 |
Parallelism (Part II) |
||||
|
Thu 3/12 |
Gradient Descent |
|||||
|
9 |
Tue 3/17 |
Linear Programming, Simplex Algorithm |
DPV §7.1 | |||
|
Thu 3/19 |
Linear Programming, Duality |
DPV §7.4 | ||||
|
10 |
Tue 3/24 |
Spring Break |
||||
|
Thu 3/26 |
Spring Break |
|||||
|
11 |
Tue 3/31 |
Klee-Minty Example |
||||
|
Thu 4/2 |
Zero-Sum Games |
DPV §7.4 | ||||
|
12 |
Tue 4/7 |
Multiplicative Weights |
||||
|
Thu 4/9 |
Midterm 2 (7 - 9 pm) |
|||||
|
13 |
Tue 4/14 |
AdWords |
||||
|
Thu 4/16 |
NP-Completeness (Part I) |
DPV §8.2 , §9 | ||||
|
14 |
Tue 4/21 |
NP-Completeness (Part II), Dealing with NP-Completeness |
DPV §8.2 , §9 | |||
|
Thu 4/23 |
Hashing / Streaming (Part I) |
|||||
|
15 |
Tue 4/28 |
Hashing / Streaming (Part II) |
||||
|
Thu 4/30 |
Quantum Algorithms |
|||||
|
16 |
Tue 5/5 |
RRR Week |
||||
|
Thu 5/7 |
RRR Week |
|||||
|
17 |
Fri 5/15 |
Final Exam (7:00 pm - 10:00 pm) |
