Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Prasad Raghavendra & Satish Rao, Fall 2019

Lecture: M/W/F 4:00-5:00 pm, Dwinelle 155
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

Week Date Lecture Reading Section Assignments
1
Mon
8/26
Wed
8/26

Intro, O() notation, Integer multiplication

slides, 6up, handout, fib.py webcast
DPV §0 , §2.1
Fri
8/30

Matrix multiplication, Master theorem

slides, 6up, handout, karat.py webcast
DPV §2.2 , §2.5
2
Mon
9/2
Labor Day
Wed
9/4

Linear-time Median

slides, 6up, handout webcast
DPV §2.4 , §2.5
Fri
9/6

Fast Fourier Transform I

slides webcast
DPV §2.6
3
Mon
9/9

Fast Fourier Transform II

slides webcast
DPV §2.6
Wed
9/11

Fast Fourier Transform III, Graphs I

slides, 6up, handout webcast
DPV §2.6 , §3.1
Fri
9/13

DFS, DAG, Linearization

slides, 6up, handout webcast
DPV §3
4
Mon
9/16

Strongly Connected Components

slides, 6up, handout webcast
DPV §3
Wed
9/18

Shortest paths I

slides, 6up, handout webcast
DPV §3
Fri
9/20

Shortest paths II

DPV §3
5
Mon
9/23

Greedy algorithms, MST

DPV §5
Wed
9/25

Greedy algorithms, MST, Huffman encoding

DPV §5
Fri
9/27

Greedy Algorithms, Huffman Encoding

DPV §5
6
Mon
9/30
Midterm 1 on Mon 9/30 (No lecture)
Wed
10/2

Dynamic Programming I

DPV §6
Fri
10/4

Dynamic Programming II

DPV §6
7
Mon
10/7

Dynamic Programming III

DPV §6
Wed
10/9

Dynamic Programming IV

DPV §6
Fri
10/11

Dynamic Programming V

DPV §6
8
Mon
10/14

Linear Programming

DPV §7.1
Wed
10/16

Simplex and Duality

DPV §7.4 , §7.6
Fri
10/18

Network Flow & Matching I

DPV §7.3
9
Mon
10/21

Network Flow & Matching II

DPV §7.3
Wed
10/23

Zero Sum Games

DPV §7.5
Fri
10/25

Multiplicative Weights I

10
Mon
10/28

Multiplicative Weights II

Wed
10/30

Search Problems, Complexity Theory

DPV §8
Fri
11/1

Reductions

DPV §8
11
Mon
11/4

NP-completeness

DPV §8
Wed
11/6
Midterm 2 on Thu 11/7 (No Lecture)
Fri
11/8

Coping with NP-completeness I

DPV §9
12
Mon
11/11
Veterans' Day
Wed
11/13

Coping with NP-completeness II

DPV §9
Fri
11/15

Coping with NP-completeness III

DPV §9
13
Mon
11/18

Special Topics


Wed
11/20

Special Topics

Fri
11/22

Special Topics

14
Mon
11/25

Special Topics


Wed
11/27
Thanksgiving
Fri
11/29
Thanksgiving
15
Mon
12/2

Special Topics


Wed
12/4

Special Topics

Fri
12/6

Special Topics