CS 170

Lecture: TuTh 12:30 PM - 1:59 PM
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 8/22	No Lecture
1	Th 8/24	Introduction, Big-O Notation, Arithmetic blank annotated recording posted!	DPV §0 , §1.1
2	Tu 8/29	Divide-and-Conquer (Part I) blank annotated recording posted!	DPV §2.1 , §2.2 , §2.3	Section 1 , Solutions Section 1 walkthrough	HW 1 , Solutions HW 1 walkthrough
2	Th 8/31	Divide-and-Conquer (Part II) blank annotated recording posted!	DPV §2.4 , §2.5 , §2.6	Section 1 , Solutions Section 1 walkthrough	HW 1 , Solutions HW 1 walkthrough
3	Tu 9/5	Fast Fourier Transform (Part I) slides recording posted!	DPV §2.6	Section 2 , Solutions Section 2 walkthrough	HW 2 , Solutions HW 2 walkthrough
3	Th 9/7	Fast Fourier Transform (Part II) slides recording posted!	DPV §2.6	Section 2 , Solutions Section 2 walkthrough	HW 2 , Solutions HW 2 walkthrough
4	Tu 9/12	Graphs and DFS blank annotations unavailable, refer to recording recording posted!	DPV §3.1 , §3.2 , §3.3	Section 3 , Solutions Section 3 walkthrough	HW 3
4	Th 9/14	Strongly Connected Components blank annotations unavailable, refer to recording recording posted!	DPV §3.4	Section 3 , Solutions Section 3 walkthrough	HW 3
5	Tu 9/19	Paths in Graphs blank (updated!) annotated recording posted!	DPV §4.1 , §4.2 , §4.3 , §4.4	Section 4 , Solutions Section 4 walkthrough	HW 4
5	Th 9/21	Greedy Algorithms blank annotated recording posted!	DPV §5	Section 4 , Solutions Section 4 walkthrough	HW 4
6	Tu 9/26	Minimum Spanning Trees	DPV §5.1	Section 5	HW 5
6	Th 9/28	Dynamic Programming (Part I)	DPV §6	Section 5	HW 5
7	Tu 10/3	Midterm 1		Section 6	HW 6
7	Th 10/5	Dynamic Programming (Part II)	DPV §6	Section 6	HW 6
8	Tu 10/10	Linear Programming	DPV §7.1	Section 7	HW 7
8	Th 10/12	Network Flow (Part I)	DPV §7.2	Section 7	HW 7
9	Tu 10/17	Network Flow (Part II)	DPV §7.2	Section 8	HW 8
9	Th 10/19	Zero-Sum Games	DPV §7.5	Section 8	HW 8
10	Tu 10/24	Multiplicative Weights		Section 9	HW 9
10	Th 10/26	Reductions, Bipartite Matching	DPV §7.3	Section 9	HW 9
11	Tu 10/31	Search Problems	DPV §8.1	Section 10	HW 10
11	Th 11/2	NP-Completeness	DPV §8.2 , §8.3	Section 10	HW 10
12	Tu 11/7	Midterm 2		Section 11	HW 11
12	Th 11/9	Coping with NP-Completeness	DPV §9	Section 11	HW 11
13	Tu 11/14	Randomized Algorithms	DPV §1.3	Section 12	HW 12
13	Th 11/16	Hashing	DPV §1.5	Section 12	HW 12
14	Tu 11/21	Sketching, Streaming			HW 13
14	Th 11/23	Thanksgiving Break			HW 13
15	Tu 11/28	Sketching, Streaming		Section 13	HW 13
15	Th 11/30	Special Topic		Section 13	HW 13

Efficient Algorithms and Intractable Problems

CS 170 at UC Berkeley with John Wright and Nika Haghtalab, Fall 2023