Course Details
Instructors: Professors Jeffrey Considine and Kira Goldner.
Teaching Assistants: Anup De and Kevin Quinn.
Email: Please use private messages on Piazza for all email needs
Office Hours:
Monday 2–3pm (Prof. Considine, CDS 1625); 3:30–5:30pm (Anup De, 5th floor study area).
Tuesday 11am–12pm and 3:30–4:30pm (Prof. Goldner, CDS 1339).
Wednesday 1–2pm (Prof. Considine, CDS 1625); 3–5pm (Kevin Quinn, 14th floor purple corner).
Thursday 11am–12pm and 3:30–4:30pm (Prof. Considine, CDS 1625).
Lectures and Discussion Sections:
A1 Tuesday/Thursday 2:00–3:15pm, CDS B64.
Discussion Section A2: Friday 10:10-11:00am, IEC B10.
Discussion Section A3: Friday 11:15am-12:05pm, IEC B10.
B1 Tuesday/Thursday 9:30–10:45am, KCB 106.
Discussion Section B2: Friday 12:20-1:10pm, IEC B10.
Discussion Section B3: Friday 1:25-2:15pm, IEC B10.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza (access code: algs)
- For submitting homework: Gradescope (entry code: VDY44D)
- 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 25.
Midterm II: Tues. April 1.
Final: (A1) Tues. May 6, 3-5pm and (B1) Thurs. May 8, 9-11am.
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 21 | 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 28 | 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 4 | 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 11 | Greedy Algorithms II: Interval Scheduling | Greedy-Stays-Ahead Guide, KT4.1 |
Feb 13 | Greedy Algorithms III: Optimal Caching | Greedy-Exchange Guide, KT4.3 |
Feb 18 | NO LECTURE (Monday Schedule) | |
Feb 20 | Greedy Algorithms IV: Scheduling to Minimize Lateness | KT4.2, similar to CLRS16.5 |
Feb 25 | MIDTERM | |
Feb 27 | Divide & Conquer I: Mergesort, Solving Recurrences | Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
Mar 4 | Divide & Conquer II: Closest Pair of Points | KT5.4 |
Mar 6 | Divide & Conquer III: Integer and Matrix Multiplication | KT5.5, CLRS4.2, Mitzenmacher's notes |
Mar 11 | NO CLASS (Spring break) | |
Mar 13 | NO CLASS (Spring break) | |
Mar 18 | Dynamic Programming I: Weighted Interval Scheduling | Dynamic Programming Guide, KT6.1-6.2 |
Mar 20 | Dynamic Programming II: Knapsack | KT6.4 |
Mar 25 | Dynamic Programming III: Segmented Least Squares | KT6.3 |
Mar 27 | Dynamic Programming IV: Bellman-Ford | KT6.8 |
Apr 1 | MIDTERM | |
Apr 3 | NP Completeness | Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading |
Apr 8 | Linear Programming I: Introduction | Linear Programming Guide, KT8.1, KT11.6 |
Apr 10 | Linear Programming II: Algorithms, Problems, and Duality | Blog Post on Simplex |
Apr 15 | Linear Programming III: Duality Theory and Zero-Sum Games | The Minimax Theorem without Duality |
Apr 17 | The Minimax Theorem and Online Learning | |
Apr 22 | Multiplicative Weight Update | Multiplicative Weights Guide |
Apr 24 | Approximation Algorithms: Random and Online | |
Apr 29 | Stable Matching | KT1.1, KT2.3 |
May 1 | Final Exam Review |