CS 170

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

Week	Date	Lecture	Reading	Section	Videos	Assignments
1	Tu 8/25
1	Th 8/27	Introduction, big-O notation webcast lec 1.1 lec 1.2 lec 1.3	DPV §0
2	Tu 9/1	Divide-and-Conquer webcast	DPV §1.1 , §2.1 , §2.2	Section 1, solutions	Mini-lecture Q&A Discussion solutions	HW 1, solutions
2	Th 9/3	Divide-and-Conquer webcast	DPV §2.3 , §2.4	Section 1, solutions	Mini-lecture Q&A Discussion solutions	HW 1, solutions
3	Tu 9/8	Divide-and-Conquer, FFT webcast \| youtube mirror Password: 2t?KQFTd	DPV §2.5 , §2.6	Section 2, solutions	Mini-lecture Q&A Discussion solutions FFT Walkthrough	HW 2, solutions HW 2 walkthrough
3	Th 9/10	FFT webcast \| youtube mirror Password: ^2QFbSd5	DPV §2.6	Section 2, solutions	Mini-lecture Q&A Discussion solutions FFT Walkthrough	HW 2, solutions HW 2 walkthrough
4	Tu 9/15	DFS webcast \| youtube mirror Password: $dGN5o@i Prof. Tal's notes	DPV §3.1 , §3.2 , §3.3	Section 3, solutions	Mini-lecture Discussion solutions	HW 3, solutions HW 3 walkthrough
4	Th 9/17	SCC, Shortest paths webcast \| youtube mirror Password: DE^2FV?& Prof. Tal's notes	DPV §3.4 , §4.1 , §4.2 , §4.3	Section 3, solutions	Mini-lecture Discussion solutions	HW 3, solutions HW 3 walkthrough
5	Tu 9/22	Shortest paths webcast \| youtube mirror Password: 8iH@lF=T Prof. Tal's notes	DPV §4.4 , §4.6 , §4.7	Section 4, solutions	Mini-lecture Discussion solutions	HW 4, solutions HW 4 walkthrough
5	Th 9/24	Greedy algorithms webcast \| youtube mirror Password: 5i%L%ygF Prof. Tal's notes	DPV §5.1 , §5.2	Section 4, solutions	Mini-lecture Discussion solutions	HW 4, solutions HW 4 walkthrough
6	Tu 9/29	Greedy algorithms webcast \| youtube mirror Password: ZkV0*XWv Prof. Tal's notes Huffman proof	DPV §5.1.3 , §5.1.5 , §5.2 , §5.4	Section 5, solutions	Mini-lecture Discussion solutions	HW 5, solutions HW 5 walkthrough
6	Th 10/1	Midterm 1 (6-8pm PST)		Section 5, solutions	Mini-lecture Discussion solutions	HW 5, solutions HW 5 walkthrough
7	Tu 10/6	Dynamic Programming webcast \| youtube mirror Password: Z3iQ0@a2 Prof. Tal's notes	DPV §6	Section 6, solutions	Mini-lecture Midterm walkthrough Discussion solutions	HW 6, solutions HW 6 walkthrough
7	Th 10/8	Dynamic Programming webcast \| youtube mirror Password: iq*3Lnq= Prof. Tal's notes	DPV §6	Section 6, solutions	Mini-lecture Midterm walkthrough Discussion solutions	HW 6, solutions HW 6 walkthrough
8	Tu 10/13	Linear Programming webcast \| youtube mirror Password: bt9$hm4M Prof. Vazirani's notes	DPV §7.1	Section 7, solutions	Mini-lecture Discussion solutions	HW 7, solutions HW 7 walkthrough
8	Th 10/15	Network Flow webcast \| youtube mirror Password: g??.*K2M Prof. Vazirani's notes	DPV §7.2	Section 7, solutions	Mini-lecture Discussion solutions	HW 7, solutions HW 7 walkthrough
9	Tu 10/20	Duality webcast \| youtube mirror Password: vn^54WTd Prof. Vazirani's notes	DPV §7.4	Section 8, solutions	Mini-lecture Discussion solutions	HW 8, solutions HW 8 walkthrough
9	Th 10/22	Zero-sum games, multiplicative weight updates webcast \| youtube mirror Password: LKMBb6*# Prof. Vazirani's notes	DPV §7.5 notes	Section 8, solutions	Mini-lecture Discussion solutions	HW 8, solutions HW 8 walkthrough
10	Tu 10/27	Zero-sum games, multiplicative weight updates, midterm review webcast \| youtube mirror Password: HV@e1LP5 Prof. Vazirani's notes	DPV §7.5 notes	Section 9, solutions	Mini-lecture Midterm 2 review Discussion solutions	HW 9, solutions
10	Th 10/29	Midterm 2 (6-8pm PST)		Section 9, solutions	Mini-lecture Midterm 2 review Discussion solutions	HW 9, solutions
11	Tu 11/3	No lecture! Please vote if you haven’t already 🗳️		Section 10, solutions	Mini-lecture Discussion solutions	HW 10, solutions Project
11	Th 11/5	Reductions webcast \| youtube mirror Password: XJ$y5P9C Prof. Tal's notes	DPV §7.3	Section 10, solutions	Mini-lecture Discussion solutions	HW 10, solutions Project
12	Tu 11/10	Search problems webcast \| youtube mirror Password: d5g%kJbf Prof. Tal's notes	DPV §8.1	Section 11, solutions	Mini-lecture Discussion solutions	HW 11, solutions Project
12	Th 11/12	NP-completeness webcast \| youtube mirror Password: Z^@%A7DC Prof. Tal's notes	DPV §8.2 , §8.3	Section 11, solutions	Mini-lecture Discussion solutions	HW 11, solutions Project
13	Tu 11/17	Coping with NP-completeness webcast \| youtube mirror Password: m^ZPV#b1 Prof. Tal's notes	DPV §9	Section 12, solutions	Mini-lecture	HW 12, solutions Project
13	Th 11/19	Modular arithmetic, primality webcast \| youtube mirror Password: cXJJS@E8 Prof. Vazirani's notes	DPV §1.2 , §1.3	Section 12, solutions	Mini-lecture	HW 12, solutions Project
14	Tu 11/24	Primality tests, hashing webcast \| youtube mirror Password: m8cG.OAa Prof. Vazirani's notes	DPV §1.5	Section 13, solutions	Discussion solutions	HW 13, solutions Project
14	Th 11/26	No lecture (Thanksgiving)		Section 13, solutions	Discussion solutions	HW 13, solutions Project
15	Tu 12/1	Hashing, streaming algorithms webcast \| youtube mirror Password: N4?RX9Wx Prof. Vazirani's notes	DPV §1.5 notes	Section 14, solutions		HW 14, solutions Project
15	Th 12/3	Quantum factoring webcast \| youtube mirror Password: fY0JD?24 Prof. Vazirani's notes		Section 14, solutions		HW 14, solutions Project

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Avishay Tal and Umesh Vazirani, Fall 2020