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

Academic and Administrative Holiday
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 ,
Solutions
HW 3 ,
Solutions
W
2/8

Strongly connected components

Whiteboard
DPV §3
F
2/10

Paths in graphs

Whiteboard
DPV §4
5
 M
2/13

Single Source Shortest Paths (continued)
Greedy Algorithms

Whiteboard
DPV §5 , §5.4
Section 4 ,
Solutions
HW 4 ,
Solutions
W
2/15

Greedy Algorithms

Whiteboard
DPV §5
F
2/17

Greedy Algorithms

Whiteboard
DPV §5
6
 M
2/20

Academic and Administrative Holiday
Presidents’ Day
Section 5 ,
Solutions
HW 5 ,
Solutions
W
2/22

Minimum Spanning Trees
Kruskal’s Algorithm

Whiteboard
DPV §5.1
F
2/24

Minimum Spanning Trees

Whiteboard
DPV §5.1
7
 M
2/27

Midterm 1

 DPV §6
Section 6 ,
Solutions
HW 6 ,
Solutions
W
3/1

Dynamic Programming (Part I)

Whiteboard
DPV §6
F
3/3

Dynamic Programming (Part II)

Whiteboard
DPV §6
8
 M
3/6

Dynamic Programming (Part III)
Knapsack, SSSP

Whiteboard
DPV §6
Section 7
HW 7
W
3/8

Dynamic Programming (Part III continued)
APSP, TSP, Independent Sets

Whiteboard
DPV §6
F
3/10

Linear Programming

Whiteboard
DPV §7.2
9
 M
3/13

Algorithms to Linear Programming, Simplex Algorithm
Max Flow

Whiteboard
DPV §7.2 , §7.6
Section 8
HW 8
W
3/15

Network Flow, Bipartite Matching

Whiteboard
DPV §7.2
F
3/17

Network Flow(Continued), Duality

Whiteboard
DPV §7.2
10
 M
3/20

Duality, Zero Sum Games

Whiteboard
DPV §7.4 , §7.5
Section 9
HW 9
W
3/22

Zero Sum Games (Continued), Multiplicative Updates

Notes
Whiteboard
DPV §7.3
F
3/24

Reductions, Bipartite Matching, Search Problems

 DPV §7.3 , §8.1
11
 M
3/27

Spring Recess
Section 10
W
3/29

Spring Recess
F
3/31

Spring Recess
César Chávez Day
12
 M
4/3

NP-Completeness

 DPV §8.2
Section 11
HW 10
W
4/5

Midterm 2
F
4/7

Reductions

 DPV §8.3
13
 M
4/10

Reductions

 DPV §8.3
Section 12
HW 11
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 12
W
4/19

Randomized Algorithms

Notes
DPV §1.3 , §1.5
F
4/21

Streaming

Notes
15
 M
4/24

Sketching, Streaming

Notes
HW 13
W
4/26

Sketching, Streaming

Notes
F
4/28

Special Topics