CS 170
Efficient Algorithms and Intractable Problems
CS 170 at UC Berkeley with Prasad Raghavendra and Christian Borgs, Spring 2024
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 Asymptotic Complexity Comparisons / Asymptotics and Limits / Complex Numbers Review part 1 / Complex Numbers Review part 2 / Recurrence Relations ] | HW 1 due 1/29 |
| 2 | Th 1/25 | 4: Fast Fourier Transform (Part I) [slides] [slides (6up)] [recording posted!] | DPV §2.6 | ||
| 3 | Tu 1/30 | 5: Fast Fourier Transform (Part II) [slides] [slides (handout)] [recording posted!] | DPV §2.6 | [Section 2,Solutions] [Section 2 walkthrough Counting Inversions / Divide and Conquer / FFT Intro / Monotone Matrices ] | HW 2 |
| 3 | Th 2/1 | 6: Depth First Search, Topological Sort [slides] [slides (handout)] [recording posted!] | DPV §3 | ||
| 4 | Tu 2/6 | 7: Strongly Connected Components [slides] [recording posted!] | DPV §3 | [Section 3,Solutions] [Section 3 walkthrough Graph Traversal a / Graph Traversal b / Graph Traversal c / Not so Exciting Scheduling / Pattern Matching / Triple Sum ] | HW 3 </br> HW 3 walkthrough Homework 3 Q2 / Homework 3 Q3 / Homework 3 Q4 / Homework 3 Q5 |
| 4 | Th 2/8 | 8: Paths in Graphs [slides] [recording posted!] | DPV §4 [FFT Applications] | ||
| 5 | Tu 2/13 | 9: Greedy Algorithms, Huffman encoding [slides] [recording posted!] | DPV §5 , §5.2 | [Section 4,Solutions] [Section 4 walkthrough Dijikstras algorithm fails on negative edges / Discussion 4 Q4 / Discussion 4 Q5 / Running Errands / Waypoint ] | HW 4 |
| 5 | Th 2/15 | 10: Minimum Spanning Trees [slides] [prim’s proof] [recording posted!] | DPV §5.1 | ||
| 6 | Tu 2/20 | 11: Union Find, Horn Formulas [slides] [recording posted!] | DPV §5.1.4 , §5.3 | [Section 5,Solutions] | HW 5 |
| 6 | Th 2/22 | 12: Dynamic Programming (Part I) [slides] [recording posted!] | DPV §6.1 , §6.2 , §6.3 | ||
| 7 | Tu 2/27 | Midterm 1 on 2/26 | [Section 6,Solutions] [Section 6 walkthrough Change Making / Dynamic Programming Introduction Fibonacci Numbers / lanting Trees / Longest Common Subsequence ] | HW 6 | |
| 7 | Th 2/29 | 13: Dynamic Programming (Part II) [slides] [recording posted!] | DPV §6.3 , §6.4 | ||
| 8 | Tu 3/5 | 14: Dynamic Programming (Part III) [slides] [recording posted!] | DPV §6.6 | [Section 7,Solutions] [Section 7 walkthrough Balloon Popping Problem / Finding More Counterexamples / Optimal Set Covering / Tiring Resorts ] | HW 7 |
| 8 | Th 3/7 | 15: Dynamic Programming (Part IV) [slides] [recording posted!] | DPV §6.5 , §6.6 , §6.7 | ||
| 9 | Tu 3/12 | 16: Linear Programs, Simplex Algorithm [slides] [recording posted!] | DPV §7.1 | [Section 8,Solutions] [Section 8 walkthrough Egg Drop Revisited / Huffman and LP / LP Basics / Simplex Practice ] | HW 8 |
| 9 | Th 3/14 | 17: Network Flow, Bipartite Matching [slides] [recording posted!] | DPV §7.2 , §7.3 | ||
| 10 | Tu 3/19 | 18: Duality, Zero-Sum Games [slides] [recording posted!] | DPV §7.4 , §7.5 | [Section 9,Solutions] [Section 9 walkthrough Advertising / Fun Duality / Max Flow Min Cut and Duality / Residual in graphs / ZeroSum Games Short Answer ] | HW 9 |
| 10 | Th 3/21 | 19: Review [slides] [recording posted!] | |||
| 11 | Tu 3/26 | Spring Recess | |||
| 11 | Th 3/28 | Spring Recess | |||
| 12 | Tu 4/2 | Midterm 2 | |||
| 12 | Th 4/4 | 20: Reductions, NP-Completeness [slides] [recording posted!] | DPV §7.3 , §8.1 | [Section 10,Solutions] [Section 10 walkthrough Bad Reductions / Graph Coloring Problem / Optimization versus Search / Set Cover vs LP ] | HW 10 |
| 13 | Tu 4/9 | 21: Reductions [slides] [recording posted!] | DPV §8.2, 8.3 | [Section 11,Solutions] [Section 11 walkthrough A Reduction Warmup / California Cycle / Cycle Cover / NP or not NP that is the question / Runtime of NP ] | HW 11 |
| 13 | Th 4/11 | 22: Coping with NP-completeness [slides] [recording posted!] | DPV §9 | ||
| 14 | Tu 4/16 | 23: Coping with NP-completeness [slides] [recording posted!] | DPV §9 | [Section 12,Solutions] | HW 12 ,Coding |
| 14 | Th 4/18 | 24: Gradient Descent (Part I) [slides] [recording posted!] | GD Notes (sections 1-3) – updated 4/29 | ||
| 15 | Tu 4/23 | 25: Gradient Descent (Part II) [slides] [recording posted!] | GD Notes – updated 4/29 | Section 13 | HW 13 |
| 15 | Th 4/25 | 26: Gradient Descent (Part III), Multiplicative Weights | GD Notes – updated 4/29 |