# Introduction.to.Algorithm.3rd.Solutions to selected excerises and problems

Selected Solutions for Chapter 2: Getting Started Solution to Exercise 2.2-2 SELECTION-SORT.A/ n D A:length for j D 1 to n ? 1 smallest D j for i D j C 1 to n if A?i? A?mid? low D mid C 1 else high D mid ? 1 returnNIL RECURSIVE-BINARY-SEARCH.A;;low;high/ if low high returnNIL mid D b.low C high/=2c if ==A?mid? return mid elseif A?mid? return RECURSIVE-BINARY-SEARCH.A;;mid C 1;high/ else return RECURSIVE-BINARY-SEARCH.A;;low;mid ? 1/ Both procedures terminate the search unsuccessfully when the range is empty (i.e., low high) and terminate it successfully if the value has been found. Based on the comparison of to the middle element in the searched range, the search continues with the range halved. The recurrence for these procedures is therefore T.n/ D T.n=2/ C ?.1/, whose solution is T.n/ D ?.lgn/. Solution to Problem 2-4 a. The inversions are .1;5/;.2;5/;.3;4/;.3;5/;.4;5/. (Rememberthat inversions are specifi ed by indices rather than by the values in the array.) b. The array with elements from f1;2;:::;ng with the most inversions is hn;n ? 1;n ? 2;:::;2;1i. For all 1 i A?j?. At the time that the outer for loop of lines 1–8 sets key D A?j?, the value that started in A?k? is still somewhere to the left of A?j?. That is, it’s in A?i?, where 1 i y. Consider an inversion .i;j/, and let x D A?i? and y D A?j?, so that i y. We claim that if we were to run merge sort, there would be exactly one merge- inversion involving x and y. To see why, observe that the only way in which array elements change their positions is within the MERGEprocedure. More- over, since MERGEkeeps elements within L in the same relative order to each other, and correspondingly for R, the only way in which two elements can change their ordering relative to each other is for the greater one to appear in L and the lesser one to appear in R. Thus, there is at least one merge-inversion involving x and y. To see that there is exactly one such merge-inversion, ob- serve that after any call of MERGEthat involves both x and y, they are in the same sorted subarray and will therefore both appear in L or both appear in R in any given call thereafter. Thus, we have proven the claim. We have shown that every inversion implies one merge-inversion. In fact, the correspondence between inversions and merge-inversions is one-to-one. Sup- pose we have a merge-inversion involving values x and y, where x originally was A?i? and y was originally A?j?. Since we have a merge-inversion, x y. And since x is in L and y is in R, x must be within a subarray preceding the subarray containing y. Therefore x started out in a position i preceding y’s original position j, and so .i;j/ is an inversion. Having shown a one-to-one correspondence between inversions and merge- inversions, it suffi ces for us to count merge-inversions. Consider a merge-inversion involving y in R. Let ′ be the smallest value in L that is greater than y. At some point during the merging process, ′ and y will be the “exposed” values in L and R, i.e., we will have ′ D L?i? and y D R?j? in line 13 of MERGE. At that time, there will be merge-inversions involving y and L?i?;L?i C 1?;L?i C2?;:::;L?n1?, and these n1? i C1 merge-inversions will be the only ones involving y. Therefore, we need to detect the fi rst time that ′ and y become exposed during the MERGEprocedure and add the value of n1? i C 1 at that time to our total count of merge-inversions. The following pseudocode, modeled on merge sort, works as we have just de- scribed. It also sorts the array A. COUNT-INVERSIONS.A;p;r/ inersions D 0 if p 0 such that 0 c1nb .n C a/b c2nbfor all n n0. Note that n C an C jaj 2nwhen jaj n , and n C an ? jaj 1 2 nwhen jaj 1 2n . Thus, when n 2jaj, 0 1 2 n n C a 2n : Since b 0, the inequality still holds when all parts are raised to the power b: 0 1 2n b .n C a/b .2n/b; 0 1 2 b nb .n C a/b 2bnb: Thus, c1D .1=2/b, c2D 2b, and n0 D 2jaj satisfy the defi nition. Solution to Exercise 3.1-3 Let the running time be T.n/. T.n/ O.n2/ means that T.n/ f.n/ for some function f.n/ in the set O.n2/. This statement holds for any running time T.n/, since the function g.n/ D 0 for all n is in O.n2/, and running times are always nonnegative. Thus, the statement tells us nothing about the running time. 3-2Selected Solutions for Chapter 3: Growth of Functions Solution to Exercise 3.1-4 2nC1D O.2n/, but 22n¤ O.2n/. To show that 2nC1D O.2n /, we must fi nd constants c;n0 0 such that 0 2nC1 c 2nfor all n n0: Since 2nC1D 2 2n for all n, we can satisfy the defi nition with c D 2 and n0D 1. To show that 22n6D O.2n/, assume there exist constants c;n0 0 such that 0 22n c 2nfor all n n0: Then 22nD 2n 2n c 2n) 2n c. But no constant is greater than all 2n, and so the assumption leads to a contradiction. Solution to Exercise 3.2-4 dlgne? is not polynomially bounded, but dlglgne? is. Proving that a function f.n/ is polynomially bounded is equivalent to proving that lg.f.n// D O.lgn/ for the following reasons. If f is polynomially bounded, then there exist constants c, k, n0such that for all n n0, f.n/ cnk. Hence, lg.f.n// kc lgn, which, since c and k are constants, means that lg.f.n// D O.lgn/. Similarly, if lg.f.n// D O.lgn/, then f is polynomially bounded. In the following proofs, we will make use of the following two facts: 1. lg.n?/ D ?.nlgn/ (by equation (3.19)). 2. dlgne D ?.lgn/, because dlgne lgn dlgne 0, we have lgbn D o.na/. Substitute lgn for n, 2 for b, and 1 for a, giving lg2.lgn/ D o.lgn/. Therefore, lg.dlglgne?/ D O.lgn/, and so dlglgne? is polynomially bounded. Selected Solutions for Chapter 4: Divide-and-Conquer Solution to Exercise 4.2-4 If you can multiply 3 3 matrices using k multiplications, then you can multiply n n matrices by recursively multiplying n=3 n=3 matrices, in time T.n/ D kT.n=3/ C ?.n2/. Using the master method to solve this recurrence, consider the ratio of nlog3 k and n2: If log3k D 2, case 2 applies and T.n/ D ?.n2lgn/. In this case, k D 9 and T.n/ D o.nlg7/. If log3k 2, case 1 applies and T.n/ D ?.nlog3 k/. In this case, k 9. T.n/ D o.nlg7/ when log3k 0. T.n/DT.?n/ C T1 ? ?/n/ C cn d?nlg.?n/ C d.1 ? ?/nlg1 ? ?/n/ C cn Dd?nlg? C d?nlgn C d.1 ? ?/nlg.1 ? ?/ C d.1 ? ?/nlgn C cn Ddnlgn C dn.? lg? C .1 ? ?/lg.1 ? ?// C cn dnlgn ; if dn.? lg? C .1 ? ?/lg.1 ? ?// C cn 0. This condition is equivalent to d.?lg? C .1 ? ?/lg.1 ? ?// ?c : Since 1=2 ? 0. We can use the same proof as for the upper bound, substituting for , and we get the requirement that 0 A?j?. More precisely, we defi ne XijD IfA?i? A?j?g for 1 i bd, the sort will put a after b, which is correct, since a b regardless of the low-order digits. If adD bd, the sort will leave a and b in the same order they were in, because it is stable. But that order is already correct, since the correct order of a and b is determined by the low-order d ?1 digits when their dth digits are equal, and the elements are already sorted by their low-order d ? 1 digits. If the intermediate sort were not stable, it might rearrange elements whose dth digits were equal—elements that were in the right order after the sort on their lower-order digits. Solution to Exercise 8.3-4 Treat the numbers as 3-digit numbers in radix n. Each digit ranges from 0 to n?1. Sort these 3-digit numbers with radix sort. There are 3 calls to counting sort, each taking ?.n C n/ D ?.n/ time, so that the total time is ?.n/. Solution to Problem 8-1 a. For a comparison algorithm A to sort, no two input permutations can reach the same leaf of the decision tree, so there must be at least n? leaves reached in TA, one for each possible input permutation. Since A is a deterministic algorithm, it must always reach the same leaf when given a particular permutation as input, so at most n? leaves are reached (one for each permutation). Therefore exactly n? leaves are reached, one for each input permutation. Selected Solutions for Chapter 8: Sorting in Linear Time8-3 These n? leaves will each have probability 1=n?, since each of the n? possible permutations is the input with the probability 1=n?. Any remaining leaves will have probability 0, since they are not reached for any input. Without loss of generality, we can assume for the rest of this problem that paths leading only to 0-probability leaves aren’t in the tree, since they cannot affect the running time of the sort. That is, we can assume that TAconsists of only the n? leaves labeled 1=n? and their ancestors. b. If k 1, then the root of T is not a leaf. This implies that all of T’s leaves are leaves in LT and RT. Since every leaf at depth h in LT or RT has depth hC1 in T, D.T/ must be the sum of D.LT/, D.RT/, and k, the total number of leaves. To prove this last assertion, let dT.x/ D depth of node x in tree T. Then, D.T/D X x2leaves.T/ dT.x/ D X x2leaves.LT/ dT.x/ C X x2leaves.RT/ dT.x/ D X x2leaves.LT/ .dLT.x/ C 1/ C X x2leaves.RT/ .dRT.x/ C 1/ D X x2leaves.LT/ dLT.x/ C X x2leaves.RT/ dRT.x/ C X x2leaves.T/ 1 DD.LT/ C D.RT/ C k : c. To show that d.k/ D min1ik?1fd.i/ C d.k ? i/ C kg we will show sepa- rately that d.k/ min 1ik?1 fd.i/ C d.k ? i/ C kg and d.k/ min 1ik?1 fd.i/ C d.k ? i/ C kg : Toshowthatd.k/ min1ik?1fd.i/ C d.k ? i/ C kg, weneedonlyshow that d.k/ d.i/ C d.k ? i/ C k, for i D 1;2;:::;k ? 1. For any i from 1 to k ? 1 we can fi nd trees RT with i leaves and LT with k ? i leaves such that D.RT/ D d.i/ and D.LT/ D d.k?i/. Construct T such that RT and LT are the right and left subtrees of T’s root respectively. Then d.k/D.T/ (by defi nition of d as min D.T/ value) D D.RT/ C D.LT/ C k(by part (b)) D d.i/ C d.k ? i/ C k(by choice of RT and LT) . Toshowthatd.k/ min1ik?1fd.i/ C d.k ? i/ C kg, weneedonlyshow that d.k/ d.i/ C d.k ? i/ C k, for some i in f1;2;:::;k ? 1g. Take the tree T with k leaves such that D.T/ D d.k/, let RT and LT be T’s right and left subtree, respecitvely, and let i be the number of leaves in RT. Then k ? i is the number of leaves in LT and d.k/ D D.T/(by choice of T) D D.RT/ C D.LT/ C k (by part (b)) d.i/ C d.k ? i/ C k (by defi ntion of d as min D.T/ value) . 8-4Selected Solutions for Chapter 8: Sorting in Linear Time Neither i nor k ?i can be 0 (and hence 1 i k ?1), since if one of these were 0, either RT or LT would contain all k leaves of T, and that k-leaf subtree would have a D equal to D.T/ ? k (by part (b)), contradicting the choice of T as the k-leaf tree with the minimum D. d. Let fk .i/ D i lgi C.k ?i/lg.k ?i/. To fi nd the value of i that minimizes fk, fi nd the i for which the derivative of fkwith respect to i is 0: f 0 k.i/ D d di i lni C .k ? i/ln.k ? i/ ln2 D lni C 1 ? ln.k ? i/ ? 1 ln2 D lni ? ln.k ? i/ ln2 is 0 at i D k=2. To verify this is indeed a minimum (not a maximum), check that the second derivative of fkis positive at i D k=2: f 00 k.i/ D d di lni ? ln.k ? i/ ln2 D 1 ln2 1 i C 1 k ? i : f 00 k.k=2/ D 1 ln2 2 k C 2 k D 1 ln2 4 k 0since k 1 . Now we use substitution to prove d.k/ D .k lgk/. The base case of the induction is satisfi ed because d.1/ 0 D c 1 lg1 for any constant c. For the inductive step we assume that d.i/ ci lgi for 1 i k ? 1, where c is some constant to be determined. d.k/Dmin 1ik?1 fd.i/ C d.k ? i/ C kg min 1ik?1 fc.i lgi C .k ? i/lg.k ? i// C kg Dmin 1ik?1 fcfk.i/ C kg Dc k 2 lg k 2 k ? k 2 lg k ? k 2 C k Dck lg k 2 C k Dc.k lgk ? k/ C k Dck lgk C .k ? ck/ ck lgkif c 1 ; and so d.k/ D .k lgk/. e. Using the result of part (d) and the fact that TA (as modifi ed in our solution to part (a)) has n? leaves, we can conclude that D.TA/ d.n?/ D .n?lg.n?// : Selected Solutions for Chapter 8: Sorting in Linear Time8-5 D.TA/ is the sum of the decision-tree path lengths for sorting all input per- mutations, and the path lengths are proportional to the run time. Since the n? permutations have equal probability 1=n?, the expected time to sort n random elements (1 input permutation) is the total time for all permutations divided by n?: .n?lg.n?// n? D .lg.n?// D .nlgn/ : f. We will show how to modify a randomized decision tree (algorithm) to defi ne a deterministic decision tree (algorithm) that is at least as good as the randomized one in terms of the average number of comparisons. At each randomized node, pick the child with the smallest subtree (the subtree with the smallest average number of comparisons on a path to a leaf). Delete all the other children of the randomized node and splice out the randomized node itself. The deterministic algorithm corresponding to this modifi ed tree still works, be- cause the randomized algorithm worked no matter which path was taken from each randomized node. The average number of comparisons for the modifi ed algorithm is no larger than the average number for the original randomized tree, since we discarded the higher-average subtrees in each case. In particular, each time we splice out a randomized node, we leave the overall average less than or equal to what it was, because thesamesetofinputpermutations reachesthemodifi edsubtreeasbefore, but those inputs are handled in less than or equal to average time than before, and the rest of the tree is unmodifi ed. The randomized algorithm thus takes at least as much time on average as the corresponding deterministic one. (We’ve shown that the expected running time for a deterministic comparison sort is .nlgn/, hence the expected time for a randomized comparison sort is also .nlgn/.) Selected Solutions for Chapter 9: Medians and Order Statistics Solution to Exercise 9.3-1 For groups of 7, the algorithm still works in linear time. The number of elements greater than x (and similarly, the number less than x) is at least 4 1 2 ln 7 m ? 2 2n 7 ? 8 ; and the recurrence becomes T.n/ T.dn=7e/ C T.5n=7 C 8/ C O.n/ ; which can be shown to be O.n/ by substitution, as for the groups of 5 case in the text. Forgroupsof3, however, thealgorithmnolongerworksinlineartime. Thenumber of elements greater than x, and the number of elements less than x, is at least 2 1 2 ln 3 m ? 2 n 3 ? 4 ; and the recurrence becomes T.n/ T.dn=3e/ C T.2n=3 C 4/ C O.n/ ; which does not have a linear solution. We can prove that the worst-case time for groups of 3 is .nlgn/. We do so by deriving a recurrence for a particular case that takes .nlgn/ time. In counting up the number of elements greater than x (and similarly, the num- ber less than x), consider the particular case in which there are exactly l 1 2 l n 3 mm groups with medians x and in which the “leftover” group does contribute 2 elements greater than x. Then the number of elements greater than x is exactly 2 l 1 2 l n 3 mm ? 1 C 1 (the ?1 discounts x’s group, as usual, and the C1 is con- tributed by x’s group) D 2dn=6e ? 1, and the recursive step for elements x has n ? .2dn=6e ? 1/ n ? .2.n=6 C 1/ ? 1/ D 2n=3 ? 1 elements. Observe also that the O.n/ term in the recurrence