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
Note: This content schedule for Fall 2026 is subject to change.
Week Date Lecture Resources Readings Discussion Homework
1
 Thu
8/27

Introduction

 blank filled 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)