CSE310 HW02, Solution and Grading Keys1. (15 pt) Suppose we have two algorithms A1 and A2 for solving the same problem. Let T1(n) bethe worst case time complexity of Algorithm A1 and T2(n) be the worst case time complexityof Algorithm A2. We know that T1(1) = 1 and T1(n) = 7·T1(n/2)+f(n), where f(n) = Θ(n2).We also know that T2(1) = 1 and T2(n) = 63 · T2(n/4) + 30 · n2.• Use the master method to decide T1(n). Follow all the steps as illustrated in class(a, b, logba, etc).a = 7, b = 2, logba = 2.80735. For ∈ (0, 0.80735), we have f (n) =O(n2.80735−). Therefore we have case-1 in the Master method. As a result,T1(n) = Θ(n2.80735).Grading:+1 pt for a;+1 pt for b;+1 pt for logba;+1 pt for the correct case;+1 pt for the correct answer.• Use the master method to decide T2(n). Follow all the steps as illustrated in class(a, b, logba, etc).a = 63, b = 4, logba = 2.98864. For ∈ (0, 0.98864), we have f(n) =O(n2.98864−). Therefore we have case-1 in the Master method. As a result,T2(n) = Θ(n2.98864).Grading:+1 pt for a;+1 pt for b;+1 pt for logba;+1 pt for the right case;+1 pt for the right answer.• Which algorithm is faster? Why?Since T1(n) = O(T2(n)), but T2(n) 6= O(T1(n)), we conclude that A1 is faster.Grading:+3 pts for the answer;+2 pts for the justification.12. (15 pt) Let A[1..n] be an array of n distinct numbers. (i, j) is called an inversion of A if i < jand A[i] > A[j]. The inversion number of A, denoted by inversion(A), is the total numberof inversions of array A.• What is the relationship of the running time of insertion sort and the inversion numberof the input array? Justify your answer.The running time of insertion sort on A is Θ(n+inversion(A)), since the numberof element-wise comparisions used by insertion sort is n − 1 + inversion(A).Grading:+3 pts for the answer;+2 pts for the justification.• List all the inversions of the following array.i 1 2 3 4 5 6A[i] 8 7 9 3 4 5<1, 2>, <1, 4>, <1, 5>, <1, 6>;<2, 4>, <2, 5>, <2, 6>;<3, 4>, <3, 5>, <3, 6>;Grading:-0.5 pt for each wrong entry (either an inversion not listed or a non-inversion listed).Take 2 pts off if the inversions are represented using < A[i], A[j] > rather than < i, j >.• Suppose you have an array A with n elements. Array B is obtained from array A bydeleting an element in array A and then inserting the deleted element into some place ofthe array. Find an upper-bound on |inversion(A) − inversion(B)|.We only need to consider the case where the inversion is increased. The movement ofthe first element can increase the inversion by at most n − 1 (which is achievable whenthe array is sorted). The movement of the second element can increase the inversion byat most n − 2 (which is again achievable). Therefore the upper bound is 2n − 3.Grading:5 pts for perfect answer;4 pts for saying 2n;3 pts for saying Θ(n);1 pts for saying O(n);23. (10 pt) Given the sequence8, 1, 2, 7, 6, 5, 3, 4List all the element comparisons made by insertion sort in the corresponding order. Use< a, b > to denote a comparison of a and b. We will denote Ai to denote the insertion ofelement i. The number of comparisons for the insertion of each element is given below:Element Comparisons Sorted arrayA1 no comparisons 8A2 < 1, 2 > 1, 8A3 < 2, 3 >, < 1, 3 > 1, 2, 8A4 < 3, 4 >, < 2, 4 > 1, 2, 7, 8A5 < 4, 5 >, < 3, 5 >, < 2, 5 > 1, 2, 6, 7, 8A6 < 5, 6 >, < 4, 6 >, < 3, 6 >, < 2, 6 > 1, 2, 5, 6, 7, 8A7 < 6, 7 >, < 5, 7 >, < 4, 7 >, < 3, 7 >, < 2, 7 > 1, 2, 3, 5, 6, 7, 8A8 < 7, 8 >, < 6, 8 >, < 5, 8 >, < 4, 8 >, < 3, 8 > 1, 2, 3, 4, 5, 6, 7, 8Grading: -0.5 pt for each wrong/non-existent comparison.4. (10 pts) Prove that in a binary tree with n elements, the height of the tree is greater than orequal to blog2(n)c. Prove that in a complete binary tree with n elements, the height of thetree is exactly blog2(n)c.Proof of the first claim: We prove this by induction on the height of the tree T . Wewill use size(T ) to denote the number of nodes in T and use height(T ) to denote the heightof the tree T . The claim to be proved is equivalent to size(T ) ≤ 2height(T )+1− 1. Whenheight(T ) = 0, the tree contains a single node, i.e., size(T ) = 1. Since 1 ≤ 20+1− 1, thisverifies that height of the tree is 0.Now assume that the claim is true for binary trees of height no more than H, i.e.,height(T ) ≤ H ⇒ size(T ) ≤ 2height(T )+1− 1. (0.1)Assume that T is a binary tree (rooted at x) with height H + 1. There are two cases: (1) xhas only one child node c; (2) x has a left child l and a right child r. In any case none of thesubtrees rooted at a child node of x has height greater than H. Therefore, none of them canhave size bigger than 2H+1− 1. Since the size of T is 1 plus the sum of the sizes of its twosubtrees, we havesize(T ) ≤ 1 + 2 × (2H+1− 1) ≤ 2H+2− 1.3This proves that the claim is true for trees of height H + 1 as well. By the principle ofmathematical induction, the claim is true for all binary trees. 2Grading: 2 pts for the base case, 3 pts for the induction step.If other methods are used, grade similarly.Proof of the second claim: Let T be a complete binary tree of size size(T ). Let k bethe integer such that2k≤ size(T ) < 2k+1.Since T is a complete binary tree, nodes 2k, 2k+ 1, . . . , size(T ) are the nodes at the lowestlevel. The other 2k− 1 nodes form a full binary tree, which has a height of k − 1. Thereforethe height of T is k. It follows from the choice of k, we have 2k≤ size(T ) < 2k+1. Thereforek = blog2(size(T ))c. 2.Grading: 3 pts for finding the right k (height), 2 additional pts for the
View Full Document
Unlocking...