算法导论第三版答案Ch5.pdf

《算法导论第三版答案Ch5.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter5MichelleBodnar,AndrewLohrFebruary16,2018Exercise5.1-1Wemayhavebeenpresentedthecandidatesinincreasingorderofgoodness.ThiswouldmeanthatwecanapplytransitivitytodetermineourpreferencebetweenanytwocandidatesExercise5.1-2Algorithm1RANDOM(a,b)1:n=dlg(ba+1)e2:Initializeanarr

2、ayAoflengthn3:whiletruedo4:fori=1tondo5:A[i]=RANDOM(0;1)6:endfor7:ifAholdsthebinaryrepresentationofoneofthenumbersinathroughbthen8:returnnumberrepresentedbyA9:endif10:endwhileEachiterationofthewhilelooptakesntimetorun.Theprobabilitythatthewhileloopstopsonagiveniterationis(ba

3、+1)=2n.Thustheexpectedrunningtimeistheexpectednumberoftimesruntimesn.Thisisgivenby:Xi1n2nba+1ba+1ba+122ni1=n=n=O(lg(ba)):2n2n2nba+1ba+1i1Exercise5.1-3ClearlysinceaandbareIID,theprobabilitythisalgorithmreturnsoneisequaltotheprobabilityitreturns0.Also,sincether

4、eisaconstantpositiveprobability(2p(p1))thatthealgorithmreturnsoneachiterationofthefor11:foralleternitydo2:a=BiasedRandom3:b=BiasedRandom4:ifa>bthen5:return16:endif7:ifa

5、(12p(p1))12p(p1)j(12p(p1))(2p(p1))==(2p(p1))22p(p1)j=0Notethattheformulausedforthesumofjjcanbeobtainedbydierentiawt-ingbothsidesofthegeometricsumformulaforjwithrespecttoExercise5.2-1Youwillhireexactlyonetimeifthebestcandidateispresentedrst.Thereare(n1)!orderingsw

6、iththebestcandidaterst,so,itiswithprobability(n1)!=1thatyouonlyhireonce.Youwillhireexactlyntimesifthecandi-n!ndatesarepresentedinincreasingorder.Thisxestheorderingtoasingleone,andsothiswilloccurwithprobability1.n!Exercise5.2-2Sincetherstcandidateisalwayshired,weneedtocomp

7、utetheprobabilitythatthatexactlyoneadditionalcandidateishired.Sinceweviewthecandidaterankingasreadinganrandompermutation,thisisequivalenttotheprobabilitythatarandompermutationisadecreasingsequencefollowedbyanincrease,followedbyanotherdecreasingsequence.Suchapermutationcanbeth

8、oughtofasapartitionof[n]into2parts.Oneofsizekandtheotherofsizenk,wh