CS 170

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

Week	Date	Lecture	Reading	Section	Videos	Assignments
1	Tu 8/24					HW 0, solutions
1	Th 8/26	Introduction, big-O notation, arithmetic webcast Prof. Nelson's notes	DPV §0 , §1.1			HW 0, solutions
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 Coding for divide-and-conquer	HW 1, solutions HW 1 walkthrough
2	Th 9/2	Divide-and-Conquer (Part II) webcast	DPV §2.4 , §2.5 , §2.6	Section 1, solutions Section 1 walkthrough	Week 2 mini-lecture Coding for divide-and-conquer	HW 1, solutions HW 1 walkthrough
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	HW 2, solutions HW 2 walkthrough
3	Th 9/9	Decompositions of graphs webcast Prof. Nelson's notes	DPV §3	Section 2, solutions Section 2 walkthrough	Mini-lecture & FFT walkthrough	HW 2, solutions HW 2 walkthrough
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 Coding for graphs	HW 3, solutions HW 3 walkthrough
4	Th 9/16	Paths in graphs (Part II) webcast	DPV §4.4 , §4.5 , §4.6 , §4.7	Section 3, solutions Section 3 walkthrough	Week 4 mini-lecture Coding for graphs	HW 3, solutions HW 3 walkthrough
5	Tu 9/21	Minimum Spanning Trees webcast	DPV §5.1	Section 4, solutions Section 4 walkthrough	Week 5 mini-lecture Coding for greedy	HW 4, solutions HW 4 walkthrough
5	Th 9/23	Greedy Algorithms webcast	DPV §5 , §5.4	Section 4, solutions Section 4 walkthrough	Week 5 mini-lecture Coding for greedy	HW 4, solutions HW 4 walkthrough
6	Tu 9/28	Union Find webcast	DPV §5.1.4	Section 5, solutions Section 5 walkthrough	Week 6 mini-lecture	HW 5, solutions
6	Th 9/30	Dynamic Programming (Part I) webcast	DPV §6	Section 5, solutions Section 5 walkthrough	Week 6 mini-lecture	HW 5, solutions
7	Tu 10/5	Midterm 1		Section 6, solutions Section 6 walkthrough	Coding for DP	HW 6, solutions HW 6 walkthrough
7	Th 10/7	Dynamic Programming (Part II) webcast	DPV §6 Jupyter Notebook	Section 6, solutions Section 6 walkthrough	Coding for DP	HW 6, solutions HW 6 walkthrough
8	Tu 10/12	Linear Programming webcast	DPV §7.1	Section 7, solutions Section 7 walkthrough	Week 8 mini-lecture	HW 7, solutions HW 7 walkthrough
8	Th 10/14	Network Flow (Part I) webcast	DPV §7.2 , §7.4	Section 7, solutions Section 7 walkthrough	Week 8 mini-lecture	HW 7, solutions HW 7 walkthrough
9	Tu 10/19	Network Flow (Part II) webcast	DPV §7.2 , §7.4	Section 8, solutions Section 8 walkthrough	Week 9 mini-lecture	HW 8, solutions HW 8 walkthrough
9	Th 10/21	Zero-Sum Games webcast	DPV §7.5	Section 8, solutions Section 8 walkthrough	Week 9 mini-lecture	HW 8, solutions HW 8 walkthrough
10	Tu 10/26	Multiplicative Updates webcast	notes	Section 9, solutions	Week 10 mini-lecture	HW 9, solutions
10	Th 10/28	Reductions, Bipartite Matching webcast	DPV §7.3	Section 9, solutions	Week 10 mini-lecture	HW 9, solutions
11	Tu 11/2	Midterm 2		Section 10, solutions Section 10 walkthrough	Week 11 mini-lecture	HW 10, solutions HW 10 walkthrough
11	Th 11/4	Search Problems webcast	DPV §8.1	Section 10, solutions Section 10 walkthrough	Week 11 mini-lecture	HW 10, solutions HW 10 walkthrough
12	Tu 11/9	NP-Completeness webcast	DPV §8.2 , §8.3	Section 11, solutions Section 11 walkthrough		HW 11, solutions HW 11 walkthrough
12	Th 11/11	No Class (Veterans Day)		Section 11, solutions Section 11 walkthrough		HW 11, solutions HW 11 walkthrough
13	Tu 11/16	Coping with NP-completeness webcast	DPV §9	Section 12, solutions Section 12 walkthrough	Week 13 mini-lecture	HW 12, solutions HW 12 walkthrough
13	Th 11/18	Randomized Algorithms webcast	notes	Section 12, solutions Section 12 walkthrough	Week 13 mini-lecture	HW 12, solutions HW 12 walkthrough
14	Tu 11/23	Hashing webcast	DPV §1.5	Section 13, solutions		HW 13, solutions
14	Th 11/25	No Class (Thanksgiving)		Section 13, solutions		HW 13, solutions
15	Tu 11/30	Sketching, Streaming	notes		Week 15 mini-lecture
15	Th 12/2	Lower Bounds	notes		Week 15 mini-lecture

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson, Fall 2021

Announcements: