Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley, Fall 2024
Prasad Raghavendra, Sanjam Garg
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 8/27 |
No lecture |
||||
|
Thu 8/29 |
Introduction, Big-O Notation, Recurrence Relations recording |
Lecture Notes | DPV §0.2 , §0.3 , §2.1 , §2.2 | |||
|
2 |
Tue 9/3 |
Integer Multiplication, Recurrence relations, Master Theorem recording |
Lecture Notes | DPV §2.3 , §2.4 , §2.5 | ||
|
Thu 9/5 |
Matrix Multiplication, Median Finding recording |
Lecture Notes | DPV §2.3 , §2.4 , §2.5 | |||
|
3 |
Tue 9/10 |
Quickselect, Divide and Conquer Examples recording |
Lecture Notes | DPV §2.3 , §2.4 , §2.5 | ||
|
Thu 9/12 |
DFS, Topological sort recording |
Lecture Notes | DPV §3.1 , §3.2 , §3.3 | |||
|
4 |
Tue 9/17 |
Strongly Connected Components recording |
Lecture Notes | DPV §3.4 | ||
|
Thu 9/19 |
Paths in Graphs recording |
Lecture Notes | DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6 | |||
|
5 |
Tue 9/24 |
Greedy Algorithms recording |
Lecture Notes | DPV §5.2 , §5.3 | ||
|
Thu 9/26 |
Minimum Spanning Trees recording |
Lecture Notes | DPV §5.1 | |||
|
6 |
Tue 10/1 |
No lecture |
||||
|
Wed 10/2 |
Midterm 1 (7 - 9 pm) |
|||||
|
Thu 10/3 |
Dynamic Programming (Part 1) recording |
Lecture Notes | DPV §6 | |||
|
7 |
Tue 10/8 |
Dynamic Programming (Part 2) recording |
Lecture Notes | DPV §6 | ||
|
Thu 10/10 |
Dynamic Programming (Part 3) recording |
Lecture Notes | DPV §6 | |||
|
8 |
Tue 10/15 |
Dynamic Programming (Part 4) recording |
Lecture Notes | DPV §6 | ||
|
Thu 10/17 |
Linear Programming, Simplex Algorithm recording |
Lecture Notes | DPV §7.1 | |||
|
9 |
Tue 10/22 |
Duality, Zero-Sum Games recording |
Lecture Notes | DPV §7.4 , §7.5 | ||
|
Thu 10/24 |
Network Flow, Bipartite Matching (Part 1) recording |
Lecture Notes | DPV §7.2 | |||
|
10 |
Tue 10/29 |
Network Flow, Bipartite Matching (Part 2) recording |
Lecture Notes LP Feasibility Reading (up to pg.10) | DPV §7.2 | ||
|
Thu 10/31 |
Solving LP Feasibility recording |
Lecture Notes LP Feasibility Reading (up to pg.10) | ||||
|
11 |
Tue 11/5 |
No lecture; Midterm 2 (7 - 9 pm) |
||||
|
Thu 11/7 |
Reductions, Search Problems recording |
Lecture Notes | DPV §8.1 | |||
|
12 |
Tue 11/12 |
NP-Completeness recording |
Lecture Notes | DPV §8.3 | ||
|
Thu 11/14 |
Reductions recording |
Lecture Notes | DPV §8.2 | |||
|
13 |
Tue 11/19 |
Coping with NP-Completeness (Part 1) recording |
Lecture Notes | DPV §9 | ||
|
Thu 11/21 |
Coping with NP-Completeness (Part 2) recording |
Lecture Notes | DPV §9 | |||
|
14 |
Tue 11/26 |
Coping with NP-Completeness (Part 3) and Interactive Proofs recording |
Lecture Notes | DPV §9 | ||
|
Thu 11/28 |
Thanksgiving Break |
|||||
|
15 |
Tue 12/3 |
LP-based approximation algorithms recording |
Lecture Notes alternate recording (CMU) | |||
|
Thu 12/5 |
SDP-based approximation algorithms recording |
Reading Lecture Notes | ||||
|
16 |
Tue 12/10 |
RRR Week |
||||
|
Thu 12/12 |
RRR Week |
|||||
|
17 |
Tue 12/17 |
Final Exam (8 - 11 am) |