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:
  • Discussion 5 walkthrough is posted!
  • Week 6 mini-lecture is posted!
  • Homework 5 walkthrough is posted!
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
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)

DPV §6
Th
3/4

Linear Programming

DPV §7.1
8
Tu
3/9

Network Flow

DPV §7.2
Th
3/11

Duality

DPV §7.4
9
Tu
3/16

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

Th
3/18

Zero-Sum Games

DPV §7.5
10
Tu
3/23

Spring Break!

Th
3/25

Spring Break!

11
Tu
3/30

Multiplicative Updates

notes
Th
4/1

Reductions, Bipartite Matching

DPV §7.3
12
Tu
4/6

Search Problems

DPV §8.1
Th
4/8

NP-Completeness

DPV §8.2 , §8.3
13
Tu
4/13

Coping with NP-completeness

DPV §9
Th
4/15

Randomized Algorithms

DPV §1.2 , §1.3
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