Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley with Prasad Raghavendra and John Wright, Spring 2022
Lecture: Tu/Th 9:30 am - 11:00 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Announcements:
Lecture is at this Zoom Link for the first two weeks!
| Week | Date | Lecture | Reading | Section | Assignments |
|---|---|---|---|---|---|
| 1 |
Tu 1/18 |
Introduction, big-O notation, arithmetic webcast |
DPV §0 , §1.1 | ||
|
Th 1/20 |
Divide-and-Conquer (Part I) webcast |
DPV §2.1 , §2.2 , §2.3 | |||
| 2 |
Tu 1/25 |
Divide-and-Conquer (Part II) Zoom Link |
DPV §2.4 , §2.5 , §2.6 | ||
|
Th 1/27 |
Fast Fourier Transform |
DPV §2.6 | |||
| 3 |
Tu 2/1 |
Decompositions of graphs |
DPV §3 | ||
|
Th 2/3 |
Paths in graphs (Part I) |
DPV §4.1 , §4.2 , §4.3 , §4.4 | |||
| 4 |
Tu 2/8 |
Paths in graphs (Part II) |
DPV §4.4 , §4.5 , §4.6 , §4.7 | ||
|
Th 2/10 |
Greedy Algorithms |
DPV §5 , §5.4 | |||
| 5 |
Tu 2/15 |
Minimum Spanning Trees |
DPV §5.1 | ||
|
Th 2/17 |
Union Find |
DPV §5.1.4 | |||
| 6 |
Tu 2/22 |
Dynamic Programming (Part I) |
DPV §6 | ||
|
Th 2/24 |
Dynamic Programming (Part II) |
DPV §6 | |||
| 7 |
Tu 3/1 |
Dynamic Programming (Part III) |
DPV §6 | ||
|
Th 3/3 |
Linear Programming |
DPV §7.1 | |||
| 8 |
Tu 3/8 |
Network Flow |
DPV §7.2 | ||
|
Th 3/10 |
Duality |
DPV §7.4 | |||
| 9 |
Tu 3/15 |
Zero-Sum Games |
DPV §7.5 | ||
|
Th 3/17 |
Multiplicative Updates |
notes | |||
| 10 |
Tu 3/22 |
Spring Break |
|||
|
Th 3/24 |
Spring Break |
||||
| 11 |
Tu 3/29 |
Reductions, Bipartite Matching |
DPV §7.3 | ||
|
Th 3/31 |
Search Problems |
DPV §8.1 | |||
| 12 |
Tu 4/5 |
Midterm 2 |
|||
|
Th 4/7 |
NP-Completeness |
DPV §8.2 , §8.3 | |||
| 13 |
Tu 4/12 |
Coping with NP-completeness |
DPV §9 | ||
|
Th 4/14 |
Randomized Algorithms |
DPV §1.2 , §1.3 notes | |||
| 14 |
Tu 4/19 |
Sketching, Streaming |
DPV §1.5 notes | ||
|
Th 4/21 |
Hashing |
||||
| 15 |
Tu 4/26 |
Special Topic |
|||
|
Th 4/28 |
Special Topic |