Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Prasad Raghavendra and John Wright, Spring 2023

Lecture: MWF 11:00 am - 11:59 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

The lectures playlist can be found here on Youtube (to be updated) and bCourses Media Gallery (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
M
1/16

Martin Luther King, Jr. Day

W
1/18

Introduction, big-O notation, arithmetic

Whiteboard
DPV §2.1 , §2.2
F
1/20

Integer multiplication, Recurrence relations, Master theorem

Whiteboard
2
M
1/23

Matrix multiplication

Whiteboard
DPV §2.5
W
1/25

Median finding

Whiteboard
DPV §2.3 , §2.4
F
1/27

Polynomial multiplication, Coefficient/value representation

Whiteboard
DPV §2.6
3
M
1/30

Complex numbers, roots of unity, Fourier transform

Whiteboard
DPV §2.6
W
2/1

Fast Fourier transform

Whiteboard
DPV §2.6
F
2/3

Depth first search, Topological sort

DPV §3
4
M
2/6

DFS continued, Topological Sort

Whiteboard
DPV §3
W
2/8

Strongly connected components

DPV §3
F
2/10

Paths in graphs

DPV §4
5
M
2/13

Greedy Algorithms

DPV §5 , §5.4
W
2/15

Minimum Spanning Trees

DPV §5.1
F
2/17

Minimum Spanning Trees

DPV §5.1
6
M
2/20

Union Find

DPV §5.1.4
W
2/22

Dynamic Programming (Part I)

DPV §6
F
2/24

Dynamic Programming (Part II)

DPV §6
7
M
2/27

Midterm 1

DPV §6
W
3/1

Dynamic Programming (Part III)

DPV §6
F
3/3

Dynamic Programming (Part IV)

DPV §6
8
M
3/6

Dynamic Programming (Part V)

DPV §6
W
3/8

Linear Programming

DPV §7.2
F
3/10

Simplex Algorithm

DPV §7.6
9
M
3/13

Network Flow, Bipartite Matching

DPV §7.2
W
3/15

Duality, Zero-Sum Games

DPV §7.4
F
3/17

Duality, Zero-Sum Games

DPV §7.5
10
M
3/20

Multiplicative Updates

Notes
DPV §7.3
W
3/22

Reductions, Bipartite Matching

DPV §7.3
F
3/24

Search Problems

DPV §8.1
11
M
3/27

Spring Recess

W
3/29

Spring Recess

F
3/31

Spring Recess

12
M
4/3

NP-Completeness

DPV §8.2
W
4/5

Midterm 2

F
4/7

Reductions

DPV §8.3
13
M
4/10

Reductions

DPV §8.3
W
4/12

Coping with NP-completeness

DPV §9
F
4/14

Coping with NP-completeness

DPV §9
14
M
4/17

Coping with NP-completeness

DPV §9
W
4/19

Randomized Algorithms

Notes
DPV §1.3 , §1.5
F
4/21

Streaming

Notes
15
M
4/24

Sketching, Streaming

Notes
W
4/26

Sketching, Streaming

Notes
F
4/28

Special Topics