Course Details
Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday & Thursday 3:30–4:30pm and by appointment.
Office Location: CDS 1339, 665 Comm Ave.
Teaching Fellows: Nathaniel Quisel (njquisel@), Ketan Suhaas Saichandran (ketanss@).
Monday OH: 4:15–6:15pm with Ketan, CDS 463.
Friday OH: 2:30–4:30pm with Nathaniel, CDS 16th floor (between 1607 and 1609).
Lectures and Discussion Sections:
Tuesday/Thursday 2:00–3:15pm, CAS 313.
Discussion Section A2: Wednesday 3:35-4:25pm, CDS 264.
Discussion Section A3: Wednesday 4:40-5:30pm, CDS 263.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza (access code: algs)
- For submitting homework: Gradescope (entry code: JK8EXP)
- 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: Tues. Feb 27.
Midterm II: Tues. April 2.
Final: Mon. May 6, 3-5pm.
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 18 | Overview and Policies, Runtime and Asymptotics | Worksheet, Notes, Slides KT2.1-2,4, CLRS3.1-2, Logic Guide |
Jan 23 | Insertion Sort, Induction, and the Comparison-Based Lower Bound | Worksheet, Notes, Induction Guide, CLRS2.1, 8.1 |
Jan 25 | Abstract Data Types and Graphs | Worksheet, Notes, CLRS10.1-2, 22.1, KT3.1, E5.1-4 |
Jan 30 | Depth-First Search | Worksheet, Notes, CLRS22.3, KT3.2-3 (skip BFS for now!), E6.1-3 |
Feb 1 | Topological Sort and Breadth-First Search | Worksheet, Notes, KT3.2,6 CLRS22.2,4 |
Feb 6 | Greedy Algorithms I: Dijkstra's Algorithm | Worksheet, Notes, KT4.4, CLRS24.3 |
Feb 8 | Greedy Algorithms II: Interval Scheduling | Worksheet, Notes, Greedy-Stays-Ahead Guide, KT4.1 |
Feb 13 | CLASS CANCELED (Snow Day) | |
Feb 15 | Greedy Algorithms III: Optimal Caching | Worksheet, Notes, Greedy-Exchange Guide, KT4.3 |
Feb 20 | Greedy Algorithms IV: Scheduling to Minimize Lateness | Worksheet, Notes, KT4.2, similar to CLRS16.5 |
Feb 22 | Divide & Conquer I: Mergesort, Solving Recurrences | Worksheet, Notes, Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
Feb 27 | MIDTERM | |
Feb 29 | Divide & Conquer II: Closest Pair of Points | Worksheet, Notes, KT5.4 |
Mar 5 | Divide & Conquer III: Integer and Matrix Multiplication | Worksheet, Notes, KT5.5, CLRS4.2, Mitzenmacher's notes |
Mar 7 | Dynamic Programming I: Weighted Interval Scheduling | Worksheet, Notes, Dynamic Programming Guide, KT6.1-6.2 |
Mar 12 | NO CLASS (Spring break) | |
Mar 14 | NO CLASS (Spring break) | |
Mar 19 | Dynamic Programming II: Knapsack | Worksheet, Notes, KT6.4 |
Mar 21 | Dynamic Programming III: Segmented Least Squares | Worksheet, Notes, KT6.3 |
Mar 26 | Dynamic Programming IV: Bellman-Ford | Worksheet, Notes, KT6.8 |
Mar 28 | NP Completeness | Worksheet, Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading |
Apr 2 | MIDTERM | |
Apr 4 | Linear Programming I: Introduction | Linear Programming Guide, KT8.1, KT11.6 |
Apr 9 | Linear Programming II: Algorithms and Problems | Blog Post on Simplex |
Apr 11 | Linear Programming III: Duality | |
Apr 16 | Linear Programming IV: More Duality and Zero-Sum Games | |
Apr 18 | The Minimax Theorem and Online Learning | |
Apr 23 | Multiplicative Weight Update | Multiplicative Weights Guide |
Apr 25 | Approximation Algorithms: Random and Online | |
April 30 | Final Exam Review |