Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition

Page 1 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 1 preview image

Computer Algorithms, Third Edition,Solutions to Selected ExercisesSara BaaseAllen Van GelderFebruary 25, 2000

Page 2 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 2 preview image

Page 3 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 3 preview image

iiINTRODUCTIONThis manual contains solutions for the selected exercises inComputer Algorithms: Introduction to Design and Analy-sis, third edition, by Sara Baase and Allen Van Gelder.Solutions manuals are intended primarily for instructors, but it is a fact that instructors sometimes put copies incampus libraries or on their web pages for use by students.For instructors who prefer to have students work onproblems without access to solutions, we have chosen not to include all the exercises from the text in this manual. Theincluded exercises are listed in the table of contents. Roughly every other exercise is solved.Some of the solutions were written specifically for this manual; others are adapted from solutions sets handed outto students in classes we taught (written by ourselves, teaching assistants, and students).Thus there is some inconsistency in the style and amount of detail in the solutions. Some may seem to be addressedto instructors and some to students. We decided not to change these inconsistencies, in part because the manual will beread by instructors and students. In some cases there is more detail, explanation, or justification than a student mightbe expected to supply on a homework assignment.Many of the solutions use the same pseudocode conventions used in the text, such as:1. Block delimiters (“f” and “g”) are omitted. Block boundaries are indicated by indentation.2. The keywordstaticis omitted from method (function and procedure) declarations. All methods declared inthe solutions arestatic.3. Class name qualifiers are omitted from method (function and procedure) calls. For example,x= cons(z,x)might be written when the Java syntax requiresx =IntList.cons(z, x).4. Keywords to control visibility,public,private, andprotected, are omitted.5. Mathematical relational operators “6=,” “,” and “” are usually written, instead of their keyboard versions.Relational operators are used on types where the meaning is clear, such asString, even though this would beinvalid syntax in Java.We thank Chuck Sanders for writing most of the solutions for Chapter 2 and for contributing many solutions inChapter 14. We thank Luo Hong, a graduate student at UC Santa Cruz, for assisting with several solutions in Chapters9, 10, 11, and 13.In a few cases the solutions given in this manual are affected by corrections and clarifications to the text. Thesecases are indicated at the beginning of each affected solution. The up-to-date information on corrections and clarifica-tions, along with other supplementary materials for students, can be found at these Internet sites:ftp://ftp.aw.com/cseng/authors/baasehttp://www-rohan.sdsu.edu/faculty/baasehttp://www.cse.ucsc.edu/personnel/faculty/avg.htmlcCopyright 2000 Sara Baase and Allen Van Gelder.Permission is granted for college and university instructors to make a reasonable number of copies, free of charge,as needed to plan and administer their courses. Instructors are expected to exercise reasonable precautions againstfurther, unauthorized copies, whether on paper, electronic, or other media.Permission is also granted for Addison-Wesley-Longman editorial, marketing, and sales staff to provide copiesfree of charge to instructors and prospective instructors, and to make copies for their own use.Other copies, whether paper, electronic, or other media, are prohibited without prior written consent of the authors.

Page 4 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 4 preview image

List of Solved Exercises1Analyzing Algorithms and Problems: Principles and Examples11.1 . . . . . . .11.2 . . . . . . .21.4 . . . . . . .21.6 . . . . . . .21.8 . . . . . . .31.10. . . . . .31.12. . . . . .31.13. . . . . .31.15. . . . . .41.18. . . . . .41.20. . . . . .41.22. . . . . .41.23. . . . . .41.25. . . . . .51.28. . . . . .51.31. . . . . .61.33. . . . . .61.35. . . . . .61.37. . . . . .61.39. . . . . .61.42. . . . . .71.44. . . . . .71.46. . . . . .71.47. . . . . .71.48. . . . . .71.50. . . . . .82Data Abstraction and Basic Data Structures92.2 . . . . . . .92.4 . . . . . . .92.6 . . . . . . .92.8 . . . . . . .92.10. . . . . .112.12. . . . . .112.14. . . . . .122.16. . . . . .132.18. . . . . .143Recursion and Induction173.2 . . . . . . .173.4 . . . . . . .173.6 . . . . . . .173.8 . . . . . . .183.10. . . . . .183.12. . . . . .184Sorting194.2 . . . . . . .194.4 . . . . . . .194.6 . . . . . . .194.9 . . . . . . .194.11. . . . . .194.13. . . . . .204.15. . . . . .204.17. . . . . .204.19. . . . . .214.21. . . . . .214.23. . . . . .214.25. . . . . .224.26. . . . . .224.27. . . . . .234.29. . . . . .234.31. . . . . .234.34. . . . . .244.35. . . . . .244.37. . . . . .244.40. . . . . .244.42. . . . . .244.44. . . . . .254.45. . . . . .254.46. . . . . .254.48. . . . . .254.49. . . . . .254.51. . . . . .264.53. . . . . .264.55. . . . . .274.57. . . . . .274.59. . . . . .284.61. . . . . .284.63. . . . . .294.65. . . . . .295Selection and Adversary Arguments315.2 . . . . . . .315.4 . . . . . . .325.6 . . . . . . .325.8 . . . . . . .335.10. . . . . .345.12. . . . . .345.14. . . . . .345.16. . . . . .345.19. . . . . .355.21. . . . . .355.22. . . . . .365.24. . . . . .376Dynamic Sets and Searching396.1 . . . . . . .396.2 . . . . . . .396.4 . . . . . . .406.6 . . . . . . .406.8 . . . . . . .416.10. . . . . .416.12. . . . . .416.14. . . . . .436.16. . . . . .456.18. . . . . .456.20. . . . . .456.22. . . . . .466.24. . . . . .476.26. . . . . .476.28. . . . . .476.30. . . . . .476.32. . . . . .486.34. . . . . .496.36. . . . . .496.37. . . . . .496.40. . . . . .50

Page 5 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 5 preview image

ivList of Solved Exercises7Graphs and Graph Traversals517.1 . . . . . . .517.3 . . . . . . .517.4 . . . . . . .517.6 . . . . . . .517.8 . . . . . . .517.10. . . . . .527.12. . . . . .527.14. . . . . .537.16. . . . . .537.18. . . . . .537.20. . . . . .547.22. . . . . .547.24. . . . . .547.27. . . . . .577.28. . . . . .577.30. . . . . .577.32. . . . . .577.34. . . . . .577.35. . . . . .587.37. . . . . .597.39. . . . . .597.40. . . . . .597.41. . . . . .597.43. . . . . .597.45. . . . . .607.47. . . . . .607.49. . . . . .618Graph Optimization Problems and Greedy Algorithms638.1 . . . . . . .638.3 . . . . . . .638.5 . . . . . . .638.7 . . . . . . .648.8 . . . . . . .648.10. . . . . .648.12. . . . . .648.14. . . . . .648.16. . . . . .658.18. . . . . .658.20. . . . . .658.22. . . . . .678.24. . . . . .678.26. . . . . .678.27. . . . . .679Transitive Closure, All-Pairs Shortest Paths699.2 . . . . . . .699.4 . . . . . . .709.6 . . . . . . .719.7 . . . . . . .719.8 . . . . . . .719.10. . . . . .719.12. . . . . .729.14. . . . . .729.16. . . . . .729.18. . . . . .7210 Dynamic Programming7310.2. . . . . .7310.4. . . . . .7310.5. . . . . .7310.7. . . . . .7310.9. . . . . .7310.10. . . . .7410.12. . . . .7510.14. . . . .7510.16. . . . .7510.18. . . . .7610.19. . . . .7710.21. . . . .7810.23. . . . .7810.26. . . . .7911 String Matching8111.1. . . . . .8111.2. . . . . .8111.4. . . . . .8111.6. . . . . .8311.8. . . . . .8411.10. . . . .8411.12. . . . .8411.15. . . . .8411.17. . . . .8411.19. . . . .8511.21. . . . .8511.23. . . . .8511.25. . . . .8612 Polynomials and Matrices8712.2. . . . . .8712.4. . . . . .8712.6. . . . . .8712.8. . . . . .8712.10. . . . .8712.12. . . . .8812.14. . . . .8812.16. . . . .8812.17. . . . .8813N P-Complete Problems8913.2. . . . . .8913.4. . . . . .8913.6. . . . . .9113.8. . . . . .9113.10. . . . .9113.12. . . . .9113.14. . . . .9213.16. . . . .9213.18. . . . .9213.20. . . . .9313.21. . . . .9313.23. . . . .9313.26. . . . .9313.28. . . . .9313.30. . . . .9413.32. . . . .9413.34. . . . .9613.35. . . . .9613.37. . . . .9613.39. . . . .9613.42. . . . .9813.44. . . . .9913.47. . . . .9913.49. . . . .99

Page 6 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 6 preview image

List of Solved Exercisesv13.51. . . . .9913.53. . . . .10013.54. . . . .10013.55. . . . .10013.57. . . . .10013.59. . . . .10113.61. . . . .10114 Parallel Algorithms10314.2. . . . . .10314.4. . . . . .10314.5. . . . . .10314.7. . . . . .10414.8. . . . . .10414.10. . . . .10414.11. . . . .10414.13. . . . .10414.14. . . . .10514.16. . . . .10514.18. . . . .10514.19. . . . .10614.20. . . . .10614.22. . . . .10614.24. . . . .10614.25. . . . .10614.27. . . . .10714.29. . . . .10714.30. . . . .10814.32. . . . .108

Page 7 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 7 preview image

viList of Solved Exercises

Page 8 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 8 preview image

Chapter 1Analyzing Algorithms and Problems: Principles and ExamplesSection 1.2:Java as an Algorithm Language1.1It is correct for instance fields whose type is an inner class to be declared before that inner class (as in Figure 1.2 inthe text) or after (as here). Appendix A.7 gives an alternative to spelling out all the instance fields in the copy methods(functions).classPersonalfpublic static classNamefStringfirstName;StringmiddleName;StringlastName;public static Namecopy(Name n)fNamen2;n2.firstName = n.firstName;n2.middleName = n.middleName;n2.lastName =n.lastName;return n2;ggpublic static classAddressfStringstreet;Stringcity;Stringstate;public static Address copy(Address a)f/* similar to Name.copy() */ggpublic static classPhoneNumberfintareaCode;intprefix;intnumber;public static PhoneNumber copy(PhoneNumber n)f/*similar to Name.copy() */ggNamename;Addressaddress;PhoneNumberphone;StringeMail;public static Personal copy(Personal p);fPersonalp2;p2.name =Name.copy(p.name);p2.address =Address.copy(p.address);p2.phone =PhoneNumber.copy(p.phone);p2.eMail =p.eMail;return p2;gg

Page 9 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 9 preview image

2Chapter 1Analyzing Algorithms and Problems: Principles and ExamplesSection 1.3:Mathematical Background1.2For 0<k<n, we haven1k=(n1)!k!(n1k)!=(n1)!(nk)k!(nk)!n1k1=(n1)!(k1)!(nk)!=(n1)!(k)k!(nk)!Add them giving:(n1)!(n)k!(nk)!=nkFor 0<nkwe use the fact thatab=0 whenevera<b. (There is no way to choose more elements than there are inthe whole set.) Thusn1k=0 in all these cases. Ifn<k,n1k1andnkare both 0, confirming the equation. Ifn=k,n1k1andnkare both 1, again confirming the equation. (We need the fact that 0!=1 whenn=k=1.)1.4It suffices to show:logcxlogbc=logbx:Considerbraised to each side.bleft side=blogbclogcx=(blogbc)logcx=clogcx=xbright side=blogbx=xSo left side = right side.1.6Letx=dlg(n+1)e. The solution is based on the fact that 2x1<n+12x.x=0;twoToTheX = 1;while (twoToTheX <n+1)x +=1;twoToTheX *= 2;return x;The values computed by this procedure for smallnand the approximate values of lg(n+1)are:nxlg(n+1)000.0111.0221.6322.0432.3532.6632.8733.0843.2943.3

Page 10 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 10 preview image

Chapter 1Analyzing Algorithms and Problems: Principles and Examples31.8Pr(SjT)=Pr(SandT)Pr(T)=Pr(S)Pr(T)Pr(T)=Pr(S)The second equation is similar.1.10We knowA<BandD<C. By direct counting:Pr(A<CjA<BandD<C)=Pr(A<CandA<BandD<C)Pr(A<BandD<C)=5=246=24=56Pr(A<DjA<BandD<C)=Pr(A<D<CandA<B)Pr(A<BandD<C)=3=246=24=36=12Pr(B<CjA<BandD<C)=Pr(A<B<CandD<C)Pr(A<BandD<C)=3=246=24=36=12Pr(B<DjA<BandD<C)=Pr(A<B<D<C)Pr(A<BandD<C)=1=246=24=161.12We assume that the probability of each coin being chosen is 1/3, that the probability that it shows “heads” after beingflipped is 1/2 and that the probability that it shows “tails” after being flipped is 1/2. Call the coinsA,B, andC. Definethe elementary events, each having probability 1/6, as follows.AHAis chosen and flipped and comes out “heads”.ATAis chosen and flipped and comes out “tails”.BHBis chosen and flipped and comes out “heads”.BTBis chosen and flipped and comes out “tails”.CHCis chosen and flipped and comes out “heads”.CTCis chosen and flipped and comes out “tails”.a)BHandCHcause a majority to be “heads”, so the probability is 1/3.b) No event causes a majority to be “heads”, so the probability is 0.c)AH,BH,CHandCTcause a majority to be “heads”, so the probability is 2/3.1.13The entry in rowi, columnjis the probability thatDiwill beatDj.0BBBB@1236183622362236123620361836223612361236163622361CCCCANote thatD1beatsD2,D2beatsD3,D3beatsD4, andD4beatsD1.

Page 11 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 11 preview image

4Chapter 1Analyzing Algorithms and Problems: Principles and Examples1.15The proof is by induction onn, the upper limit of the sum. The base case isn=0. Then∑0i=1i2=0, and2n3+3n2+n6=0.So the equation holds for the base case. Forn>0, assume the formula holds forn1.n∑i=1i2=n1∑i=1i2+n2=2(n1)3+3(n1)2+n16+n2=2n36n2+6n2+3n26n+3+n16+n2=2n33n2+n6+6n26=2n3+3n2+n61.18Consider any two realsw<z. We need to show thatf(w)f(z); that is,f(z)f(w)0. Sincef(x)is differentiable,it is continuous. We call upon theMean Value Theorem(sometimes called theTheorem of the Mean), which can befound in any college calculus text. By this theorem there is some pointy, such thatw<y<z, for whichf0(y)=(f(z)f(w))(zw):By the hypothesis of the lemma,f0(y)0. Also,(zw)>0. Therefore,f(z)f(w)0.1.20Letabbreviate the phrase, “is logically equivalent to”. We use the identity::AAas needed.:(8x(A(x))B(x)))9x:(A(x))B(x))(by Eq. 1.24)9x:(:A(x)_B(x))(by Eq. 1.21)9x(A(x)^:B(x))(by DeMorgan’s law, Eq. 1.23):Section 1.4:Analyzing Algorithms and Problems1.22The total number of operations in the worst case is 4n+2; they are:Comparisons involvingK:nComparisons involvingindex:n+1Additions:nAssignments toindex:n+11.23a)if (a< b)if (b< c)median =b;else if (a<c)median =c;elsemedian =a;else if (a< c)median = a;else if (b< c)median = c;elsemedian = b;

Page 12 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 12 preview image

Chapter 1Analyzing Algorithms and Problems: Principles and Examples5b)Dis the set of permutations of three items.c) Worst case = 3; average = 223.d) Three comparisons are needed in the worst case because knowing the median of three numbers requires knowingthe complete ordering of the numbers.1.25Solution 1.Pair up the entries and find the larger of each pair; ifnis odd, one element is not examined(bn=2ccomparisons). Then find the maximum among the larger elements using Algorithm 1.3, including the unexaminedelement ifnis odd (b(n+1)=2c1 comparisons). This is the largest entry in the set. Then find the minimum amongthe smaller elements using the appropriate modification of Algorithm 1.3, again including the unexamined element ifnis odd (b(n+1)=2c1 comparisons). This is the smallest entry in the set. Whethernis odd or even, the total isb32(n1)c. The following algorithm interleaves the three steps./**Precondition:n> 0.*/if(odd(n))min = E[n-1];max = E[n-1];else if(E[n-2] < E[n-1])min = E[n-2];max = E[n-1];elsemax = E[n-2];min = E[n-1];for(i =0; i<= n-3;i =i+2)if (E[i] <E[i+1])if (E[i] <min) min =E[i];if (E[i+1] >max) max =E[i+1];elseif (E[i] >max) max =E[i];if (E[i+1] <min) min =E[i+1];Solution 2.When we assign this problem after covering Divide and Conquer sorting algorithms in Chapter 4, manystudents give the following Divide and Conquer solution. (But most of them cannot show formally that it does roughly3n=2 comparisons.)If there are at most two entries in the set, compare them to find the smaller and larger. Otherwise, break the set inhalves, and recursively find the smallest and largest in each half. Then compare the largest keys from each half to findthe largest overall, and compare the smallest keys from each half to find the smallest overall.Analysis of Solution 2 requires material introduced in Chapter 3.The recurrence equation for this procedure,assumingnis a power of 2, isW(n)=1forn=2W(n)=2W(n=2)+2forn>2The recursion tree can be evaluated directly. It is important that the nonrecursive costs in then=2leavesof this treeare 1 each. The nonrecursive costs in then=21internal nodesare 2 each. This leads to the total of 3n=22 for thespecial case thatnis a power of 2. More careful analysis verifies the resultd3n=22efor alln. The result can also beproven by induction.Section 1.5:Classifying Functions by Their Asymptotic Growth Rates1.28limn!∞p(n)nk=limn!∞ak+ak1n+ak2n2+:::+a1nk1+a0nk=ak>0:

Page 13 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 13 preview image

6Chapter 1Analyzing Algorithms and Problems: Principles and Examples1.31The solution here combines parts (a) and (b). The functions on the same line are of the same asymptotic order.lg lgnlgn;lnn(lgn)2pnnnlgnn1+εn2;n2+lgnn3nn3+7n52n1;2nenn!1.33Letf(n)=n. For simplicity we show a counter-example in which a nonmonotonic function is used. Consider thefunctionh(n):h(n)=nfor oddn1for evennClearlyh(n)2O(f(n)). Buth(n)62Ω(f(n)), soh(n)62Θ(f(n)). Therefore,h(n)2O(f(n))Θ(f(n)). It remains toshow thath(n)62o(f(n)). But this follows by the fact thath(n)=f(n)=1 for odd integers.With more difficultyh(n)can be constructed to be monotonic. For allk1, leth(n)be constant on the intervalkkn((k+1)k+11)and leth(n)=kkon this interval. Thus whenn=kk,h(n)=f(n)=1, but whenn=(k+1)k+11,h(n)=f(n)=kk=((k+1)k+11), which tends to 0 asngets large.1.35Property 1: Supposef2O(g).There arec>0 andn0such that fornn0,f(n)cg(n).Then fornn0,g(n)(1=c)f(n). The other direction is proved similarly.Property 2:f2Θ(g)meansf2O(g)\Ω(g). By Property 1,g2Ω(f)\O(f), sog2Θ(f).Property 3: Lemma 1.9 of the text gives transitivity. Property 2 gives symmetry. Since for anyf,f2Θ(f), we havereflexivity.Property 4: We showO(f+g)O(max(f;g)). The other direction is similar. Leth2O(f+g). There arec>0 andn0such that fornn0,h(n)c(f+g)(n). Then fornn0,h(n)2cmax(f;g)(n).1.37We will use L’Hˆopital’s Rule, so we need to differentiate 2n. Observe that 2n=(eln 2)n=enln2. Letc= ln20.7.The derivative ofenisen, so, using the chain rule, we find that the derivative of 2nisc2n. Now, using L’Hˆopital’s Rulerepeatedly,limn!∞nk2n=limn!∞knk1c2n=limn!∞k(k1)nk2c22n==limn!∞k!ck2n=0sincekis constant.1.39f(n)=1nforoddnforevenng(n)=n1foroddnforevennThere are also examples using continuous functions on the reals, as well as examples using monotonic functions.

Page 14 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 14 preview image

Chapter 1Analyzing Algorithms and Problems: Principles and Examples7Section 1.6:Searching an Ordered Array1.42The revised procedure is:intbinarySearch(int[] E, intfirst, intlast, int K)1.if(last < first)2.index =-1;3.else if(last == first)4.if(K ==E[first])5.index = first;6.else7.index = -1;8.else9.intmid= (first +last) /2;10.if(KE[mid])11.index = binarySearch(E, first, mid, K);12.else13.index = binarySearch(E, mid+1, last, K);14.return index;Compared to Algorithm 1.4 (Binary Search) in the text, this algorithm combines the tests of lines 5 and 7 into one teston line 10, and the left subrange is increased from mid1 to mid, because mid might contain the key being searchedfor. An extra base case is needed in lines 3–7, which tests for exact equality when the range shrinks to a single entry.Actually, if we can assume the precondition firstlast, then lines 1–2 can be dispensed with. This procedurepropagates that precondition into recursive calls, whereas the procedure of Algorithm 1.4 does not, in certain cases.1.44The sequential search algorithm considers only whetherxis equal to or unequal to the element in the array beingexamined, so we branch left in the decision tree for “equal” and branch right for “unequal.”Each internal nodecontains the index of the element to whichxis compared. The tree will have a long path, withninternal nodes, downto the right, labeled with indexes 1;:::;n. The left child for a node labelediis an output node labeledi. The rightmostleaf is an output node for the case whenxis not found.1.46The probability thatxis in the array isn=m.Redoing the average analysis for Binary Search (Section 1.6.3) with the assumption thatxis in the array (i.e.,eliminating the terms for the gaps) gives an average of approximatelydlgne1. (The computation in Section 1.6.3assumes thatn=2k1 for somek, but this will give a good enough approximation for the average in general.)The probability thatxis not in the array is 1n=m. In this case (again assuming thatn=2k1),dlgnecomparisonsare done. So the average for all cases is approximatelynm(dlgne1)+(1nm)dlgne=dlgnenmdlgne:(Thus, under various assumptions, Binary Search does roughly lgncomparisons.)1.47We examine selected elements in the array in increasing order until an entry larger thanxis found; then do a binarysearch in the segment that must containxif it is in the array at all. To keep the number of comparisons inO(logn), thedistance between elements examined in the first phase is doubled at each step. That is, comparextoE[1],E[2],E[4],E[8];:::;E[2k]. We will find an element larger thanx(perhapsmaxint) after at mostdlgne+1 probes (i.e.,kdlgne).(Ifxis found, of course, the search terminates.) Then do the Binary Search in the rangeE[2k1+1];:::;E[2k1]using at mostk1 comparisons. (IfE[1]>x, examineE[0].) Thus the number of comparisons is at most 2k=2dlgne.1.48Forx>0, writexlnxaslnx(1x). By L’Hˆopital’s rule the limit of this ratio asx!0 is the same as the limit of1x(1x2)=x.

Page 15 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 15 preview image

8Chapter 1Analyzing Algorithms and Problems: Principles and Examples1.50The strategy is to divide the group of coins known to contain the fake coin into subgroups such that, after one moreweighing, the subgroup known to contain the fake is as small as possible, no matter what the outcome of the weighing.Obviously, two equal subgroups would work, but we can do better by makingthreesubgroups that are as equal aspossible.Then weigh two of those subgroups that have an equal number of coins.If the two subgroups that areweighed have equal weight, the fake is in the third subgroup.Round 123, 23, 24Round 28, 8, 8(or 8, 8, 7)Round 33, 3, 2(or 3, 2, 2)Round 41, 1, 1(or 1, 1, 0)So four weighings suffice.

Page 16 of 16

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 16 preview image

Chapter 2Data Abstraction and Basic Data StructuresSection 2.2:ADT Specification and Design Techniques2.2Several answers are reasonable, provided that they bring out that looking at the currentimplementationof the ADT isa bad idea.Solution 1.GorpTester.javawould be preferable because thejavadocutility (with an html browser) permitsthe ADT specifications and type declarations to be inspected without looking at the source code ofGorp.java.Trying to infer what the ADT operations do by looking at the implementation inGorp.javais not reliable. How-ever, even if the implementation inGorp.javachanges, as long as the ADT specifications do not change, then thebehavior ofGorpTester.javawill remain unchanged, so it is a reliable source of information.Solution 2.Gorp.javawould be preferable because the javadoc comments in it should contain the preconditionsand postconditions for each operation.Section 2.3:Elementary ADTs — Lists and Trees2.4The proof is by induction ond, the depth of the node. For a given binary tree, letnddenote the number of nodes atdepthd. Ford=0, there is only 1 root node and 1=20.Ford>0, assume the formula holds ford1. Because each node at depthd1 has at most 2 children,nd2nd12(2d1)2d2.6A tree of heightdlg(n+1)e2 would, by Lemma 2.2, have a t most 2dlg(n+1)e11 nodes. But2dlg(n+1)e11<2lg(n+1)1=n+11=nBecause that expression is less thann, any tree withnnodes would have to have height at leastdlg(n+1)e1.2.8The point of the exercise is to recognize that a binary tree in which all the left subtrees are nil is logically the sameas a list. We would give full credit, or almost full credit, to any solution that brings out that idea, without worryingtoo much about details specific to Java, which can get somewhat complicated. (It is also possible to make all the rightsubtrees nil and use the left subtrees to contain the elements, but this is less natural.) We will give several solutions todemonstrate the range of possibilities. Solutions 2 and 3 have been compiled and tested in Java 1.2.Solution 1.This solution merely uses theBinTreefunctions and does not even return objects in theListclass,so all the objects are in the classBinTree. Therefore, this solution doesn’t really meet the specifications of the ListADT. Its virtue is simplicity. (In C, the type discrepancy can be solved with a type cast; Java is more strict.)public class List{public static final BinTree nil =BinTree.nil;public staticObject first(BinTree aList) {return BinTree.root(aList); }public staticBinTree rest(BinTree aList) {return BinTree.rightSubtree(aList); }public staticBinTree cons(Object newElement, BinTree oldList){return BinTree.buildTree(newElement, BinTree.nil, oldList); }}

Preview Mode

This document has 114 pages. Sign in to access the full document!

Report

Learning Tools

Writing Tools

Browse Resources

Solution Manual for Computer Algorithms: Introduction to Design and Analysis, 3rd Edition - Page 1

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools