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

Piazza 1

Piazza 2

Mon
8/26
Section 1,
solutions
HW 1,
solutions
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
Section 2,
solutions
HW 2,
solutions
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

Piazza 3

Piazza 4

Mon
9/9

Fast Fourier Transform II

slides webcast 		DPV §2.6
Section 3,
solutions
HW 3,
solutions
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

Piazza 5

Piazza 6

Mon
9/16

Strongly Connected Components

slides , 6up , handout webcast 		DPV §3
Section 4,
solutions
HW 4,
solutions
Wed
9/18

Shortest paths I

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

Shortest paths II

slides , 6up , handout webcast 		DPV §4
5

Piazza 7

Mon
9/23

Greedy algorithms, MST

slides , 6up , handout webcast 		DPV §5
Section 5,
solutions
HW 5,
solutions
Wed
9/25

Greedy algorithms, MST, Huffman encoding

slides , 6up , handout webcast 		DPV §5
Fri
9/27

Greedy Algorithms, Huffman Encoding

slides , 6up , handout webcast 		DPV §5
6

Piazza 8

Mon
9/30 		Midterm 1 on Mon 9/30 (No lecture)
Section 6,
solutions
HW 6,
solutions
Wed
10/2

Dynamic Programming I

slides webcast 		DPV §6
Fri
10/4

Dynamic Programming II

slides webcast 		DPV §6
7
 Mon
10/7

Dynamic Programming III

slides webcast 		DPV §6
Section 7,
solutions
HW 7,
solutions
Wed
10/9 		No lecture - classes cancelled
Fri
10/11 		No lecture - classes cancelled
8

Piazza 9

Mon
10/14

Dynamic Programming IV

shorter webcast (same content) webcast 		DPV §6
Section 8,
solutions
HW 8,
solutions
Wed
10/16

Dynamic Programming V

 DPV §6
Fri
10/18

Linear Programming

 DPV §7.1
9
 Mon
10/21

Simplex and Duality

 DPV §7.4 , §7.6
Section 9,
solutions
HW 9,
solutions
Wed
10/23

Network Flow & Matching I

 DPV §7.3
Fri
10/25

Network Flow & Matching II

 DPV §7.3
10
 Mon
10/28

Zero Sum Games

 DPV §7.5
Section 10,
solutions
HW 10,
solutions
Wed
10/30

Multiplicative Weights I
Fri
11/1

Multiplicative Weights II
11
 Mon
11/4

Search Problems, Complexity Theory

 DPV §8
HW 11,
solutions

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

Reductions

 DPV §8
12
 Mon
11/11 		Veterans' Day
Section 11,
solutions
HW 12,
solutions

Project
Wed
11/13

NP-completeness

 DPV §8
Fri
11/15

Coping with NP-completeness I

 DPV §9
13
 Mon
11/18

Coping with NP-completeness II

 DPV §9
Section 12,
solutions
HW 13,
solutions

Project
Wed
11/20

Coping with NP-completeness III

 DPV §9
Fri
11/22

Special Topics
14
 Mon
11/25

Special Topics
HW 14,
solutions

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

Special Topics
Section 13,
solutions
HW 15,
solutions

Project
Wed
12/4

Special Topics
Fri
12/6

Special Topics