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: 111 Cummington Mall, 138P.

Teaching Fellow: TBD.
Office Hours: TBD.
OH Location: TBD.

Lectures and Discussion Sections:
Tuesday/Thursday 3:30–4:45pm.
Discussion Section A2: Monday 3:30-4:25pm.
Discussion Section A3: Monday 4:40-5:30pm.

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 first thing Thurs. March 30, due 2:59pm Tues. April 4.
Final: TBD.

Lecture Schedule (Tentative)

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

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.