SU-CS161 TA Review

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\left(n \log n + m\right)
Bellman-Ford Algorithm Intuition: Dijkstra but k rounds across the whole graph
Floyd-Warshall Algorithm All-pairs shortest path. Naive solution is O\left(n\right)O\left(nm\right) = O\left(n^{2}m\right) 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