[[
wikihub
]]
Search
⌘K
Explore
Activity
People
For Agents
Sign in
Explore
Activity
People
For Agents
Sign in
×
@jemoka / Jemoka Knowledge Base / raw/course/cs161_review/kbhsu_cs161_review_2.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "SU-CS161 TA Review" source: https://www.jemoka.com/posts/kbhsu_cs161_review_2/ --- 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