Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley, Spring 2025
Nika Haghtalab, John Wright
Lecture: TuTh 2:00pm - 3:30pm, Valley Life Sciences Building 2050
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/21 |
Introduction, Big-O Notation, Recurrence Relations recording |
blank full | DPV §0.2 , §0.3 , §2.1 , §2.2 | ||
|
Thu 1/23 |
Divide-and-Conquer (Part I) recording |
blank full | DPV §2.3 , §2.4 , §2.5 | |||
|
2 |
Tue 1/28 |
Divide-and-Conquer (Part II) recording |
blank full | DPV §2.3 , §2.4 , §2.5 | ||
|
Thu 1/30 |
Divide-and-Conquer (Part III) recording |
blank full | DPV §2.3 , §2.4 , §2.5 | |||
|
3 |
Tue 2/4 |
Decomposition of Graphs recording |
blank full | DPV §3.1 , §3.2 , §3.3 , §3.4 | ||
|
Thu 2/6 |
Paths in Graphs (Part I) recording |
blank full | DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6 | |||
|
4 |
Tue 2/11 |
Paths in Graphs (Part II) recording |
blank full | DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6 | ||
|
Thu 2/13 |
Greedy (Part I) recording |
blank full | DPV §5.2 , §5.3 | |||
|
5 |
Tue 2/18 |
Greedy (Part II) recording |
blank full | DPV §5.1 , §5.2 | ||
|
Thu 2/20 |
Greedy (Part III) recording |
blank full | ||||
|
6 |
Tue 2/25 |
Midterm 1 (7 - 9 pm) |
||||
|
Thu 2/27 |
Dynamic Programming (Part I) recording |
blank | DPV §6 | |||
|
7 |
Tue 3/4 |
Dynamic Programming (Part II) recording |
blank full | DPV §6 | ||
|
Thu 3/6 |
Dynamic Programming (Part III) recording |
blank full | DPV §6 | |||
|
8 |
Tue 3/11 |
Dynamic Programming (Part IV) recording |
blank full | DPV §6 | ||
|
Thu 3/13 |
Linear Programming recording |
blank full | DPV §7.1 | |||
|
9 |
Tue 3/18 |
Network Flow, Bipartite Matching recording |
LP max flow LP full | DPV §7.2 | ||
|
Thu 3/20 |
Duality recording |
blank | DPV §7.4 | |||
|
10 |
Tue 3/24 |
Spring Recess |
||||
|
Thu 3/28 |
Spring Recess |
|||||
|
11 |
Tue 4/1 |
Zero-Sum Games, Search Problems recording |
blank | DPV §7.5 | ||
|
Thu 4/3 |
Midterm 2 (7 - 9 pm) |
|||||
|
12 |
Tue 4/8 |
P vs. NP recording |
blank | DPV §8 | ||
|
Thu 4/10 |
Reductions recording |
blank | DPV §7.1.3 , §8 | |||
|
13 |
Tue 4/15 |
NP-Completeness recording |
blank | DPV §8 | ||
|
Thu 4/17 |
Coping with NP-Completeness (Part I) recording |
blank | DPV §9 | |||
|
14 |
Tue 4/22 |
Coping with NP-Completeness (Part II) recording |
blank | DPV §9 | ||
|
Thu 4/24 |
Randomized Algorithms |
blank | DPV §1 , §9 | |||
|
15 |
Tue 4/29 |
TBD |
||||
|
Thu 5/1 |
TBD |
|||||
|
16 |
Tue 5/6 |
RRR Week |
||||
|
Thu 5/8 |
RRR Week |
|||||
|
17 |
Mon 5/12 |
Final Exam (11:30 am - 2:30 pm) |