CptS 223 – Advanced Data Structures Exam 1 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 • Factorials and Stirling’s approximation • Series: Definitions, manipulations, arithmetic and geometric series closed form • Modular arithmetic • 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) • Maximum subsequence sum problem o Definition o Four different algorithms o Analysis of each algorithm • Binary search problem: Definition, algorithm, analysis 12 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 o 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 o • 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
View Full Document
Unlocking...