CS 170

Lecture: Tu/Th 3:30 - 5:00 pm, Dwinelle 155
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

Week	Date	Lecture	Reading	Section	Assignments
1	Tu 1/21	Introduction, big-O notation, arithmetic webcast	DPV §0 , §1.1	Section 1, solutions	HW 1, solutions
1	Th 1/23	Divide-and-Conquer Part I webcast	DPV §2.1 , §2.2 , §2.3	Section 1, solutions	HW 1, solutions
2	Tu 1/28	Divide-and-Conquer Part II webcast	DPV §2.4 , §2.5 , §2.6	Section 2, solutions	HW 2, solutions
2	Th 1/30	Fast Fourier Transform webcast	DPV §2.6	Section 2, solutions	HW 2, solutions
3	Tu 2/4	Decompositions of graphs webcast	DPV §3	Section 3, solutions	HW 3, solutions
3	Th 2/6	Paths in graphs Part I webcast	DPV §4.1 , §4.2 , §4.3 , §4.4	Section 3, solutions	HW 3, solutions
4	Tu 2/11	Paths in graphs Part II webcast	DPV §4.4 , §4.5 , §4.6 , §4.7	Section 4, solutions	HW 4, solutions
4	Th 2/13	Greedy Algorithms webcast	DPV §5.4	Section 4, solutions	HW 4, solutions
5	Tu 2/18	Minimum Spanning Trees webcast	DPV §5.1	Section 5, solutions	HW 5, solutions
5	Th 2/20	Midterm 1 on Th 2/20 (No lecture)		Section 5, solutions	HW 5, solutions
6	Tu 2/25	Union Find webcast	DPV §5.1.4	Section 6, solutions	HW 6, solutions
6	Th 2/27	Dynamic Programming Part I notebook webcast	DPV §6	Section 6, solutions	HW 6, solutions
7	Tu 3/3	Dynamic Programming Part II webcast	DPV §6	Section 7, solutions	HW 7, solutions
7	Th 3/5	Linear Programming and Duality webcast	DPV §7.1 , §7.4	Section 7, solutions	HW 7, solutions
8	Tu 3/10	Network Flow webcast	DPV §7.2	Section 8, solutions	HW 8, solutions
8	Th 3/12	Network Flow webcast	DPV §7.2	Section 8, solutions	HW 8, solutions
9	Tu 3/17	Zero-Sum Games webcast	DPV §7.5	Section 9, solutions	HW 9, solutions
9	Th 3/19	Multiplicative Updates webcast	notes	Section 9, solutions	HW 9, solutions
10	Tu 3/24	Spring Break
10	Th 3/26	Spring Break
11	Tu 3/31	Reductions, Bipartite Matching webcast	DPV §7.3	Section 10, solutions	HW 10, solutions Project
11	Th 4/2	No Lecture (Time to work on the checkpoint)		Section 10, solutions	HW 10, solutions Project
12	Tu 4/7	Search Problems webcast	DPV §8.1	Section 11, solutions	HW 11, solutions Project
12	Th 4/9	NP-Completeness webcast	DPV §8.2 , §8.3	Section 11, solutions	HW 11, solutions Project
13	Tu 4/14	Coping with NP-Completeness webcast	DPV §9	Section 12, solutions	HW 12, solutions Project
13	Th 4/16	Randomized Algorithms webcast	notes	Section 12, solutions	HW 12, solutions Project
14	Tu 4/21	Sketching, Streaming webcast	notes	Section 13, solutions	HW 13, solutions Project
14	Th 4/23	Lower Bounds webcast	notes	Section 13, solutions	HW 13, solutions Project
15	Tu 4/28	Hashing webcast	DPV §1.5	Section 14, solutions	HW 14, solutions Project
15	Th 4/30	Special Topic webcast		Section 14, solutions	HW 14, solutions Project

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Alessandro Chiesa and Jelani Nelson, Spring 2020