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

 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)

In-class Quiz (date subject to change)
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

Greedy Wrap-Up and Introduction to Dynamic Programming

 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

In-class Quiz (date subject to change)
DPV §7.5
11
 Tue
11/3

Search
HW 10
solutions
Thu
11/5

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

P vs NP

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

Veterans Day
Thu
11/12

Reductions

 DPV §7.1.3 , §8
13
 Tue
11/17

NP-Completeness

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

Coping with NP-completeness I

 DPV §9
14
 Tue
11/24

Coping with NP completeness II

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

Thanksgiving Holiday
15
 Tue
12/1

Randomized Algorithms

In-class Quiz (date subject to change)
DPV §1 , §9
Disc 12,
solutions,
HW 14
solutions
Thu
12/3

TBD
16
 Tue
12/8

RRR Week
Thu
12/10

RRR Week
17
 Tue
12/15

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