Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson, Fall 2021

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

Announcements:
    Midterm 2 is on Tuesday Nov 2nd, 7-9pm
Week Date Lecture Reading Section Videos Assignments
1
Tu
8/24
Th
8/26

Introduction, big-O notation, arithmetic

webcast
Prof. Nelson's notes
DPV §0 , §1.1
2
Tu
8/31

Divide-and-Conquer (Part I)

webcast
DPV §2.1 , §2.2 , §2.3
Th
9/2

Divide-and-Conquer (Part II)

webcast
DPV §2.4 , §2.5 , §2.6
3
Tu
9/7

Fast Fourier Transform

webcast
Prof. Nelson's notes
DPV §2.6
Th
9/9

Decompositions of graphs

webcast
Prof. Nelson's notes
DPV §3
4
Tu
9/14

Paths in graphs (Part I)

webcast
DPV §4.1 , §4.2 , §4.3 , §4.4
Th
9/16

Paths in graphs (Part II)

webcast
DPV §4.4 , §4.5 , §4.6 , §4.7
5
Tu
9/21

Minimum Spanning Trees

webcast
DPV §5.1
Th
9/23

Greedy Algorithms

webcast
DPV §5 , §5.4
6
Tu
9/28

Union Find

webcast
DPV §5.1.4
Th
9/30

Dynamic Programming (Part I)

webcast
DPV §6
7
Tu
10/5

Midterm 1

Th
10/7

Dynamic Programming (Part II)

webcast
DPV §6 Jupyter Notebook
8
Tu
10/12

Linear Programming

webcast
DPV §7.1
Th
10/14

Network Flow (Part I)

webcast
DPV §7.2 , §7.4
9
Tu
10/19

Network Flow (Part II)

webcast
DPV §7.2 , §7.4
Th
10/21

Zero-Sum Games

webcast
DPV §7.5
10
Tu
10/26

Multiplicative Updates

webcast
notes
Th
10/28

Reductions, Bipartite Matching

webcast
DPV §7.3
11
Tu
11/2

Midterm 2


Th
11/4

Search Problems

webcast
DPV §8.1
12
Tu
11/9

NP-Completeness

webcast
DPV §8.2 , §8.3
Th
11/11

No Class (Veterans Day)

13
Tu
11/16

Coping with NP-completeness

webcast
DPV §9
Th
11/18

Randomized Algorithms

webcast
notes
14
Tu
11/23

Hashing

webcast
DPV §1.5
Th
11/25

No Class (Thanksgiving)

15
Tu
11/30

Sketching, Streaming

notes
Th
12/2

Lower Bounds

notes