Mark Allen Weiss 数据结构与算法分析 课后习题答案10.pdf

《Mark Allen Weiss 数据结构与算法分析 课后习题答案10.pdf》由会员分享，可在线阅读，更多相关《Mark Allen Weiss 数据结构与算法分析 课后习题答案10.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter10:AlgorithmDesignTechniques10.1First,we show that if N?evenly divides P?,then each of?j?(i?1)P?+1through?jiP?must beplaced as the i?th?job on some processor.Suppose otherwise.Then in the supposedoptimal ordering,we must be able to find some jobs?jx?and?jy?such that?jx?is the t?th?jobon some

2、processor and?jy?is the t?+1th?job on some processor but tx?ty?.Let?jz?be thejob immediately following?jx?.If we swap?jy?and?jz?,it is easy to check that the mean pro-cessing time is unchanged and thus still optimal.But now?jy?follows?jx?,which is impos-sible because we know that the jobs on any pro

3、cessor must be in sorted order from theresults of the one processor case.Let?je?1,?je?2,.,?jeM?be the extra jobs if N?does not evenly divide P?.It is easy to see thatthe processing time for these jobs depends only on how quickly they can be scheduled,and that they must be the last scheduled job on s

4、ome processor.It is easy to see that thefirst M?processors must have jobs?j?(i?1)P?+1through?jiP?+M?;we leave the details to thereader.10.3,4789015spnl3:6210.4One method is to generate code that can be evaluated by a stack machine.The two opera-tions are Push?(the one node tree corresponding to)a sy

5、mbol onto a stack and Combine,?which pops two trees off the stack,merges them,and pushes the result back on.For theexample in the text,the stack instructions are Push(s),Push(nl),Combine,Push(t),Com-bine,Push(a),Combine,Push(e),Combine,Push(i),Push(sp),Combine,Combine.By encoding a Combine?with a 0

6、and a Push?with a 1 followed by the symbol,the totalextra space is 2N?1 bits if all the symbols are of equal length.Generating the stackmachine code can be done with a simple recursive procedure and is left to the reader.10.6Maintain two queues,Q?1and Q?2.Q?1will store single-node trees in sorted or

7、der,and Q?2will store multinode trees in sorted order.Place the initial single-node trees on Q?1,enqueueing the smallest weight tree first.Initially,Q?2is empty.Examine the first twoentries of each of Q?1and Q?2,and dequeue the two smallest.(This requires an easilyimplemented extension to the ADT.)M

8、erge the tree and place the result at the end of Q?2.Continue this step until Q?1is empty and only one tree is left in Q?2.-54-10.9To implement first fit,we keep track of bins bi?,which have more room than any of thelower numbered bins.A theoretically easy way to do this is to maintain a splay treeo

9、rdered by empty space.To insert w?,we find the smallest of these bins,which has atleast w?empty space;after w?is added to the bin,if the resulting amount of empty space isless than the inorder predecessor in the tree,the entry can be removed;otherwise,aDecreaseKey?is performed.To implement best fit,

10、we need to keep track of the amount of empty space in each bin.As before,a splay tree can keep track of this.To insert an item of size w?,perform aninsert of w?.If there is a bin that can fit the item exactly,the insert will detect it and splayit to the root;the item can be added and the root delete

11、d.Otherwise,the insert has placedw?at the root(which eventually needs to be removed).We find the minimum element M?in the right subtree,which brings M?to the right subtrees root,attach the left subtree toM?,and delete w?.We then perform an easily implemented DecreaseKey?on M?to reflectthe fact that

12、the bin is less empty.10.10Next fit:12 bins(.42,.25,.27),(.07,.72),(.86,.09),(.44,.50),(.68),(.73),(.31),(.78,.17),(.79),(.37),(.73,.23),(.30).First fit:10 bins(.42,.25,.27),(.07,.72,.09),(.86),(.44,.50),(.68,.31),(.73,.17),(.78),(.79),(.37,.23,.30),(.73).Best fit:10 bins(.42,.25,.27),(.07,.72,.09),

13、(.86),(.44,.50),(.68,.31),(.73,.23),(.78,.17),(.79),(.37,.30),(.73).First fit decreasing:10 bins(.86,.09),(.79,.17),(.78,.07),(.73,.27),(.73,.25),(.72,.23),(.68,.31),(.50,.44),(.42,.37),(.30).Best fit decreasing:10 bins(.86,.09),(.79,.17),(.78),(.73,.27),(.73,.25),(.72,.23),(.68,.31),(.50,.44),(.42,

14、.37,.07),(.30).Note that use of 10 bins is optimal.10.12We prove the second case,leaving the first and third(which give the same results asTheorem 10.6)to the reader.Observe thatlog p?N?=log p?(b?m?)=m?p?log p?b?Working this through,Equation(10.9)becomes T?(N?)=T?(b?m?)=a?m?i?=0m?ab?k?_?i?i?p?log p?

15、b?If a?=b?k?,thenT?(N?)=a?m?log p?b?i?=0mi?p?=O?(a?m?m?p?+1log p?b?)Since m?=log N?/log b?,and a?m?=N?k?,and b?is a constant,we obtainT?(N?)=O?(N?k?log p?+1N?)10.13The easiest way to prove this is by an induction argument.-55-10.14Divide the unit square into N?1 square grids each with side 1/?N?1.Si

16、nce there are N?points,some grid must contain two points.Thus the shortest distance is conservativelygiven by at most?2/(N?1).10.15The results of the previous exercise imply that the width of the strip is O?(1/?N?).Because the width of the strip is O?(1/?N?),and thus covers only O?(1/?N?)of the area

17、 ofthe square,we expect a similar fraction of the points to fall in the strip.Thus onlyO?(N?/?N?)points are expected in the strip;this is O?(?N?).10.17The recurrenceworks out toT?(N?)=T?(2N?/3)+T?(N?/3)+O?(N?)This is not linear,because the sum is not less than one.The running time is O?(N?log N?).10

18、.18The recurrencefor median-of-median-of-sevenpartitioning isT?(N?)=T?(5N?/7)+T?(N?/7)+O?(N?)If all we are concerned about is the linearity,then median-of-median-of-seven can beused.10.20When computing the median-of-median-of-five,30%of the elements are known to besmaller than the pivot,and 30%are k

19、nown to be larger.Thus these elements do not needto be involved in the partitioning phase.(Extra work would need to be done to imple-ment this,but since the whole algorithm isnt practical anyway,we can ignore any extrawork that doesnt involve element comparisons.)The original paper 9 describes theex

20、act constants in the worst-case bound,with and without this extra effort.10.21We derive the values of s?and,following the style in the original paper 17.Let Rt?,X?be the rank of element t?in some sample X?.If a sample S?of elements is chosen ran-domly from S?,and?|?S?|?=s?,?|?S?|?=N?,then weve alrea

21、dy seen thatE?(Rt?,S?)=s?+1N?+1_ _Rt?,S?where E?means expected value.For instance,if t?is the third largest in a sample of 5 ele-ments,then in a group of 19 elements it is expected to be the tenth largest.We can alsocalculate the variance:V?(Rt?,S?)=?(s?+1)2(s?+2)(Rt?,S?)(s?Rt?,S?+1)(N?+1)(N?s?)_ _=

22、O?(N?/?s?)We choose v?1and v?2so thatE?(Rv?1,S?)+2dV?(Rv?1,S?)k?E?(Rv?2,S?)2dV?(Rv?2,S?)where d?indicates how many variances we allow.(The larger d?is,the less likely the ele-ment we are looking for will not be in S?.)The probability that k?is not between v?1and v?2is2derf?(x?)dx?=O?(e?d?2/d?)If d?=

23、log1/2N?,then this probability is(1/N?),specifically O?(1/(N?log N?).This meansthat the expected work in this case is O?(log1N?)because O?(N?)work is performed withvery small probability.-56-These mean and variance equations implyRv?1,S?k(N?+1)(s?+1)_ d?s?andRv?2,S?k(N?+1)(s?+1)_+d?s?This gives equa

24、tion(A):=d?s?=?s?log 1/2N?(A)If we first pivot around v?2,the cost is N?comparisons.If we now partition elements in S?that are less than v?2around v?1,the cost is Rv?2,S?,which has expected value k?+s?+1N?+1_ _.Thus the total cost of partitioning is N?+k?+s?+1N?+1_ _.The cost of the selections to fi

25、nd v?1and v?2in the sample S?is O?(s?).Thus the total expected number of comparisons isN?+k?+O?(s?)+O?(N?/s?)The low order term is minimized whens?=N?/s?(B)Combining Equations(A)and(B),we see thats?2=N?=?s?N?log 1/2N?(C)s?3/2=N?log 1/2N?(D)s?=N?2/3log 1/3N?(E)=N?1/3log 2/3N?(F)10.22First,we calculat

26、e 12*43.In this case,XL?=1,XR?=2,YL?=4,YR?=3,D?1=1,D?2=1,XL?YL?=4,XR?YR?=6,D?1D?2=1,D?3=11,and the result is 516.Next,we calculate 34*21.In this case,XL?=3,XR?=4,YL?=2,YR?=1,D?1=1,D?2=1,XL?YL?=6,XR?YR?=4,D?1D?2=1,D?3=11,and the result is 714.Third,we calculate 22*22.Here,XL?=2,XR?=2,YL?=2,YR?=2,D?1=

27、0,D?2=0,XL?YL?=4,XR?YR?=4,D?1D?2=0,D?3=8,and the result is 484.Finally,we calculate 1234*4321.XL?=12,XR?=34,YL?=43,YR?=21,D?1=22,D?2=2.By previous calculations,XL?YL?=516,XR?YR?=714,and D?1D?2=484.ThusD?3=1714,and the result is 714+171400+5160000=5332114.10.23Themultiplicationevaluates to(ac?bd?)+(b

28、c?+ad?)i?.Computeac?,bd?,and(a?b?)(d?c?)+ac?+bd?.10.24The algebra is easy to verify.The problem with this method is that if X?and Y?are posi-tive N?bit numbers,their sum might be an N?+1 bit number.This causes complications.10.26Matrix multiplication is not commutative,so the algorithm couldnt be us

29、ed recursivelyon matrices if commutativity was used.-57-10.27If the algorithm doesnt use commutativity(which turns out to be true),then a divide andconquer algorithm gives a running time of O?(N?log70143640)=O?(N?2.795).10.281150 scalar multiplications are used if the order of evaluation is(A?1A?2)(

30、A?3A?4)A?5)A?6)10.29(a)Let the chain be a 1x1 matrix,a 1xA matrix,and an AxB matrix.Multiplication byusing the first two matrices first makes the cost of the chain A?+AB?.The alternativemethod gives a cost of AB?+B?,so if A?B?,then the algorithm fails.Thus,a counterex-ample is multiplying a 1x1 matr

31、ix by a 1x3 matrix by a 3x2 matrix.(b,c)A counterexample is multiplying a 1x1 matrix by a 1x2 matrix by a 2x3 matrix.10.31The optimal binary search tree is the same one that would be obtained by a greedy stra-tegy:I?is at the root and has children and?and it?;a?and or?are leaves;the total cost is2.1

32、4.10.33This theorem is from F.Yaos paper,reference58.10.34A recursive procedure is clearly called for;if there is an intermediate vertex,StopOver?onthe path from s?to t?,then we want to print out the path from s?to StopOver?and thenStopOver?to t?.We dont want to print out StopOver?twice,however,so t

33、he proceduredoes not print out the first or last vertex on the path and reserves that for the driver._ _ _/*Print the path between S and T,except do not print*/*the first or last vertex.Print a trailing to only.*/voidPrintPath1(TwoDArray Path,int S,int T)int StopOver=Path S T;if(S!=T&StopOver!=0)Pri

34、ntPath1(Path,S,StopOver);printf(%d to,StopOver);PrintPath1(Path,StopOver,T);/*Assume the existence of a Path of length at least 1*/voidPrintPath(TwoDArray Path,int S,int T)printf(%d to,S);PrintPath1(Path,S,T);printf(%d,T);NewLine();_ _ _-58-10.35Many random number generators are poor.The default UNI

35、X random number generatorrand?uses a modulus of the form 2b?,as does the VAX/VMS random number generator.UNIX does,however,provide better random number generators in the form of random.?The Turbo random number generators,likewise,are also deficient.The paper by Parkand Miller 44 discusses the random

36、 number generators on many machines.10.38If the modulus is a power of two,then the least significant bit of the random numberoscillates.Thus Flip?will always return heads and tails alternately,and the level chosenfor a skip list insertion will always be one or two.Consequently,the performance of the

37、skip list will be(N?)per operation.10.39(a)25 32 mod?341,210 1 mod?341.Since 322 1 mod?341,this proves that 341 isnot prime.We can also immediately conclude that 2340 1 mod?341 by raising the lastequationtothe34th?power.Theexponentiationwouldcontinueasfollows:220 1 mod?341,221 2 mod?341,242 4 mod?34

38、1,284 16 mod?341,285 32 mod?341,2170 1 mod?341,and 2340 1 mod?341.(b)If A?=2,then although 2560 1 mod?561,2280 1 mod?561 proves that 561 is notprime.If A?=3,then 3561 375 mod?561,which proves that 561 is not prime.A?=4obviously doesnt fool the algorithm,since 4140 1 mod?561.A?=5 fools the algorithm:

39、51 5 mod?561,52 25 mod?561,54 64 mod?561,58 169 mod?561,516 511 mod?561,517=311 mod?561,534 229 mod?561,535 23 mod?561,570 529 mod?561,5140 463 mod?561,5280 67 mod?561,5560 1 mod?561.10.41The two point sets are 0,4,6,9,16,17 and 0,5,7,13,16,17.10.42To find all point sets,we backtrack even if Found=t

40、rue,and print out informationwhen line 2 is executed.In the case where there are some duplicate distances,it is possi-ble that several symmetries will be printed.10.43205079506541925986886839596517945079659286886865945065866865658668656868MaxMinMaxMinMax10.44Actually,it implements both;Alpha?is lowe

41、red for subsequent recursive calls on line 9when Value?is changed at line 12.Beta?is used to terminate the while?loop when a lineof play leads to a position so good that it is obvious the human player(who has alreadyseen a more favorable line for himself or herself before making this call)wont play

42、intoit.To implement the complementary routine,switch the roles of the human and com-puter.Lines that change are 3 and 4(obvious changes),5(replace Alpha?with Beta?),6(replace*Value?Alpha?),8(obvious),9(replaceHuman?.*Value?,Beta?with Comp?.Alpha?,*Value?),and 11(obvious).-59-10.46We place circles in

43、 order.Suppose we are trying to place circle?j?,of radius r?j?.If somecircle i?of radius ri?is centered at xi?,then?j?is tangent to i?if it is placed at xi?+2?ri?rs?j?.To see this,notice that the line connecting the centers has length ri?+r?j?,and thedifference in y?-coordinates of the centers is?|?

44、r?j?ri?|?.The difference in x?-coordinatesfollows from the Pythagorean theorem.To place circle?j?,we compute where it would be placed if it were tangent to each of thefirst?j?1 circles,selecting the maximum value.If this value is less than r?j?,then we placecircle?j?at x?j?.The running time is O?(N?

45、2).10.47Construct a minimum spanning tree T?of G?,pick any vertex in the graph,and then find apath in T?that goes through every edge exactly once in each direction.(This is done by adepth-first search;see Exercise 9.31.)This path has twice the cost of the minimum span-ning tree,but it is not a simpl

46、e cycle.Make it a simple cycle,without increasing the total cost,by bypassing a vertex when it isseen a second time(except that if the start vertex is seen,close the cycle)and going to thenext unseen vertex on the path,possibly bypassing several vertices in the process.Thecost of this direct route c

47、annot be larger than original because of the triangle inequality.If there were a tour of cost K?,then by removing one edge on the tour,we would have aminimum spanning tree of cost less than K?(assuming that edge weights are positive).Thus the minimum spanning tree is a lower bound on the optimal tra

48、veling salesman tour.This implies that the algorithm is within a factor of 2 of optimal.10.48If there are two players,then the problem is easy,so assume k?1.If the players are num-bered 1 through N?,then divide them into two groups:1 through N?/2 and N?/2+1though N?.On the i?th?day,for 1 i?N?/2,play

49、er p?in the second group plays players(p?+i?)mod?N?/2)+1 in the first group.Thus after N?/2 days,everyone in group 1 hasplayed everyone in group 2.In the last N?/21 days,recursively conduct round-robintournaments for the two groups of players.10.49Divide the players into two groups of size?N?/2?and?

50、N?/2?,respectively,and recur-sively arrange the players in any order.Then merge the two lists(declare that px?py?ifx?has defeated y?,and py?px?if y?has defeated x?exactly one is possible)in linear timeas is done in mergesort.10.5010.51Divide and conquer algorithms(among others)can be used for both p