Transcript here
Review for Final Exam • Non-cumulative, covers material since exam 2 • Data structures covered: – – – – Treaps Hashing Disjoint sets Graphs • For each of these data structures – – – – – – Basic idea of data structure and operations Be able to work out small example problems Prove related theorems Advantages and limitations Asymptotic time performance Comparison • Review questions are available on the web. Treaps – Definition • • • • It is both a BST and a binary min heap (heap is not a CBT) Each node has a key/priority pair (priority is a random number) It obeys BST order according to key value It obeys heap order according to priority value – Treap operations • • • • • find: same as BST (no change) insert: first insert as in BST, then rotate until heap order is restored remove: first find the item, then rotate it down until it becomes leaf Why rorate? What to do if item is not there or if it is a duplicate – Performance analysis • Height is almost always O(log n) • Why? – Comparison to BST, RBT, Splay tree Hashing – Hash table • Table size (primes) • Trading space for time – Hashing functions • Properties making a good hashing function • Examples of division and multiplication hashing functions • Operations (insert/remove/find/) – Collision management • Separate chaining • Open addressing (different probing techniques, clustering problem) – Worst case time performance: • O(1) for find/insert/delete if is small and hashing function is good – Limitations • Hard to answer order based queries (successor, min/max, etc.) Disjoint Sets – Equivalence relation and equivalence class • definitions and examples – Disjoint sets and up-tree representation • representative of each set • direction of pointers – Union-find operations • basic union and find operation • path compression (for find) and union by weight heuristics • time performance when the two heuristics are used: O(m lg* n) for m operations (what does lg* n mean) O(1) amortized time for each operation Graphs – Graph definitions • G = (V, E), directed and undirected graphs, DAG • path, path length (with/without weights), cycle, simple path • connectivity, connected component, connected graph, complete graph, strongly and weakly connectedness. – Adjacency and representation • adjacency matrix and adjacency lists, when to use which • time performance with each – Graph traversal: DF and BF – Single source shortest path • Breadth first (with unweighted edges) • Dijkstra’s algorithm (with weighted edges) – Topological order (for DAG) • What is a topological order (definitions of predecessor, successor, partial order) • Algorithm for topological sort