ConclusionsCourse OverviewAnalysis ToolsPerformanceObject-Oriented Design in C++Basic Data StructuresAdvanced Data StructuresAdvanced Data StructuresAdvanced Data StructuresAdvanced Data StructuresAdvanced Data StructuresAlgorithm DesignAlgorithm Design and Analysis: SortingAlgorithm Design and Analysis: SortingHard ProblemsClasses of Hard ProblemsNP-Complete ProblemsApplicationsProblem-solvingSummary111111ConclusionsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityCourse Overview Advanced data structures Trees, hash tables, heaps, disjoint sets, graphs Algorithm development and analysis Insert, delete, search, sort Applications Object-oriented implementation in C++2Analysis Tools Counting primitive operations Exponents, logarithms and summations Analyzing recursive solutions Recurrence equations: T(N) = 2T(N/2) + Θ(N) Proof by induction and contradiction Rate of growth notation: O, Ω, Θ Summarizes analysis Eases comparison among solutions34PerformanceObject-Oriented Design in C++ Encapsulation: Class = Data + Methods Information hiding Hiding implementation details Operator overloading Perform familiar operations (<, ==) with complex elements Templates Design data structures independent of element type Standard Template Library (STL)5Basic Data Structures Lists, stacks, queues O(1) insert/delete O(N) search STL: vector, list, stack, queue6Advanced Data Structures Trees Binary search tree O(log N) insert, delete and search Balanced BST: AVL and Splay Massive trees: B-tree STL: set, map7Advanced Data Structures Hash tables O(1) insert and search Collision resolution Chaining, Open addressing Good hash functions, probe sequences Rehashing Extendible hashing STL+: hash_set, hash_map8Advanced Data Structures Heaps (Priority Queues) Keep elements partially ordered Heap = complete binary tree O(log N) insert, delete (worst-case) O(1) insert (average-case) Mergeable heaps: Binomial heap STL: priority_queue9Advanced Data Structures Disjoint sets Implement equivalence class operations Find and Union Tree representation Union by rank Path compression O(1) find, union (average-case)10Advanced Data Structures Graphs Adjacency list vs. adjacency matrix Algorithms Breadth-first search (BFS): O(V+E) Depth-first search (DFS): O(V+E) Topological sort (DFS): O(V+E) Shortest path: O(E log V) Maximum flow: O(E2log V) Minimum spanning tree: O(E log V) Biconnectivity and articulation points (DFS): O(V+E) Euler circuits (DFS): O(V+E) Strongly-connected components (DFS): O(V+E)11Algorithm Design12Algorithm Design and Analysis: Sorting Comparison sorts Insertion sort Merge sort Heap sort Quicksort Lower bound: Θ(N log N) Linear sorting Counting sort Bucket sort External sorting13Algorithm Design and Analysis: SortingSort WorstCaseAverageCaseBestCaseCommentsInsertionSort Θ(N2) Θ(N2) Θ(N) Fast forsmall NMergeSort Θ(N log N) Θ(N log N) Θ(N log N) Requires memoryHeapSort Θ(N log N) Θ(N log N) Θ(N log N) Large constantsQuickSort Θ(N2) Θ(N log N) Θ(N log N) Small constants14Hard ProblemsInput Size vs. Complexity10 20 30 40 50 60n .00001 s .00002 s .00003 s .00004 s .00005 s .00006 sn2.0001 s .0004 s .0009 s .0016 s .0025 s .0036 sn3.001 s .008 s .027 s .064 s .125 s .216 sn5.1 s 3.2 s 24.3 s 1.7 min 5.2 min 13.0 min2n.001 s 1.0 s 17.9 min 12.7 days35.7 years366 centuries3n.059 s 58 min 6.5 years3855 centuries2x108centuries1.3 x 1013centuries15Classes of Hard Problems16All ProblemsNP-HardNPPNP-CompleteDifficultyDoes P = NP ?NP-Complete Problems The hardest problems in NP Prove problem is NP-Complete by “reducing” known NP-Complete problem to it Determining the class of a problem helps us know the best performance we can achieve Approximation algorithms17Applications Operating systems Compilers Databases Route planning Dictionary/symbol lookup Molecular analysis Image processing Theory of computation Many more …18Problem-solving19Summary Moral Appropriate data structures ease design and improve performance Challenge Design appropriate data structure and associated algorithms for a problem Analyze to show improved performance20PLEASE FILL OUT YOUR ON-LINE COURSE
View Full Document
Unlocking...