DS 320 - Algorithms for Data Science
The notes linked below are intended to supplement lecture material and textbook readings for DS 320. Beware: these notes are AI-generated, so read carefully and please check with the instructor if you find any mistakes.
Introduction
- Runtime and asymptotic analysis (what)
- Insertion sort (what)
- Induction and loop invariants (what)
- Abstract data types and graphs (what)
- Depth-first search (what)
- Topological sort (what)
- Breadth-first search (what)
Greedy Algorithms
- Shortest paths (what)
- Dijkstra’s algorithm (what)
- Dijkstra computes shortest paths on non-negative weights (why)
- Interval scheduling (what)
- Greedy stays ahead (what)
- Optimal caching (what)
- Belady’s farthest-in-future is optimal (why)
- Single machine scheduling (what)
- Minimizing maximum lateness (what)
- Greedy exchange argument (what)
Divide and Conquer
- Mergesort (what)
- Solving recurrences (what)
- The master theorem (why)
- Closest pair of points (what)
- Integer multiplication (what)
- Karatsuba runs in \(\Theta(n^{\log_2 3})\) time (why)
- Matrix multiplication (what)
- Strassen runs in \(\Theta(n^{\log_2 7})\) time (why)
Dynamic Programming
- Weighted interval scheduling (what)
- Knapsack (what)
- Segmented least squares (what)
- Bellman-Ford (what)
- Bellman-Ford computes shortest paths in \(n - 1\) rounds (why)
Linear Programming
- NP-completeness (what)
- Integer linear programming (what)
- Integer linear programming is NP-complete (why)
- Linear programming (what)
- Approximating NP-complete problems with relaxed linear programs (what)
- Algorithms for linear programming (what)
- Linear programming duality (what)
- Zero-sum games (what)
- The minimax theorem (why)
- Online learning (what)
- Multiplicative weight update (what)