---
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&rsquo;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&rsquo;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&rsquo;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 &ldquo;greedy choices don&rsquo;t limit future success.&rdquo;
activity selection Huffman Coding minimum spanning tree Prim&rsquo;s Algorithm Kruskal&rsquo;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
