DS 320: Algorithms for Data Science
Spring 2024
Boston University


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:

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:

Below is a table with that will reflect what we cover in each lecture and will point to corresponding reading material. There is no required textbook for this course, as all materials are available online for free and we will switch between materials. Some shorthand for the reading material:
  • KTx = Kleinberg and Tardos chapter x.
  • CLRSx = Cormen, Leiserson, Rivest, and Stein chapter x.
  • Ex = Erickson chapter x.
Resources listed are optional, and often multiple versions of the same material are listed so that you can find what is best suited to you.

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