算法导论第二版习题答案英文版.pdf

《算法导论第二版习题答案英文版.pdf》由会员分享，可在线阅读，更多相关《算法导论第二版习题答案英文版.pdf（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法导论第二版习题答案英文版Solutions for Introduction to algorithmssecond editionPhilip BilleThe author of this document takes absolutely no responsibility for the contents.This is merelya vague suggestion to a solution to some of the exercises posed in the book Introduction to algo-rithms by Cormen,Leiserson an

2、d Rivest.It is very likely that there are many errors and that thesolutions are wrong.If you have found an error,have a better solution or wish to contribute insome constructive way please send a message to beetleit.dk.It is important that you try hard to solve the exercises on your own.Use this doc

3、ument only asa last resort or to check if your instructor got it all wrong.Please note that the document is under construction and is updated only sporadically.Havefun with your algorithms.Best regards,Philip BilleLast update:December 9,20021.2 2Insertion sort beats merge sort when 8n2 64nlgn,n 8lgn

4、,2n/8 key to Ai s.Algorithm 2 SELECTION-SORT(A)Input:A=ha1,a2,.aniOutput:sorted A.for i 1 to n 1 doj FIND-MIN(A,i,n)Aj Aiend forAs a loop invariant we choose that A1,.,i1 are sorted and all other elements are greaterthan these.We only need to iterate to n 1 since according to the invariant the nth e

5、lement willthen the largest.The n calls of FIND-MINgives the following bound on the time complexity:nXi=1i!=(n2)This holds for both the best-and worst-case running time.2.2 3Given that each element is equally likely to be the one searched for and the element searched for ispresent in the array,a lin

6、ear search will on the average have to search through half the elements.This is because half the time the wanted element will be in the first half and half the time it willbe in the second half.Both the worst-case and average-case of LINEAR-SEARCHis(n).32.2 4One can modify an algorithm to have a bes

7、t-case running time by specializing it to handle a best-case input efficiently.2.3 5A recursive version of binary search on an array.Clearly,the worst-case running time is(lgn).Algorithm 3 BINARY-SEARCH(A,v,p,r)Input:A sorted array A and a value v.Output:An index i such that v=Ai or nil.if p r and v

8、 6=Ap thenreturn nilend ifj Ab(r p)/2cif v=Aj thenreturn jelseif v 0 and BINARY-SEARCH(A,Ai 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.)43.1 1Let f(n),g(n)be asymptotically nonnegative.Show that max(f(n

9、),g(n)=(f(n)+g(n).Thismeans that there exists positive constants c1,c2and n0such that,0 6 c1(f(n)+g(n)6 max(f(n),g(n)6 c2(f(n)+g(n)for all n n0.Selecting c2=1 clearly shows the third inequality since the maximum must be smaller thanthe sum.c1should be selected as 1/2 since the maximum is always grea

10、ter than the weightedaverage of f(n)and g(n).Note the significance of the“asymptotically nonnegative”assumption.The first inequality could not be satisfied otherwise.3.1 42n+1=O(2n)since 2n+1=2 2n6 2 2n!However 22nis not O(2n):by definition we have22n=(2n)2which for no constant c asymptotically may

11、be less than or equal to c 2n.3 4Let f(n)and g(n)be asymptotically positive functions.a.No,f(n)=O(g(n)does not imply g(n)=O(f(n).Clearly,n=O(n2)but n26=O(n).b.No,f(n)+g(n)is not(min(f(n),g(n).As an example notice that n+1 6=(min(n,1)=(1).c.Yes,if f(n)=O(g(n)then lg(f(n)=O(lg(g(n)provided that f(n)1

12、and lg(g(n)1are greater than or equal 1.We have that:f(n)6 cg(n)lgf(n)6 lg(cg(n)=lgc+lgg(n)To show that this is smaller than blgg(n)for some constant b we set lgc+lgg(n)=blgg(n).Dividing by lgg(n)yields:b=lg(c)+lgg(n)lgg(n)=lgclgg(n)+1 6 lgc+1The last inequality holds since lgg(n)1.d.No,f(n)=O(g(n)d

13、oes not imply 2f(n)=O(2g(n).If f(n)=2n and g(n)=n we have that2n 6 2 n but not 22n6 c2nfor any constant c by exercise 3.1 4.e.Yes and no,if f(n)1 for large n then f(n)2 1 and the statement is trivially true.f.Yes,f(n)=O(g(n)implies g(n)=(f(n).We have f(n)6 cg(n)for positive c and thus1/c f(n)6 g(n).

14、g.No,clearly 2n66 c2n/2=c2nfor any constant c if n is sufficiently large.h.By a small modification to exercise 3.11 we have that f(n)+o(f(n)=(max(f(n),o(f(n)=(f(n).54.1 1Show that T(n)=T(dn/2e)+1 is O(lgn).Using substitution we want to prove that T(n)6clg(n b).Assume this holds for dn/2e.We have:T(n

15、)6 clg(dn/2 be)+1 2 and c 1.4.2 1Determine an upper bound on T(n)=3T(bn/2c)+n using a recursion tree.We have that eachnode of depth i is bounded by n/2iand therefore the contribution of each level is at most(3/2)in.The last level of depth lgn contributes(3lg n)=(nlg 3).Summing up we obtain:T(n)=3T(b

16、n/2c)+n6 n+(3/2)n+(3/2)2n+(3/2)lg n1n+(nlg 3)=nlg n1Xi=0(3/2)i+(nlg 3)=n(3/2)lg n 1(3/2)1+(nlg 3)=2(n(3/2)lg n n)+(nlg 3)=2n3lg n2lg n 2n+(nlg 3)=2 3lg n 2n+(nlg 3)=2nlg 3 2n+(nlg 3)=(nlg 3)We can prove this by substitution by assumming that T(bn/2c)6 cbn/2clg 3 cbn/2c.Weobtain:T(n)=3T(bn/2c)+n6 3cb

17、n/2clg 3 cbn/2c+n63cnlg 32lg 3cn2+n6 cnlg 3cn2+n6 cnlg 3Where the last inequality holds for c 2.64.2 3Draw the recursion tree of T(n)=4T(bn/2c)+cn.The height of the tree is lgn,the out degreeof each node will be 4 and the contribution of the ith level will be 4ibcn/2ic.The last levelcontributes 4lg

18、n(1)=(n2).Hence we have a bound on the sum given by:T(n)=4T(bn/2c)+cn=lg n1Xi=04i bcn/2ic+(n2)6lg n1Xi=04i cn/2i+(n2)=cnlg n1Xi=02i+(n2)+(n2)=cn 2lg n 12 1+(n2)=(n2)Using the substitution method we can verify this bound.Assume the following clever inductionhypothesis.Let T(bn/2c)6 cbn/2c2 cbn/2c.We

19、have:T(n)=4T(bn/2c)+cn6 4(cbn/2c2 cbn/2c)+cn 4c(n/2)2 4cn/2+cn=cn2 2cn+cn=cn2 cn4.3 1Use the master method to find bounds for the following recursions.Note that a=4,b=4 andnlog24=n2 T(n)=4T(n/2)+n.Since n=O(n2?)case 1 applies and we get T(n)=(n2).T(n)=4T(n/2)+n2.Since n2=(n2)we have T(n)=(n2lgn).T(n

20、)=4T(n/2)+n3.Since n3=(n2+?)and 4(n/2)3=1/2n36 cn3for some c 1 wehave that T(n)=(n3).76.1 1There is a most 2h+11 vertices in a complete binary tree of height h.Since the lower level neednot be filled we may only have 2hvertices.6.1 2Since the height of an n-element heap must satisfy that 2h6 n 6 2h+

21、1 1 2h+1.we haveh 6 lgn 1 and APARENT(i).7.2 2If the elements in A are the same,then by exercise 7.1 2 the returned element from each callto PARTITION(A,p,r)is r 1 thus yielding the worst-case partitioning.The total running time iseasily seen to be(n2).7.2 3If the elements in A are distinct and sort

22、ed in decreasing order then,as in the previous exercise,we have worst-case partitioning.The running time is again(n2).7 4a.Clearly,the QUICKSORT does exactly the same as the original QUICKSORTand therefore workscorrectly.b.Worst-case partitioning can cause the stack depth of QUICKSORT to be(n).c.If

23、we recursively call QUICKSORT on the smallest subarray returned by PARTITIONwe willavoid the problem and retain a O(lgn)bound on the stack depth.118.2 3COUNTING-SORTwill work correctly no matter what order A is processed in,however it is notstable.The modification to the for loop actually causes num

24、bers with the same value to appear inreverse order in the output.This can seen by running a few examples.8.2 4Given n integers from 1 to k show how to count the number of elements from a to b in O(1)timewith O(n+k)preprocessing time.As shown in COUNTING-SORTwe can produce an array C suchthat Ci cont

25、ains the number of elements less than or equal to i.Clearly,Cb Ca gives thedesired answer.8.3 4Show how to sort n integers in the range 0 to n2 1 in O(n)time.Notice that the number ofdigits used to represent an n2different numbers in a k-ary number system is d=logk(n2).Thusconsidering the n2numbers

26、as radix n numbers gives us that:d=logn(n2)=2logn(n)=2Radix sort will then have a running time of(d(n+k)=(2(n+n)=(n).8.4 2Show ho to improve the worst-case running time of bucket sort to O(nlgn).Simply replace theinsertion sort used to sort the linked lists with some worst case O(nlgn)sorting algori

27、thm,e.g.merge sort.The sorting then takes time:n1Xi=0O(nilgni)6n1Xi=0O(nilgn)=O(lgn)n1Xi=0O(ni)=O(nlgn)The total time of bucket sort is thus O(nlgn).129.1 1Show how to find the the second smallest element of n elements using n+dlgne2 comparisons.To find the smallest element construct a tournament as

28、 follows:Compare all the numbers in pairs.Only the smallest number of each pair is potentially the smallest of all so the problem is reducedto size dn/2e.Continuing in this fashion until there is only one left clearly solves the problem.Exactly n 1 comparisons are needed since the tournament can be

29、drawn as an n-leaf binarytree which has n 1 internal nodes(show by induction on n).Each of these nodes correspond toa comparison.We can use this binary tree to also locate the second smallest number.The path from the rootto the smallest element(of height dlgne)must contain the second smallest elemen

30、t.Conductinga tournament among these uses dlgne 1 comparisons.The total number of comparisons are:n 1+dlgne 1=n+dlgne 2.9.3 1Consider the analysis of the algorithm for groups of k.The number of elements less than(orgreater than)the median of the medians x will be at least dk2e?12dnke?2?n4 k.Hence,in

31、the worst-case SELECTwill be called recursively on at most n?n4 k?=3n4+k elements.Therecurrence isT(n)6 T(dn/ke)+T(3n/4+k)+O(n)Solving by substitution we obtain a bound for which k the algorithm will be linear.AssumeT(n)6 cn for all smaller n.We have:T(n)6 clnkm+c?3n4+k?+O(n)6 c(nk+1)+3cnk+ck+O(n)6c

32、nk+3cnk+c(k+1)+O(n)=cn?1k+34?+c(k+1)+O(n)6 cnWhere the last equation only holds for k 4.Thus,we have shown that the algorithm willcompute in linear time for any group size of 4 or more.In fact,the algorithm is(nlgn)fork=3.This can be shown by example.9.3 3Quicksort can be made to run in O(nlgn)time

33、worst-case by noticing that we can perform“perfectpartitioning”:Simply use the linear time select to find the median and perform the partitioningaround it.This clearly achieves the bound.9.3 5Assume that we have a routine MEDIANthat computes the median of an array in O(n)time.Showhow to find an arbi

34、trary order statistic in O(n).13Algorithm 6 SELECT(A,i)Input:Array A and integer i.Output:The ith largest element of A.x MEDIAN(A).Partition A around xif i 6 b(n+1)/2c thenRecursively find the ith in the first halfelseRecursively find(i b(n+1)/2c)th in the second halfend ifClearly,this algorithm doe

35、s the job.1410.1 2Two stacks can be implemented in a single array without overflows occuring if they grow fromeach end and towards the middle.10.1 6Implement a queue using two stacks.Denote the two stacks S1and S2.The ENQUEUEoperationis simply implemented as a push on S1.The dequeue operation is imp

36、lemented as a pop on S2.IfS2is empty,successively pop S1and push S2.The reverses the order of S1onto S2.The worst-case running time is O(n)but the amortized complexity is O(1)since each elementis only moved a constant number of times.10.2 1No,INSERTand DELETEcan not be implemented in O(1)on a linked

37、 list.A scan through the listis required for both operations.INSERTmust check that no duplicates exist.10.2 2A stack can be implemented using a linked list in the following way:PUSHis done by appendinga new element to the front of the list and POPis done by deleting the first element of the list.151

38、1.1 1Find the maximum element in a direct-address table T of length m.In the worst-case searchingthe entire table is needed.Thus the procedure must take O(m)time.11.1 2Describe how to implement a dynamic set with a bitvector.The elements have no satellite data.Simply set the ith bit to 1 if the i el

39、ement is inserted and set the bit to 0 if it is deleted.11.2 3Consider keeping the chaining lists in sorted order.Searching will still take time proportional tothe length of the list and therefore the running times are the same.The only difference is theinsertions which now also take time proportion

40、al to the length of the list.11.3 1Searching a list of length n where each element contains a long key k and a small hash value h(k)can be optimized in the following way:Comparing the keys should be done first comparing thehash values and if succesfull then comparing the keys.1612.1 2The definitions

41、 clearly differ.If the heap property allowed the elements to be printed in sortedorder in time O(n)we would have an O(n)time comparison sorting algorithm since BUILD-HEAPtakes O(n)time.This,however,is impossible since we know(nlgn)is a lower bound forsorting.12.1 5Show that constructing a binary tre

42、e from an arbitrary list in a comparison based model must takeat(nlgn)worst-case.The value of the nodes in the tree can be printed in sorted order in O(n)time.The existance of an algorithm for constructing a binary tree in o(nlgn)time would thuscontradict the lower bound for sorting.12.2 5Show that

43、if a node in a binary search tree has two children then its successor has no left child andits predecessor has no right child.Let v be a node with two children.The nodes that immidiatelyprecede v must be in the left subtree and the nodes that immidiately follow v must be in the rightsubtree.Thus the

44、 successor s must be in the right subtree and s will be the next node from v in aninorder walk.Therefore s cannot have a left child since this child since this would come before sin the inorder walk.Similarly,the predecessor has no right child.12.2 7Show that the inorder walk of a n-node binary sear

45、ch tree implemented with a call to TREE-MINIMUNfollowed by n 1 calls to TREE-SUCCESSORtakes O(n)time.Consider the algorithm at any given node during the algorithm.The algorithm will never goto the left subtree and going up will therefore cause it to never return to this same node.Hencethe algorithm

46、only traverses each edge at most twice and therefore the running time is O(n).12.2 9If x is a leaf node,then if px=y and x is the left child then running TREE-SUCCESSORyields y.Similarly if x is the right child then running TREE-PREDECESSORyields y.12.3 1Algorithm 7 TREE-INSERT(z,k)Input:A node z an

47、d value k.Output:The binary tree with k inserted.if z=nil thenkeyz kleftz nilrightz nilelseif k f2j 1+t2,j1+a1,jf2j 1+a2,j f1j 1+t1,j1+a2,jBy cancelling out the as we obtain a contradiction and the statement follows.15.2 1Solve the matrix chain order for a specific problem.This can be done by comput

48、ing MATRIX-CHAIN-ORDER(p)where p=h5,10,3,12,5,50,6i or simply using the equation:mi,j=?0if i=jmini6kjmi,k+mk+1,j+pi1pkpjif i 0 and xi=yjmax(ci,j 1,ci 1,j)if i,j 0 and xi6=yj22Algorithm 8 LCS-LENGTH(X,Y)Input:The two strings X and Y.Output:The longest common substring of X and Y.m lengthXn lengthYfor

49、 i 1 to m dofor j 1 to n doci,j 1end forend forreturn LOOKUP-LENGTH(X,Y,m,n)Algorithm 9 LOOKUP-LENGTH(X,Y,i,j)if ci,j 1 thenreturn ci,jend ifif i=0 or j=0 thenci,j 0elseif xi=yithenci,j LOOKUP-LENGTH(X,Y,i 1,j 1)+1elseci,j maxLOOKUP-LENGTH(X,Y,i,j 1),LOOKUP-LENGTH(X,Y,i 1,j)end ifend ifreturn ci,j15

50、.4 5Given a sequence X=hx1,x2,.,xni we wish to find the longest monotonically increasing subse-quence.First sort the elements of X and create another sequence X0.Finding the longest commonsubsequence of X and X0yields the longest monotonically increasing subsequence of X.The run-ning time is O(n2)si