Homework #2UCSD Winter 2002, CSE 101, 1/31/02Question 1. Heap Data Structures. Consider a min-heap storing the values 1, 2, 3, ..., 15. Answereach 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 atlocation A[1].Part b) Which values can possibly be stored in entry A[2]? We have exactly 15 elements, which is (24-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 thesenumbers 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 atpositions 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 IsomorphismSolution:The straightforward way one could think of is to divide each binary tree into two subtrees, and thencheck if the subtrees are isomorphic. If two subtrees of a node in a tree are respectively isomorphicto two subtrees of a node in the other tree, then the parent trees should also be isomorphic. Bydoing this recursively, we could figure out the solution to our original problem. So let’s considerthe following DQ algorithm: Assumptions: - x, y are the roots of two binary trees, xT and yT. - Left(z) is a pointer to the left child of node z in either tree, and Right(z) points to the rightchild. 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 subtreerooted at z. Size(NIL) is defined to be 0. (Note: We can compute Size(x) recursively in lineartime by recursively computing and storing all sizes in the two subtrees and then definingSize(x) = 1 + Size(left(x)) + Size(right(x)). )- Then algorithm SameTree(x,y) returns a Boolean answer that says whether or not the treesrooted at x and y are isomorphic, i.e., the same if you ignore the difference between left andright 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 xT and yT are of both size n: If the subtrees of xT and yT are of different size l and r = n-l-1, then we do atmost one recursive call (suppose it doesn’t return false immediately) of size l andone 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 haveT(n) 3T(n/2) + O(1), because we will make at most 3 recursive sub-calls of sizeless than n/2. This seems to be the worst case, and we get T(n) = O(3log2n)according to the Master method. Now we conjecture this is true, that is, this is also true with the case when the subtrees areof different size l and r. We prove it by induction.Claim: T(n) c3log2nBase: choose appropriate c, the claim is true when n = 1.Induction: hypothesis: assume the claim is true for all kn 1Now let n = k+1, apply the induction hypothesis, we haveT(n) c3log2l+ c3log2)1(  ln+ c  cl13log2l+ c(n-l-1)13log2)1( ln+ c(cl+ c(n-l-1)) 13log2n+ c(c(n-1)) 13log2n+ cc3log2n- c13log2n+ cc3log2n (because 1n)Therefore, by induction, T(n) c3log2n is true for all n. So the runtime of this DQalgorithm should be T(n) = O(3log2n).By the way, there is another non-DQ solution to this problem in linear time. Briefly, first transformboth trees to left-heavy (or right-heavy) form, that is, the bigger subtree is always on the left (orright). This can be done using several O(n) DFS traversals. Then by using DFS compare the size ofsubtrees 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 itmeans that 4 elements in X are less than the median and n-5 elements are greater. This then impliesthat the remainder of the elements less than the median are in Y[], so we know that in Y[] the first n-4 elements are less than the median and the last 5 elements are greater than the median. What weneed to do is to perform a binary search for the median in one of the arrays. The search is guided bythe 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 tothe right of (n-i+1) in Y. The following is a recursive DQ algorithm, which essentially is amodified 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 the Master Method we get that the running time of this proposed algorithm isΘ(lg n). Since the running time of the Merge function is O(n), the call to it in the base case does notaffect the overall running time complexity of the main algorithm since the arguments of Merge arearrays of constant length (i.e., length <= 2).Question4. Skyline problem:Solution:We divide the inputs into smaller subset (generally of equal size), then solve (conquer) each subsetrecursively, and merge the solutions together. Assume n is a power of 2. (If not, add at most nbuildings of height 0 to the list to make the total a power of 2. This at most doubles n.) Now wegive the pseudo code: Skyline(Buildings[1…n]: Array of triples of real numbers(start, end, height))::List of points(x, y)sorted by first co-ordinate x);1. IF n=1