CS 170

Lecture: TuTh 3:30 PM - 4:59 PM in Li Ka Shing 245
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)

For this semester, we unfortunately currently no longer plan to publish lectures to YouTube. The lectures playlist can still be found on bCourses in the Media Gallery tab (CalNet CAS required). Please refer to the playlist for the most up-to-date lectures available.

Please be informed that access to the majority of solutions on this website necessitates authentication through CalNet CAS. Should you require access to these restricted materials but do not possess a CalNet ID, kindly contact us for further assistance.

Week	Date	Lecture	Reading	Section	Assignments
1	Tu 1/16	1: Introduction, Big-O Notation, Arithmetic slides slides (6up) recording posted!	DPV §0 , §1.1
1	Th 1/18	2: Integer Multiplication, Recurrence Relations, Master Theorem slides slides (6up) recording posted!	DPV §2.1 , §2.2
2	Tu 1/23	3: Matrix Muliplication, Median-Finding slides slides (6up) recording posted!	DPV §2.3 , §2.4 , §2.5	Section 1, Solutions Section 1 walkthrough	HW 1 due 1/29 , Solutions
2	Th 1/25	4: Fast Fourier Transform (Part I) slides slides (6up) recording posted!	DPV §2.6	Section 1, Solutions Section 1 walkthrough	HW 1 due 1/29 , Solutions
3	Tu 1/30	5: Fast Fourier Transform (Part II) slides slides (handout) recording posted!	DPV §2.6	Section 2, Solutions Section 2 walkthrough	HW 2 , Solutions
3	Th 2/1	6: Depth First Search, Topological Sort slides slides (handout) recording posted!	DPV §3	Section 2, Solutions Section 2 walkthrough	HW 2 , Solutions
4	Tu 2/6	7: Strongly Connected Components slides recording posted!	DPV §3	Section 3, Solutions Section 3 walkthrough	HW 3 , Solutions HW 3 walkthrough
4	Th 2/8	8: Paths in Graphs slides recording posted!	DPV §4 FFT Applications	Section 3, Solutions Section 3 walkthrough	HW 3 , Solutions HW 3 walkthrough
5	Tu 2/13	9: Greedy Algorithms, Huffman encoding slides recording posted!	DPV §5 , §5.2	Section 4, Solutions Section 4 walkthrough	HW 4 , Solutions
5	Th 2/15	10: Minimum Spanning Trees slides prim's proof recording posted!	DPV §5.1	Section 4, Solutions Section 4 walkthrough	HW 4 , Solutions
6	Tu 2/20	11: Union Find, Horn Formulas slides recording posted!	DPV §5.1.4 , §5.3	Section 5, Solutions	HW 5 , Solutions
6	Th 2/22	12: Dynamic Programming (Part I) slides recording posted!	DPV §6.1 , §6.2 , §6.3	Section 5, Solutions	HW 5 , Solutions
7	Tu 2/27	Midterm 1 on 2/26		Section 6, Solutions	HW 6 , Solutions
7	Th 2/29	13: Dynamic Programming (Part II) slides recording posted!	DPV §6.3 , §6.4	Section 6, Solutions	HW 6 , Solutions
8	Tu 3/5	14: Dynamic Programming (Part III) slides recording posted!	DPV §6.6	Section 7, Solutions	HW 7 , Solutions
8	Th 3/7	15: Dynamic Programming (Part IV) slides recording posted!	DPV §6.5 , §6.6 , §6.7	Section 7, Solutions	HW 7 , Solutions
9	Tu 3/12	16: Linear Programs, Simplex Algorithm slides recording posted!	DPV §7.1	Section 8, Solutions	HW 8 , Solutions
9	Th 3/14	17: Network Flow, Bipartite Matching slides recording posted!	DPV §7.2 , §7.3	Section 8, Solutions	HW 8 , Solutions
10	Tu 3/19	18: Duality, Zero-Sum Games slides recording posted!	DPV §7.4 , §7.5	Section 9, Solutions	HW 9 , Solutions
10	Th 3/21	19: Review slides recording posted!		Section 9, Solutions	HW 9 , Solutions
11	Tu 3/26	Spring Recess
11	Th 3/28	Spring Recess
12	Tu 4/2	Midterm 2		Section 10, Solutions	HW 10
12	Th 4/4	20: Reductions, NP-Completeness slides recording posted!	DPV §7.3 , §8.1	Section 10, Solutions	HW 10
13	Tu 4/9	21: Reductions slides recording posted!	DPV §8.2, 8.3	Section 11	HW 11
13	Th 4/11	22: Coping with NP-completeness slides recording posted!	DPV §9	Section 11	HW 11
14	Tu 4/16	23: Coping with NP-completeness	DPV §9	Section 12	HW 12
14	Th 4/18	24: TBD		Section 12	HW 12
15	Tu 4/23	25: TBD		Section 13	HW 13
15	Th 4/25	26: TBD		Section 13	HW 13

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with Prasad Raghavendra and Christian Borgs, Spring 2024