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
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
7
Tu
2/27

Midterm 1 on 2/26

Th
2/29

13: Dynamic Programming (Part II)

DPV §6
8
Tu
3/5

14: Dynamic Programming (Part III)

DPV §6
Th
3/7

15: Linear Programs, Simplex Algorithm

DPV §7.1 , §7.6
9
Tu
3/12

16: Network Flow, Bipartite Matching

DPV §7.2
Th
3/14

17: Duality, Zero-Sum Games

DPV §7.4 , §7.5
10
Tu
3/19

18: Multiplicative Updates

Th
3/21

19: Reductions, Search Problems

DPV §7.3 , §8.1
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 §8.2 , §8.3
13
Tu
4/9

21: Reductions

DPV §8.3
Th
4/9

22: Coping with NP-completeness

DPV §9
14
Tu
4/23

23: Coping with NP-completeness

DPV §9
Th
4/25

24: Randomized Algorithms

DPV §1.3 , §1.5
15
Tu
4/30

25: TBD

Th
5/2

26: TBD