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
HW 0
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
Section 1 ,
Solutions
HW 1 ,
Solutions
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
Section 2 ,
Solutions
HW 2 ,
Solutions
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
Section 3
HW 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
Section 4
HW 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
Section 5
HW 5
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
Section 6
HW 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
Section 7
HW 7
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
Section 8
HW 8
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
Section 9
HW 9
W
3/22

Reductions, Bipartite Matching

 DPV §7.3
F
3/24

Search Problems

 DPV §8.1
11
 M
3/27

Spring Recess
Section 10
HW 10
W
3/29

Spring Recess
F
3/31

Spring Recess
12
 M
4/3

NP-Completeness

 DPV §8.2
Section 11
HW 11
W
4/5

Midterm 2
F
4/7

Reductions

 DPV §8.3
13
 M
4/10

Reductions

 DPV §8.3
Section 12
HW 12
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
Section 13
HW 13
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