CptS 223 – Advanced Data Structures Exam 2 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. First, here are topics from the first exam you still need to know. 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, counterexample, contradition • 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, STL, iterators 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 • General use of list, stack and queue ADTs 1Trees • Definitions: root, leaf, child, parent, ancestor, descendant, path, height, depth • Binary tree: Definition, traversals Here are new topics since the first exam. 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 Linear, random and quadratic probing Double hashing o Rehashing o Extendible 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 23 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 • Solutions (know algorithms and running times) o Unweighted shortest path o Dijkstra’s algorithm, and why it works o Graphs with negative edge costs o Acyclic graphs and critical path analysis • Network flow o Problem definition Network graph, flow graph, residual graph, augmenting path o Maximum flow algorithm and variants Know algorithms and running times o
View Full Document
Unlocking...