SU-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