Course Details
NOTE: The waitlist is automatically handled through My BU Student. Please address all questions about registration or automated prerequisites to cds-advising@bu.edu or mkcarven@bu.edu.
Instructors: Professors Jeffrey Considine and Kira Goldner.
Teaching Assistants: TBD.
Email: Please use private messages on Piazza for all email needs
Office Hours:
TBD.
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:00–12:15am, CGS 527.
Discussion Section B2: Friday 12:20-1:10pm, EOP 269.
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: 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 26.
Midterm II: Tues. March 31.
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 | 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 | Greedy Algorithms II: Interval Scheduling | Greedy-Stays-Ahead Guide, KT4.1 |
| Feb 12 | Greedy Algorithms III: Optimal Caching | Greedy-Exchange Guide, KT4.3 |
| Feb 17 | NO LECTURE (Monday Schedule) | |
| Feb 19 | Greedy Algorithms IV: Scheduling to Minimize Lateness | KT4.2, similar to CLRS16.5 |
| Feb 24 | Divide & Conquer I: Mergesort, Solving Recurrences | Divide & Conquer Guide, KT5.1, CLRS4.3-5 |
| Feb 26 | MIDTERM | |
| Mar 3 | Divide & Conquer II: Closest Pair of Points | KT5.4 |
| Mar 5 | Divide & Conquer III: Integer and Matrix Multiplication | KT5.5, CLRS4.2, Mitzenmacher's notes |
| Mar 10 | NO CLASS (Spring break) | |
| Mar 12 | NO CLASS (Spring break) | |
| Mar 17 | Dynamic Programming I: Weighted Interval Scheduling | Dynamic Programming Guide, KT6.1-6.2 |
| Mar 19 | Dynamic Programming II: Knapsack | KT6.4 |
| Mar 24 | Dynamic Programming III: Segmented Least Squares | KT6.3 |
| Mar 26 | Dynamic Programming IV: Bellman-Ford | KT6.8 |
| Mar 31 | MIDTERM | |
| Apr 2 | NP Completeness | Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading |
| Apr 7 | Linear Programming I: Introduction | Linear Programming Guide, KT8.1, KT11.6 |
| Apr 9 | Linear Programming II: Algorithms, Problems, and Duality | Blog Post on Simplex |
| Apr 14 | Linear Programming III: Duality Theory and Zero-Sum Games | The Minimax Theorem without Duality |
| Apr 16 | The Minimax Theorem and Online Learning | |
| Apr 21 | Multiplicative Weight Update | Multiplicative Weights Guide |
| Apr 23 | Approximation Algorithms: Random and Online | |
| Apr 28 | Stable Matching | KT1.1, KT2.3 |
| Apr 30 | Final Exam Review |