Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson and James W. Demmel, Fall 2022

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

The lectures playlist can be found here on Youtube. Please refer to the playlist for the most up-to-date lectures available.

Week Date Lecture Reading Section Assignments
1
Tu
8/23

No lecture

Th
8/25

Introduction, Big-O Notation, Arithmetic

webcast Python's Karatsuba
Code
DPV §0 , §1.1
2
Tu
8/30

Divide-and-Conquer (Part I)

webcast Code
DPV §2.1 , §2.2 , §2.3
Th
9/1

Divide-and-Conquer (Part II)

webcast Code
DPV §2.4 , §2.5 , §2.6
3
Tu
9/6

Fast Fourier Transform

webcast Code
DPV §2.6
Th
9/8

Graph decomposition

webcast Code
DPV §3
4
Tu
9/13

Paths in graphs (Part I)

webcast Code
DPV §4.1 , §4.2 , §4.3 , §4.4
Th
9/15

Paths in graphs (Part II)

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

Minimum Spanning Trees

webcast Code
DPV §5.1
HW 4

due 9/26

Th
9/22

Greedy Algorithms

webcast Code
DPV §5 , §5.4
6
Tu
9/27

Union Find

webcast
DPV §5.1.4
HW 5

(OPTIONAL)

Th
9/29

Dynamic Programming (Part I)

webcast Code
DPV §6
7
Tu
10/4

Midterm 1

HW 6

due 10/11

Th
10/6

Dynamic Programming (Part II)

webcast Code
DPV §6
8
Tu
10/11

Linear Programming

webcast
DPV §7.2
HW 7

due 10/17

Th
10/13

Network Flow (Part I)

webcast Code
DPV §7.2
9
Tu
10/18

Network Flow (Part II)

webcast Code
DPV §7.2
HW 8

due 10/24

Th
10/20

Zero-Sum Games

webcast
DPV §7.5
10
Tu
10/25

Multiplicative Updates

webcast Notes
HW 9

(OPTIONAL)

Th
10/27

Reductions, Bipartite Matching

webcast
DPV §7.3
11
Tu
11/1

Midterm 2

HW 10

due 11/7

Th
11/3

Search Problems

webcast
DPV §8.1
12
Tu
11/8

NP-Completeness

webcast
DPV §8.2 , §8.3
HW 11

due 11/14


Th
11/10

Coping with NP-completeness

webcast
DPV §9
13
Tu
11/15

Randomized Algorithms

webcast Notes
DPV §1.3
HW 12

(OPTIONAL)


Th
11/17

Hashing

webcast Break Python dict
Python dict
DPV §1.5
14
Tu
11/22

Sketching, Streaming

webcast

Th
11/24

Thanksgiving

15
Tu
11/29

Lower bounds

webcast

Th
12/1

(Special topic) Spectral Graph Theory

webcast