Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Prasad Raghavendra and Christian Borgs, Spring 2024

Lecture: TuTh 3:30 PM - 4:59 PM in Li Ka Shing 245
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

For this semester, we unfortunately currently no longer plan to publish lectures to YouTube. The lectures playlist can still be found on bCourses in the Media Gallery tab (CalNet CAS required). Please refer to the playlist for the most up-to-date lectures available.

Please be informed that access to the majority of solutions on this website necessitates authentication through CalNet CAS. Should you require access to these restricted materials but do not possess a CalNet ID, kindly contact us for further assistance.

Week Date Lecture Reading Section Assignments
1
Tu
1/16

1: Introduction, Big-O Notation, Arithmetic

slides
slides (6up)
recording posted!
DPV §0 , §1.1
Th
1/18

2: Integer Multiplication, Recurrence Relations, Master Theorem

slides
slides (6up)
recording posted!
DPV §2.1 , §2.2
2
Tu
1/23

3: Matrix Muliplication, Median-Finding

slides
slides (6up)
recording posted!
DPV §2.3 , §2.4 , §2.5
HW 1

due 1/29

,
Solutions
Th
1/25

4: Fast Fourier Transform (Part I)

slides
slides (6up)
recording posted!
DPV §2.6
3
Tu
1/30

5: Fast Fourier Transform (Part II)

slides
slides (handout)
recording posted!
DPV §2.6
Th
2/1

6: Depth First Search, Topological Sort

slides
slides (handout)
recording posted!
DPV §3
4
Tu
2/6

7: Strongly Connected Components

slides
recording posted!
DPV §3
Th
2/8

8: Paths in Graphs

slides
recording posted!
DPV §4
FFT Applications
5
Tu
2/13

9: Greedy Algorithms, Huffman encoding

slides
recording posted!
DPV §5 , §5.2
Th
2/15

10: Minimum Spanning Trees

slides
prim's proof
recording posted!
DPV §5.1
6
Tu
2/20

11: Union Find, Horn Formulas

slides
recording posted!
DPV §5.1.4 , §5.3
Th
2/22

12: Dynamic Programming (Part I)

slides
recording posted!
DPV §6.1 , §6.2 , §6.3
7
Tu
2/27

Midterm 1 on 2/26

Th
2/29

13: Dynamic Programming (Part II)

slides
recording posted!
DPV §6.3 , §6.4
8
Tu
3/5

14: Dynamic Programming (Part III)

slides
recording posted!
DPV §6.6
Th
3/7

15: Dynamic Programming (Part IV)

slides
recording posted!
DPV §6.5 , §6.6 , §6.7
9
Tu
3/12

16: Linear Programs, Simplex Algorithm

slides
recording posted!
DPV §7.1
Th
3/14

17: Network Flow, Bipartite Matching

slides
recording posted!
DPV §7.2 , §7.3
10
Tu
3/19

18: Duality, Zero-Sum Games

slides
recording posted!
DPV §7.4 , §7.5
Th
3/21

19: Review

slides
recording posted!
11
Tu
3/26

Spring Recess

Th
3/28

Spring Recess

12
Tu
4/2

Midterm 2

Th
4/4

20: Reductions, NP-Completeness

slides
recording posted!
DPV §7.3 , §8.1
13
Tu
4/9

21: Reductions

slides
recording posted!
DPV §8.2, 8.3
Th
4/11

22: Coping with NP-completeness

slides
recording posted!
DPV §9
14
Tu
4/16

23: Coping with NP-completeness

slides
recording posted!
DPV §9
Th
4/18

24: Gradient Descent (Part I)

slides
recording posted!
GD Notes (sections 1-3) -- updated 4/29
15
Tu
4/23

25: Gradient Descent (Part II)

slides
recording posted!
GD Notes -- updated 4/29
Th
4/25

26: Gradient Descent (Part III), Multiplicative Weights

GD Notes -- updated 4/29