We have NOT seen the exam We do NOT know the format of the exam What we are presenting is what we think is important for the exam Data Structures Steve Sinha and Winston Liaw Inheritance Method Calls Asymptotic Analysis Data Structures Binary Search Trees B Trees Heaps Hash Tables Graphs DFS BFS Topological Sort Dijkstra Kruskal Sorting Skip Lists Threading Synchronization Given the class definitions on the next slide which lines in class foobarbaz are illegal package foo import bar bar public class foobarbaz package foo static void main String args public class foo foo f new foo static void f1 bar r new bar protected boolean f2 int x baz z private String f3 String s r f3 3 f f2 3 package foo z baz f public class baz extends foo f new baz private String f3 String s f f2 3 z baz f package bar z f1 import foo foo r f1 public class bar extends foo foo r f1 protected boolean f3 int x Access table world public X package child X X protected X X default X private definer X X X X Static methods called according to static type Child type can be assigned to parent variable without a cast but the reverse requires one and the dynamic types must match 1 package foo import bar bar public class foobarbaz package foo static void main String args public class foo foo f new foo static void f1 bar r new bar protected boolean f2 int x baz z private String f3 String s r f3 3 ILLEGAL f f2 3 package foo z baz f ILLEGAL public class baz extends foo f new baz private String f3 String s f f2 3 z baz f package bar z f1 import foo foo r f1 ILLEGAL public class bar extends foo foo r f1 protected boolean f3 int x O Upper bound Worst case Lower bound both o strictly Upper bound More detail T n is O f n if and only if there exists positive constants C and N such that T n C f n for all n N T n is O f n if and only if there exists positive constants C and N such that T n C f n for all n N N 5 f n C f n T n 4n f n n T n T n 4n is O n f n n n T n is O f n if and only if there exists positive constants C and N such that T n C f n for all n N T n is f n if and only if T n is O f n and T n is f n T n is f n if and only if there exists positive constants C and N such that T n C f n for all n N Examples 5n2 1 is n2 3n is O n2 but 3n is NOT n2 because 3n is not n2 2 The nested loops give away the answer the outer loop executes x times the inner loop an average of x 2 times for a running time of O x2 Find the running time of the following code int foo int x int ans 1 for int i 0 i x i for int j 0 j i j ans i j return ans int foo int x int ans 1 for int i 0 i x i for int j 0 j i j ans i j return ans Remove 8 from A Tree B 6 G C F E What are the Pre In and Postorder traversals of this tree 1 D Preorder Inorder Postorder 8 3 5 7 11 9 ABCEGFD CEBAGDF ECBDFGA 13 Remove 8 from Final tree 6 6 8 3 1 5 7 11 9 9 3 1 13 5 7 11 13 Replace with successor left left most node in right subtree subtree 3 Insert 4 5 6 7 8 9 2 Remove 9 Suggest a sequence of operations that would create the 2 3 4 tree You can use removal as well as insertion 5 7 2 4 4 5 6 6 8 Insert 4 5 6 7 8 9 2 Remove 9 Insert 4 5 6 7 8 9 2 Remove 9 Touch node size 3 4 5 6 5 4 Insert 4 5 6 7 8 9 2 Remove 9 Insert 4 5 6 7 8 9 2 Remove 9 5 4 6 7 5 6 7 8 4 6 7 8 Touch node size 3 4 Insert 4 5 6 7 8 9 2 Remove 9 Insert 4 5 6 7 8 9 2 Remove 9 5 7 4 5 7 6 8 9 2 4 6 8 0 1 Add 9 76 54 3 33 21 to a max heap using only the array based representation 0 1 Insert at the last position in the heap Reheapify up if the element is greater than its parent swap them and repeat For an element at position n its children are at 2n 1 and 2n 2 For an element at position n its parent is at floor n 1 2 0 1 Add 9 76 54 3 33 21 to a max heap using only the array based representation 9 0 0 1 Add 9 76 54 3 33 21 to a max heap using only the array based representation 1 2 3 4 5 9 0 76 1 76 0 2 3 4 5 2 3 4 5 9 1 5 0 1 Add 9 76 54 3 33 21 to a max heap using only the array based representation 76 0 9 1 54 2 4 5 76 0 Add 9 76 54 3 33 21 to a max heap using only the array based representation 76 9 1 76 0 54 2 33 1 3 3 54 2 33 4 3 3 4 76 0 5 33 1 0 1 76 33 1 54 2 3 3 9 4 21 5 4 5 54 3 3 9 4 21 5 76 Tree Representation Remove the max from the heap 0 3 3 2 33 3 54 2 Add 9 76 54 3 33 21 to a max heap using only the array based representation 9 9 1 0 1 5 Add 9 76 54 3 33 21 to a max heap using only the array based representation 3 0 1 0 0 1 54 9 21 0 1 Replace the max element with the last element in the heap Reheapify down if one or both of its children is larger than it swap with the larger of the children and repeat For an element at position n its children are at 2n 1 and 2n 2 For an element at position n its parent is at floor n 1 2 6 0 1 Remove the max from the heap 76 0 33 1 21 0 54 3 2 33 1 3 54 3 2 3 21 5 5 9 4 Remove the max from the heap 9 4 0 1 …
View Full Document
Unlocking...