Chapter 7Michelle Bodnar, Andrew LohrSeptember 17, 2017Exercise 7.1-113 19 9 5 12 8 7 4 21 2 6 1113 19 9 5 12 8 7 4 21 2 6 1113 19 9 5 12 8 7 4 21 2 6 119 19 13 5 12 8 7 4 21 2 6 119 5 13 19 12 8 7 4 21 2 6 119 5 13 19 12 8 7 4 21 2 6 119 5 8 19 12 13 7 4 21 2 6 119 5 8 7 12 13 19 4 21 2 6 119 5 8 7 4 13 19 12 21 2 6 119 5 8 7 4 13 19 12 21 2 6 119 5 8 7 4 2 19 12 21 13 6 119 5 8 7 4 2 6 12 21 13 19 119 5 8 7 4 2 6 11 21 13 19 12Exercise 7.1-2If all elements in the array have the same value, PARTITION returns r. Tomake PARTITION return q = b(p + r)/2c when all elements have the samevalue, modify line 4 of the algorithm to say this: if A[j] ≤ x and j(mod2) =(p + 1)(mod2). This causes the algorithm to treat half of the instances of thesame value to count as less than, and the other half to count as greater than.Exercise 7.1-3The for loop makes exactly r − p iterations, each of which takes at mostconstant time. The part outside the for loop takes at most constant time. Sincer − p is the size of the subarray, PARTITION takes at most time proportionalto the size of the subarray it is called on.Exercise 7.1-4To modify QUICKSORT to run in non-increasing order we need only modifyline 4 of PARTITION, changing ≤ to ≥.1Exercise 7.2-1By definition of Θ, we know that there exists c1, c2so that the Θ(n) termis between c1n and c2n. We make that inductive hypothesis be that c1m2≤T (m) ≤ c2m2for all m < n, then, for large enough n,c1n2≤ c1(n − 1)2+ c1n ≤ T (n − 1) + Θ(n)= T (n) = T (n − 1) + Θ(n) ≤ c2(n − 1)2+ c2n ≤ c2n2Exercise 7.2-2The running time of QUICKSORT on an array in which evey element has thesame value is n2. This is because the partition will always occur at the last po-sition of the array (Exercise 7.1-2) so the algorithm exhibits worst-case behavior.Exercise 7.2-3If the array is already sorted in decreasing order, then, the pivot element isless than all the other elements. The partition step takes Θ(n) time, and thenleaves you with a subproblem of size n − 1 and a subproblem of size 0. Thisgives us the recurrence considered in 7.2-1. Which we showed has a solutionthat is Θ(n2).Exercise 7.2-4Let’s say that by “almost sorted” we mean that A[i] is at most c positionsfrom its correct place in the sorted array, for some constant c. For INSERTION-SORT, we run the inner-while loop at most c times before we find where to insertA[j] for any particular iteration of the outer for loop. Thus the running timetime is O(cn) = O(n), since c is fixed in advance. Now suppose we run QUICK-SORT. The split of PARTITION will be at best n − c to c, which leads to O(n2)running time.Exercise 7.2-5The minimum depth corresponds to repeatedly taking the smaller subprob-lem, that is, the branch whose size is proportional to α. Then, this will fall to1 in k steps where 1 ≈ (α)kn. So, k ≈ logα(1/n) = −lg(n)lg(α). The longest depthcorresponds to always taking the larger subproblem. we then have and identicalexpression, replacing α with 1 − α.Exercise 7.2-62Without loss of generality, assume that the entries of the input array aredistinct. Since only the relative sizes of the entries matter, we may assumethat A contains a random permutation of the numbers 1 through n. Now fix0 < α ≤ 1/2. Let k denote the number of entries of A which are less thanA[n]. PARTITION produces a split more balanced than 1 − α to α if andonly if αn ≤ k ≤ (1 − α)n. This happens with probability(1−α)n−αn+1n=1 − 2α + 1/n ≈ 1 − 2α.Exercise 7.3-1We analyze the expected run time because it represents the more typicaltime cost. Also, we are doing the expected run time over the possible random-ness used during computation because it can’t be produced adversarially, unlikewhen doing expected run time over all possible inputs to the algorithm.Exercise 7.3-2In either case, Θ(n) calls are made to RANDOM. PARTITION will runfaster in the best case because the inputs will generally be smaller, but RAN-DOM is called every single time RANDOMIZED-PARTITION is called, whichhappens Θ(n) times.Exercise 7.4-1By definition of Θ, we know that there exists c1, c2so that the Θ(n) termis between c1n and c2n. We make that inductive hypothesis be that c1m2≤T (m) ≤ c2m2for all m < n, then, for large enough n,c1n2≤ c1maxq∈[n]n2− 2n(q + 2) + (q + 1)2+ (q + 1)2+ n= maxq∈[n]c1(n − q − 2)2+ c1(q + 1)2+ c1n≤ maxq∈[n]T (n − q − 2) + T (q + 1) + Θ(n)= T (n)Similarly for the other directionExercise 7.4-2We’ll use the substitution method to show that the best-case running timeis Ω(n lg n). Let T (n) be the best-case time for the procedure QUICKSORT onan input of size n. We have the recurrenceT (n) = min1≤q≤n−1(T (q) + T (n − q − 1)) + Θ(n).Suppose that T (n) ≥ c(n lg n + 2n) for some constant c. Substituting this guess3into the recurrence givesT (n) ≥ min1≤q≤n−1(cq lg q + 2cq + c(n − q − 1) lg(n − q − 1) + 2c(n − q − 1)) + Θ(n)=cn2lg(n/2) + cn + c(n/2 − 1) lg(n/2 − 1) + cn − 2c + Θ(n)≥ (cn/2) lg n − cn/2 + c(n/2 − 1)(lg n − 2) + 2cn − 2cΘ(n)= (cn/2) lg n − cn/2 + (cn/2) lg n − cn − lg n + 2 + 2cn − 2cΘ(n)= cn lg n + cn/2 − lg n + 2 − 2c + Θ(n)Taking a derivative with respect to q shows that the minimum is obtained whenq = n/2. Taking c large enough to dominate the − lg n + 2 − 2c + Θ(n) termmakes this greater than cn lg n, proving the bound.Exercise 7.4-3We will treat the given expression to be continuous in q, and then, any ex-tremal values must be either adjacent to a critical point, or one of the endpoints.The second derivative with respect to q is 4, So, we have that any critical pointswe find will be minima. The expression has a derivative with respect to q of2q − 2(n − q − 2) = −2n + 4q + 4 which is zero when we have 2q + 2 = n. So,there will be a minima at q =n−22. So, the maximal values must only be theendpoints. We can see that the endpoints are equally large because at q = 0, itis (n − 1)2, and at q = n − 1, it is (n − 1)2+ (n − n + 1 − 1)2= (n − 1)2.Exercise 7.4-4We’ll use the lower bound (A.13) for the expected running time …
View Full Document
Unlocking...