Course Details
Instructors: Professors Kira Goldner (first half of semester: 1/20–3/15) and Jeffrey Considine (second half of semester: 3/15–5/18).
Teaching Assistants: Anup De and Theo (Thodoris) Tsilivis.
Email: Please use private messages on Piazza for all email needs.
Office Hours:
Monday 11am–12pm (Prof. Considine, CDS 1645).
Monday 5–7pm (Anup De, CDS 5th Floor Pavilion West Side).
Wednesday 9–11am (Theo Tsilivis, CDS 13th floor yellow corner).
Wednesday 1–2pm and 4–5pm (Prof. Considine, CDS 1645).
Thursday 1–2pm (Prof. Considine, CDS 1645).
Lectures and Discussion Sections:
A1 Tuesday/Thursday 3:30–4:45pm, WED 130.
Discussion Section A2: Friday 10:10-11:00am, COM 217.
Discussion Section A3: Friday 11:15am-12:05pm, KCB 103.
B1 Tuesday/Thursday 11:00am–12:15pm, CAS B20.
Discussion Section B2: Friday 12:20-1:10pm, KCB 106.
Discussion Section B3: Friday 1:25-2:15pm, KCB 103.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza (access code: algs)
- For submitting homework: Gradescope (entry code: B55B38)
- What to expect from this course: FAQ
Homework: Homeworks will be posted on Piazza when they become available. Homework must be handwritten or 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 10.
Midterm II: Tues. March 3.
Midterm III: Tues. March 24.
Midterm IV: Tues. April 14.
Final: Per course matrix. (A1) Thurs. May 7, 3-5pm in WED 130 and (B1) Tues. May 5, 12-2pm in CAS B20.
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 20 | Overview and Policies, Runtime and Asymptotics | Worksheet, Notes, Slides, KT2.1-2,4, CLRS3.1-2, Logic Guide |
| Jan 22 | Insertion Sort, Induction, and Loop Invariants | Worksheet, Notes, Induction Guide, CLRS2.1, 8.1 |
| Jan 27 | Abstract Data Types and Graphs | Worksheet, Notes, CLRS10.1-2, 22.1, KT3.1, E5.1-4 |
| Jan 29 | Depth-First Search | Worksheet, Notes, CLRS22.3, KT3.2-3 (skip BFS for now!), E6.1-3 |
| Feb 3 | Topological Sort and Breadth-First Search | Worksheet, Notes, KT3.2,6 CLRS22.2,4 |
| Feb 5 | Greedy Algorithms I: Dijkstra's Algorithm | Worksheet, Notes, KT4.4, CLRS24.3 |
| Feb 10 | MIDTERM 1 | |
| Feb 12 | Greedy Algorithms II: Interval Scheduling | Worksheet, Notes, Greedy-Stays-Ahead Guide, KT4.1 |
| Feb 17 | NO LECTURE (Monday Schedule) | |
| Feb 19 | Greedy Algorithms III: Optimal Caching | Worksheet, Notes, Greedy-Exchange Guide, KT4.3 |
| Feb 24 | NO CLASS (Snow Day) | |
| Feb 26 | Greedy Algorithms IV: Scheduling to Minimize Lateness | Worksheet, Notes, KT4.2, similar to CLRS16.5 |
| Mar 3 | MIDTERM 2 | |
| Mar 5 | Divide & Conquer I: Mergesort, Solving Recurrences | Worksheet, Notes, Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
| Mar 10 | NO CLASS (Spring break) | |
| Mar 12 | NO CLASS (Spring break) | |
| Mar 17 | Divide & Conquer II: Closest Pair of Points | KT5.4 |
| Mar 19 | Divide & Conquer III: Integer and Matrix Multiplication | KT5.5, CLRS4.2, Mitzenmacher's notes |
| Mar 24 | MIDTERM 3 | |
| Mar 26 | Dynamic Programming I: Weighted Interval Scheduling | Dynamic Programming Guide, KT6.1-6.2 |
| Mar 31 | Dynamic Programming II: Knapsack | KT6.4 |
| Apr 2 | Dynamic Programming III: Segmented Least Squares | KT6.3 |
| Apr 7 | Dynamic Programming IV: Bellman-Ford | KT6.8 |
| Apr 9 | NP Completeness | Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading |
| Apr 14 | MIDTERM 4 | |
| Apr 16 | Linear Programming I: Introduction | Linear Programming Guide, KT8.1, KT11.6 |
| Apr 21 | Linear Programming II: Algorithms, Problems, and Approximations | Blog Post on Simplex |
| Apr 23 | Linear Programming III: Duality Theory and Zero-Sum Games | The Minimax Theorem without Duality |
| Apr 28 | Linear Programming IV: Zero-Sum Games and Minimax Theorem | The Minimax Theorem without Duality |
| Apr 30 | Online Learning and Multiplicative Weight Update | Multiplicative Weights Guide |