Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley, Spring 2026

Lijie Chen, Umesh Vazirani

Lecture: TuTh 3:30pm - 5:00pm, Stanley 105
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Jump to current week

PnPenguin logo
Warning: This webpage for Spring 2026 is under construction. There may be misleading information from past semesters on this webpage, which will be different from the Spring 2026 offering of the course.

We will remove this warning when the information on this webpage is accurate.
Note: This content schedule for Spring 2026 is subject to change.
Week Date Lecture Resources Readings Discussion Homework
1
 Tue
1/20

Introduction, Arithmetic Algorithms

 DPV §2.1 , §2.2
Disc 1,
solutions,
reference
HW 1
solutions
Thu
1/22

Fast Multiplication, Master Theorem, Median Finding

 DPV §2.3 , §2.4
2
 Tue
1/27

Fast Matrix Multiplication

 DPV §2.5
Disc 2,
solutions,
HW 2
solutions
Thu
1/29

Graph Alogorithms, DFS, Topological Sort

 DPV §3
3
 Tue
2/3

BFS, Shortest Paths

 DPV §3
Disc 3,
solutions,
HW 3
solutions
Thu
2/5

Greedy Algorithms (Part I)

 DPV §5 , §5.4
4
 Tue
2/10

Greedy Algorithms (Part II)

 DPV §5 , §5.4
Disc 4,
solutions,
HW 4
solutions
Thu
2/12

Dynamic Programming (Part I)

 DPV §6
5
 Tue
2/17

Dynamic Programming (Part II)

 DPV §6
Disc 5,
solutions,
HW 5
solutions
Thu
2/19

Dynamic Programming (Part III)

 DPV §6
6
 Tue
2/24

Backpropogation

 DPV §6
Disc 6,
solutions,
HW 6
solutions
Thu
2/26

Midterm 1 (7 - 9 pm)
7
 Tue
3/3

Parallelism (Miscommunication)
Disc 7,
solutions,
HW 7
solutions
Thu
3/5

Parallelism, Fast Fourier Transform (FFT)

 DPV §2.6
8
 Tue
3/10

Fast Fourier Transform (FFT)

 DPV §2.6
Disc 8,
solutions,
HW 8
solutions
Thu
3/12

Gradient Descent
9
 Tue
3/17

Linear Programming, Simplex Algorithm

 DPV §7.1
Disc 9,
solutions,
HW 9
solutions
Thu
3/19

Linear Programming, Duality

 DPV §7.4
10
 Tue
3/24

Spring Break
Thu
3/26

Spring Break
11
 Tue
3/31

Klee-Minty Example
Disc 11,
solutions,
HW 11
solutions
Thu
4/2

Zero-Sum Games

 DPV §7.4
12
 Tue
4/7

Multiplicative Weights (Part I)
Disc 12,
solutions,
HW 12
solutions
Thu
4/9

Midterm 2 (7 - 9 pm)
13
 Tue
4/14

Multiplicative Weights (Part II)
Disc 13,
solutions,
HW 13
solutions
Thu
4/16

AdWords
14
 Tue
4/21

NP-Completeness (Part I)

 DPV §8.2 , §9
Disc 14,
solutions,
HW 14
solutions
Thu
4/23

NP-Completeness (Part II)

 DPV §8.2 , §9
15
 Tue
4/28

Dealing with NP-Completeness

 DPV §9
Thu
4/30

Hashing / Streaming (Part I)
16
 Tue
5/5

Hashing / Streaming (Part II)
Thu
5/7

Quantum Algorithms
17
 Fri
12/15

Final Exam (7:00 pm - 10:00 pm)