e文算法导论习题答案1end

《e文算法导论习题答案1end》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SolutionsforIntroductiontoalgorithmsPhilipBilleSpring2001Theauthorofthisdocumenttakesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroductiontoalgo-rithmsbyCormen,LeisersonandRivest.Itisverylikelythattherearemany

2、errorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutionorwishtocontributeinsomeconstructivewaypleasesendamessagetobeetle@diku.dk.Itisimportantthatyoutryhardtosolvetheexercisesonyourown.Usethisdocumentonlyasalastresortortocheckifyourinstructorgotitallwrong.Sincea

3、secondeditionforthebookrecentlyhasbeendonethisdocumentislongerbeingupdated.Havefunwithyouralgorithms.Bestregards,PhilipBilleLastupdate:may17,20011:1-2Inline5ofINSERTION-SORTalterA[i]>keytoA[i]

4、ha1;a2;:::aniandavaluev.Output:Anindexisuchthatv=A[i]ornilifv62Afori1tondoifA[i]=vthenreturniendifendforreturnnil1:2-1Thisisaslightimprovementoftherequestedalgorithm:sortingisdonein-placeinsteadofusingasecondarray.AssumethatFIND-MIN(A;r;s)returnstheindexofthesmallestelementinAbetwe

5、enindicesrands.Clearly,thiscanbeimplementedinO(s-r)timeifr>s.Algorithm2SELECTION-SORT(A)Input:A=ha1;a2;:::aniOutput:sortedA.fori1tondojFIND-MIN(A;i;n)A[j]$A[i]endforThencallsofFIND-MINgivesthefollowingboundonthetimecomplexity:!Xn2i=(n)i=1Thisholdsforboththebest-andworst-caserunni

6、ngtime.1:2-2Giventhateachelementisequallylikelytobetheonesearchedfor,alinearsearchwillontheaveragehavetosearchthroughhalftheelements.Thisisbecausehalfthetimethewantedelementwillbeinthersthalfandhalfthetimeitwillbeinthesecondhalf.Boththeworst-caseandaverage-caseofLINEAR-SEARCHis(n

7、).1:2-3SolvetheElementUniquenessProblemin(nlgn)time.Simplysortthenumbersandperformalinearrunthroughthearraysearchingforduplicates.1:2-5n3=1000-100n2-100n+3=(n3).21:2-6Onecanmodifyanalgorithmtohaveabest-caserunningtimebyspecializingittohandleabest-caseinputefciently.1:3-2Algorith

8、m3MERGE(A;p;q;r)Input:Twos