Efficient Algorithms and Intractable Problems

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

Lecture: Tu/Th 9:30 am - 11:00 am
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

Recordings of all lectures past the first four are posted on bCourses.
Week Date Lecture Reading Section Videos Assignments
1
Tu
1/18

Introduction, big-O notation, arithmetic

webcast
DPV §0 , §1.1
Th
1/20

Divide-and-Conquer (Part I)

webcast
DPV §2.1 , §2.2 , §2.3
2
Tu
1/25

Divide-and-Conquer (Part II)

webcast
DPV §2.4 , §2.5 , §2.6
Th
1/27

Fast Fourier Transform

webcast
DPV §2.6
3
Tu
2/1

Decompositions of graphs

DPV §3
Th
2/3

Paths in graphs (Part I)

DPV §4.1 , §4.2 , §4.3 , §4.4
4
Tu
2/8

Paths in graphs (Part II)

Prof. Wright's notes
DPV §4.4 , §4.5 , §4.6 , §4.7
Th
2/10

Greedy Algorithms

Prof. Wright's notes
DPV §5 , §5.4
5
Tu
2/15

Minimum Spanning Trees

Prof. Wright's notes
DPV §5.1
Th
2/17

Union Find

Prof. Wright's notes
DPV §5.1.4
6
Tu
2/22

Dynamic Programming (Part I)

Prof. Wright's notes
DPV §6
Th
2/24

Dynamic Programming (Part II)

Prof. Wright's notes
DPV §6
7
Tu
3/1

Dynamic Programming (Part III)

Prof. Wright's notes
DPV §6
Th
3/3

Dynamic Programming (Part IV)

Prof. Raghavendra's notes
DPV §7.1
8
Tu
3/8

Linear Programming

Prof. Raghavendra's notes
DPV §7.2
Th
3/10

Network Flow + Bipartite Matching

Prof. Raghavendra's notes
DPV §7.4
9
Tu
3/15

Duality + Zero-Sum Games

Prof. Raghavendra's notes
DPV §7.5
Th
3/17

Multiplicative Updates

Prof. Raghavendra's notes
notes
10
Tu
3/22

Spring Break

Th
3/24

Spring Break

11
Tu
3/29

Reductions, Bipartite Matching

Prof. Raghavendra's notes
DPV §7.3
Th
3/31

Search Problems

Prof. Raghavendra's notes
DPV §8.1
12
Tu
4/5

Midterm 2

Th
4/7

NP-Completeness

Prof. Raghavendra's notes
DPV §8.2 , §8.3
13
Tu
4/12

Coping with NP-completeness

Prof. Raghavendra's notes
DPV §9
Th
4/14

Streaming

Prof. Raghavendra's notes
DPV §1.2 , §1.3 notes
14
Tu
4/19

Sketching, Streaming

Prof. Wright's notes
DPV §1.5
Th
4/21

Cancelled

15
Tu
4/26

Randomized Algorithms

Prof. Wright's notes
DPV §1.3 notes §3
Th
4/28

Quantum Algorithms

Prof. Wright's notes (Part 1)
Prof. Wright's notes (Part 2)