Course Details
NOTE: The waitlist is automatically handled through My BU Stude nt. Please address all questions about registration or automated prerequisites to cds-advising@bu.edu or mkcarven@bu.edu.
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 5–7pm (Anup De).
Tuesday 9:45–10:45am and 5–6pm (Prof. Goldner, CDS 1339).
Wednesday 9–11am (Theo Tsilivis).
Thursday 9:45–10:45am and 5–6pm (Prof. Goldner, CDS 1339).
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.
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 the Comparison-Based Lower Bound | Induction Guide, CLRS2.1, 8.1 |
| Jan 27 | Abstract Data Types and Graphs | CLRS10.1-2, 22.1, KT3.1, E5.1-4 |
| Jan 29 | Depth-First Search | CLRS22.3, KT3.2-3 (skip BFS for now!), E6.1-3 |
| Feb 3 | Topological Sort and Breadth-First Search | KT3.2,6 CLRS22.2,4 |
| Feb 5 | Greedy Algorithms I: Dijkstra's Algorithm | KT4.4, CLRS24.3 |
| Feb 10 | MIDTERM | |
| Feb 12 | Greedy Algorithms II: Interval Scheduling | Greedy-Stays-Ahead Guide, KT4.1 |
| Feb 17 | NO LECTURE (Monday Schedule) | |
| Feb 19 | Greedy Algorithms III: Optimal Caching | Greedy-Exchange Guide, KT4.3 |
| Feb 24 | Greedy Algorithms IV: Scheduling to Minimize Lateness | KT4.2, similar to CLRS16.5 |
| Feb 26 | Divide & Conquer I: Mergesort, Solving Recurrences | Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
| Mar 3 | MIDTERM | |
| Mar 5 | Divide & Conquer II: Closest Pair of Points | KT5.4 |
| Mar 10 | NO CLASS (Spring break) | |
| Mar 12 | NO CLASS (Spring break) | |
| Mar 17 | Divide & Conquer III: Integer and Matrix Multiplication | KT5.5, CLRS4.2, Mitzenmacher's notes |
| Mar 19 | Dynamic Programming 0: Optimal Control | |
| Mar 24 | MIDTERM | |
| 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 | |
| Apr 16 | Linear Programming I: Introduction | Linear Programming Guide, KT8.1, KT11.6 |
| Apr 21 | Linear Programming II: Algorithms, Problems, and Duality | Blog Post on Simplex |
| Apr 23 | Linear Programming III: Duality Theory and Zero-Sum Games | The Minimax Theorem without Duality |
| Apr 28 | The Minimax Theorem and Online Learning | |
| Apr 30 | Multiplicative Weight Update | Multiplicative Weights Guide |