1Course ReviewCpt S 223Fall 20092Final ExamWhen: Tuesday (12/15) 8 -10amWhere: in classClosed book, closed notesComprehensiveMaterial for preparation:Lecture slides & class notesHomeworks & program assignments Weiss book3Course OverviewProving techniques and recursionAsymptotic notation & analysis Data structures & purpose:GraphNetwork, interactionsHash tableSearching (unordered), string=>int mappingUnion-findDisjoint sets Binary heap, binomial heapPrioritizingBST, AVL tree, B-treeSearching (ordered) Queue, stackFIFO, LIFOLinked list, arrayMaintaining a set of elements4Course Review …Program designTradeoffs: space, time efficiency, design simplicityRuntime measurement, plotting and explanationSTL:vector, list, queue, stackset, map, multiset, multimappriority_queuehash_set, hash_map5Developmental CycleUserProblemspecification…Garage Tools(data structures)refine- optimize costs - maximize performance- space-time tradeoffs- design simplicityAnalysisHigh-level design(tools)Algorithm design(methods)(testing)Experimentation- Simulations- real data- benchmarkinginput6Objectives1.Introduce new & advanced data structures2.Introduce algorithmic design and analysis3.Solve problems using different data structures and design techniques, and compare their performance and tradeoffs4.Implement algorithms and data structures in C++7Math ReviewSeries: Definitions, manipulations, arithmetic and geometric series closed form Proofs: Know definition, components, and how to use the following Proof by induction Proof by counterexample Proof by contradiction Recursion Know definition and rules Analyze running time of recursive algorithm Tail recursion8Algorithmic AnalysisWhy analyze an algorithm?Line-by-line analysis Input:Best-case, worst-case and average-case analysisProblem:Upper bound, lower boundRate of growth for algorithms: Definitions and notation (O, Ω, Θ, o, w)9Abstract Data Types Lists  Operations: Insert, Delete, Search  Implementations: vectors, singly-linked lists, double-linked lists, sentinels  Analysis of operations for each implementation  Stacks (LIFO) Operations: Push, Pop, Top  Implementations: linked-list, vector  Analysis of operations for each implementation  Queues (FIFO) Operations: Enqueue, dequeue  Implementations: linked-list, vector  Analysis of operations for each implementation  Standard Template Library (STL)  Use of vector, list, stack and queue template classes  Use of iterators  Know all the tradeoffs (in time & space) between all these data structures10Trees (in memory)Definitions: root, leaf, child, parent, ancestor, descendant, path, height, depth Binary tree: Definition, traversals Storing/representation:All children: use array or listStore pointers to only Leftmost child and right siblingOther representations possibleTree traversalsInorder, postorder and preorder11Search Trees Binary search tree (BST)  Definition  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  Balanced BST (AVL trees) Definition  Operations: Rotations & Cases, Insert, Lazy Delete, Search, FindMin, FindMax  Know how to perform these on an AVL tree and show resulting AVL tree  Know worst-case performance  STL set and map classes  Differences  How to use them12Disk-based Search TreesB-trees Definition and properties Input parameters: B, D, KM and L, and how to choose them Operations: Insert, Delete, Search Know how to perform these on a B-tree and show resulting B-tree Know worst-case performanceKnow how to calculate height of a B-tree13Priority QueuesBinary heap, Binomial heapsStructure and heap-order propertiesImplementation:Binary heap Tree structure can be implemented as an array Where nodes are stored in breadth-first orderChildren of node at A[i] are at: A[2i] and A[2i+1]Binomial heapArray of pointers to each binomial treelog n binomial tree pointers14Run-times for each heap operationO(log n)O(log n)O(1) Binomial HeapO(n)O(log n)O(1) -amortizedBinary heapMergeDeleteMinInsertOther operations: • deleteMax() • decreaseKey(p,v), increaseKey(p,v) • remove(p)Two main techniques: PercolateUp and PercolateDown15Union-Find data structurePurpose: Disjoint set operations (union & find)Typical application:For computing subsets defined by equivalence relationSmart Union (by rank, by size)Smart Find (path compression)16Heuristics & their GainsO(m Inv.Ackermann(m,n))= O(m log*n)Union-by-rank, Path compression FindO(m log n)Arbitrary Union, Path compression FindO(m log n)Union-by-rank,Simple FindO(m log n)Union-by-size, Simple FindO(m n)Arbitrary Union, Simple FindWorst-case run-time for m operationsExtremely slowGrowing function17Hashing Hash functions (purpose: string to integer) Choice of a “good” hash functions Reduce chance of collision Relatively smaller key value Does not need huge hash table size Hash table purpose: to search efficiently to map string labels to integer ids efficiently Load factor  Know algorithms & analysis for the following Collision resolution by chaining Collision resolution by open-addressingLinear probing, quadratic probingDouble hashing Rehashing18SortingKnow algorithms & analysis of all sort methods mentioned belowInsertion sortMerge sortHeap sortQuick sortLower bound for sorting Integer sortingCounting sortBucket sortAPPLICATIONS OF SORTING19GraphsDefinitions Simple graph, directed graph, weighted graph Path, cycle Representation as adjacency matrix and adjacency list Topological sort: Algorithm and running time20Thank You & Good Luck !COURSE EVALUATIONS