CptS 223 – Advanced Data Structures Final Exam Outline The following outlines the topics you should know, and the things you need to be able to do, for the exam. In general, you will not be responsible for C++ code presented in class, except as noted in the outline; however, you may need to read and understand C++ code presented on the exam. The exam will be closed book, closed notes, and closed computer. Introduction • What is the point of this class? Math Review • Floors, ceilings, exponents and logarithms: Definitions and manipulations • Series: Definitions, manipulations, arithmetic and geometric series closed form • Proofs: Know definition, components, and how to use the following o Proof by induction o Proof by counterexample o Proof by contradiction • Recursion o Know definition and rules o Analyze running time of recursive algorithm C++ Review • Know definitions and how to use the following o Class, method, encapsulation o Constructor, destructor, accessor, mutator o Reference variable (&x) and call by reference o Copy constructor, operator overloading, operator= o Templates Algorithm Analysis • Why analyze an algorithm? • What do we measure and how do we measure it? • Line-by-line analysis • Best-case, worst-case and average-case analysis • Rate of growth: Definitions and notation (O, Ω, Θ, o) Abstract Data Types • Lists o Operations: Insert, Delete, Search o Implementations: vectors, singly-linked lists, double-linked lists, sentinels o Analysis of operations for each implementation • Stacks o Operations: Push, Pop, Top 1o Implementations: linked-list, vector o Analysis of operations for each implementation • Queues o Operations: Enqueue, dequeue o Implementations: linked-list, vector o Analysis of operations for each implementation • Standard Template Library (STL) o Use of vector, list, stack and queue template classes o Use of iterators Trees • Definitions: root, leaf, child, parent, ancestor, descendant, path, height, depth • Binary tree: Definition, traversals • Binary search tree (BST) o Definition o Operations: Insert, Delete, Search, FindMin, FindMax, traversals  Know how to perform these on a BST and show resulting BST  Know worst-case and average-case analysis of performance • AVL trees o Definition o Operations: Rotations, Insert, Lazy Delete, Search, FindMin, FindMax, traversals  Know how to perform these on an AVL tree and show resulting AVL tree  Know worst-case performance • Splay trees o Definition o Operations: Rotations, Zig-Zag, Zig-Zig, Insert, Delete, Search, FindMin, FindMax, traversals  Know how to perform these on a Splay tree and show resulting Splay tree  Know amortized cost per operation • B-trees o Definition and properties o M and L, and how to choose them o Operations: Insert, Delete, Search  Know how to perform these on a B-tree and show resulting B-tree  Know worst-case performance • STL set and map classes o Differences o How to use them Hashing • Hash functions, choosing good hash functions • Collision • Load factor • Know algorithms and analysis for the following o Collision resolution by chaining o Collision resolution by open-addressing 2 Linear, random and quadratic probing  Double hashing Priority Queues (Heaps) • Definition • Operations: insert, deleteMin, decreaseKey, increaseKey, remove • Binary heap o Definition o Implementation as array o Operations and their running times o BuildHeap and its analysis • Mergeable heaps o Binomial heap  Definition  Binomial tree  Algorithms and running times for above heap operations and Merge Sorting (know algorithm and analysis of all sort methods mentioned below) • InsertionSort • MergeSort • HeapSort • QuickSort • Lower bound on comparison sorting • Linear sorting o CountingSort o BucketSort • External sorting o External MergeSort Graphs • Definitions o Simple graph, directed graph, weighted graph o Path, cycle • Representation as adjacency matrix and adjacency list • Topological sort: Algorithm and running time • Shortest paths o Problem definition o Single-source and all-pairs o Negative weights and negative-weight cycles o Solutions (know algorithms and running times)  Unweighted shortest path  Dijkstra’s algorithm, and why it works  Graphs with negative edge costs  Acyclic graphs and critical path analysis • Network flow 34 o Problem definition  Network graph, flow graph, residual graph, augmenting path o Maximum flow algorithm and variants  Know algorithms and running times o Applications • Minimum spanning trees o Problem definition o Prim’s algorithm (know algorithm and running time) o Kruskal’s algorithm (know algorithm and running time) o Applications • Applications o Depth-first search (know algorithm and running time) o Breadth-first search (know algorithm and running time) o Biconnectivity and articulation points  Definition  Finding articulation points (know algorithm and running time) o Euler circuits  Definition  Finding Euler circuits (know algorithm and running time) o Strongly-connected components  Definition  Finding strongly-connected components (know algorithm and running time) o How to find the Kevin Bacon Number of an actor/actress NP-Completeness • Definition: P, NP, NP-Complete • Showing a new problem is NP-Complete by o Showing it is in the class NP (polynomially verifiable) o Showing how a known NP-Complete problem can be reduced to it in polynomial time • Definitions of these NP-Complete problems o Hamiltonian cycle o Traveling