CS 170

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

Week	Date	Lecture	Reading	Section	Videos	Assignments
1	Tu 1/18	Introduction, big-O notation, arithmetic webcast	DPV §0 , §1.1			HW 0, solutions HW 0 walkthrough
1	Th 1/20	Divide-and-Conquer (Part I) webcast	DPV §2.1 , §2.2 , §2.3			HW 0, solutions HW 0 walkthrough
2	Tu 1/25	Divide-and-Conquer (Part II) webcast	DPV §2.4 , §2.5 , §2.6	Section 1, solutions Section 1 walkthrough	Week 2 mini-lecture	HW 1, solutions HW 1 walkthrough
2	Th 1/27	Fast Fourier Transform webcast	DPV §2.6	Section 1, solutions Section 1 walkthrough	Week 2 mini-lecture	HW 1, solutions HW 1 walkthrough
3	Tu 2/1	Decompositions of graphs	DPV §3	Section 2, solutions Section 2 walkthrough	Week 3 mini-lecture	HW 2, solutions HW 2 walkthrough
3	Th 2/3	Paths in graphs (Part I)	DPV §4.1 , §4.2 , §4.3 , §4.4	Section 2, solutions Section 2 walkthrough	Week 3 mini-lecture	HW 2, solutions HW 2 walkthrough
4	Tu 2/8	Paths in graphs (Part II) Prof. Wright's notes	DPV §4.4 , §4.5 , §4.6 , §4.7	Section 3, solutions Section 3 walkthrough	Week 4 mini-lecture	HW 3, solutions HW 3 walkthrough
4	Th 2/10	Greedy Algorithms Prof. Wright's notes	DPV §5 , §5.4	Section 3, solutions Section 3 walkthrough	Week 4 mini-lecture	HW 3, solutions HW 3 walkthrough
5	Tu 2/15	Minimum Spanning Trees Prof. Wright's notes	DPV §5.1	Section 4, solutions Section 4 walkthrough	Week 5 mini-lecture	HW 4, solutions HW 4 walkthrough
5	Th 2/17	Union Find Prof. Wright's notes	DPV §5.1.4	Section 4, solutions Section 4 walkthrough	Week 5 mini-lecture	HW 4, solutions HW 4 walkthrough
6	Tu 2/22	Dynamic Programming (Part I) Prof. Wright's notes	DPV §6		Week 6 mini-lecture	HW 5, solutions HW 5 walkthrough
6	Th 2/24	Dynamic Programming (Part II) Prof. Wright's notes	DPV §6		Week 6 mini-lecture	HW 5, solutions HW 5 walkthrough
7	Tu 3/1	Dynamic Programming (Part III) Prof. Wright's notes	DPV §6	Section 6, solutions Section 6 walkthrough	Week 7 mini-lecture	HW 6, solutions HW 6 walkthrough
7	Th 3/3	Dynamic Programming (Part IV) Prof. Raghavendra's notes	DPV §7.1	Section 6, solutions Section 6 walkthrough	Week 7 mini-lecture	HW 6, solutions HW 6 walkthrough
8	Tu 3/8	Linear Programming Prof. Raghavendra's notes	DPV §7.2	Section 7, solutions Section 7 walkthrough		HW 7, solutions HW 7 walkthrough
8	Th 3/10	Network Flow + Bipartite Matching Prof. Raghavendra's notes	DPV §7.4	Section 7, solutions Section 7 walkthrough		HW 7, solutions HW 7 walkthrough
9	Tu 3/15	Duality + Zero-Sum Games Prof. Raghavendra's notes	DPV §7.5	Section 8, solutions Section 8 walkthrough		HW 8, solutions
9	Th 3/17	Multiplicative Updates Prof. Raghavendra's notes	notes	Section 8, solutions Section 8 walkthrough		HW 8, solutions
10	Tu 3/22	Spring Break
10	Th 3/24	Spring Break
11	Tu 3/29	Reductions, Bipartite Matching Prof. Raghavendra's notes	DPV §7.3	Section 9, solutions		HW 9, solutions
11	Th 3/31	Search Problems Prof. Raghavendra's notes	DPV §8.1	Section 9, solutions		HW 9, solutions
12	Tu 4/5	Midterm 2				HW 10, solutions
12	Th 4/7	NP-Completeness Prof. Raghavendra's notes	DPV §8.2 , §8.3			HW 10, solutions
13	Tu 4/12	Coping with NP-completeness Prof. Raghavendra's notes	DPV §9	Section 11, solutions		HW 11, solutions Project
13	Th 4/14	Streaming Prof. Raghavendra's notes	DPV §1.2 , §1.3 notes	Section 11, solutions		HW 11, solutions Project
14	Tu 4/19	Sketching, Streaming Prof. Wright's notes	DPV §1.5	Section 12, solutions		HW 12, solutions Project
14	Th 4/21	Cancelled		Section 12, solutions		HW 12, solutions Project
15	Tu 4/26	Randomized Algorithms Prof. Wright's notes	DPV §1.3 notes §3	Section 13, solutions		HW 13, solutions Project
15	Th 4/28	Quantum Algorithms Prof. Wright's notes (Part 1) Prof. Wright's notes (Part 2)		Section 13, solutions		HW 13, solutions Project

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Prasad Raghavendra and John Wright, Spring 2022