Homework 2 UCSD Winter 2002 CSE 101 1 31 02 Question 1 Heap Data Structures Consider a min heap storing the values 1 2 3 15 Answer each of the following questions and justify your answers Part a Where in the heap can the value 1 possibly go Since it is a min heap the minimum element has to go to the root of the tree which is at location A 1 Part b Which values can possibly be stored in entry A 2 We have exactly 15 elements which is 2 4 1 This means we have a full heap of height 3 There must be 6 elements below A 2 thus we can have 2 9 at this position since for these numbers it is true that there are at least 6 elements that are greater Part c Where in the heap can the value 15 possibly go 15 must go in a leaf since there are no elements that are greater than it Leaves are at positions A 8 A 15 Part d Where in the heap can the value 6 possibly go Anywhere but the root A 1 Question2 Binary Tree Isomorphism Solution The straightforward way one could think of is to divide each binary tree into two subtrees and then check if the subtrees are isomorphic If two subtrees of a node in a tree are respectively isomorphic to two subtrees of a node in the other tree then the parent trees should also be isomorphic By doing this recursively we could figure out the solution to our original problem So let s consider the following DQ algorithm Assumptions x y are the roots of two binary trees Tx and T y Left z is a pointer to the left child of node z in either tree and Right z points to the right child If the node doesn t have a left or right child the pointer returns NIL Each node z also has a field Size z which returns the number of nodes i in the subtree rooted at z Size NIL is defined to be 0 Note We can compute Size x recursively in linear time by recursively computing and storing all sizes in the two subtrees and then defining Size x 1 Size left x Size right x Then algorithm SameTree x y returns a Boolean answer that says whether or not the trees rooted at x and y are isomorphic i e the same if you ignore the difference between left and right pointers Program SameTree x y Nodes Boolean IF Size x Size y THEN return False halt IF x NIL THEN return True halt IF SameTree Left x Left y THEN return SameTree Right x Right y ELSE return SameTree Right x Left y AND SameTree Left x Right y Time analysis If the two trees are of different sizes the program immediately returns false If Tx and T y are of both size n If the subtrees of Tx and T y are of different size l and r n l 1 then we do at most one recursive call suppose it doesn t return false immediately of size l and one of size r So we have T n T l T n l 1 O 1 If all subtrees are of equal size then all of them should be size n 1 2 thus we have T n 3T n 2 O 1 because we will make at most 3 recursive sub calls of size less than n 2 This seems to be the worst case and we get T n O n log 2 3 according to the Master method Now we conjecture this is true that is this is also true with the case when the subtrees are of different size l and r We prove it by induction Claim T n c n log 2 3 Base choose appropriate c the claim is true when n 1 Induction hypothesis assume the claim is true for all 1 n k Now let n k 1 apply the induction hypothesis we have T n c l log 2 3 c n l 1 log 2 3 c cl l log 2 3 1 c n l 1 n l 1 log 3 1 c cl c n l 1 n log 2 3 1 c c n 1 n log 2 3 1 c c n log 2 3 c n log 2 3 1 c c n log 2 3 because n 1 Therefore by induction T n c n log 2 3 is true for all n So the runtime of this DQ algorithm should be T n O n log 2 3 2 By the way there is another non DQ solution to this problem in linear time Briefly first transform both trees to left heavy or right heavy form that is the bigger subtree is always on the left or right This can be done using several O n DFS traversals Then by using DFS compare the size of subtrees in all levels we will get the answer Question 3 Median of two sorted lists CLRS 9 3 8 2nd edition pg 193 Solution We have to take advantage of the fact that we know that X and Y are sorted If X 5 is the median it means that 4 elements in X are less than the median and n 5 elements are greater This then implies that the remainder of the elements less than the median are in Y so we know that in Y the first n4 elements are less than the median and the last 5 elements are greater than the median What we need to do is to perform a binary search for the median in one of the arrays The search is guided by the contents of the other array In particular if we claim that the median is the i th element in X then we have three cases Case 1 If X i Y n i 1 then the claim is true Case 2 If X i Y n i 1 then the claim is false and the actual median is to the right of i in X or to the left of n i 1 in Y Case 3 If X i Y n i 1 then the claim is false and the actual median is to the left of i in X or to the right of n i 1 in Y The following is a recursive DQ algorithm which essentially is a modified binary search in a sorted list FindMedian X 1 n Y 1 n n length X if n 2 Z Merge X 1 n Y 1 n return Z 2 end c floor n 1 2 if X c Y n c 1 return X c if X c Y n c 1 return findMedian X 1 c Y n c 1 n return findMedian X c n Y 1 n c 1 The algorithm is essentially the same as binary search The recurrence relation for it is T n T n 2 O 1 Using …