Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley, Fall 2024

Prasad Raghavendra, Sanjam Garg

Lecture: TuTh 2:00pm - 3:30pm, Valley Life Sciences Building 2050
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
Jump to current week

PnPenguin logo
Note: This content schedule for Fall 2024 is subject to change.
Week Date Lecture Resources Readings Discussion Homework
1
Tue
8/27

No lecture

Thu
8/29

Introduction, Big-O Notation, Recurrence Relations

recording
Lecture Notes DPV §0.2 , §0.3 , §2.1 , §2.2
2
Tue
9/3

Integer Multiplication, Recurrence relations, Master Theorem

recording
Lecture Notes DPV §2.3 , §2.4 , §2.5
Thu
9/5

Matrix Multiplication, Median Finding

recording
Lecture Notes DPV §2.3 , §2.4 , §2.5
3
Tue
9/10

Quickselect, Divide and Conquer Examples

recording
Lecture Notes DPV §2.3 , §2.4 , §2.5
Thu
9/12

DFS, Topological sort

recording
Lecture Notes DPV §3.1 , §3.2 , §3.3
4
Tue
9/17

Strongly Connected Components

recording
Lecture Notes DPV §3.4
Thu
9/19

Paths in Graphs

recording
Lecture Notes DPV §4.1 , §4.2 , §4.3 , §4.4 , §4.6
5
Tue
9/24

Greedy Algorithms

recording
Lecture Notes DPV §5.2 , §5.3
Thu
9/26

Minimum Spanning Trees

recording
Lecture Notes DPV §5.1
6
Tue
10/1

No lecture

Wed
10/2

Midterm 1 (7 - 9 pm)

Thu
10/3

Dynamic Programming (Part 1)

recording
Lecture Notes DPV §6
7
Tue
10/8

Dynamic Programming (Part 2)

recording
Lecture Notes DPV §6
Thu
10/10

Dynamic Programming (Part 3)

recording
Lecture Notes DPV §6
8
Tue
10/15

Dynamic Programming (Part 4)

recording
Lecture Notes DPV §6
Thu
10/17

Linear Programming, Simplex Algorithm

recording
Lecture Notes DPV §7.1
9
Tue
10/22

Duality, Zero-Sum Games

recording
Lecture Notes DPV §7.4 , §7.5
Thu
10/24

Network Flow, Bipartite Matching (Part 1)

recording
Lecture Notes DPV §7.2
10
Tue
10/29

Network Flow, Bipartite Matching (Part 2)

recording
Lecture Notes DPV §7.2
Thu
10/31

Solving LP Feasibility

recording
Lecture Notes
11
Tue
11/5

No lecture; Midterm 2 (7 - 9 pm)

Thu
11/7

Reductions, Search Problems

recording
Lecture Notes DPV §8.1
12
Tue
11/12

NP-Completeness

DPV §8.3
Thu
11/14

Reductions

DPV §8.2
13
Tue
11/19

Coping with NP-Completeness (Part 1)

DPV §9
Thu
11/21

Coping with NP-Completeness (Part 2)

DPV §9
14
Tue
11/26

TBD

Thu
11/28

Thanksgiving Break

15
Tue
12/3

TBD

Thu
12/5

TBD

16
Tue
12/10

RRR Week

Thu
12/12

RRR Week

17
Tue
12/17

Final Exam (8 - 11 am)