CSE310 Lecture 27 Overall Review Guoliang Larry Xue Department of CSE Arizona State University http www fulton asu edu xue Guoliang Xue asu edu Final Exam Logistics 110 minutes Closed Book Notes You are allowed one letter sized cheat sheet No electronic device allowed Visit the class website for announcements 2 Guoliang Xue asu edu Asymptotic Notations Asymptotic notations the three symbols Using the master method to solve recurrences there are three cases Commonly used summations 3 Guoliang Xue asu edu Binary Search Tree key 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 In Order Post Order root left sub tree right sub tree left sub tree root right sub tree left sub tree right sub tree root What does Successor X return Insertion Deletion 4 Guoliang Xue asu edu Example How to Insert a Node 14 12 14 5 2 18 19 15 9 13 17 12 5 2 18 19 15 9 13 17 14 5 Guoliang Xue asu edu Example How to Delete a Node Three cases 15 5 3 1 12 5 20 18 13 z 10 no child 15 16 3 23 2 3 10 has one child 3 20 18 13 10 23 15 3 16 12 10 y 6 7 13 7 15 y 6 5 23 6 7 z 20 18 12 6 3 23 7 15 5 16 z 12 18 6 7 15 20 12 10 6 5 16 z 3 18 10 23 6 16 12 20 13 15 5 3 20 13 7 6 18 16 12 10 23 20 13 18 23 7 Guoliang Xue asu edu Binary Search Tree Performance Best Average Worst case scenario Search Insertion Deletion What is a balanced BST 7 Guoliang Xue asu edu Red Black Tree 5 Properties What do these properties guarantee Is RBT a balanced tree No But it is approximately balanced What does that entail 8 Guoliang Xue asu edu Heaps and Priority Queues Binary heap min or max Insertion Deletion Decrease Key or Increase Key Linear Time Build Heap 9 Guoliang Xue asu edu Disjoint Set Array representation Find with or without path compression Union by rank 10 Guoliang Xue asu edu DS Initial 8 singleton sets Union 1 2 Union 3 4 Union 2 4 Union 5 6 Union 7 8 Union 8 6 Union 3 7 11 Guoliang Xue asu edu DS i 1 2 3 4 5 6 7 8 A 3 1 1 3 4 3 0 6 Find 8 w o PC Find 8 w PC Union 5 7 12 Guoliang Xue asu edu Graphs and Representations Graphs vertices edges paths cycles connected components strongly connected components Representations adjacency matrix adjacency list Given one representation draw the graph or construct another representation The transpose of a directed graph 13 Guoliang Xue asu edu Breadth First Search and Depth First Search Performing Breadth First Search BFS Tree Performing Depth First Search DFS Tree Computing discovery time and finish time 14 Guoliang Xue asu edu Minimum Spanning Trees Definition of a spanning tree Kruskal 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 Algorithm Example for Prim s Algorithm 15 Guoliang Xue asu edu 4 a b 11 8 4 a h 4 b 11 4 a 8 i g 8 i g 8 c 2 i 1 4 6 1 7 7 7 4 6 g 2 a 10 8 d 9 4 e a 10 8 h d 9 4 b 11 f 10 8 h d 9 4 b 14 f e a 10 11 8 16 h i g 8 i g 1 8 i g 1 8 i 1 7 4 6 g e f 10 d 9 e f 10 d 9 e 14 2 c 2 7 7 4 6 9 14 2 c 2 7 7 4 6 d 14 2 c 2 7 4 6 1 b 11 a 7 7 c 2 h f e 8 b 11 f 14 2 4 e 14 2 c 2 7 7 4 6 d 9 14 2 c 1 b h g 2 7 4 6 8 h 11 i 1 b 8 8 7 7 c 2 h 11 a 8 f 10 d 9 14 2 f e 10 Guoliang Xue asu edu Breadth First Search Algorithm r s t u 0 Q r s t u 1 0 2 t x v s r s 1 0 v w 2 1 2 y v w x t u r s t u 1 0 2 3 x 0 Q v 1 w x s t u 1 0 2 v 1 2 w x y Q x v u 1 1 y r 2 2 2 y wr Q 2 1 2 v w x Q r s r t x 1 1 2 2 17 2 2 3 y t u 0 2 3 2 1 2 3 v w x y Q Guoliang Xue asu edu Depth First Search Algorithm u 1 v w u 1 v 2 7 u 1 8 w F B 4 5 3 6 z x y z u 1 v2 w u 1 v 2 7 w 4 3 x y z B 4 5 3 6 x y z F v2 w u 1 8 F B 4 5 3 x y z v 2 7 w B 4 5 3 6 x y y v 2 7 z w 9 C B 4 5 3 6 10 x u 1 8 y v 2 7 z w 9 12 F u 1 3 6 x u 1 8 y w 9 C B 4 5 x F v 2 7 B C B 4 5 3 6 x y 1 8 2 7 9 12 4 5 3 6 10 11 10 11 B z z 18 two trees Guoliang Xue asu edu Topological Order What is a topological order Linear time algorithm for computing a topological order or finding a directed cycle in a directed graph 19 Guoliang Xue asu edu Topological Sort using queue 1 2 3 4 5 6 7 8 9 10 For each vertex v Compute in degree v Color v white If in degree v 0 insert v into a queue Q While Q is not empty Delete v from Q For all edges v u do in degree u if in degree u 0 insert u into Q color v black If all vertices are black the order they are deleted from Q form a topological sort Otherwise the graph has a cycle 20 Guoliang Xue asu edu Strongly Connected Components a Graph G b Component graph d 13 14 11 16 1 10 12 15 3 4 2 7 5 6 e f g h a b c 14 Transpose …
View Full Document
Unlocking...