TODO: create a table—algo, problem it solves, runtime, conditions. Prof lemmas?

Shortest-Path Algorithms

Dijikstra’s Algorithm

Intuition: subpaths of shortest paths are shortest paths. \(O\qty(n \log n + m)\)

Bellman-Ford Algorithm

Intuition: Dijkstra but k rounds across the whole graph

Floyd-Warshall Algorithm

All-pairs shortest path. Naive solution is \(O\qty(n)O\qty(nm) = O\qty(n^{2}m)\) by running bell

DP Problems

• fib
• shortest path
• longest common subsequence
• knapsack of all kinds
• independent set

Greedy

• activity selection
• scheduling
• DO THIS ON REVIEW: Huffman Coding is Greedy
• minimum spanning tree