Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson, Fall 2021

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

Announcements:
  • Piazza signup link. You can find the zoom link in Piazza.
  • If you'd like to go to in-person lecture, please sign up first.
  • Prof. Nelson's Office Hours: Mondays 7:45-9:45am. Starts 9/13 since 9/6 is holiday.
Jump to current week
Week Date Lecture Reading Section Videos Assignments
1
 Tu
8/24
HW 0,
solutions
Th
8/26

Introduction, big-O notation, arithmetic

webcast
Prof. Nelson's notes
DPV §0 , §1.1
2
 Tu
8/31

Divide-and-Conquer (Part I)

webcast
DPV §2.1 , §2.2 , §2.3
Section 1,
solutions
Section 1 walkthrough
Week 2 mini-lecture

HW 1,
solutions
HW 1 walkthrough
Th
9/2

Divide-and-Conquer (Part II)

webcast
DPV §2.4 , §2.5 , §2.6
3
 Tu
9/7

Fast Fourier Transform

webcast
Prof. Nelson's notes
DPV §2.6
Section 2,
solutions
Section 2 walkthrough
Mini-lecture & FFT walkthrough
Coding for divide-and-conquer
HW 2,
solutions
HW 2 walkthrough
Th
9/9

Decompositions of graphs

webcast
Prof. Nelson's notes
DPV §3
4
 Tu
9/14

Paths in graphs (Part I)

webcast
DPV §4.1 , §4.2 , §4.3 , §4.4
Section 3,
solutions
Section 3 walkthrough
Week 4 mini-lecture

HW 3,
solutions
Th
9/16

Paths in graphs (Part II)

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

Minimum Spanning Trees

 DPV §5.1
Section 4,
solutions
HW 4,
solutions
Th
9/23

Greedy Algorithms

 DPV §5 , §5.4
6
 Tu
9/28

Union Find

 DPV §5.1.4
Th
9/30

Dynamic Programming (Part I)

 DPV §6
7
 Tu
10/5

Midterm 1
Th
10/7

Dynamic Programming (Part II)

 DPV §6
8
 Tu
10/12

Linear Programming

 DPV §7.1
Th
10/14

Network Flow (Part I)

 DPV §7.2 , §7.4
9
 Tu
10/19

Network Flow (Part II)

 DPV §7.2 , §7.4
Th
10/21

Zero-Sum Games

 DPV §7.5
10
 Tu
10/26

Multiplicative Updates

 notes
Th
10/28

Reductions, Bipartite Matching

 DPV §7.3
11
 Tu
11/2

Midterm 2
Th
11/4

Search Problems

 DPV §8.1
12
 Tu
11/9

NP-Completeness

 DPV §8.2 , §8.3
Th
11/11

No Class (Veterans Day)
13
 Tu
11/16

Coping with NP-completeness

 DPV §9
Th
11/18

Randomized Algorithms

 notes
14
 Tu
11/23

Sketching, Streaming

 notes
Th
11/25

No Class (Thanksgiving)
15
 Tu
11/30

Lower Bounds

 notes
Th
12/2

Hashing

 DPV §1.5