算法设计与分析基础课后习题答案.pdf

ThisfilecontainstherciseshintsandsolutionsforChapter2ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms”2ndeditionbyA.Levitin.Theproblemsthatmightbechallengingforatleastsomestudentsaremarkedbythosethatmightbedifficultforamajorityofstudentsaremarkedby.rcises2.11.Foreachofthefollowingalgorithmsindicate(i)anaturalsizemetricforitss(ii)itsbasicoperation(iii)whetherthebasicoperationcountcanbedifferentforsofthesamesize:putingn!c.findingthelargestelementinalistofnnumbersd.Euclidsalgorithme.sieveofEratosthenesf.pen-and-pencilalgorithmultiplyingtwon-digitdecimalintegers2.a.Considerthedefinition-basedalgorithmforaddingtwon-by-nmatri-ces.WhatisitsbasicoperationHowmanytimesisitperedasafunctionofthematrixordernAsafunctionofthetotalnumberofelementsinthematricesb.Answerthesamequestionsforthedefinition-basedalgorithmatrixmultiplication.3.Consideravariationofsequentialsearchthatscansalisttoreturnthenumberofoccurrencesofagivensearchkeyinthelist.Willitsefficiencydifferfromtheefficiencyofclassicsequentialsearch4.a.GloveselectionThereare22glovesinadrawer:5pairsofredgloves4pairsofyellowand2pairsofgreen.Youselecttheglovesinthedarkandcancheckthemonlyafteraselectionhasbeenmade.Whatisthesmallestnumberofglovesyouneedtoselecttohaveatleastonematchingpairinthebestcaseintheworstcase(afterMos01#18)b.MissingsocksImaginethatafterwashing5distinctpairsofsocksyoudiscoverthattwosocksaremissing.Ofcourseyouwouldliketohavethelargestnumberofcompletepairsremaining.Thusyouareleftwith4completepairsinthebest-casescenarioandwith3completepairsintheworstcase.Assumingthattheprobabilityofdisappearanceforeach1ofthe10socksisthesamefindtheprobabilityofthebest-casescenariotheprobabilityoftheworst-casescenariothenumberofpairsyoushouldexpectintheaveragecase.(afterMos01#48)5.a.Proveula(2.1)forthenumberofbitsinthebinaryrepresentationofapositiveinteger.b.Whatwouldbetheanalogousulaforthenumberofdecimaldigitsc.Explainwhywithintheacceptedanalysisframeworkitdoesnotmat-terwhetherweusebinaryordecimaldigitsinmeasuringnssize.6.Suggesthowanysortingalgorithmcanbeaugmentedinawaytomakethebest-casecountofitskeycomparisonsequaltojustn1(nisalistssizeofcourse).Doyouthinkitwouldbeaworthwhileadditiontoanysortingalgorithm7.Gaussianeliminationtheclassicalgorithmforsolvingsystemsofnlinearequationsinnunknownsrequiresabout13n3multiplicationswhichisthealgorithmsbasicoperation.a.HowmuchlongershouldyouexpectGaussianeliminationtoworkonasystemof1000equationsversusasystemof500equationsb.Youareconsideringbuyingacomputerthatis1000timesfasterthantheoneyoucurrentlyhave.Bywhatfactorwillthefastercomputerin-creasethesizesofsystemssolvableinthesameamountoftimeasontheoldcomputer8.Foreachofthefollowingfunctionsindicatehowmuchthefunctionsvaluewillchangeifitsargumentisincreasedfourfold.a.log2nb.nc.nd.n2e.n3f.2n9.Indicatewhetherthefirstfunctionofeachofthefollowingpairshasasmallersameorlargerorderofgrowth(towithinaconstantmultiple)thanthesecondfunction.a.n(n+1)and2000n2b.100n2and0.01n3c.log2nandlnnd.log22nandlog2n2e.2n1and2nf.(n1)!andn!10.InventionofchessAccordingtoawell-knownlegendthegameofchesswasinventedmanycenturiesagoinnorthwesternIndiabyasagenamedShashi.Whenhetookhisinventiontohiskingthekinglikedthegame2somuchthatheofferedtheinventoranyrewardhewanted.Sashiaskedforsomegraintobeobtainedasfollows:justasinglegrainofwheatwastobeplacedonthefirstsquareofthechessboardtwoonthesecondfouronthethirdeightonthefourthandsoonuntilall64squareshadbeenfilled.Whatwouldtheultimateresultofthisalgorithmhavebeen3Hintstorcises2.11.Thequestionsareindeedasstraightforwardastheyappearthoughsomeofthemmayhavealternativeanswers.Alsokeepinmindthecaveataboutmeasuringanintegerssize.2.a.Thesumoftwomatricesisdefinedasthematrixwhoseelementsarethesumsofthecorrespondingelementsofthematricesgiven.b.Matrixmultiplicationrequirestwooperations:multiplicationandad-dition.Whichofthetwowouldyouconsiderbasicandwhy3.Willthealgorithmsefficiencyvaryondifferentsofthesamesize4.a.Glovesarenotsocks:theycanberight-handedandleft-handed.b.Youhaveonlytwoqualitativelydifferentoutcomespossible.Countthenumberofwaystogeteachofthetwo.5.a.Provefirstthatifapositivedecimalintegernhasbdigitsinitsbinaryrepresentationthen2b1n0.87.Prove(byusingthedefinitionsofthenotationsinvolved)ordisprove(bygivingaspecificcounterexample)thefollowingassertions.a.Ift(n)O(g(n)theng(n)(t(n).b.(g(n)=(g(n)where0.c.(g(n)=O(g(n)(g(n).d.Foranytwononnegativefunctionst(n)andg(n)definedonthesetofnonnegativeintegerseithert(n)O(g(n)ort(n)(g(n)orboth.8.Provethesectionstheoremfora.notation.b.notation.9.Wementionedinthissectionthatonecancheckwhetherallelementsofanarrayaredistinctbyatwo-partalgorithmbasedonthearrayspresorting.a.Ifthepresortingisdonebyanalgorithmwiththetimeefficiencyin(nlogn)whatwillbethetimeefficiencyclassoftheentirealgorithmb.Ifthesortingalgorithmusedforpresortingneedsanextraarrayofsizenwhatwillbethespaceefficiencyclassoftheentirealgorithm10.DoorinawallYouarefacingawallthatstretchesinfinitelyinbothdirections.Thereisadoorinthewallbutyouknowneitherhowfarawaynorinwhichdirection.Youcanseethedooronlywhenyouarerightnexttoit.DesignanalgorithmthatenablesyoutoreachthedoorbywalkingatmostO(n)stepswherenisthe(unknowntoyou)numberofstepsbetweenyourinitialpositionandthedoor.Par95#6529Hintstorcises2.21.Usethecorrespondingcountsofthealgorithmsbasicoperation(seeSec-tion2.1)andthedefinitionsofOand.2.Establishtheorderofgrowthofn(n+1)2firstandthenusetheinaldefinitionsofOand.(Similarexamplesweregiveninthesection.)3.Simplifythefunctionsgiventosingleoutthetermsdefiningtheirordersofgrowth.4.a.Checkcarefullythepertinentdefinitions.b.Computetheratiolimitsofeverypairofconsecutivefunctionsonthelist.5.Firstsimplifysomeofthefunctions.ThenusethelistoffunctionsinTable2.2to“anchor”eachofthefunctionsgiven.Provetheirfinalplacementbycomputingappropriatelimits.6.a.Youcanprovethisassertioneitherbycomputinganappropriatelimitorbyapplyingmathematicalinduction.b.Computelimnan1an2.7.Provethecorrectnessof(a)(b)and(c)byusingtheappropriatede-finitionsconstructacounterexamplefor(d)(e.g.byconstructingtwofunctionsbehavingdifferentlyforoddandevenvaluesoftheirarguments).8.Theproofofpart(a)issimilartotheonegivenforthetheoremsassertioninSection2.2.Ofcoursedifferentinequalitiesneedtobeusedtoboundthesumfrombelow.9.Followtheanalysisplanusedinthetextwhenthealgorithmwasmen-tionedforthefirsttime.10.Youshouldwalkintermittentlyleftandrightfromyourinitialpositionuntilthedoorisreached.10Solutionstorcises2.21.a.SinceCworst(n)=nCworst(n)(n).b.SinceCbest(n)=1Cbest(1)(1).c.SinceCavg(n)=p(n+1)2+n(1p)=(1p2)n+p2where0p1Cavg(n)(n).2.n(n+1)2n22isquadratic.Thereforea.n(n+1)2O(n3)istrue.b.n(n+1)2O(n2)istrue.c.n(n+1)2(n3)isfalse.d.n(n+1)2(n)istrue.3.a.Inally(n2+1)10(n2)10=n20(n20)allylimn(n2+1)10n20=limn(n2+1)10(n2)10=limnn2+1n210=limn1+1n210=1.Hence(n2+1)10(n20).Note:Analternativeproofcanbebasedonthebinomialulaandtheassertionofrcise6a.b.Inally10n2+7n+310n2=10n(n).allylimn10n2+7n+3n=limn10n2+7n+3n2=limn10+7n+3n2=10.Hence10n2+7n+3(n).c.2nlg(n+2)2+(n+2)2lgn2=2n2lg(n+2)+(n+2)2(lgn1)(nlgn)+(n2lgn)=(n2lgn).d.2n+1+3n1=2n2+3n13(2n)+(3n)=(3n).e.Inallylog2nlog2n(logn).allybyusingthein-equalitiesx1log2n1log2n12log2n(foreveryn4)=12log2n.Hencelog2n(log2n)=(logn).114.a.TheorderofgrowthandtherelatednotationsOanddealwiththeasymptoticbehavioroffunctionsasngoestoinfinity.Thereforenospecificvaluesoffunctionswithinafiniterangeofnsvaluessuggestiveastheymightbecanestablishtheirordersofgrowthwithmathematicalcertainty.b.limnlog2nn=limn(log2n)(n)=limn1nlog2e1=log2elimn1n=0.limnnnlog2n=limn1log2n=0.limnnlog2nn2=limnlog2nn=(seethefirstlimitofthisrcise)=0.limnn2n3=limn1n=0.limnn32n=limn(n3)(2n)=limn3n22nln2=3ln2limnn22n=3ln2limn(n2)(2n)=3ln2limn2n2nln2=6ln22limnn2n=6ln22limn(n)(2n)=6ln22limn12nln2=6ln32limn12n=0.limn2nn!=(seeExample3inthesection)0.5.(n2)!(n2)!)5lg(n+100)10=50lg(n+100)(logn)22n=(22)n(4n)0.001n4+3n3+1(n4)ln2n(log2n)3n(n13)3n(3n).Thelistofthesefunctionsorderedinincreasingorderofgrowthlooksasfollows:5lg(n+100)10ln2n3n0.001n4+3n3+13n22n(n2)!6.a.limnp(n)nk=limnaknk+ak1nk1+.+a0nk=limn(ak+ak1n+.+a0nk)=ak0.Hencep(n)(nk).b.limnan1an2=limna1a2n=0ifa1a2an2o(an1)7.a.Theassertionshouldbecorrectbecauseitstatesthatiftheorderofgrowthoft(n)issmallerthanorequaltotheorderofgrowthofg(n)then12theorderofgrowthofg(n)islargerthanorequaltotheorderofgrowthoft(n).Thealproofisimmediatetoo:t(n)cg(n)forallnn0wherec0implies(1c)t(n)g(n)forallnn0.b.Theassertionthat(g(n)=(g(n)shouldbetruebecauseg(n)andg(n)differjustbyapositiveconstantmultipleandhencebythedefinitionofmusthavethesameorderofgrowth.Thealproofhastoshowthat(g(n)(g(n)and(g(n)(g(n).Letf(n)(g(n)wellshowthatf(n)(g(n).Indeedf(n)cg(n)forallnn0(wherec0)canberewrittenasf(n)c1g(n)forallnn0(wherec1=c0)i.e.f(n)(g(n).Letnowf(n)(g(n)wellshowthatf(n)(g(n)for0.Indeediff(n)(g(n)f(n)cg(n)forallnn0(wherec0)andthereforef(n)cag(n)=c1g(n)forallnn0(wherec1=c0)i.e.f(n)(g(n).c.Theassertionisobviouslycorrect(similartotheassertionthata=bifandonlyifabandab).Thealproofshouldshowthat(g(n)O(g(n)(g(n)andthatO(g(n)(g(n)(g(n)whichimmediatelyfollowfromthedefinitionsofOand.d.Theassertionisfalse.Thefollowingpairoffunctionscanserveasacounterexamplet(n)=nifnisevenn2ifnisoddandg(n)=n2ifnisevennifnisodd138.a.Weneedtoprovethatift1(n)(g1(n)andt2(n)(g2(n)thent1(n)+t2(n)(maxg1(n)g2(n).ProofSincet1(n)(g1(n)thereexistsomepositiveconstantc1andsomenonnegativeintegern1suchthatt1(n)c1g1(n)forallnn1.Sincet2(n)(g2(n)thereexistsomepositiveconstantc2andsomenonnegativeintegern2suchthatt2(n)c2g2(n)forallnn2.Letusdenotec=minc1c2andconsidernmaxn1n2sothatwecanusebothinequalities.Addingthetwoinequalitiesaboveyieldsthefollowing:t1(n)+t2(n)c1g1(n)+c2g2(n)cg1(n)+cg2(n)=cg1(n)+g2(n)cmaxg1(n)g2(n).Hencet1(n)+t2(n)(maxg1(n)g2(n)withtheconstantscandn0requiredbytheOdefinitionbeingminc1c2andmaxn1n2re-spectively.b.Theprooffollowsimmediatelyfromthetheoremprovedinthetext(theOpart)theassertionprovedinpart(a)ofthisrcise(thepart)andthedefinitionof(seercise7c).9.a.Sincetherunningtimeofthesortingpartofthealgorithmwillstilldominatetherunningtimeoftheseconditstheerthatwilldeter-minethetimeefficiencyoftheentirealgorithm.allyitfollowsfromequality(nlogn)+O(n)=(nlogn)whosidityiseasytoproveinthesamemannerasthatofthesectionstheorem.b.Sincethesecondpartofthealgorithmwillusenoextraspacethespaceefficiencyclasswillbedeterminedbythatofthefirst(sorting)part.Thereforeitwillbein(n).10.Thekeyideahereistowalkintermittentlyrightandleftgoingeachtimeexponentiallyfartherfromtheinitialposition.Asimpleimplementationofthisideaistodothefollowinguntilthedoorisreached:Fori=01.make2istepstotherightreturntotheinitialpositionmake2istepsto14theleftandreturntotheinitialpositionagain.Let2k1ni=1(ni1)=nni=11ini=11nn+111xdxn=nln(n+1)n(nlogn).9.Hereisaproofbymathematicalinductionthatni=1i=n(n+1)2foreverypositiveintegern.(i)Basisstep:Forn=1ni=1i=1i=1i=1andn(n+1)2n=1=1(1+1)2=1.(ii)Inductivestep:Assumethatni=1i=n(n+1)2forapositiveintegern.Weneedtoshowthatthenn+1i=1i=(n+1)(n+2)2.Thisisobtainedasfollows:n+1i=1i=ni=1i+(n+1)=n(n+1)2+(n+1)=n(n+1)+2(n+1)2=(n+1)(n+2)2.TheyoungGausscomputedthesum1+2+.+99+100bynoticingthatitcanbecomputedasthesumof50pairseachwiththesum101:1+100=2+99=.=50+51=101.Hencetheentiresumisequalto50101=5050.(Thewell-knownhistoricanecdoteclaimsthathisteachergavethisassignmenttoaclasstokeep24theclassbusy.)TheGaussideacanbeeasilygeneralizedtoanarbitrarynbyaddingS(n)=1+2+.+(n1)+nandS(n)=n+(n1)+.+2+1toobtain2S(n)=(n+1)nandhenceS(n)=n(n+1)2.10.a.ThenumberofmultiplicationsM(n)andthenumberofdivisionsD(n)madebythealgorithmaregivenbythesamesum:M(n)=D(n)=n2i=0n1j=i+1nk=i1=n2i=0n1j=i+1(ni+1)=n2i=0(ni+1)(n1(i+1)+1)=n2i=0(ni+1)(ni1)=(n+1)(n1)+n(n2)+.+31=n1j=1(j+2)j=n1j=1j2+n1j=12j=(n1)n(2n1)6+2(n1)n2=n(n1)(2n+5)613n3(n3).b.TheinefficiencyistherepeateduationoftheratioAjiAiiinthealgorithmsinnermostloopwhichinfactdoesnotchangewiththeloopvariablek.Hencethisloopinvariantcanbecomputedjustoncebeforeenteringthisloop:tempAjiAiitheinnermostloopisthenchangedtoAjkAjkAiktemp.Thischangeeliminatesthemostexpensiveoperationofthealgorithmthedivisionfromitsinnermostloop.Therunningtimegainobtainedbythischangecanbeestimatedasfollows:Told(n)Tnew(n)cM13n3+cD13n3cM13n3=cM+cDcM=cDcM+1wherecDandcMarethetimeforonedivisionandonemultiplicationrespectively.2511.Theanswercanbeobtainedbyastraightforwarduationofthesum2ni=1(2i1)+(2n+1)=2n2+2n+1.(Onecanalsogettheclosed-answerbynotingthatthecellsontheal-ternatingdiagonalsofthevonNeumannneighborhoodofrangencomposetwosquaresofsizesn+1andnrespectively.)26rcises2.41.Solvethefollowingrecurrencerelations.a.x(n)=x(n1)+5forn1x(1)=0b.x(n)=3x(n1)forn1x(1)=4c.x(n)=x(n1)+nforn0 x(0)=0d.x(n)=x(n2)+nforn1x(1)=1(solveforn=2k)e.x(n)=x(n3)+1forn1x(1)=1(solveforn=3k)2.SetupandsolvearecurrencerelationforthenumberofcallsmadebyF(n)therecursivealgorithmforcomputingn!.3.Considerthefollowingrecursivealgorithmforcomputingthesumofthefirstncubes:S(n)=13+23+.+n3.AlgorithmS(n):ApositiveintegernOutput:Thesumofthefirstncubesifn=1return1elsereturnS(n1)+nnna.Setupandsolvearecurrencerelationforthenumberoftimesthealgorithmsbasicoperationiscuted.b.Howdoesthisalgorithmcomparewiththestraightforwardnonrecursivealgorithmforcomputingthisfunction4.Considerthefollowingrecursivealgorithm.AlgorithmQ(n):Apositiveintegernifn=1return1elsereturnQ(n1)+2n1a.Setuparecurrencerelationforthisfunctionsvaluesandsolveittodeterminewhatthisalgorithmcomputes.b.Setuparecurrencerelationforthenumberofmultiplicationsmadebythisalgorithmandsolveit.c.Setuparecurrencerelationforthenumberofadditionssubtractionsmadebythisalgorithmandsolveit.275.a.IntheoriginalversionoftheTowerofHanoipuzzleasitwaspublishedbyEdouardLucasaFrenchmathematicianinthe1890stheworldwillendafter64diskshavebeenmovedfromamysticalTowerofBrahma.Estimatethenumberofyearsitwilltakeifmonkscouldmoveonediskperminute.(Assumethatmonksdonoteatsleepordie.)b.Howmanymovesaremadebytheithlargestdisk(1in)inthisalgorithmc.DesignanonrecursivealgorithmfortheTowerofHanoipuzzle.6.a.Provethattheexactnumberofadditionsmadebytherecursivealgo-rithmBinRec(n)foranarbitrarypositiveintegernislog2n.b.Setuparecurrencerelationforthenumberofadditionsmadebythenonrecursiveversionofthisalgorithm(seeSection2.3Example4)andsolveit.7.a.Designarecursivealgorithmforcomputing2nforanynonnegativeintegernthatisbasedontheula:2n=2n1+2n1.b.Setuparecurrencerelationforthenumberofadditionsmadebythealgorithmandsolveit.c.Drawatreeofrecursivecallsforthisalgorithmandcountthenumberofcallsmadebythealgorithm.d.Isitagoodalgorithmforsolvingthisproblem8.Considerthefollowingrecursivealgorithm.AlgorithmMin1(A0.n1):AnarrayA0.n1ofrealnumbersifn=1returnA0elsetempMin1(A0.n2)iftempAn1returntempelsereturnAn1a.Whatdoesthisalgorithmcomputeb.Setuparecurrencerelationforthealgorithmsbasicoperationcountandsolveit.9.ConsideranotheralgorithmforsolvingthesameproblemastheoneinProblem8whichrecursivelydividesanarrayintotwohalves:28callMin2(A0.n1)whereAlgorithmMin2(Al.r)ifl=rreturnAlelsetemp1Min2(Al.(l+r)2)temp2Min2(A(l+r)2+1.r)iftemp1temp2returntemp1elsereturntemp2a.Setuparecurrencerelationforthealgorithmsbasicoperationandsolveit.b.WhichofthealgorithmsMin1orMin2isfasterCanyousug-gestanalgorithmfortheproblemtheysolvethatwouldbemoreefficientthaneitherofthem10.Thedeterminantofann-by-nmatrixA=a11a1na21a2nan1anndenoteddetAcanbedefinedasa11forn=1andforn1bytherecursiveuladetA=nj=1sja1jdetAjwheresjis+1ifjisoddand-1ifjisevena1jistheelementinrow1andcolumnjandAjisthe(n1)-by-(n1)matrixobtainedfrommatrixAbydeletingitsrow1andcolumnj.a.Setuparecurrencerelationforthenumberofmultiplicationsmadebythealgorithmimplementingthisrecursivedefinition.b.Withoutsolvingtherecurrencewhatcanyousayaboutthesolu-tionsorderofgrowthascomparedton!9.vonNeumannneighborhoodrevisitedFindthenumberofcellsinthevonNeumannneighborhoodofrangen(seeProblem11inrcises2.3)bysettingupandsolvingarecurrencerelation.29Hintstorcises2.41.Eachoftheserecurrencescanbesolvedbytheofbackwardsub-stitutions.2.Therecurrencerelationinquestionisalmostidenticaltotherecurrencerelationforthenumberofmultiplicationswhichwassetupandsolvedinthesection.3.a.Thequestionissimilartothatabouttheefficiencyoftherecursivealgorithmforcomputingn!.b.Writeapseudocodeforthenonrecursivealgorithmanddetermineitsefficiency.4.a.Notethatyouareaskedhereaboutarecurrenceforthefunctionsvaluesnotaboutarecurrenceforthenumberoftimesitsoperationiscuted.Justfollowthepseudocodetosetitup.Itiseasiertosolvethisrecurrencebyforwardsubstitutions(seeAppendixB).b.Thisquestionisverysimilartoonewehavealreadydiscussed.c.Youmaywanttoincludethesubstractionneededtodecreasen.5.a.Usetheulaforthenumberofdiskmovesderivedinthesection.b.Solvetheproblemfor3diskstoinvestigatethenumberofmovesmadebyeachofthedisks.Thengeneralizetheobservationsandprovetheirvalidityforthegeneralcaseofndisks.c.Ifyoufaildonotfeeldiscouraged:thoughanonrecursivealgorithmforthisproblemsisnotcomplicateditisnoteasytodiscover.AsaconsolationfindasolutionontheWeb.6.a.Considerseparatelythecasesofevenandoddvaluesofnandshowthatforbothofthemlog2nsatisfiestherecurrencerelationanditsinitialcondition.b.Justfollowthealgorithmspseudocode.7.a.Usetheula2n=2n1+2n1withoutsimplifyingitdonotforgettoprovideaconditionforstoppingyourrecursivecalls.b.AsimilaralgorithmwasinvestigatedinSection2.4.c.AsimilarquestionwasinvestigatedinSection2.4.d.Abadefficiencyclassofanalgorithmbyitselfdoesnotmeanthat30thealgorithmisbad.ForexampletheclassicalgorithmfortheTowerofHanoipuzzleisoptimaldespiteitsexponential-timeefficiency.Thereforeaclaimthataparticularalgorithmisnotgoodrequiresareferencetoabetterone.8.a.Tracingthealgorithmforn=1andn=2shouldhelp.b.Itisverysimilartooneoftheexample