Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Alessandro Chiesa and James Demmel, Spring 2021

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

Announcements:
Jump to current week
Week Date Lecture Reading Section Videos Assignments
1
Tu
1/19

Introduction, big-O notation, arithmetic

webcast | youtube mirror
Password: $t*x9h*^
Prof. Chiesa's notes
DPV §0 , §1.1
Th
1/21

Divide-and-Conquer (Part I)

webcast | youtube mirror
Password: 4xr@=yrr
Prof. Chiesa's notes
DPV §2.1 , §2.2 , §2.3
2
Tu
1/26

Divide-and-Conquer (Part II)

webcast | youtube mirror
Password: .6XiwsPg
Prof. Chiesa's notes
DPV §2.4 , §2.5 , §2.6
Th
1/28

Fast Fourier Transform

webcast | youtube mirror
Password: xswe&CN3
Prof. Chiesa's notes
DPV §2.6
3
Tu
2/2

Decompositions of graphs

webcast | youtube mirror
Password: P%4T@dCS
Prof. Chiesa's notes
DPV §3
Th
2/4

Paths in graphs (Part I)

webcast | youtube mirror
Password: VIY$L&n4
Prof. Chiesa's notes
DPV §4.1 , §4.2 , §4.3 , §4.4
4
Tu
2/9

Paths in graphs (Part II)

webcast | youtube mirror
Password: %b5wLL*8
Prof. Demmel's notes
DPV §4.4 , §4.5 , §4.6 , §4.7
Th
2/11

Greedy Algorithms

webcast | youtube mirror
Password: *q7QQBr*
Prof. Demmel's notes
DPV §5 , §5.4
5
Tu
2/16

Minimum spanning trees

webcast | youtube mirror
Password: @AB3?uJ%
Prof. Demmel's notes
DPV §5.1
Th
2/18

Midterm 1 (9:00am - 11:00am PST)

Midterm prep
Midterm prep sols
Midterm walkthrough
6
Tu
2/23

Huffman encoding and Horn formulas

webcast | youtube mirror
Password: @?YUZ#s8
Prof. Demmel's notes
DPV §5.2 , §5.3
Th
2/25

Dynamic Programming (Part I)

webcast | youtube mirror
Password: 2?KtSy4G
Prof. Demmel's notes
DPV §6
7
Tu
3/2

Dynamic Programming (Part II)

webcast | youtube mirror
Password: d18wP=A*
Prof. Chiesa's notes
DPV §6
Th
3/4

Linear Programming

webcast | youtube mirror
Password: 6yk%#q4s
Prof. Chiesa's notes
DPV §7.1
8
Tu
3/9

Network Flow

webcast | youtube mirror
Password: $3Apdj1s
Prof. Chiesa's notes
DPV §7.2
Th
3/11

Duality

webcast | youtube mirror
Password: &EujG0Tm
Prof. Chiesa's notes
DPV §7.4
9
Tu
3/16

Midterm 2 (9:00am - 11:00am PST)


Th
3/18

Zero-Sum Games

webcast | youtube mirror
Password: h65@Om$#
Prof. Demmel's notes
(pre-lec)

Prof. Demmel's notes
(post-lec)

DPV §7.5
10
Tu
3/23

Spring Break!

Th
3/25

Spring Break!

11
Tu
3/30

Multiplicative Updates

webcast | youtube mirror
Password: G!A&97A%
Prof. Chiesa's notes
notes
Th
4/1

Reductions, Bipartite Matching

webcast
Password: @M7ss1@G
Prof. Demmel's notes
(post-lec)

Prof. Demmel's notes
(pre-lec)

DPV §7.3
12
Tu
4/6

Search Problems

webcast
Password: 2!Q0d%3w
Prof. Demmel's notes
(post-lec)

Prof. Demmel's notes
(pre-lec)

DPV §8.1
Th
4/8

NP-Completeness

webcast | youtube mirror
Password: =M%2s.ms
Prof. Demmel's notes
(post-lec)

Prof. Demmel's notes
(pre-lec)

DPV §8.2 , §8.3
13
Tu
4/13

Coping with NP-completeness

webcast
Password: 7%HN@S5a
Prof. Chiesa's notes
DPV §9

Th
4/15

Randomized Algorithms

webcast
Password: .PUyb^8G
Prof. Demmel's notes
(post-lec)

Prof. Demmel's notes
(pre-lec)

notes
14
Tu
4/20

Sketching, Streaming

DPV §1.5 notes
Th
4/22

Lower Bounds

15
Tu
4/27

Hashing

DPV §1.5
Th
4/29

Interactive Proofs (special topic)

Final time: Wednesday 5/12, 11:30am - 2:30pm PST