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	Week 8 mini-lecture	HW 7, solutions
8	Th 10/14	Network Flow (Part I)	DPV §7.2 , §7.4	Section 7, solutions	Week 8 mini-lecture	HW 7, solutions
9	Tu 10/19	Network Flow (Part II)	DPV §7.2 , §7.4
9	Th 10/21	Zero-Sum Games	DPV §7.5
10	Tu 10/26	Multiplicative Updates	notes
10	Th 10/28	Reductions, Bipartite Matching	DPV §7.3
11	Tu 11/2	Midterm 2
11	Th 11/4	Search Problems	DPV §8.1
12	Tu 11/9	NP-Completeness	DPV §8.2 , §8.3
12	Th 11/11	No Class (Veterans Day)
13	Tu 11/16	Coping with NP-completeness	DPV §9
13	Th 11/18	Randomized Algorithms	notes
14	Tu 11/23	Sketching, Streaming	notes
14	Th 11/25	No Class (Thanksgiving)
15	Tu 11/30	Lower Bounds	notes
15	Th 12/2	Hashing	DPV §1.5

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Jelani Nelson, Fall 2021

Announcements: