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 ,
Solutions
HW 7 ,
Solutions
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 ,
Solutions
HW 8 ,
Solutions
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 ,
Solutions
HW 9 ,
Solutions
W
3/22

Zero Sum Games (Continued), Multiplicative Updates

Notes
Whiteboard
DPV §7.3
F
3/24

Zero Sum Games (Continued), Multiplicative Updates

Notes
Whiteboard
DPV §7.3
11
 M
3/27

Spring Recess
W
3/29

Spring Recess
F
3/31

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

Search Problems, NP-Completeness

Whiteboard
DPV §8.1 , §8.2
Section 10 ,
Solutions
HW 10 ,
Solutions
W
4/5

Midterm 2
F
4/7

Reductions

Whiteboard
DPV §8.3
13
 M
4/10

Reductions

Whiteboard
DPV §8.3
Section 11 ,
Solutions
HW 11 ,
Solutions
W
4/12

Reductions

Whiteboard
DPV §8.3
F
4/14

Coping with NP-completeness

Whiteboard
DPV §9
14
 M
4/17

Coping with NP-completeness, Approximation

Whiteboard
DPV §9
Section 12 ,
Solutions
HW 12 ,
Solutions
W
4/19

Approximation II

Whiteboard
DPV §9
F
4/21

Approximation III

Whiteboard
DPV §9
15
 M
4/24

Approximation Wrap-Up, Sampling, Sketching, Streaming

Notes
Whiteboard
Section 13 ,
Solutions
HW 13 ,
Solutions
W
4/26

Sketching, Streaming

Notes
F
4/28

Special Topics