Course Details
Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 5–6pm and by appointment.
Office Location: CDS 1339, 665 Comm Ave.
Teaching Fellow: Freddy Reiber (freddyr@).
Office Hours: CDS 1338.
OH Location: Wednesday 3–5pm.
Lectures and Discussion Sections:
Tuesday/Thursday 3:30–4:45pm, CDS 164.
Discussion Section A2: Monday 3:30-4:25pm, CGS 311.
Discussion Section A3: Monday 4:40-5:30pm, EOP 262.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza (access code: algs)
- For submitting homework: Gradescope (entry code: V5PJW4)
- What to expect from this course: FAQ
Homework: Homeworks will be posted on Piazza when they become available. Homework must be typed up using LaTeX; here is a quick resource on LaTeX and here is a LaTeX template you may use for the homework. Here is another short guide to LaTeX. You may find it easier to use Overleaf.
Important Dates (Tentative)
Midterm I: Out the night of Wed. Feb 22, due 11:59pm Mon. Feb 27.
Midterm II: Out the night of Wed. March 29, due 11:59pm Mon. April 3.
Final: Out the night of Wed. May 3, due 3pm Wed. May 10 (during assigned slot).
Lecture Schedule (Tentative)
The following resources may also be helpful for those who need refreshers on proof concepts:
- Building Blocks for Theoretical Computer Science by Fleck.
- Mathematics for Computer Science by Lehman, Leighton, and Meyer.
- KTx = Kleinberg and Tardos chapter x.
- CLRSx = Cormen, Leiserson, Rivest, and Stein chapter x.
- Ex = Erickson chapter x.
| Date | Topic | Resources |
|---|---|---|
| Jan 19 | Overview and Policies, Runtime and Asymptotics | Worksheet, Notes, Slides, KT2.1-2,4, CLRS3.1-2 |
| Jan 24 | Insertion Sort, Induction, and the Comparison-Based Lower Bound | Worksheet, Notes, Induction Guide, CLRS2.1, 8.1 |
| Jan 26 | Abstract Data Types and Graphs | Worksheet, Notes, CLRS10.1-2, 22.1, KT3.1, E5.1-4 |
| Jan 31 | Depth-First Search | Worksheet, Notes, CLRS22.3, KT3.2-3 (skip BFS for now!), KT3.6, E6.1-3 |
| Feb 2 | Breadth-First Search and Testing Bipartiteness | No Worksheet, Notes, KT3.2,4, CLRS22.2 |
| Feb 7 | Topological Sort and Greedy Algorithms I: Dijkstra's Algorithm | Worksheet, Notes, KT4.4, CLRS24.3 |
| Feb 9 | Greedy Algorithms II: Finishing Dijkstra and Interval Scheduling | Worksheet, Notes, Greedy-Stays-Ahead Guide, KT4.1 |
| Feb 14 | Greedy Algorithms III: Optimal Caching | Worksheet, Notes, Greedy-Exchange Guide, KT4.3 |
| Feb 16 | Greedy Algorithms IV: Scheduling to Minimize Lateness | Worksheet, Notes, KT4.2, similar to CLRS16.5 |
| Feb 21 | NO CLASS (Monday schedule) | |
| Feb 23 | Midterm—NO CLASS | |
| Feb 28 | Divide & Conquer I: Mergesort, Solving Recurrences | Worksheet, Notes, Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
| Mar 2 | Divide & Conquer II: Closest Pair of Points | Worksheet, Notes, KT5.4 |
| Mar 7 | NO CLASS (Spring break) | |
| Mar 9 | NO CLASS (Spring break) | |
| Mar 14 | Divide & Conquer III: Integer and Matrix Multiplication | Worksheet, Notes, KT5.5, CLRS4.2, Mitzenmacher's notes |
| Mar 16 | Dynamic Programming I: Weighted Interval Scheduling | Worksheet, Notes, Dynamic Programming Guide, KT6.1-6.2 |
| Mar 21 | Dynamic Programming II: Segmented Least Squares | Worksheet, Notes, KT6.3 |
| Mar 23 | Dynamic Programming III: Knapsack | Worksheet, Notes, KT6.4 |
| Mar 28 | Dynamic Programming IV: Bellman-Ford | Worksheet, Notes, KT6.8 |
| Mar 30 | Midterm—NO CLASS | |
| Apr 4 | NP Completeness | Worksheet, Notes, Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading |
| Apr 6 | Linear Programming I: Introduction | Worksheet, Notes, Linear Programming Guide, KT8.1, KT11.6 |
| Apr 11 | Linear Programming II: Algorithms and Problems | Worksheet, Notes, Blog Post on Simplex |
| Apr 13 | Linear Programming III: Duality | Worksheet, Notes |
| Apr 18 | Linear Programming IV: More Duality and Zero-Sum Games | Worksheet, Notes |
| Apr 20 | The Minimax Theorem and Online Learning | Worksheet, Notes |
| Apr 25 | Multiplicative Weight Update | Worksheet, Notes, Multiplicative Weights Guide |
| Apr 27 | Approximation Algorithms: Random and Online | Worksheet, Notes |
| May 2 | Final Exam Review | Worksheet, Notes |
Huge gratitude to Justin Thaler, Adam Smith, Sam Taggart, Alexa Sharp, Tom Wexler, Michael Mitzenmacher, Tim Roughgarden, and Aaron Roth for their materials and/or for their publicly available lecture notes which have made the development of this course possible.