算法导论第2版习题解答

算法导论第2版习题解答2.1-2In line 5 of INSERTIoN-sort alter Ali> key to Alil< key in order to sort the elements innonincreasing order.2.1-3Algorithm 1 LINEAR-SEARCH(A, vInput: A=(a1, a2,.anana a value vOutput: An index i such that= Ali] or nil ifve Afori←1 to n doif Ai=v thenreturn 1end ifend forreturn nilAs a loop invariant we say that none of the elements at index All, ...,i-1 are equal to vClearly, all properties are fullfilled by this loop invariant2.2-1n3/100-10n2-10n+3-O(n3)2.2-2Assume that FIND-MIN(A, T, s returns the index of the smallest element in a between indices rand s. Clearly, this can be implemented in O(s-r) time ifr>sAlgorithm 2 SELECTION-SORT(A)Input:A=(a1, a2,.anOutput: sorted afori←ton-1doj←FIND-MIN(A,i,nAil+→A[iend forAs a loop invariant we choose that A[1, ...,i-1 are sorted and all other elements are greaterthan these. We only need to iterate to n- 1 since according to the invariant the nth element willthen the largestThe n calls of Find-Min gives the following bound on the time complexityi=1This holds for both the best-and worst-case running time2.2-3Given that each element is equally likely to be the one searched for and the element searched for ispresent in the array, a linear search will on the average have to search through half the elementsThis is because half the time the wanted clement will be in the first half and half the time it willbe in the second half. Both the worst-case and average-case of L.INEAR-SEARCH is O(n)2.2-4One can modify an algorithm to have a best-case running time by specializing it to handle a bestcase input efficientl2.3-5A recursive version of binary search on an array. Clearly, the worst-case running time is e(lg n)Algorithm 3 BINARY-SEARCH(A, v, p, r)Input: A sorted array a and a value vOutput: An index i such that v= Ali or nilifp≥ r and v≠ Alp] thenreturn nilend ifi←-Ar-p)/2」if v= Ail thenreturnelseif v< All thenreturn BINARY-SEARCH(A, v,p, ielsereturn BINARY-SEARCH(A, v,i,r)end ifend if2.3-7Give a O(nlg n time algorithm for determining if there exist two elements in an set s whose sumis exactly some value xAlgorithm 4 CHECKSUMS(A, x)Input: An array A and a value xOutput: a boolean value indicating if there is two elements in A whose sum is xA←-SoRr(A)L← lengthfori← to n doif Ali]>>o and BINARy-SEARCH(A, Alil-x, 1, n) thenreturn trueend ifend forreturn falseClearly, this algorithm does the job. (It is assumed that nil cannot be true in the if-statement.3.1-1Let f(n), g(n) be asymptotically nonnegative. Show that max((n, gn))=o(f(n)+g(n)). Thismeans that there exists positive constants cl, C2 and no such that0≤c1(f(n)+g(n)≤max(f(n),g(n)≤c2(f(n)+g(n)for all n≥noSelecting C2= 1 clearly shows the third inequality since the maximum must be smaller thanthe sum. cI should be selected as 1/2 since the maximum is always greater than the weightedaverage of f(n) and g(n). Note the significance of the asymptotically nonnegative"assumptionThe first inequality could not be satisfied otherwise3.1-42n+I=O(2n)since 2n+1=2. 2n 2. 2n! However 22n is not O(2n) by definition we have(2n which for no constant c asymptotically may be less than or equal to c: 2n3Let f(n)and g(n be asymptotically positive functionsa. No, f(n)=oig(n)) does not imply g(n)=o(f(n)). Clearly, n=O(n2)but n*o(n)b. No, f(n)+g(n) is not O(min(f(n),g(n))). As an example notice that n+ 1 +e(min(n, 1))Yes, if f(n)=o(g(n))then lg(f(n))=o(lg(g(n))) prof(n)≥1 and 1g(g(n)≥1are greater than or equal 1. we have thatf(n)≤cgmn)→lgf(m)≤lg(cg(mn)=gc+lgg(n)To show that this is smaller than blg g(n) for some constant b we set lgc +lg gin)= blg gn)Dividing by lg g(n yields:blg(c)+lg g(n) lg cIg g(n)Ig g(n≤1gc+1The last inequality holds since lg g(n >1d. No, f(n)=o(g(n)) does not imply 2f n)=O(29In)). If f(n)=2n and g(n=n we have that2n <2 n but not 2n c2n for any constant c by exercise 3. 1-4.e. Yes and no, if f(n)< 1 for large n then f(n)2 f nand the upper bound will not holdOtherwise f(n)> 1 and the statement is trivially truef. Yes, f(n)=o(g(n)) implies g(n)=Q(f(n)). We have f(n)< cg(n) for positive c and thus1/c.f(n)≤g(n)g. No, clearly 2n c2 /2=cv 2n for any constant c if n is sufficiently largeh. By a small modification to exercise 3. 1-1 we have that f(n)+o(f(n))-O(max(f(n),o(f(n)o((n).4.1-1Show that T(n)=t(n/2])+ 1 is o(lg n). Using substitution we want to prove that t(n)sclg(n-b) Assume this holds for n/ 2. We haveT(n)≤clg(「n/2-b1)+ 24.2-3Draw the recursion tree of T(n)=4T(In/2))+cn. The height of the tree is lg n, the out degreeof each node will be 4 and the contribution of the ith level will be 4 cn/2. The last levecontributes 4gno(1)=0(n). Hence we have a bound on the sum given byT(n)=4T(n/2」)+cn2」+nlg n-14·cn/2+cn2+e(n2)+Q(T1 gcn+O(n2Using the substitution mcthod we can verify this bound. Assume the following clever inductionhypothesis. Let T(In/2))< c[n/2J2-cLn/2.We haveT(n)=4T(n/2」)+cn≤4(cln/22-cln/2」)+<4c(n/2)2-4cn/2+cn2ccncn4.3-1Use the master method to find bounds for the following recursions. Note that a=4, b= 4 andT(n)=4T(n/2)+n. Since n=O(n)case 1 applies and we get T(n)=on.T(n)=4T(n/2)+n2. Since n2=O(n2 we have T(n)=0(n2 n)T(n)-4T(n/2)+n3.Since n3-Q(n2+e)and 4(n/2)3-1/2n3 cn3 for some c< I wehave that t(n)=0(n2)6.1-1There is a most 2h+ -1 vertices in a complete binary tree of height h. Since the lower level neednot be filled we may only have 2n vertices6.1-2Since the height of an n-clement hcap must satisfy that 2h n 2h+1-1< 2+. we haveh≤lgn 1 and A[PARENT(i)l< key doAli]++ Aparent(ii← PARENT i)end whileend if6.5-8Given k sorted lists with a total of n elements show how to merge them in O(n lg k) time. Insertall k elements a position 1 from each list into a heap. Use ExtRact-MaX to obtain the first elementof the merged list. Insert element at position 2 from the list where the largest element originallycame from into the heap. Continuing in this fashion yields the desired algorithm. Clearly therunning time is O(nIgk)6-2a. a d-ary heap can be implemented using a dimensional array as follows. The root is keptnode with index i to its parent and its jth child are given bp and so on. The procedures to map aAll, its d children are kept in order in A[2 through A[d+1D- ARY-PARENT(讠)return l(i-2)/d+1」D-ARY-CHILD(i, jreturn d(i-1)+j+1b. Since each node has d children the height of the tree is o(loga n)c. The HEAP-EXTRACT-MAX algorithm given in the text works fine for d-ary heaps; the problemis MAX-HEAPIrY. Here we need to compare the argument node to all its children. This takese(d loga n) and dominates the overall time spent by HE.AP-EXTRACT-MAXd. The MAX-HEAP-INSERT given in the text works fine as well. The worst-case running time isthe height of the heap, that is e(loga n)e. The HEAP-IN CREASE-Key algorithm given in the text works fine10