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		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)	DPV §6	Section 6, solutions		HW 7, solutions
7	Th 3/4	Linear Programming	DPV §7.1	Section 6, solutions		HW 7, solutions
8	Tu 3/9	Network Flow	DPV §7.2	Section 7, solutions		HW 8, solutions
8	Th 3/11	Duality	DPV §7.4	Section 7, solutions		HW 8, solutions
9	Tu 3/16	Midterm 2 (9:00am - 11:00am PST)		Section 8, solutions		HW 9, solutions
9	Th 3/18	Zero-Sum Games	DPV §7.5	Section 8, solutions		HW 9, solutions
10	Tu 3/23	Spring Break!		Section 9, solutions		HW 10, solutions
10	Th 3/25	Spring Break!		Section 9, solutions		HW 10, solutions
11	Tu 3/30	Multiplicative Updates	notes	Section 10, solutions		HW 11, solutions
11	Th 4/1	Reductions, Bipartite Matching	DPV §7.3	Section 10, solutions		HW 11, solutions
12	Tu 4/6	Search Problems	DPV §8.1	Section 11, solutions		HW 12, solutions
12	Th 4/8	NP-Completeness	DPV §8.2 , §8.3	Section 11, solutions		HW 12, solutions
13	Tu 4/13	Coping with NP-completeness	DPV §9	Section 12, solutions		HW 13, solutions
13	Th 4/15	Randomized Algorithms	DPV §1.2 , §1.3	Section 12, solutions		HW 13, solutions
14	Tu 4/20	Sketching, Streaming	DPV §1.5 notes	Section 13, solutions		HW 14, solutions
14	Th 4/22	Lower Bounds		Section 13, solutions		HW 14, solutions
15	Tu 4/27	Hashing	DPV §1.5	Section 14, solutions
15	Th 4/29	Interactive Proofs (special topic)		Section 14, solutions

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: