CSE310 Lecture 27: Overall ReviewFinal Exam LogisticsAsymptotic NotationsBinary-Search TreeExample: How to Insert a Node?Example: How to Delete a Node?Binary Search Tree - PerformanceRed-Black TreeHeaps and Priority QueuesDisjoint SetDSSlide 12Graphs and RepresentationsBreadth First Search and Depth First SearchMinimum Spanning TreesPowerPoint PresentationSlide 17Slide 18Topological OrderTopological Sort using queueSlide 21Shortest PathsSlide 23Dynamic Data StructuresSlide [email protected] Lecture 27:CSE310 Lecture 27:Overall ReviewOverall ReviewGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://www.fulton.asu.edu/[email protected] Exam LogisticsFinal Exam Logistics110 minutes, Closed Book/NotesYou are allowed one letter-sized cheat sheetNo electronic device allowedVisit the class website for [email protected] NotationsAsymptotic notations: the three symbols.Using the master method to solve recurrences: there are three cases.Commonly used [email protected] Treekey[left_child]<=key[parent]<=key[right_child]Where is the largest element stored in a BST?Where is the largest element in a min-heap?Tree walks:Pre-Order: root, left sub-tree, right sub-treeIn-Order: left sub-tree, root, right sub-treePost-Order: left sub-tree, right sub-tree, rootWhat does Successor(X) return?Insertion/[email protected]: How to Insert a Node?Example: How to Insert a Node?2 9512181917141413152 [email protected]: How to Delete a Node?Example: How to Delete a Node?Three cases:15531067231618201312z1553106723161820121553106723182013121563107231618201312y15536231618201312z107(1)no child15531067231618201312z(2)has one child15531067231618201312zy(3)[email protected] Search Tree - PerformanceBest/Average/Worst case scenarioSearch/Insertion/DeletionWhat is a balanced [email protected] Tree5 PropertiesWhat do these properties guarantee?Is RBT a balanced tree?No!But it is approximately balanced.What does that [email protected] and Priority QueuesBinary heap (min or max)InsertionDeletionDecrease Key (or Increase Key)Linear Time Build [email protected] SetArray representationFind with or without path compressionUnion by [email protected]Initial: 8 singleton setsUnion(1,2)Union(3,4)Union(2,4)Union(5,6)Union(7,8)Union(8,6)Union(3,7)[email protected]Find(8) w/o PCFind(8) w PCUnion(5,7)i 1 2 3 4 5 6 7 8A -3 1 1 3 4 3 0 [email protected] and RepresentationsGraphs and RepresentationsGraphs, vertices, edges, paths, cycles, connected components, strongly connected componentsRepresentations: adjacency matrix, adjacency list; Given one representation, draw the graph or construct another representation.The transpose of a directed [email protected] First Search and Depth First SearchBreadth First Search and Depth First SearchPerforming Breadth First SearchBFS TreePerforming Depth First SearchDFS TreeComputing discovery time and finish [email protected] Spanning TreesMinimum Spanning TreesDefinition of a spanning treeKruskal’s algorithm for computing a minimum spanning tree in an undirected graph. Know the algorithm and its time complexity.Prim’s algorithm for computing a minimum spanning tree in an undirected graph. Know the algorithm and its time complexity.Example for Kruskal’s AlgorithmExample for Prim’s [email protected] e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 1446bhcgdfia e481 2109782711 [email protected]0Breadth-First Search Algorithmr s t uv w x ysQ0101r s t uv w x ywQr1 110122r s t uv w x yrQtx1 2 2120122r s t uv w x ytQxv2 2 21201223r s t uv w x yxQvu2 2 312012233r s t uv w x yQ = [email protected]/Depth-First Search Algorithmu v wx y z1/4/2/3/u v wx y z1/4/52/3/u v wx y zB1/4/52/73/6u v wx y zB1/4/52/73/6u v wx y zBF1/84/52/73/6u v wx y zBF1/84/52/73/69/u v wx y zBFC1/84/52/73/69/10/u v wx y zBFC1/84/52/73/69/1210/11u v wx y zBFC1/84/52/73/69/1210/11two [email protected] OrderTopological OrderWhat is a topological order.Linear time algorithm for computing a topological order or finding a directed cycle in a directed [email protected] Sort using queueTopological Sort using queue1. For each vertex v{2. Compute in-degree(v).3. Color v white.4. If in-degree(v)=0, insert v into a queue Q.}5. While Q is not empty{6. Delete v from Q.7. For all edges (v, u) do{8. in-degree(u)--;9. if in-degree(u)=0, insert u into Q;}10. color v black;}If all vertices are black, the order they are deleted from Q form a topological sort. Otherwise, the graph has a [email protected] Connected Components13/1412/1511/163/48/95/6a b de f h1/102/7cgGraphGabefgcdhComponentgraphStronglyconnectedcomponentsa b de f [email protected] PathsShortest PathsDefinitionsDijkstra’s algorithm for single-source shortest paths. Know the algorithm and its time complexity.Draw the Shortest Path [email protected]’s Single-Source Shortest Path Alg.Dijkstra-SP(G, w, s)1. Initialize-Single-Source(G, s)2. S := 3. Q := V[G]4. while Q do5. u := Extract-Min(Q)6. S := S {u}7. for each vertex v u.adj do8. Relax(u, v, w)0105219326471050105219326478514010521932647785130105219326477859010521932647723Guoliang.Xue@asu.edu24Dynamic Data StructuresDynamic Data StructuresThe Heap Data StructureBinary Search TreesRed-Black TreesDisjoint [email protected] Data StructuresDynamic Data StructuresWhat data structures have the following properties?Insertion in log(n) timeDeletion in log(n) timeDecreaseKey in log(n) timeSearching in log(n)
View Full Document
Unlocking...