[[
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.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "SU-CS161 Review" source: https://www.jemoka.com/posts/kbhsu_cs161_review/ --- Key Questions Does it work? Is it fast? Can I do better? General Structure worst-case analysis: what’s the performance on the worst input Big-oh notation Syllabus Divide and Conquer merge sort Karatsuba Integer Multiplication k-select We typically proof these’s correctness via induction, and we proof runtime by substitution method or master theorem. Randomized Algorithm quicksort: worst-case input, we use randomness after input is chosen sorting with a model of computation radix sort, in an ordered model limitations of comparison based sorting data structures red-black tree and its balacne rules hash table and Universal Hash Family and example of universal hash family DFS/BFS depth first search strongly connected components topological sort breadth first search shortest paths Shortest Paths Dijikstra’s Algorithm (DFS) Bellman-Ford Algorithm (DP) Floyd-Warshall Algorithm (DP) DP dynamic programming has a recipe: identify optimal substructure, write down the recursive formulation, fill in table to figure out full answer. Greedy greedy algorithm: make a series of choices and immediately commit. Proof: induction by “greedy choices don’t limit future success.” activity selection Huffman Coding minimum spanning tree Prim’s Algorithm Kruskal’s Algorithm Cuts and Flows minimum cut and maximum flow and the Folk-Fulkerson Algorithm Ethics Abstraction and Idealization, incommesurability tame problems and wicked problems Methods algos: Divide and Conquer, dynamic programming, greedy algorithm tools: worst-case analysis, asymptotic analysis, recurrence relation, induction data structures: graph, trees, hash family