Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley, Fall 2025
Sanjam Garg, John Wright
Lecture: TuTh 2:00pm - 3:30pm, Wheeler 150
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 |
Thu 8/28 |
Introduction, Big-O Notation, Recurrence Relations recording |
lecture notes | DPV §2.1 , §2.2 | ||
|
2 |
Tue 9/2 |
Integer Multiplication, Recurrence Relations, Master Theorom |
DPV §2.3 , §2.4 , §2.5 | |||
|
Thu 9/4 |
Matrix Multiplication, Medians |
DPV §2.3 , §2.4 , §2.5 | ||||
|
3 |
Tue 9/9 |
Divide and Conquer Examples |
DPV §2.3 , §2.4 , §2.5 | |||
|
Thu 9/11 |
Depth First Search, Topological Sort |
DPV §3 | ||||
|
4 |
Tue 9/16 |
Strongly Connected Components |
DPV §3 | |||
|
Thu 9/18 |
Paths in Graphs |
DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.5 , §4.6 , §4.7 | ||||
|
5 |
Tue 9/23 |
Greedy Algorithms (Part I) |
DPV §5 , §5.4 | |||
|
Thu 9/25 |
Greedy Algorithms (Part II) |
DPV §5 , §5.4 | ||||
|
6 |
Tue 9/30 |
Midterm 1 (7 - 9 pm) |
||||
|
Thu 10/2 |
Dynamic Programming (Part I) |
DPV §6 | ||||
|
7 |
Tue 10/7 |
Dynamic Programming (Part II) |
DPV §6 | |||
|
Thu 10/9 |
Dynamic Programming (Part III) |
DPV §6 | ||||
|
8 |
Tue 10/14 |
Dynamic Programming (Part IV) |
DPV §6 | |||
|
Thu 10/16 |
Linear Programming, Simplex Algorithm |
DPV §7.1 | ||||
|
9 |
Tue 10/21 |
Network Flow, Bipartite Matching |
DPV §7.2 | |||
|
Thu 10/23 |
Duality, Zero-Sum Games |
DPV §7.4 | ||||
|
10 |
Tue 10/28 |
Gradient Descent (Part I) |
||||
|
Thu 10/30 |
Gradient Descent (Part II) |
|||||
|
11 |
Tue 11/4 |
Midterm 2 (7 - 9 pm) |
||||
|
Thu 11/6 |
Reductions, Bipartite Matching, Search Problems |
DPV §8.1 , §8.3 | ||||
|
12 |
Tue 11/11 |
Holiday |
||||
|
Thu 11/13 |
Reductions, NP-Completeness |
DPV §8.2 | ||||
|
13 |
Tue 11/18 |
Reductions |
DPV §9 | |||
|
Thu 11/20 |
Coping with NP-Completeness (Part I) |
DPV §9 | ||||
|
14 |
Tue 11/25 |
Coping with NP-Completeness (Part II) |
DPV §9 | |||
|
Thu 11/27 |
Thanksgiving |
|||||
|
15 |
Tue 12/2 |
TBD |
||||
|
Thu 12/4 |
TBD |
|||||
|
16 |
Tue 12/9 |
RRR Week |
||||
|
Thu 12/11 |
RRR Week |
|||||
|
17 |
Tue 12/16 |
Final Exam (8:00 am - 11:00 am) |