Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with John Wright and Nika Haghtalab, Fall 2023

Lecture: TuTh 12:30 PM - 1:59 PM
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
8/22

No Lecture

Th
8/24

1: Introduction, Big-O Notation, Arithmetic

blank
annotated
recording posted!
DPV §0 , §1.1
2
Tu
8/29

2: Divide-and-Conquer (Part I)

blank
annotated
recording posted!
DPV §2.1 , §2.2 , §2.3
Th
8/31

3: Divide-and-Conquer (Part II)

blank
annotated
recording posted!
DPV §2.4 , §2.5 , §2.6
3
Tu
9/5

4: Fast Fourier Transform (Part I)

slides
recording posted!
DPV §2.6
Th
9/7

5: Fast Fourier Transform (Part II)

slides
recording posted!
DPV §2.6
4
Tu
9/12

6: Graphs and DFS

blank
annotations unavailable, refer to recording
recording posted!
DPV §3.1 , §3.2 , §3.3
Th
9/14

7: Strongly Connected Components

blank
annotations unavailable, refer to recording
recording posted!
DPV §3.4
5
Tu
9/19

8: Paths in Graphs

blank (updated!)
annotated
recording posted!
DPV §4.1 , §4.2 , §4.3 , §4.4
Th
9/21

9: Greedy Algorithms

blank
annotated
recording posted!
DPV §5
6
Tu
9/26

10: Minimum Spanning Trees

blank
annotated
recording posted!
DPV §5.1
Th
9/28

11: More on MSTs and Set Cover

blank
annotated
recording posted!
DPV §5.1 , §5.4
7
Tu
10/3

Midterm 1

Th
10/5

12: Dynamic Programming (Part I)

blank
annotated
recording posted!
DPV §6
8
Tu
10/10

13: Dynamic Programming (Part II)

blank
annotated
recording posted!
DPV §6
Th
10/12

14: Dynamic Programming (Part III)

blank
annotated
recording posted!
DPV §6
9
Tu
10/17

15: Linear Programming

blank
annotated
recording posted!
DPV §7.1
Th
10/19

16: Network Flow (Part I)

slides
recording posted!
DPV §7.2
10
Tu
10/24

17: Network Flow (Part II)

slides - duality
slides - ZSG
recording posted!
DPV §7.2
Th
10/26

18: Zero-Sum Games

slides - ZSG part 2
slides - P/NP
recording posted!
DPV §7.5
11
Tu
10/31

19: Reductions, Bipartite Matching

slides
recording posted!
DPV §7.3
Th
11/2

20: Search Problems

slides
recording posted!
DPV §8.1
12
Tu
11/7

Midterm 2

Th
11/9

21: NP-Completeness

slides
recording posted!
DPV §8.2 , §8.3
13
Tu
11/14

22: Coping with NP-Completeness

slides
recording posted!
DPV §9
Th
11/16

23: Sketching, Streaming

slides
further reading
recording posted!
DPV §1.5
14
Tu
11/21

24: Sketching and Streaming (Part II)

slides
further reading
recording posted!
DPV §1.5
Th
11/23

Thanksgiving Break

15
Tu
11/28

25: Randomized Algorithms

slides
recording posted!
DPV §1.3
Th
11/30

26: Special Topic (Quantum Algorithms!)