CS 170

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

The lectures playlist can be found here on Youtube. Please refer to the playlist for the most up-to-date lectures available.

Week	Date	Lecture	Reading	Section	Assignments
1	Tu 8/23	No lecture
1	Th 8/25	Introduction, Big-O Notation, Arithmetic webcast Python's Karatsuba Code	DPV §0 , §1.1
2	Tu 8/30	Divide-and-Conquer (Part I) webcast Code	DPV §2.1 , §2.2 , §2.3	Section 1	HW 1
2	Th 9/1	Divide-and-Conquer (Part II) webcast Code	DPV §2.4 , §2.5 , §2.6	Section 1	HW 1
3	Tu 9/6	Fast Fourier Transform webcast Code	DPV §2.6	Section 2	HW 2
3	Th 9/8	Graph decomposition webcast Code	DPV §3	Section 2	HW 2
4	Tu 9/13	Paths in graphs (Part I) webcast Code	DPV §4.1 , §4.2 , §4.3 , §4.4	Section 3	HW 3
4	Th 9/15	Paths in graphs (Part II) webcast Code	DPV §4.4 , §4.5 , §4.6 , §4.7	Section 3	HW 3
5	Tu 9/20	Minimum Spanning Trees webcast Code	DPV §5.1	Section 4	HW 4 due 9/26
5	Th 9/22	Greedy Algorithms webcast Code	DPV §5 , §5.4	Section 4	HW 4 due 9/26
6	Tu 9/27	Union Find webcast	DPV §5.1.4	Section 5	HW 5 (OPTIONAL)
6	Th 9/29	Dynamic Programming (Part I) webcast Code	DPV §6	Section 5	HW 5 (OPTIONAL)
7	Tu 10/4	Midterm 1		Section 6	HW 6 due 10/11
7	Th 10/6	Dynamic Programming (Part II) webcast Code	DPV §6	Section 6	HW 6 due 10/11
8	Tu 10/11	Linear Programming webcast	DPV §7.2	Section 7	HW 7 due 10/17
8	Th 10/13	Network Flow (Part I) webcast Code	DPV §7.2	Section 7	HW 7 due 10/17
9	Tu 10/18	Network Flow (Part II) webcast Code	DPV §7.2	Section 8	HW 8 due 10/24
9	Th 10/20	Zero-Sum Games webcast	DPV §7.5	Section 8	HW 8 due 10/24
10	Tu 10/25	Multiplicative Updates webcast Notes		Section 9	HW 9 (OPTIONAL)
10	Th 10/27	Reductions, Bipartite Matching webcast	DPV §7.3	Section 9	HW 9 (OPTIONAL)
11	Tu 11/1	Midterm 2		Section 10	HW 10 due 11/7
11	Th 11/3	Search Problems webcast	DPV §8.1	Section 10	HW 10 due 11/7
12	Tu 11/8	NP-Completeness webcast	DPV §8.2 , §8.3	Section 11	HW 11 due 11/14 Project
12	Th 11/10	Coping with NP-completeness webcast	DPV §9	Section 11	HW 11 due 11/14 Project
13	Tu 11/15	Randomized Algorithms webcast Notes	DPV §1.3	Section 12	HW 12 (OPTIONAL) Project
13	Th 11/17	Hashing webcast Break Python dict Python dict	DPV §1.5	Section 12	HW 12 (OPTIONAL) Project
14	Tu 11/22	Sketching, Streaming webcast			Project
14	Th 11/24	Thanksgiving			Project
15	Tu 11/29	Lower bounds webcast			Project
15	Th 12/1	(Special topic) Spectral Graph Theory webcast			Project

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson and James W. Demmel, Fall 2022