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)

Announcements:
    Lecture is at this Zoom Link for the first two weeks!
Week Date Lecture Reading Section 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)

Zoom Link
DPV §2.4 , §2.5 , §2.6
Th
1/27

Fast Fourier Transform

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)

DPV §4.4 , §4.5 , §4.6 , §4.7
Th
2/10

Greedy Algorithms

DPV §5 , §5.4
5
Tu
2/15

Minimum Spanning Trees

DPV §5.1
Th
2/17

Union Find

DPV §5.1.4
6
Tu
2/22

Dynamic Programming (Part I)

DPV §6
Th
2/24

Dynamic Programming (Part II)

DPV §6
7
Tu
3/1

Dynamic Programming (Part III)

DPV §6
Th
3/3

Linear Programming

DPV §7.1
8
Tu
3/8

Network Flow

DPV §7.2
Th
3/10

Duality

DPV §7.4
9
Tu
3/15

Zero-Sum Games

DPV §7.5
Th
3/17

Multiplicative Updates

notes
10
Tu
3/22

Spring Break

Th
3/24

Spring Break

11
Tu
3/29

Reductions, Bipartite Matching

DPV §7.3
Th
3/31

Search Problems

DPV §8.1
12
Tu
4/5

Midterm 2

Th
4/7

NP-Completeness

DPV §8.2 , §8.3
13
Tu
4/12

Coping with NP-completeness

DPV §9
Th
4/14

Randomized Algorithms

DPV §1.2 , §1.3 notes
14
Tu
4/19

Sketching, Streaming

DPV §1.5 notes
Th
4/21

Hashing

15
Tu
4/26

Special Topic

Th
4/28

Special Topic