DS 320: Algorithms for Data Science
Spring 2022
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: Habeen Chang (ahc98@).
Office Hours: Monday 11:30am–12:30pm.
OH Location: 111 Cummington Mall, Room 103.

Lectures and Discussion Sections:
Tuesday/Thursday 3:30–4:45pm, BRB 121.
Discussion Section A2: Monday 9:05-9:55am, CGS 111A.
Discussion Section A3: Monday 10:10-11:00am, IEC B06.

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

Midterm I: Out the night of Wed. Feb 23, due 11:59pm Mon. Feb 28.
Midterm II: Out first thing Thurs. March 31, due 2:59pm Tues. April 5.
Final: May 11, 3-5pm, BRB 121.

Lecture Schedule

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