Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley, Fall 2026

Nika Haghtalab, John Wright

Lecture: TuTh 9:30am - 10:59am, Undergraduate Academic Building 100
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Jump to current week

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

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

Introduction, Big-O Notation, Recurrence Relations

 DPV §0.2 , §0.3 , §2.1 , §2.2
2
 Tue
9/1

Divide-and-Conquer (Part I)

 DPV §2.3 , §2.4 , §2.5
Disc 1,
solutions,
HW 1
solutions
Thu
9/3

Divide-and-Conquer (Part II)

 DPV §2.3 , §2.4 , §2.5
3
 Tue
9/8

Divide-and-Conquer (Part III)

 DPV §2.3 , §2.4 , §2.5
Disc 2,
solutions,
HW 2
solutions
Thu
9/10

Decomposition of Graphs

 DPV §3.1 , §3.2 , §3.3 , §3.4
4
 Tue
9/15

Paths in Graphs (Part I)

 DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6
Disc 3,
solutions,
HW 3
solutions
Thu
9/17

Paths in Graphs (Part II)

 DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6
5
 Tue
9/22

Greedy (Part I)

 DPV §5.2 , §5.3
Disc 4,
solutions,
HW 4
solutions
Thu
9/24

Greedy (Part II)

 DPV §5.1 , §5.2
6
 Tue
9/29

Greedy (Part III)
HW 5
solutions
Thu
10/1

Midterm 1 (8 - 10 pm)
7
 Tue
10/6

Dynamic Programming (Part I)

 DPV §6
Disc 5,
solutions,
HW 6
solutions
Thu
10/8

Dynamic Programming (Part II)

 DPV §6
8
 Tue
10/13

Dynamic Programming (Part III)

 DPV §6
Disc 6,
solutions,
HW 7
solutions
Thu
10/15

Dynamic Programming (Part IV)

 DPV §6
9
 Tue
10/20

Linear Programming

 DPV §7.1
Disc 7,
solutions,
HW 8
solutions
Thu
10/22

Network Flow, Bipartite Matching

 DPV §7.2
10
 Tue
10/27

Duality

 DPV §7.4
Disc 8,
solutions,
HW 9
solutions
Thu
10/29

Zero-Sum Games, Search Problems

 DPV §7.5
11
 Tue
11/3

P vs. NP

 DPV §8
HW 10
solutions
Thu
11/5

Midterm 2 (7 - 9 pm)
12
 Tue
11/10

Reductions

 DPV §7.1.3 , §8
Disc 9,
solutions,
HW 11
solutions
Wed
11/11

Veterans Day
Thu
11/12

NP-Completeness

 DPV §8
13
 Tue
11/17

Coping with NP-Completeness (Part I)

 DPV §9
Disc 10,
solutions,
HW 12
solutions
Thu
11/19

Coping with NP-Completeness (Part II)

 DPV §9
14
 Tue
11/24

Randomized Algorithms

 DPV §1 , §9
Disc 11,
solutions,
HW 13
solutions
Thu
11/26

Thanksgiving Holiday
15
 Tue
12/1

Online Algorithms (Part I)
Disc 12,
solutions,
HW 14
solutions
Thu
12/3

Online Algorithms (Part II)
16
 Tue
12/8

RRR Week
Thu
12/10

RRR Week
17
 Tue
12/15

Final Exam (3:00 pm - 6:00 pm)