CS 170

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

Week	Date	Lecture	Reading	Section	Videos	Assignments
1	Tu 1/19	Introduction, big-O notation, arithmetic webcast \| youtube mirror Password: $tx9h^ Prof. Chiesa's notes	DPV §0 , §1.1		Week 1 mini-lecture	HW 1, solutions HW 1 walkthrough
1	Th 1/21	Divide-and-Conquer (Part I) webcast \| youtube mirror Password: 4xr@=yrr Prof. Chiesa's notes	DPV §2.1 , §2.2 , §2.3		Week 1 mini-lecture	HW 1, solutions HW 1 walkthrough
2	Tu 1/26	Divide-and-Conquer (Part II) webcast \| youtube mirror Password: .6XiwsPg Prof. Chiesa's notes	DPV §2.4 , §2.5 , §2.6	Section 1, solutions Section 1 walkthrough	FFT Walkthrough Week 2 mini-lecture	HW 2, solutions HW 2 walkthrough
2	Th 1/28	Fast Fourier Transform webcast \| youtube mirror Password: xswe&CN3 Prof. Chiesa's notes	DPV §2.6	Section 1, solutions Section 1 walkthrough	FFT Walkthrough Week 2 mini-lecture	HW 2, solutions HW 2 walkthrough
3	Tu 2/2	Decompositions of graphs webcast \| youtube mirror Password: P%4T@dCS Prof. Chiesa's notes	DPV §3	Section 2, solutions Section 2 walkthrough	Week 3 mini-lecture	HW 3, solutions HW 3 walkthrough
3	Th 2/4	Paths in graphs (Part I) webcast \| youtube mirror Password: VIY$L&n4 Prof. Chiesa's notes	DPV §4.1 , §4.2 , §4.3 , §4.4	Section 2, solutions Section 2 walkthrough	Week 3 mini-lecture	HW 3, solutions HW 3 walkthrough
4	Tu 2/9	Paths in graphs (Part II) webcast \| youtube mirror Password: %b5wLL*8 Prof. Demmel's notes	DPV §4.4 , §4.5 , §4.6 , §4.7	Section 3, solutions Section 3 walkthrough	Week 4 mini-lecture	HW 4, solutions HW 4 walkthrough
4	Th 2/11	Greedy Algorithms webcast \| youtube mirror Password: q7QQBr Prof. Demmel's notes	DPV §5 , §5.4	Section 3, solutions Section 3 walkthrough	Week 4 mini-lecture	HW 4, solutions HW 4 walkthrough
5	Tu 2/16	Minimum spanning trees webcast \| youtube mirror Password: @AB3?uJ% Prof. Demmel's notes	DPV §5.1	Section 4, solutions	Week 5 mini-lecture Other MT1 walkthroughs DnC coding example Fall 2020 MT1 walkthrough	HW 5, solutions HW 5 walkthrough
5	Th 2/18	Midterm 1 (9:00am - 11:00am PST) Midterm prep Midterm prep sols Midterm walkthrough		Section 4, solutions		HW 5, solutions HW 5 walkthrough
6	Tu 2/23	Huffman encoding and Horn formulas webcast \| youtube mirror Password: @?YUZ#s8 Prof. Demmel's notes	DPV §5.2 , §5.3	Section 5, solutions Section 5 walkthrough	Week 6 mini-lecture	HW 6, solutions
6	Th 2/25	Dynamic Programming (Part I) webcast \| youtube mirror Password: 2?KtSy4G Prof. Demmel's notes	DPV §6	Section 5, solutions Section 5 walkthrough	Week 6 mini-lecture	HW 6, solutions
7	Tu 3/2	Dynamic Programming (Part II) webcast \| youtube mirror Password: d18wP=A* Prof. Chiesa's notes	DPV §6	Section 6, solutions Section 6 walkthrough	Week 7 mini-lecture	HW 7, solutions HW 7 walkthrough
7	Th 3/4	Linear Programming webcast \| youtube mirror Password: 6yk%#q4s Prof. Chiesa's notes	DPV §7.1	Section 6, solutions Section 6 walkthrough	Week 7 mini-lecture	HW 7, solutions HW 7 walkthrough
8	Tu 3/9	Network Flow webcast \| youtube mirror Password: $3Apdj1s Prof. Chiesa's notes	DPV §7.2	Section 7, solutions	Week 8 mini-lecture	HW 8, solutions HW 8 walkthrough
8	Th 3/11	Duality webcast \| youtube mirror Password: &EujG0Tm Prof. Chiesa's notes	DPV §7.4	Section 7, solutions	Week 8 mini-lecture	HW 8, solutions HW 8 walkthrough
9	Tu 3/16	Midterm 2 (9:00am - 11:00am PST)		Section 8, solutions Section 8 walkthrough	Week 9 mini-lecture
9	Th 3/18	Zero-Sum Games webcast \| youtube mirror Password: h65@Om$# Prof. Demmel's notes (pre-lec) Prof. Demmel's notes (post-lec)	DPV §7.5	Section 8, solutions Section 8 walkthrough	Week 9 mini-lecture
10	Tu 3/23	Spring Break!
10	Th 3/25	Spring Break!
11	Tu 3/30	Multiplicative Updates webcast \| youtube mirror Password: G!A&97A% Prof. Chiesa's notes	notes	Section 9, solutions Section 9 walkthrough	Week 11 mini-lecture	HW 9, solutions HW 9 walkthrough
11	Th 4/1	Reductions, Bipartite Matching webcast Password: @M7ss1@G Prof. Demmel's notes (post-lec) Prof. Demmel's notes (pre-lec)	DPV §7.3	Section 9, solutions Section 9 walkthrough	Week 11 mini-lecture	HW 9, solutions HW 9 walkthrough
12	Tu 4/6	Search Problems webcast Password: 2!Q0d%3w Prof. Demmel's notes (post-lec) Prof. Demmel's notes (pre-lec)	DPV §8.1	Section 10, solutions	Week 12 mini-lecture	HW 10, solutions
12	Th 4/8	NP-Completeness webcast \| youtube mirror Password: =M%2s.ms Prof. Demmel's notes (post-lec) Prof. Demmel's notes (pre-lec)	DPV §8.2 , §8.3	Section 10, solutions	Week 12 mini-lecture	HW 10, solutions
13	Tu 4/13	Coping with NP-completeness webcast Password: 7%HN@S5a Prof. Chiesa's notes	DPV §9	Section 11, solutions	Week 13 mini-lecture	HW 11, solutions Project
13	Th 4/15	Randomized Algorithms webcast Password: .PUyb^8G Prof. Demmel's notes (post-lec) Prof. Demmel's notes (pre-lec)	notes	Section 11, solutions	Week 13 mini-lecture	HW 11, solutions Project
14	Tu 4/20	Sketching, Streaming	DPV §1.5 notes	Section 12, solutions		HW 12, solutions Project
14	Th 4/22	Lower Bounds		Section 12, solutions		HW 12, solutions Project
15	Tu 4/27	Hashing	DPV §1.5	Section 13, solutions		HW 13, solutions Project
15	Th 4/29	Interactive Proofs (special topic)		Section 13, solutions		HW 13, solutions Project

Final time: Wednesday 5/12, 11:30am - 2:30pm PST

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Alessandro Chiesa and James Demmel, Spring 2021

Announcements: