DS 320: Algorithms for Data Science
Spring 2023
Boston University

Course Details

Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 5–6pm and by appointment.
Office Location: CDS 1339, 665 Comm Ave.

Teaching Fellow: Freddy Reiber (freddyr@).
Office Hours: CDS 1338.
OH Location: Wednesday 3–5pm.

Lectures and Discussion Sections:
Tuesday/Thursday 3:30–4:45pm, CDS 164.
Discussion Section A2: Monday 3:30-4:25pm, CGS 311.
Discussion Section A3: Monday 4:40-5:30pm, EOP 262.

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: Out the night of Wed. Feb 22, due 11:59pm Mon. Feb 27.
Midterm II: Out the night of Wed. March 29, due 11:59pm Mon. April 3.
Final: Out the night of Wed. May 3, due 3pm Wed. May 10 (during assigned slot).

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 19 Overview and Policies, Runtime and Asymptotics Worksheet, Notes, Slides, KT2.1-2,4, CLRS3.1-2
Jan 24 Insertion Sort, Induction, and the Comparison-Based Lower Bound Worksheet, Notes, Induction Guide, CLRS2.1, 8.1
Jan 26 Abstract Data Types and Graphs Worksheet, Notes, CLRS10.1-2, 22.1, KT3.1, E5.1-4
Jan 31 Depth-First Search Worksheet, Notes, CLRS22.3, KT3.2-3 (skip BFS for now!), KT3.6, E6.1-3
Feb 2 Breadth-First Search and Testing Bipartiteness No Worksheet, Notes, KT3.2,4, CLRS22.2
Feb 7 Topological Sort and Greedy Algorithms I: Dijkstra's Algorithm Worksheet, Notes, KT4.4, CLRS24.3
Feb 9 Greedy Algorithms II: Finishing Dijkstra and Interval Scheduling Worksheet, Notes, Greedy-Stays-Ahead Guide, KT4.1
Feb 14 Greedy Algorithms III: Optimal Caching Worksheet, Notes, Greedy-Exchange Guide, KT4.3
Feb 16 Greedy Algorithms IV: Scheduling to Minimize Lateness Worksheet, Notes, KT4.2, similar to CLRS16.5
Feb 21 NO CLASS (Monday schedule)
Feb 23 Midterm—NO CLASS
Feb 28 Divide & Conquer I: Mergesort, Solving Recurrences Worksheet, Notes, Divide & Conquer Guide, KT5.1, CLRS4.3-5
Mar 2 Divide & Conquer II: Closest Pair of Points Worksheet, Notes, KT5.4
Mar 7 NO CLASS (Spring break)
Mar 9 NO CLASS (Spring break)
Mar 14 Divide & Conquer III: Integer and Matrix Multiplication Worksheet, Notes, KT5.5, CLRS4.2, Mitzenmacher's notes
Mar 16 Dynamic Programming I: Weighted Interval Scheduling Worksheet, Notes, Dynamic Programming Guide, KT6.1-6.2
Mar 21 Dynamic Programming II: Segmented Least Squares Worksheet, Notes, KT6.3
Mar 23 Dynamic Programming III: Knapsack Worksheet, Notes, KT6.4
Mar 28 Dynamic Programming IV: Bellman-Ford Worksheet, Notes, KT6.8
Mar 30 Midterm—NO CLASS
Apr 4 NP Completeness Worksheet, Notes, Complexity Guide, KT8.2-3, KT8/CLRS34 for addtl reading
Apr 6 Linear Programming I: Introduction Worksheet, Notes, Linear Programming Guide, KT8.1, KT11.6
Apr 11 Linear Programming II: Algorithms and Problems Worksheet, Notes, Blog Post on Simplex
Apr 13 Linear Programming III: Duality Worksheet, Notes
Apr 18 Linear Programming IV: More Duality and Zero-Sum Games Worksheet, Notes
Apr 20 The Minimax Theorem and Online Learning Worksheet, Notes
Apr 25 Multiplicative Weight Update Worksheet, Notes, Multiplicative Weights Guide
Apr 27 Approximation Algorithms: Random and Online Worksheet, Notes
May 2 Final Exam Review Worksheet, Notes

Huge gratitude to Justin Thaler, Adam Smith, Sam Taggart, Alexa Sharp, Tom Wexler, Michael Mitzenmacher, Tim Roughgarden, and Aaron Roth for their materials and/or for their publicly available lecture notes which have made the development of this course possible.