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
DPV §5.1.4 , §5.3
Th
2/22

12: Dynamic Programming (Part I)

Slides
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
DPV §6.3 , §6.4
8
Tu
3/5

14: Dynamic Programming (Part III)

slides
DPV §6.6
Th
3/7

15: Dynamic Programming (Part IV)

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

16: Linear Programs, Simplex Algorithm

slides
DPV §7.1
Th
3/14

17: Network Flow, Bipartite Matching

slides
DPV §7.2 , §7.3
10
Tu
3/19

18: Duality, Zero-Sum Games

slides
DPV §7.4 , §7.5
Th
3/21

19: Review

slides
11
Tu
3/26

Spring Recess

Th
3/28

Spring Recess

12
Tu
4/2

Midterm 2

Th
4/4

20: Reductions, NP-Completeness

DPV §7.3 , §8.1
13
Tu
4/9

21: Reductions

DPV §8.2, 8.3
Th
4/11

22: Coping with NP-completeness

DPV §9
14
Tu
4/16

23: Coping with NP-completeness

DPV §9
Th
4/18

24: TBD

15
Tu
4/23

25: TBD

Th
4/25

26: TBD