Introduction to Algorithms 第二版 (Tomas H. Cormen 著) 机械工业出版社 课后答案 52页

'课后答案网：www.hackshp.cn课后答案网您最真诚的朋友www.hackshp.cn网团队竭诚为学生服务，免费提供各门课后答案，不用积分，甚至不用注册，旨在为广大学生提供自主学习的平台！课后答案网：www.hackshp.cn视频教程网：www.efanjy.comPPT课件网：www.ppthouse.com课后答案网www.hackshp.cn若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnSolutionsforIntroductiontoalgorithmssecondeditionPhilipBilleTheauthorofthisdocumenttakesabsolutelynoresponsibilityforthecontents.ThisismerelyavaguesuggestiontoasolutiontosomeoftheexercisesposedinthebookIntroductiontoalgo-rithmsbyCormen,LeisersonandRivest.Itisverylikelythattherearemanyerrorsandthatthesolutionsarewrong.Ifyouhavefoundanerror,haveabettersolutionorwishtocontributeinsomeconstructivewaypleasesendamessagetobeetle@it.dk.Itisimportantthatyoutryhardtosolvetheexercisesonyourown.Usethisdocumentonlyasalastresortortocheckifyourinstructorgotitallwrong.Pleasenotethatthedocumentisunderconstructionandisupdatedonlysporadically.Havefunwithyouralgorithms.Bestregards,PhilipBille课后答案网www.hackshp.cnLastupdate:December9,2002若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn1:2-2Insertionsortbeatsmergesortwhen8n2<64nlgn,)n<8lgn,)2n=8keytoA[i]s.Algorithm2SELECTION-SORT(课后答案网A)Input:A=ha1;a2;:::aniOutput:sortedA.fori1ton-1dojFIND-MIN(A;i;n)A[j]$A[i]endforwww.hackshp.cnAsaloopinvariantwechoosethatA[1;:::;i-1]aresortedandallotherelementsaregreaterthanthese.Weonlyneedtoiterateton-1sinceaccordingtotheinvariantthenthelementwillthenthelargest.ThencallsofFIND-MINgivesthefollowingboundonthetimecomplexity:!Xni=(n2)i=1Thisholdsforboththebest-andworst-caserunningtime.2:2-3Giventhateachelementisequallylikelytobetheonesearchedforandtheelementsearchedforispresentinthearray,alinearsearchwillontheaveragehavetosearchthroughhalftheelements.Thisisbecausehalfthetimethewantedelementwillbeinthersthalfandhalfthetimeitwillbeinthesecondhalf.Boththeworst-caseandaverage-caseofLINEAR-SEARCHis(n).3若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn2:2-4Onecanmodifyanalgorithmtohaveabest-caserunningtimebyspecializingittohandleabest-caseinputefciently.2:3-5Arecursiveversionofbinarysearchonanarray.Clearly,theworst-caserunningtimeis(lgn).Algorithm3BINARY-SEARCH(A;v;p;r)Input:AsortedarrayAandavaluev.Output:Anindexisuchthatv=A[i]ornil.ifp>randv6=A[p]thenreturnnilendifjA[b(r-p)=2c]ifv=A[j]thenreturnjelseifv0andBINARY-Swww.hackshp.cnEARCH(A;A[i]-x;1;n)thenreturntrueendifendforreturnfalseClearly,thisalgorithmdoesthejob.(Itisassumedthatnilcannotbetrueintheif-statement.)4若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn3:1-1Letf(n),g(n)beasymptoticallynonnegative.Showthatmax(f(n);g(n))=(f(n)+g(n)).Thismeansthatthereexistspositiveconstantsc1,c2andn0suchthat,06c1(f(n)+g(n))6max(f(n);g(n))6c2(f(n)+g(n))foralln>n0.Selectingc2=1clearlyshowsthethirdinequalitysincethemaximummustbesmallerthanthesum.c1shouldbeselectedas1=2sincethemaximumisalwaysgreaterthantheweightedaverageoff(n)andg(n).Notethesignicanceofthe“asymptoticallynonnegative”assumption.Therstinequalitycouldnotbesatisedotherwise.3:1-42n+1=O(2n)since2n+1=2
2n62
2n!However22nisnotO(2n):bydenitionwehave22n=(2n)2whichfornoconstantcasymptoticallymaybelessthanorequaltoc
2n.3-4Letf(n)andg(n)beasymptoticallypositivefunctions.a.No,f(n)=O(g(n))doesnotimplyg(n)=O(f(n)).Clearly,n=O(n2)butn26=O(n).b.No,f(n)+g(n)isnot(min(f(n);g(n))).Asanexamplenoticethatn+16=(min(n;1))=(1).c.Yes,iff(n)=O(g(n))thenlg(f(n))=O(lg(g(n)))providedthatf(n)>1andlg(g(n))>1aregreaterthanorequal1.Wehavethat:f(n)6cg课后答案网(n))lgf(n)6lg(cg(n))=lgc+lgg(n)Toshowthatthisissmallerthanblgg(n)forsomeconstantbwesetlgc+lgg(n)=blgg(n).Dividingbylgg(n)yields:lg(c)+lgg(n)lgcb==+16lgc+1lgg(n)lgg(n)Thelastinequalityholdssincelgwww.hackshp.cng(n)>1.d.No,f(n)=O(g(n))doesnotimply2f(n)=O(2g(n)).Iff(n)=2nandg(n)=nwehavethat2n62
nbutnot22n6c2nforanyconstantcbyexercise3:1-4.e.Yesandno,iff(n)<1forlargenthenf(n)21andthestatementistriviallytrue.f.Yes,f(n)=O(g(n))impliesg(n)=(f(n)).Wehavef(n)6cg(n)forpositivecandthus1=c
f(n)6g(n).pg.No,clearly2n6c2n=2=c2nforanyconstantcifnissufcientlylarge.h.Byasmallmodicationtoexercise3:1-1wehavethatf(n)+o(f(n))=(max(f(n);o(f(n))))=(f(n)).5若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn4:1-1ShowthatT(n)=T(dn=2e)+1isO(lgn).UsingsubstitutionwewanttoprovethatT(n)6clg(n-b).Assumethisholdsfordn=2e.Wehave:T(n)6clg(dn=2-be)+12andc>1.4:2-1DetermineanupperboundonT(n)=3T(bn=2c)+nusingarecursiontree.Wehavethateachnodeofdepthiisboundedbyn=2iandthereforethecontributionofeachlevelisatmost(3=2)in.Thelastlevelofdepthlgncontributes(3lgn)=(nlg3).Summingupweobtain:T(n)=3T(bn=2c)+n6n+(3=2)n+(3=2)2n+


+(3=2)lgn-1n+(nlg3)lgXn-1ilg3=n(3=2)+(n)i=0(3=2)lgn-1=n
+(nlg3)(3=2)-1=2(n(课后答案网3=2)lgn-n)+(nlg3)3lgn=2n-2n+(nlg3)2lgn=2
3lgn-2n+(nlg3)=2nlg3-2n+(nlg3)=(nlg3)Wecanprovethisbysubstitutionbyassummingthatwww.hackshp.cnT(bn=2c)6cbn=2clg3-cbn=2c.Weobtain:T(n)=3T(bn=2c)+n63cbn=2clg3-cbn=2c+n3cnlg3cn6-+n2lg32lg3cn6cn-+n26cnlg3Wherethelastinequalityholdsforc>2.6若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn4:2-3DrawtherecursiontreeofT(n)=4T(bn=2c)+cn.Theheightofthetreeislgn,theoutdegreeofeachnodewillbe4andthecontributionoftheithlevelwillbe4ibcn=2ic.Thelastlevelcontributes4lgn(1)=(n2).Hencewehaveaboundonthesumgivenby:T(n)=4T(bn=2c)+cnlgXn-1=4i
bcn=2ic+(n2)i=0lgXn-164i
cn=2i+(n2)i=0lgXn-1=cn2i+(n2)+(n2)i=02lgn-12=cn
+(n)2-1=(n2)Usingthesubstitutionmethodwecanverifythisbound.Assumethefollowingcleverinductionhypothesis.LetT(bn=2c)6cbn=2c2-cbn=2c.Wehave:T(n)=4T(bn=2c)+cn264(cbn=2c-cbn=2c)+cn<4c(n=2)2-4cn=2+cn=cn2-2cn+cn课后答案网=cn2-cn4:3-1Usethemastermethodtondboundsforthefollowingrecursions.Notethata=4;b=4andnlog24=n2T(n)=4T(n=2)+n.Sincewww.hackshp.cnn=O(n2-)case1appliesandwegetT(n)=(n2).T(n)=4T(n=2)+n2.Sincen2=(n2)wehaveT(n)=(n2lgn).T(n)=4T(n=2)+n3.Sincen3=(n2+)and4(n=2)3=1=2n36cn3forsomec<1wehavethatT(n)=(n3).7若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn6:1-1Thereisamost2h+1-1verticesinacompletebinarytreeofheighth.Sincethelowerlevelneednotbelledwemayonlyhave2hvertices.6:1-2Sincetheheightofann-elementheapmustsatisfythat2h6n62h+1-1<2h+1.wehaveh6lgn1andA[PARENT(i)].7:2-2IftheelementsinAarethesame,thenbyexercise7:1-2thereturnedelementfromeachcalltoPARTITION(A;p;r)isr-1thusyieldingtheworst-casepartitioning.Thetotalrunningtimeiseasilyseentobe(n2).7:2-3IftheelementsinAaredistinctandsortedindecreasingorderthen,asinthepreviousexercise,wehaveworst-casepartitioning.Therunningtimeisagain(n2).7-4a.Clearly,theQUICKSORT"doesexactlythesameastheoriginalQ课后答案网UICKSORTandthereforeworkscorrectly.b.Worst-casepartitioningcancausethestackdepthofQUICKSORT"tobe(n).c.IfwerecursivelycallQUICKSORT"onthesmallestsubarrayreturnedbyPARTITIONwewillavoidtheproblemandretainawww.hackshp.cnO(lgn)boundonthestackdepth.11若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn8:2-3COUNTING-SORTwillworkcorrectlynomatterwhatorderAisprocessedin,howeveritisnotstable.Themodicationtotheforloopactuallycausesnumberswiththesamevaluetoappearinreverseorderintheoutput.Thiscanseenbyrunningafewexamples.8:2-4Givennintegersfrom1tokshowhowtocountthenumberofelementsfromatobinO(1)timewithO(n+k)preprocessingtime.AsshowninCOUNTING-SORTwecanproduceanarrayCsuchthatC[i]containsthenumberofelementslessthanorequaltoi.Clearly,C[b]-C[a]givesthedesiredanswer.8:3-4Showhowtosortnintegersintherange0ton2-1inO(n)time.Noticethatthenumberofdigitsusedtorepresentann2differentnumbersinak-arynumbersystemisd=log(n2).Thuskconsideringthen2numbersasradixnnumbersgivesusthat:2d=logn(n)=2logn(n)=2Radixsortwillthenhavearunningtimeof(d(n+k)=(2(n+n))=(n).8:4-2Showhotoimprovetheworst-caserunningtimeofbucketsorttoO(nlgn).SimplyreplacetheinsertionsortusedtosortthelinkedlistswithsomeworstcaseO(nlgn)sortingalgorithm,e.g.mergesort.Thesortingthentakestime:nX-1nX-1nX-1O(nilgni)6O(nilgn)=O(lgn)O(ni)=O(nlgn)i=0课后答案网i=0i=0ThetotaltimeofbucketsortisthusO(nlgn).www.hackshp.cn12若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn9:1-1Showhowtondthethesecondsmallestelementofnelementsusingn+dlgne-2comparisons.Tondthesmallestelementconstructatournamentasfollows:Compareallthenumbersinpairs.Onlythesmallestnumberofeachpairispotentiallythesmallestofallsotheproblemisreducedtosizedn=2e.Continuinginthisfashionuntilthereisonlyoneleftclearlysolvestheproblem.Exactlyn-1comparisonsareneededsincethetournamentcanbedrawnasann-leafbinarytreewhichhasn-1internalnodes(showbyinductiononn).Eachofthesenodescorrespondtoacomparison.Wecanusethisbinarytreetoalsolocatethesecondsmallestnumber.Thepathfromtheroottothesmallestelement(ofheightdlgne)mustcontainthesecondsmallestelement.Conductingatournamentamongtheseusesdlgne-1comparisons.Thetotalnumberofcomparisonsare:n-1+dlgne-1=n+dlgne-2.9:3-1Considertheanalysisofthealgorithmforgroupsofk.Thenumberofelementslessthan(or
greaterthan)themedianofthemediansxwillbeatleastdke1dne-2>n-k.Hence,in22k
4theworst-caseSn3nELECTwillbecalledrecursivelyonatmostn--k=+kelements.The44recurrenceisT(n)6T(dn=ke)+T(3n=4+k)+O(n)Solvingbysubstitutionweobtainaboundforwhichkthealgorithmwillbelinear.AssumeT(n)6cnforallsmallern.Wehave:lmn3nT(n)6c+c+k+O(n)k4n3cn6c(+1)++ck+O(n)kk课后答案网cn3cn6++c(k+1)+O(n)kk13=cn++c(k+1)+O(n)k46cnWherethelastequationonlyholdsfork>4.Thus,wehaveshownthatthealgorithmwillcomputeinlineartimeforanygroupsizeofwww.hackshp.cn4ormore.Infact,thealgorithmis(nlgn)fork=3.Thiscanbeshownbyexample.9:3-3QuicksortcanbemadetoruninO(nlgn)timeworst-casebynoticingthatwecanperform“perfectpartitioning”:Simplyusethelineartimeselecttondthemedianandperformthepartitioningaroundit.Thisclearlyachievesthebound.9:3-5AssumethatwehavearoutineMEDIANthatcomputesthemedianofanarrayinO(n)time.ShowhowtondanarbitraryorderstatisticinO(n).13若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnAlgorithm6SELECT(A;i)Input:ArrayAandintegeri.Output:TheithlargestelementofA.xMEDIAN(A).PartitionAaroundxifi6b(n+1)=2cthenRecursivelyndtheithinthersthalfelseRecursivelynd(i-b(n+1)=2c)thinthesecondhalfendifClearly,thisalgorithmdoesthejob.课后答案网www.hackshp.cn14若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn10:1-2Twostackscanbeimplementedinasinglearraywithoutoverowsoccuringiftheygrowfromeachendandtowardsthemiddle.10:1-6Implementaqueueusingtwostacks.DenotethetwostacksS1andS2.TheENQUEUEoperationissimplyimplementedasapushonS1.ThedequeueoperationisimplementedasapoponS2.IfS2isempty,successivelypopS1andpushS2.ThereversestheorderofS1ontoS2.Theworst-caserunningtimeisO(n)buttheamortizedcomplexityisO(1)sinceeachelementisonlymovedaconstantnumberoftimes.10:2-1No,INSERTandDELETEcannotbeimplementedinO(1)onalinkedlist.Ascanthroughthelistisrequiredforbothoperations.INSERTmustcheckthatnoduplicatesexist.10:2-2Astackcanbeimplementedusingalinkedlistinthefollowingway:PUSHisdonebyappendinganewelementtothefrontofthelistandPOPisdonebydeletingtherstelementofthelist.课后答案网www.hackshp.cn15若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn11:1-1Findthemaximumelementinadirect-addresstableToflengthm.Intheworst-casesearchingtheentiretableisneeded.ThustheproceduremusttakeO(m)time.11:1-2Describehowtoimplementadynamicsetwithabitvector.Theelementshavenosatellitedata.Simplysettheithbitto1iftheielementisinsertedandsetthebitto0ifitisdeleted.11:2-3Considerkeepingthechaininglistsinsortedorder.Searchingwillstilltaketimeproportionaltothelengthofthelistandthereforetherunningtimesarethesame.Theonlydifferenceistheinsertionswhichnowalsotaketimeproportionaltothelengthofthelist.11:3-1Searchingalistoflengthnwhereeachelementcontainsalongkeykandasmallhashvalueh(k)canbeoptimizedinthefollowingway:Comparingthekeysshouldbedonerstcomparingthehashvaluesandifsuccesfullthencomparingthekeys.课后答案网www.hackshp.cn16若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn12:1-2Thedenitionsclearlydiffer.IftheheappropertyallowedtheelementstobeprintedinsortedorderintimeO(n)wewouldhaveanO(n)timecomparisonsortingalgorithmsinceBUILD-HEAPtakesO(n)time.This,however,isimpossiblesinceweknow(nlgn)isalowerboundforsorting.12:1-5Showthatconstructingabinarytreefromanarbitrarylistinacomparisonbasedmodelmusttakeat(nlgn)worst-case.ThevalueofthenodesinthetreecanbeprintedinsortedorderinO(n)time.Theexistanceofanalgorithmforconstructingabinarytreeino(nlgn)timewouldthuscontradictthelowerboundforsorting.12:2-5Showthatifanodeinabinarysearchtreehastwochildrenthenitssuccessorhasnoleftchildanditspredecessorhasnorightchild.Letvbeanodewithtwochildren.Thenodesthatimmidiatelyprecedevmustbeintheleftsubtreeandthenodesthatimmidiatelyfollowvmustbeintherightsubtree.Thusthesuccessorsmustbeintherightsubtreeandswillbethenextnodefromvinaninorderwalk.Thereforescannothavealeftchildsincethischildsincethiswouldcomebeforesintheinorderwalk.Similarly,thepredecessorhasnorightchild.12:2-7Showthattheinorderwalkofan-nodebinarysearchtreeimplementedwithacalltoTREE-MINIMUNfollowedbyn-1callstoTREE-SUCCESSORtakesO(n)time.Considerthealgorithmatanygivennodeduringthealgorithm.Thealgorithmwillnevergototheleftsubtreeandgoingupwillthereforecauseittoneverreturntothissamenode.Hencethealgorithmonlytraverseseachedgeatmosttwiceandthereforetherunningtimeis课后答案网O(n).12:2-9Ifxisaleafnode,thenifp[x]=yandxistheleftchildthenrunningTREE-SUCCESSORyieldsy.SimilarlyifxistherightchildthenrunningTREE-PREDECESSORyieldsy.12:3-1Algorithm7TREE-INSERT(z;kwww.hackshp.cn)Input:Anodezandvaluek.Output:Thebinarytreewithkinserted.ifz=nilthenkey[z]kleft[z]nilright[z]nilelseifkf2[j-1]+t2;j-1+a1;jf2[j-1]+a2;j>f1[j-1]+t1;j-1+a2;jBycancellingoutthea"sweobtainacontradictionandthestatementfollows.15:2-1Solvethematrixchainorderforaspecicproblem.ThiscanbedonebycomputingMATRIX-CHAIN-ORDER(p)wherep=h5;10;3;12;5;50;6iorsimplyusingtheequation:0ifi=jm[i;j]=mini6k<0ifi=0orj=0c[i;j]=c[i-1;j-1]+1ifi;j>0andxi=yj>:max(c[i;j-1];c[i-1;j])ifi;j>0andxi6=yj22若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnAlgorithm8LCS-LENGTH(X;Y)Input:ThetwostringsXandY.Output:ThelongestcommonsubstringofXandY.mlength[X]nlength[Y]fori1tomdoforj1tondoc[i;j]-1endforendforreturnLOOKUP-LENGTH(X;Y;m;n)Algorithm9LOOKUP-LENGTH(X;Y;i;j)ifc[i;j]>-1thenreturnc[i;j]endififi=0orj=0thenc[i;j]0elseifxi=yithenc[i;j]LOOKUP-LENGTH(X;Y;i-1;j-1)+1elsec[i;j]maxfLOOKUP-LENGTH(X;Y;i;j-1);LOOKUP-LENGTH(X;Y;i-1;j)gendifendifreturnc[i;j]15:4-5课后答案网GivenasequenceX=hx1;x2;:::;xniwewishtondthelongestmonotonicallyincreasingsubse-quence.FirstsorttheelementsofXandcreateanothersequenceX0.FindingthelongestcommonsubsequenceofXandX0yieldsthelongestmonotonicallyincreasingsubsequenceofX.Therun-ningtimeisO(n2)sincesortingcanbedoneinO(nlgn)andthecalltoLCS-LENGTHisO(n2).15-1www.hackshp.cnComputethebitonictourofnpointsintheplane.Sortthepointsandenumeratefromlefttoright:1;:::n.Foranyi,16i6n,andforanyk,16k6n,letB[i;k]denotetheminimunlengthoftwodisjointbitonicpaths,onefrom1toi,theotherfrom1tok.Wheni=kwehaveaminumincostbitonictourthroughtherstipoints.Wheni=k=nwehaveaminimumcostbitonictourthroughallnpoints.Notethatweneedonlyconsiderdisjointpathssinceanynon-disjointpathscannotbeoptimalduetothetriangleinequality.WecannowdescribehowtocomputeBusingdynamicprogramming.FirstdeneB[0;0]=0.WewilldeterminethevalueofB[i+1;k]forsomexediandforallk,16k6i+1byusingB-valuesfromtherstirowsandicolumnsofB.Case1:k<0ifi=0orw=0c[i;w]=c[i-1;w]ifwi>w>:max(vi+c[i-1;w-wi];c[i-1;w])ifi>0andw>wi25若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnNoticethatthelastcasedetermineswhetherornottheithelementshouldbeincludedinanoptimalsolution.Wecanusethisrecursiontocreateastraightforwarddynamicprogrammingalgorithm:Algorithm10DYNAMIC-0-1-KNAPSACK(v;w;n;W)Input:Twosequencesv=hv1;:::;vniandw=hw1;:::;wnithenumberofitemsnandthemaximumweightW.Output:Theoptimalvalueoftheknapsack.forw0toWdoc[0;w]0endforfori1tondoc[i;0]0forw1toWdoifwi6wthenifvi+c[i-1;w-wi]>c[i-1;w]thenc[i;w]vi+c[i-1;w-wi]elsec[i;w]c[i-1;w]endifelsec[i;w]c[i-1;w]endifendforendforreturnc[n;W]Fortheanalysisnoticethatthereare(n+1)
(W+1)=(nW)entriesinthetableceachtaking(1)tollout.Thetotalrunningtimeisthus课后答案网(nW).16:2-5Describeanalgorithmtondthesmallestunit-lengthset,thatcontainsallofthepointsfx1;:::xngontherealline.Considerthefollowingverysimplealgorithm:Sortthepointsobtaininganewarrayfy1;:::yng.Therstintervalisgivenby[y1;y1+1].Ifyiistheleftmostpointnotcontainedinanyexistingintervalthenextintervalis[yi;yi+1]andsoon.Thisgreedyalgorithmdoesthejobsincetherightmostelementofthesetmustbecontainedinanintervalandwecandonobetterthantheintervalwww.hackshp.cn[y1;y1+1].Additionally,anysubproblemtotheoptimalsolutionmustbeoptimal.Thisiseasilyseenbyconsideringtheproblemforthepointsgreaterthany1+1andarguinginductively.16:3-8Showthatwecannotexpecttocompressaleofrandomlychosenbits.NoticethatthenumberofpossiblesourcelesSusingnbitsandcompressedlesEusingnbitsis2n+1-1.Sinceanycompressionalgorithmmustassigneachelements2Stoadistinctelemente2Ethealgorithmcannothopetoactuallycompressthesourcele.26若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn17:1-2IfaDECREMENToperationisaddedwecaneasilyforcethecountertochangeallbitsperoperationbycallingDECREMENTandINCREMENTon2k-1.Thisgivesatotalrunningtimeof(nk).17:1-3Consideradatastructurewherenoperationsareperformed.Theithoperationcostsiifiisanexactpoweroftwoand1otherwise.Determinetheamortizedcostofeachoperationusingtheaggregatemethod.Letcidenotethecostoftheithoperation.Summingthecostofthenoperationsyield:XnbXlgncc6n+2j=n+2blgnc+1-10areintegersandjischosenaslargeaspossible.Letthepotentialfunctionbegivenby(Di)=2k.Clearly,thisfunctionsatiestherequirements.Therearetwocasestoconsiderfortheithoperation:Ifk=0thentheactualcostiswww.hackshp.cniandtheamortizedcostisgivenby:c^i=ci+(Di)-(Di-1)=i+0-2
(2j-1-2j-1)=i-(2
(2j-2j-1)-2)=i-(2j
(2-1)-2)=i-i+2=2Otherwisetheactualcostwillbe1andwendthatc^i=ci+(Di)-(Di-1)=1+2k-2(k-1)=327若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn17:4-3ShowthattheamortizedcostofTABLE-DELETEwheni-1>1=2isboundedabovebyaconstant.Noticethattheithoperationcannotcausethetabletocontractsincecontractonlyoccurswhenai<1=4.Weneedtoconsidercasesfortheloadfactori.Forbothcasesnumi=numi-1-1andsizei=sizei-1.Assumei>1=2.c^i=ci+i-i-1=1+(2
numi-sizei)-(2
numi-1-sizei-1)=1+(2
numi-sizei)-(2
(numi+1)-sizei)=-1Thenconsideri<1=2.c^i=ci+i-i-1=1+(2
numi-sizei)-(sizei-1=2-numi-1)=3
numi-3=2
sizei+2=3i
sizei-3=2
sizei+2<3=2
sizei-3=2
sizei+2=217-2Constructadynamicbinarysearchdatastructure.Letk=dlg(n+1)e.MaintainksortedarraysA;A;:::AsuchthatthelengthofAis2i.01k-1ia.ASEARCHoperationcanbeimplementedbyusingabinarysearchonallthearrays.The课后答案网worst-casecomplexityofthismustbe:XkXkk(k+1)lg(2i)=i==O(k2)=O(lg2n)2i=0i=0b.Theworst-caseoftheINSERToperationoccurswhenallthesortedarrayhavetobemergedintoanewarray.Thatis,whenwww.hackshp.cnnincreasesfrom2k-1to2kforsomek.Usingk-waymergingasinexercise6:5-8withatotalofnelementsyieldsarunningtimeofO(nlgk)=O(nlglgn).Fromtheanalysisofincrementingabinarycounterwehavethattheithbitisippedatotalofbn=2ictimesinnINCREMENToperations.ThecorrespondancetothisproblemisthateverytimetheithbitinnisippedweneedtomergethelistsA;A;:::AusingtimeO(2ilgi).Theii-10totalrunningtimeisthus:bXlgncXlgnYlgnbn=2ic2ilginFIND-SEToperationsonthenodeofgreatestdepth.Settingm=n+n-1+kgivesthedesiredrunningtimeof(n+mlgn)=(mlgn).21:4-4Showthattherunningtimeofthedisjoint-setforestwithunionbyrankonlyisO(mlgn).Firstnoticethattherankofanodeisatmosttheheightofthesubtreerootedatthatnode.Byexercise21:4-2everynodehasrankatmostblgncandthereforetheheighthofanysubtreeisatmostblgnc.Clearly,eachcalltoFIND-SET(andthusUNION)takesatmostO(h)=O(lgn)time.21-1Consideranoff-lineminimumproblem,wherewearegivennINSERTandmEXTRACT-MINcalls.Theelementsareallfromthesetf1;:::;ng.Wearerequiredtoreturnanarrayextracted[1:::m]suchthatextracted[i]isthereturnvalueoftheithEXTRACT-MINcall.31若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cna.Considerthefollowingsequence:4;8;E;3;E;9;2;6;E;E;E;1;7;E;5Thecorrespondingextractedarrayis:4;3;2;6;8;1b.Runninganexampleconvincesoneofthecorrectnessofthealgorithm.c.UsingUNION-FINDtechniqueswecanconstructanefcientimplementationofthealgorithm.Initiallycreatedisjoint-setsforthesubsequencesI1;:::Im+1andplacetherepresentativeofeachsetinalinkedlistinsortedorder.Additionally,labeleachrepresentativewithitssubsequencenumber.Weproceedasfollows:Line2isimplementedbyaFIND-SEToperationoniyieldingtherepresentativeofsubse-quenceIjlabeledj.Inline5thenextsetcanfoundfromtherootasthenextsetinthelinkedlist.Line6isimplementedwithaUNIONoperationandadeletioninthelinkedlist.TheoverallrunningtimeisseentobeO(m(n)).21-2Considerthedepth-determinationproblemwherewemaintainaforestF=fTigofrootedtreesandsupporttheMAKE-TREE,FIND-DEPTHandGraftoperations.a.Showthatmoperationsusingasimpledisjointtreestakes(m2).Createsinglenodetreesv;:::;vwithM10kAKE-TREE,wherek=3m.Thenusek-1GRAFToperationstolinkthemintoasinglepathv0;:::;vkwithroot课后答案网vk.Finally,callFIND-DEPTH(v0)ktimes.Thesem+1operationstakes(k+1)+k+k2<(1m)2=(m2)time.3b.implementMAKE-DEPTH(v)bycreatingadisjoint-setSwiththenodevansettingd[v]0.c.ConsiderFIND-DEPTH(v)andletv=v0;:::;vkbethepathtotheroot.ForeachvicomputePk-1d[vi]i=jd[vj].ThenusetheordinaryFwww.hackshp.cnIND-SETwithpathcompression.d.ShowhowtoimplementGRAFT(r;v).WewillusetheordinaryUNIONoperationandupdatethepseudodistancesappropriately.Therearetwocasestoconsiderasshowningure5.32若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnwrvwvr(b)rw(a)v(c)Figure5:(a)ThetreebeforeGRAFT(r;v).ThecasesontherightshowthetreeafterGRAFT(r;v)andthetwocases:(b)rank(r)6rank(w)(c)rank(r)>rank(w)Letthepathfromvtowbev=v0;:::;vk=w.ThedepthofanynodeinthesubtreerootedPk课后答案网atrisincreasedbyi=0d[vi]whilethedepthsoftheothernodesisunaffected.Forcase(b)thisPPk-1kcanbeachievedbysettingd[r]d[r]+i=0d[vi].Forcase(c)setd[r]d[r]+i=0d[vi]andthensetd[w]d[w]-d[r].BothcasesareeasilyhandledwithoutextracosttotheUNIONoperation.e.Clearly,thetotalcostisOwww.hackshp.cn(m(n))asinUNION-FINDalgorithm.33若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn22:1-1Giventheadjacency-listrepresentationofagraphtheoutandin-degreeofeverynodecaneasilybecomputedinO(E+V)time.22:1-3ThetransposeofadirectedgraphGTcanbecomputedasfollows:Ifthegraphisrepresentedbyanadjacency-matrixAsimplycomputethetransposeofthematrixATintimeO(V2).Ifthegraphisrepresentedbyanadjacency-listasinglescanthroughthislistissufcienttoconstructthetranspose.ThetimeusedisO(E+V).22:1-5Thesquareofagraphcanbecomputedasfollows:Ifthegraphisrepresentedasanadjacency-matrixAsimplycomputetheproductA2wheremultiplicationandadditionisexchangedbyand"ingandor"ing.UsingthetrivialalgorithmyieldsarunningtimeofO(n3).UsingStrassensalgorithmimprovestheboundtoO(nlg7)=O(n2;81).Ifweareusingtheadjacency-listrepresentationwecansimplyappendlistseliminatingdupli-cates.Assumingthelistsaresortedwecanproceedasfollows:ForeachnodevinsomelistreplacethevwithAdj[v]andmergethisintothelist.EachlistcanbeatmostVlongandthereforeeachmergeoperationtakesatmostO(V)time.ThusthetotalrunningtimeisO((E+V)V)=O(E+V2).22:1-6Noticethatifedgeispresentbetweenverticesvanduthenvcannotbeasinkandiftheedgeisnotpresentthenucannotbeasink.Searchingtheadjancency-listinalinearfashionenablesustoexcludeonevertexatatime.22:2-3Ifbreadth-rst-searchisrunonagraphrepresentedbyanadjacency-matrixthetimeusedscanning课后答案网forneighbourcanincreasetoO(V2)yieldingatotalrunningtimeofO(V2+V).22:2-6Theproblemisthesameasdeterminingifagraphisbipartite.Fromgraphtheoryweknowthatthisissoifandonlyifeverycyclehasevenlength.Usingthisfactwecansimplymodifybreadth-rst-searchtocomparethecurrentdistancewiththedistanceofanencounteredgraywww.hackshp.cnvertex.Additionally,everyothervertexwithinacyclewillbeinoneofthevertexsetsandwecanthereforeeasilyconstructthepartition.TherunningtimeisO(E+V).22:2-7Thediameterofatreecancomputedinabottom-upfashionusingarecursivesolution.Ifxisanodewithadepthd(x)inthetreethenthediameterD(x)mustbe:maxfmaxifD(x:childi)g;maxijfd(x:childi)+d(x:childj)g+2g;ifxisaninternalnodeD(x)=0ifxisaleafSincethediametermustbeinoneofthesubtreesorpassthroughtherootandthelongestpathfromtherootmustbethedepth.Thedepthcaneasilybecomputedatthesametime.Usingdynamicprogrammingweobtainalinearsolution.34若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnActually,theproblemcanalsobesolvedbycomputingthelongestshortestpathfromanarbi-trarynode.Thenodefarthestawaywillbetheendpointofadiameterandwecanthuscomputethelongestshortestpathfromthisnodetoobtainthediameter.Seerelevantlitteratureforaproofofthis.22:3-1Inthefollowingtableweindicateiftherecanbeanedge(i;j)withthespeciedcoloursduringadepth-rstsearch.Iftheentryinthetableispresentwealsoindicatewhichtypetheedgemightbe:Tree,ForwardorBackedge.Forthedirectedcase:(i;j)WHITEGRAYBLACKWHITETBFCBCCGRAYTFTFBTFCBLACKBTFBCFortheundirectedcase:(i;j)WHITEGRAYBLACKWHITETBTBGRAYTBTBTBBLACKTBTB22:4-3ShowhowtodetermineifanundirectedgraphcontainsacycleinO(V)time.Adepth-rstsearchonanundirectedgraphyieldsonlytreeedgesandbackedgesasshowninthetableinexercise22:3-1.Observethatanundirectedgraphisacyclicifandonlyifadepth-rstsearchyieldsnobackedges.Wenowperformadepth-rstsearchandifwediscoverabackedgethenthegraphmustbe课后答案网acyclic.ThetimetakenisO(V)sinceifwediscovermorethanVdistinctedgesthegraphmustbeacyclicandwewillhaveseenabackedge.22-3a.IfGhasanEulertouranypathgoing“into”avertexmust“leave”it.Conversely,iftheinandout-degreesofanyvertexisthesameanywecanconstructapaththatvisitsalledges.www.hackshp.cnb.SincetheedgesofanyEulergraphcanbesplitintodisjointcycles,wecansimplyndthesecyclesand“merge”themintoanEulertour.NotesfortheexercisesThankstoStephenAlstrupforprovidingasolutiontoexercise22:2-7.35若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn23:1-1Showthataminimum-weightedge(u;v)belongstosomeminimumspanningtree.If(u;v)isaminimumweightedgethenitwillbesafeforanycutwithuandvonseparatesides.Thestatementfollows.23:1-3Showthatifanedge(u;v)belongstosomeminimumspanningtreeitisalightedgeofsomecut.Consideracutwithuandvonseparatesides.If(u;v)isnotalightedgethenclearlythegraphwouldnotbeaminimumspanningtree.23:1-5Showthatifebethemaximum-weightedgeonsomecycleinG=(V;E)theneisnotpartofaminimumspanningtreeofG.Ifewasintheminimumspanningtreethenreplacingitwithanyotheredgeonthecyclewouldyielda“better”minimumspanningtree.23:2-1GivenaminimumspanningtreeTwewishtosorttheedgesinKruskal"salgorithmsuchthatitproducesT.ForeachedgeeinTsimplymakesurethatitpreceedsanyotheredgenotinTwithweightw(e).23:2-3ConsidertherunningtimesofPrimsalgorithmimplementedwitheitherabinaryheaporaFibon-nacciheap.SupposejEj=(V)thentherunningtimesare:Binary:O(ElgV)=O(VlgV)Fibonnacci:O(E+VlgV课后答案网)=O(VlgV)IfjEj=(V2)then:Binary:O(ElgV)=O(V2lgV)Fibonnacci:O(E+VlgV)=O(V2)TheFibonnacciheapbeatsthebinaryheapimplementationofPrimsalgorithmwhenjEj=!(V)sinceO(E+VlgV)=www.hackshp.cnO(VlgV)tforjEj=O(VlgV)butO(ElgV)=!(VlgV)forjEj=!(V).ForjEj=!(VlgV)theFibonnacciversionclearlyhasabetterrunningtimethantheordinaryversion.23:2-4AssumethatE>V-1.TherunningtimeofKruskalsalgorithmcanbeanalysedasfollows:Sortingtheedges:O(ElgE)time.O(E)operationsonadisjoint-setforesttakingO(E(V)).ThesortdominatesandhencethetotaltimeisO(ElgE).Sortingusingcountingsortwhentheedgesfallintherange1;:::;jVjyieldsO(V+E)=O(E)timesorting.ThetotaltimeisthenO(E(V)).Iftheedgesfallintherange1;:::;WforanyconstantWwestillneedtouse(E)timeforsortingandthetotalrunningtimecannotbeimprovedfurther.36若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn23:2-5TherunningtimeofPrimsalgorithmiscomposed:O(V)initialization.O(V
timeforEXTRACT-MIN).O(E
timeforDECREASE-KEY).Iftheedgesareintherange1;:::;jVjtheVanEmdeBoaspriorityqueuecanspeedupEXTRACT-MINandDECREASE-KEYtoO(lglgV)thusyieldingatotalrunningtimeofO(VlglgV+ElglgV)=O(ElglgV).Iftheedgesareintherangefrom1toWwecanimplementthequeueasanarray[1:::W+1]wheretheithslotholdsadoublylinkedlistoftheedgeswithweighti.TheW+1stslotcontains1.EXTRACT-MINnowrunsinO(W)=O(1)timesincewecansimplyscanfortherstnonemptyslotandreturntherstelementofthatlist.DECREASE-KEYrunsinO(1)timeaswellsinceitcanbeimplementedbymovinganelementfromoneslottoanother.23-1LetG=(V;E)beanundirectedgraphwithnonnegativedistinctedgeweights.Wewillusethefollowingpropertyofminimumspanningtrees:IfuandvarenotconnectedinsomeminimumspanningtreeTthentheweightof(u;v)mustbegreaterorequalthantheweightofanyedgeonthepathfromutovinT.Otherwisewecouldreplace(u;v)withaheavieredgeonthepathtoobtainalighterminimumspanningtree.a.Showthattheminimumspanningtreeisuniquebutthesecond-bestminimumspanningtreeneednotbeunique.AssumeTandT0aredistinctminimumspanningtrees.Thensomeedge(u;v)isinTbutnotinT0.SincealledgeweightsaredistincttheedgesontheuniquepathfromutovinT0mustthenbestrictlylighterthan(u;v)contradictingthefactthatTisaminimumspanningtree.Itcaneasilybeseenbyexamplethatthesecond-bestminimumspanningtreesisnotunique.课后答案网b.Showthatasecond-bestminimumspanningtreecanbeobtainedfromtheminimumspanningtreebyreplacingasingleedgefromthetreewithanotheredgenotinthetree.LetTbeaminimunspanningtree.WewishtondatreethathasthesmallestpossibleweightthatislargerthantheweightofT.Wecaninsertanedge(u;v)62Tbyremovingsomeotheredgeontheuniquepathbetweenuandv.Bytheabovepropertysuchareplacementmustincreasetheweightofthetree.Bycarefullyconsideringthecasesitisseenthatreplacingtwoormoreedgeswillnotproduceatreebetterthanthesecondbestminimumspanningtree.www.hackshp.cnc.Letmax(u;v)betheweightoftheedgeofmaximumweightontheuniquepathbetweenuandvinaspanningtree.TocomputethisinO(V2)timeforallnodesinthetreedothefollowing:Foreachnodevperformatraversalofthetree.Inordertocomputemax(v;k)forallk2Vsimplymaintainthelargestweightencountedsofarforthepathbeinginvestigated.DoingthisyieldsalineartimealgorithmforeachnodeandwethereforeobtainatotalofO(V2)time.d.Usingtheideaofthesecondsubexerciseandtheprovidedalgorithminthethirdsubexercise,wecannowcomputeT2fromTinthefollowingway:Computemax(u;v)forallverticesinT.Computeforanyedge(u;v)notinTthedifferencew(u;v)-max(u;v).Thetwoedgesyieldingthesmallestpositivedifferenceshouldbereplaced.37若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn23-4Weconsiderthethreeproposedminimumspanningtreealgorithms.Foreachweproveordisproveit"scorrectnessandgiveanefcientimplementation.a.ThealgorithmclearlyproducesaspanningtreeT.Considertwoverticesuandvsuchthattheedge(u;v)isinGbutnotinT.Thenw(u;v)isatleastaslargeasanyweightofanedgeeonthepathfromutovsinceotherwiseewouldhavebeenremovedearlier.Byexercise23:1-5thisimpliesthatthealgorithmproducesaminimumspanningtree.ThesortontheedgescanbedoneinO(ElgE)=O(ElgV)time.Usingadepth-rstsearchtodetermineconnectivityinline5thetotalrunningtimeisO(ElgV+E(V+E))=O(E2+EV).Therunningtimecanbereducedusingresultsonthe“decrementalconnectivityproblem”.b.Thisalgorithmsimplyproducesaspanningtree,butclearlydoesnotgauranteethatthetreeisofminimumweight.Line3and4inthealgorithmcanbeimplementedusingdisjoint-setoperationsyieldingatotalrunningtimeofO(E(V)).c.ThealgorithmproducesaspanningtreeT.Observethatoncompletionanyedge(u;v)inGbutnotinTwillbeamaximumweightedgeonthepathfromutov.Againbyexercise23:1-5thealgorithmproducesaminimumspanningtree.Wecanimplementthealgorithmasfollows:Line3canbedoneinO(1)timebyappendingtheedgetotheproperadjancencylist.Line4canbedoneinO(V)timeusingadepth-rstsearchasdescribedinexercise22:4-3.SincethenumberofedgesinTisatmostO(V)line5canbedoneusingalinearsearchontheedgesinO(V)time.Line6canbedoneusingasearchontheadjancencylisttakingatmostO(V)time.TheforloopiteratesatmostO课后答案网(E)timesandthetotalrunningtimeisthusO(EV).www.hackshp.cn38若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn24:1-3Letmbethemaximumoverallpairsofverticesu;v2Voftheminimumnumberofedgesinashortestpathfromutov.Stoppingafterm+1iterationsinBELLMAN-FORDline2willproduceshortestpaths.24:2-4WecountthenumberofdirectedpathsinadirectedacyclicgraphG=(V;E)asfollows.Firstperformatopologicalsortoftheinput.Thenforallv2Vcompute,B(v)denedasfollows.1vislastintheorderB(v)=P1+B(w)otherwise(v;w)2EB(v)computesthenumberofdirectedpathsbeginningatvsinceifvislastintheordertheonlypathstartingatvistheemptyone.Otherwiseforeachnodew,(v;w)2E,(v;w)concatenatedwiththepathsfromwandtheemptypatharethepathsstartingfromv.Wethencomputethenumberofdirectedpathsaftervinthetopologicalorder.WedenotethisbyD(v)andweobtainthefollowing.XD(v)=B(v)+D(w)(v;w)2ESincethenodesofGareorderedtopologicallyB(v)andD(v)canbecomputedinlinear.ThusthetotalrunningtimeisO(E+V).24:3-3ConsiderstoppingDijkstra"salgorithmjustbeforeextractingthelastvertexvfromthepriority-queue.Theshortestpathestimateofthisvertexmusttheshortestpathsincealledgesgoingintovmusthavebeenrelaxed.Additionally,vwastobeextractedlastsoitwillhavethelargestshortestpathofallverticesandanyrelaxationfromvwillthereforenotaltershortestpathestimates.Thereforethemodiedalgorithmiscorrect.课后答案网24:3-4Considertoproblemofcomputingthemostreliablechannelbetweentwovertices.Observethatthisisequivalenttoashortestpathproblemonthegraphwithw(e)=lg(r(e))foralle2EwhichcanbesolvedusingDijkstra"salgorithm.Thereliabilityofthemostreliablepathtoanynodevcanthenbefoundas2d[v].www.hackshp.cn24:3-6ConsiderrunningDijkstra"salgorithmonagraph,wheretheweightfunctionisw:E!f1;:::W-1g.Tosolvethisefciently,implementthepriorityqueuebyanarrayAoflengthWV+1.AnynodewithshortestspathestimatediskeptinalinkedlistatA[d].A[WV+1]containsthenodeswith1asestimate.EXTRACT-MINisimplementedbysearchingfromthepreviousminimunshortestpathestimateuntilanewisfound.DECREASE-KEYsimplymovesverticesinthearray.TheEXTRACT-MINoper-ationstakesatotalofO(VW)andtheDECREASE-KEYoperationstakeO(E)timeintotal.HencetherunningtimeofthemodiedalgorithmwillbeO(VW+E).39若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn24:3-7Considertheproblemfromtheaboveexercise.NoticethateverytimeanodevisextractedbyEXTRACT-MINtherelaxationsperformedontheneighbourofvgivesshortestspathestimatesintherangefd[v];:::d[v]+W-1g.HenceaftereveryEXTRACT-MINoperationonlyWdistinctshortestpathestimatesareinthepriorityqueueatanytime.ConvertingthearrayimplementationtoabinaryheapofthepreviousexercisemustgivearunningtimeofO(V+E)lgW)sinceboththeEXTRACT-MINoperationandtheDECREASE-KEYoperationtakeO(lgW)time.IfweuseabonnacciheaptherunningtimecanbefurtherimprovedtoO(VlgW+E).24-2Weconsiderd-dimensionalboxes.a.Thenestingrelationisclearlytransitive.b.Wecandetermineifaboxnestswithinanotherbysortingthedimensionsofeachboxandcomparingthemsequentially.c.TondthelongestnestsequencewedeterminethenestingrelationsonallboxesbysortingeachinO(dlgd)timeandcomparingthenpairwiseinO(d)timeforeachoftheO(n2)pairs.Thisproducesapartialrelation(bydenitionofnesting)andthusadirectedacyclicgraphinwhichwendthelongestpathusingO(n2+n)time.ThetotalrunningtimeisthusO(dlgd+dn2+n2+n)=O(d(n2+lgd)).课后答案网www.hackshp.cn40若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn25:1-3Theidentitymatrixfor“multiplication”shouldlookastheonegivenintheexercisesince0istheidentityfor+and1istheidentityformin.25:1-8ByoverridingpreviousmatriceswecanreducethespaceusedbyFASTER-ALL-PAIRS-SHORTEST-PATHto(n2).25:1-9Thepresenceofanegative-weightcyclecanbedeterminedbylookingatthediagonalofthematrixL(n-1)computedbyanall-pairsshortest-pathalgorithm.Ifthediagonalcontainsanynegativenumbertheremustbeanegative-weightcycle.25:1-10Asinthepreviousexercisewhencandeterminethepresenceofanegative-weightcyclebylookingforanegativenumberinthediagonal.IfL(m)isthersttimeforwhichthisoccursthenclearlythenegative-weightcyclehaslengthm.WecaneitheruseSLOW-ALL-PAIRS-SHORTEST-PATHinthestraightforwardmannerorperformabinarysearchformusingFASTER-ALL-PAIRS-SHORTEST-PATH.25:2-4Asinexercise25:1-8overridingtheresultofpreviouscalculationsdoesnotalterthecorrectnessofthealgorithm.25:2-6Asinexercise25:1-10anegative-weightcyclecanbedeterminedbylookingatthediagonalof课后答案网theoutputmatrix.25:2-8WewishtocomputethetransitiveclosureofadirectedgraphG=(V;E).ConstructanewgraphG=(V;E)whereEisinitiallyempty.ForeachvertexvtraversethegraphGaddingedgesforeverynodeencounteredinEwww.hackshp.cn.ThistakesO(VE)time.25-1WeconsidertheproblemofdynamicallymaintainingthetransitiveclosureofagraphG=(V;E)representedbyabooleanmatrixB.FirstnoticethatgiventwoconnectedcomponentsC1andC2a.ForaconnectedcomponentCinGwehaveBij=1ifi;j2CC.ThusfortwoconnectedcomponentsC1andC2withnoedgesbetweenthemwecancomputeC1[C2simplybysettingBij=1ifi;j2C1[C2C1[C2.Inthematrixthiscanbedonebycomputingthebitwiseorofrowiandj,denotedbyr,inBifedgetheedge(i;j)isadded.Thekthbitinris1ifandonlyifk2C1[C2.WeseteachrowinC1[C2tor.b.LetG=(V;E)beagraphwithanevennumberofvertices.LetC1andC2betwoconnectcomponentspartitioningGsuchthatjC1j=jC2j=jV=2j.AssumetherearenoedgesbetweenC1andC2.ThenhalfofBcontainszerosbutaddinganedgebetweenC1andC2willleaveBconsistingcompletelyofzeros.Thistakes(V2)time.41若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cnc.Noticethatwhenaddinganedge(i;j)wecancheckifthataltersthetransitiveclosureinO(V)time.Iftheithandjthrowarethesametheniandjareinthesameconnectedcomponentandthereisnoneedtoupdatethematrix.ThusweneedonlyperformtheO(V2)updateistheconnectedcomponentsarealtered.ThishappensatmostV+1times.TheotherO(V2)useO(V)timeatmost.ThetotaltimeisO(V3)foranysequenceofninsertions.25-2Weconsideran-densegraphG=(V;E)wherejEj=(V1+).a.Byexercise6-2INSERTandDECREASE-KEYcanbedoneinO(logdn)timewhileEXTRACT-MINtakesO(dlogn)time.Ford=nweobtainrunningtimesof1=andn=.db.Usingdijkstra"salgorithmtherunningtimedependsonthepriorityqueueasfollows.jVj
INSERTjVj
EXTRACT-MINjEj
DECREASE-KEYWithd-aryheapsandd=(V)weobtainarunningtimeofVV+E=O(E)forconstant,0<61.c.Computesinglesourceshortestpathfromeachvertexv2Vusingthealgorithmfromsubex-erciseb.课后答案网www.hackshp.cn42若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn26:1-1Assume(u;v)62Eand(v;u)62Ethenbycapacityconstraintf(u;v)60andf(v;u)60.BySkewsymmetryf(u;v)=f(v;u)=0.26:1-6Letf1andf2beowsinaownetworkG=(V;E).Thesumf1+f2isdenedby(f1+f2)(u;v)=f1(u;v)+f2(u;v)forallu;v2V.Ofthetreeowpropertiesthefollowingaresatiedbyf1+f2:Capacityconstraint:Mayclearlybeviolated.Skewsymmetry:Wehave:(f1+f2)(u;v)=f1(u;v)+f2(u;v)=-f1(v;u)-f2(v;u)=-(f1(v;u)+f2(v;u))=-(f1+f2)(v;u)Flowconservation:Letu2V-s;tbegiven.Then:XXXX(f1+f2)(u;v)=(f1(u;v)+f2(u;v))=f1(u;v)+f2(u;v)v2Vv2Vv2Vv2V=0+0=026:2-4Provethatforanyverticesuandvandanyowandcapacityfunctionsfandcwehave:cf(u;v)+cf(v;u)=c(u;v)+c(u;v).Obvioussince:cf(u;v)+课后答案网cf(v;u)=c(u;v)-f(u;v)+c(v;u)-f(v;u)=c(u;v)+c(v;u)-f(u;v)+f(v;u)=c(u;v)+c(v;u)26:2-7Showthatthefunctionfgivenby:8www.hackshp.cn>:0otherwiseisaowinGfwithvaluejfpj=cf(p)>0.Wesimplycheckthatthethreepropertiesaresatied:Capacityconstraint:Sincecf(p)isaminimumcapacityonthepathpand0otherwise,nocapacitiescanbeexceeded.Skewsymmetry:Ifuandvareonpthedenitionclearlysatiesthisconstraint.Otherwisetheowis0andtheconstraintisagainsatied.Flowconservation:Sincecf(p)isconstantalongapathowconservationmustclearlybepre-served.43若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn26:2-9WewishtocomputetheedgeconnectivityofanundirectedgraphG=(V;E)byrunningamaximum-owalgorithmonatmostjVjownetworksofthesamesizeasG.LetGuvbethedirectedversionofG.WewillconsiderGuvasaownetworkwheres=uandt=v.Wesetthecapacityofeveryedgeto1sothatthenumberofedgescrossinganycutwillequalthecapacityofthecut.LetfuvbeamaximumowofGuv.Theedgeconnectivitycannowbecomputedbyndingminv2V-fugjfuvj.Thisiscaneasilybeseenbyusingthemax-owmin-cuttheorem.26:3-3WewishtogiveanupperboundonthelengthofanyaugmentingpathfoundintheG0graph.TheaugmentingpathisasimplepathintheresidualgraphG0.ThekeyobservationisthatedgesinftheresidualgraphmaygofromRtoL.Henceapathmustbeoftheform:s!L!R!:::!L!R!tCrossingbetweenLandRasmanytimesasitcanwithoutusingavertextwice.Atmost2+2min(jLj;jRj)verticescanbeinthepathandanupperboundonthelengthistherefore2min(jLj;jRj)+1.课后答案网www.hackshp.cn44若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn32:1-2AssumeallthecharactersofParedifferent.AmismatchwithTapositioniofPinline4ofNAIVE-STRING-MATCHERthenimpliesthatmeanthatwecancontinueoursearchfrompositions+iinT.ThusalinearsearchofTissufcient.32:1-4TodetermineifapatternPwithgapcharactersexistsinTpartitionPintosubstringsP1;:::;Pkdeterminedbythegapcharacters.SearchforP1andiffoundcontinuesearchingforP2andsoon.Thisclearlyndapatternifoneexists.32:3-5WecanconstructtheniteautomatoncorrespondingtoapatternPusingthesameideaasinexercise32:1-4.PartitionPintosubstringsP1;:::;Pkdeterminedbythegapcharacters.ConstructniteautomatonsforeachPiandcombinesequentially,i.e.,theacceptingstateofPi,1>i2mg.32:4-5WecandetermineifTisacyclicrotationof课后答案网T0matchingT0againstTT.www.hackshp.cn45若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn33:1-4Showhowtodetermineifthreepointarecollinearinasetofnpoints.Foreachpointp0sortthen-1otherpointsaccordingtothepolaranglewithrespecttop.Iftwopointsp1andp2havethesamepolaranglethenp0,p1andp2arecollinear.ThiscanapproachcanbeimplementedinO(n2lgn).33:2-3FindtwocaseswheretheANY-SEGMENT-INTERSECTgowrongifusedtocomputeallintersectionsfromlefttoright.Figure6:TwocasesfortheANY-SEGMENT-INTERSECTOntherstillustrationtherightmostintersectionisfoundrstandontheotherthemiddlehorisontalsegmentisnotfound.33:2-4Ann-vertexpolygonissimpleifandonlyifnoedgesintersect.HencewecansimplyrunANY-SEGMENT-INTERSECTinO(nlgn)timetodetermineifapolygonissimple.33:2-5课后答案网Tocheckiftwosimplen-vertexpolygonsintersectwecanasabovesimplyrunANY-SEGMENT-INTERSECTinO(nlgn)time.33:3-2Showthatalowerboundofcomputingaconvexhullofnpointsis(nlgn)ifthecomputationmodelhasthesamelowerboundforsorting.www.hackshp.cnThenpointscanbetransformedintopointsintheplanebylettingapointimaptothepoint(i;i2).Computingtheconvexhulloutputsthepointsincounterclockwiseorderandthussorted.33-1a.Computetheconvexlayersofnpointsintheplane.Lethidenotethenumberofpointsintheithlayer.Initially,computetheconvexhullusingJarvis"march.RemovingthesepointsandPrepeatingtheprocedureuntilnopointsexistsdoesthejobsincehi=nandthecompleterunningtimethereforeisO(n2).b.Clearly,ifalowerboundforcomputingtheconvexhullis(nlgn)byexercise33:3-2thismustalsobealowerboundforcomputingtheconvexlayers.46若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn34:1-4ThedynamicprogrammingalgorithmfortheknapsackproblemrunsintimeO(nW)wherenisthenumberofitemsandWisthemaximunweightoftheitems.SinceWdonotdependonthesizeoftheinputthealgorithmisnotpolynomial.34:1-5ConsideranalgorithmthatcallsO(n)subroutineseachtakinglineartime.TherstcallcanproduceO(n)outputwhichcanbeconcatenatedtotheoriginalinputandusedasinputtothePnknextgivingittimeO(2n)andsofort.Thetotaltimeusedisthen2nwhichisclearlyk=1notpolynomial.Ifhoweverweonlycallaconstantnumberofsubroutinesthealgorithmwillbepolynomial.34:1-6AssumethatL,L1,L22P.Thefollowingstatementshold:L1[L22Psincewecandecideifx2L1[L2bydecidingifx2L1andthenifx2L2.Ifeitherholdsthenx2L1[L2otherwiseitisnot.L1L22Psincewecandecideifx2L1andthenifx2L2.Ifbothholdsthenx2L1L2otherwiseitisnot.L2Psincex2L()x62L.L1L22P.Givenastringxoflengthndenoteitssubstringfromindexitojbyxij.Wecanthendecidexbydecidingx1k2L1andxk+1n2L2forallthenpossiblevaluesofk.L2P.WecanprovethisshowingthattheresultholdsforLkforallkandthusfor[kL.i=0kWewilluseinductiononk.Ifk=0weonlyconsidertheemptylanguageandtheresultistrivial.AssumethatLk2PandconsiderLk+1=LLk.TheaboveresultonconcatenationgivesusthatLLk2P.课后答案网34:2-3AssumethatHAM-CYCLE2P.Firstnoticethatforeachnodesexactlytwoincidentedgespartic-ipateinthecycle.Wecanndahamiltoncycleasfollows.Pickanodev2VandletEvbetheedgesincidenttov.Computeapaire;e2EsuchthatG0=(V;(E-E)[fe;egcontainsa12vv12hamiltoncycle.Thiscanbedoneinpolynomialtimebytryingallpossiblepairs.Recursivelyapplytheprocedureonanothernodewww.hackshp.cnwforthegraphG0.ThisproducesinpolynomialtimeagraphH=(V;C)whereCEisahamiltoniancycle.34:2-5kAnyNPcompletelanguagecanbedecidedbyanalgorithmrunningintime2O(n)forsomeconstantksimplybytryingallthepossiblecerticates.34:2-9WewishtoshowthatPco-NP.AssumethatL2P.SincePisclosedundercomplementwehavethatL2PandthusL2NPgivingusthatL2co-NP.34:2-10ShowthatNP6=co-NP=)P6=NP.BycontrapositionthestatementisthesameasP=NP=)NP=co-NP.SincePisclosedundercomplementthestatementisobvious.47若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn34:3-2Showthat6pisatransitiverelation.LetL16pL2andL26pL3.Thenthereexistspolynomial-timecomputablereductionfunctionsf1andf2suchthat:x2L1()f1(x)2L2x2L2()f2(x)2L3Thefunctionf2(f1(x))ispolynomial-timecomputableandsatiesthatx2L1()f2(f1(x))2L3thusgivingusthatL16pL3.34:3-3ShowthatL6pL()L6pL.IfL6pLandfisthereductionfunctionthenwehavebydenitionthatx2L()f(x)2Lforsomex.Thismeansthatx62L()f(x)62Lwhichisx2L()f(x)2LgivingusthatL6pL.Theconversecanbeprovedsimilarly.34:3-6AssumethatL2P.WewishtoshowthatLisP-completeunlessitistheemptylanguageorf0;1g.GivenL02PwecanreduceittoLsimplybyusingthepolynomial-timealgorithmfordecidingL0toconstructthereductionfunctionf.Givenxdecideifx2L0andsetf(x)suchthatf(x)2Lifx2Landf(x)62Lotherwise.Clearly,thisisnotpossibleforthetwotriviallanguagesmentionedabove.34:3-7ShowthatL2NPC()L2co-NPC.AssumeL2NPC.ThenL2NPgivingusthatL2co-NP.AssumefurtherthatL06LforallL2NP.Thismeansthatx2L0()f(x)2Lpforsomepolynomial-timereductionfunctionf.Thenwehavethatx2L0()f(x)2LwhichmeansthatL06pLforallL02课后答案网co-NP.Theconversecanbeshownsimilarly.34:4-5IfaformulaisgivenindisjunctivenormalformwecansimplycheckifanyoftheAND"clausescanbesatiedtodetermineiftheentireformulacanbesatied.34:4-7www.hackshp.cnShowthat2-CNFissolvableinpolynomialtime.Assumew.l.o.g.thateachclausecontainsexactly2literals.FollowingthehintweconstructadirectedgraphG=(V;E)asfollows.Letx0;:::;xnbethevariablesintheformula.Therearetwoverticesviandviforeachxi.Thevertexvicorrespondstoxiandvicorrespondsto:xiForeachclauseweconstructtwoedgesasinthehint.Forexample,givenforxi_:xjwecreate(vj;vi)(vi;vj).WeclaimthatthisformulaissatiableifandonlyifnopairofcomplimentaryliteralsareinthesamestronglyconnectedcomponentofG.Iftherearepathsfromutovandviceversa,theninanytruthassignemtthecorrespondingliteralsmusthavethesamevaluesinceapathisachainofimplications.Conversely,supposenopairofcomplementaryliteralsareinthesamestronglyconnectedcomponent.Considerthedagobtainedbycontractingeachstronglyconnectedcomponenttoasinglevertex.Thisdaginducesapartialorder,whichwethenextendtoatotalorderusing48若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cntopologicalsort.Foreachxi,ifthecomponentofviprecedesthecomponentofvi,setxi=0elsesetxi=1.Weclaimthatthisisavalidtruthassignment,i.e.,that(i)allliteralsinthesamecomponentareassignedthesamevaluesand(ii)ifacomponentBisreachablefromAthenA,Bcannotbeassigned1,0.Werstprove(i).Assumeforthecontrarythattwoliteralsl1andl2areinthesamestronglyconnectedcomponentSbutthestronglyconnectedcomponentcontaining:l1precedesSinthetotalorderandthecomponentcontaining:l2isprecededbyS.Sincel1andl2areinthesamecomponentl1!l2andl2!l1.Italsofollowsthattheclauses(l1_:l2)and(:l1_l2)canbeobtained.Hence,theremustbeapathfrom:l2to:l1.Thiscontradictsthetotalorder.Weprove(ii).AssumeforcontradictionthattherearetwoconnectedcomponentsAandBsuchthatBisreachablefromA,butouralgorithmassigns1and0toAandB.LetlaandlbbealiteralsinAandBrespectively.Notethattheremustbeapathfrom:lbto:la.LetBandAbethecomponentof:laand:lb.Clearly,Bhasvalue1andAhasvalue0.InthetotalorderBprecededBandAprecededA.Thisimpliesthatthereisacycleinthetotalorder.34:5-1Showthatthesubgraph-isomorphismproblemisNP-complete.ItisstraightforwardtoshowthattheproblemisinNP.ToshowthatitisNP-hardwereducefromthehamiltoniancycleproblem.LetGbeagraphGwithnvertices.Clearly,GhasahamiltoniancycleifandonlyifthecyclewithnverticesCnisisomorphictoasubgraphofG.34:5-5Showthattheset-partitioningproblemisNP-complete.Clearly,usingthepartionofthesetascerticateshowsthattheproblemisinNP.FortheNP-hardnesswegiveareductionfromsubset-Psum.GivenaninstancePS=fx1;:::;xngandtcomputersuchthatr+t=(x2Sx+r)=2(r=x2Sx-2t).Theinstanceforset-partitionisthenR=fx1;:::;xn;rg.WeclaimthatShasasubsetsummingtotifandonlyifRcanbepartitioned.AssumeShasasubsetS0summingtot.ThenthesetS0[frgsumstor+tandthuspartitionsR.Conversely,ifRcanbepartitionedthenthesetcontainingtheelement课后答案网rsumstor+t.AllotherelementsinthissetsumtotthusprovidingthesubsetS0.34:5-6Byexercise34:2-6thehamiltonian-pathproblemisinNP.ToshowthattheproblemisNP-hardconstructareductionfromthehamilton-cycleproblem.GivenagraphGpickanyvertexvandmakea“copy”ofv,uthatisconnectedtothesameverticesasv.Itcanbeshownthatthisgraphhasahamiltonianpathfromwww.hackshp.cnvtouifandonlyifGhasahamilton-cycle.NotesfortheexercisesThesolutiontoexercise34:4-7islargelytakenfromasolutiongivenbyEdithCohen.49若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn35:1-1Agraphwithtwoverticesandanedgebetweenthemhastheoptimalvertexcoverofconsistingofasinglevertex.However,APPROX-VERTEX-COVERreturnsbothverticesinthiscase.35:1-3Thefollowinggraphwillnotyieldanratioboundoftwousingtheproposedheuristic.TheverticesareV=fa1;a2;a3;a4;a5;a6;a7;b1;b2;b3;b4;b5;b6;c1;c2;c3;c4;c5;c6gandtheadjancancylistrepresentationisgivenby:a1:b1;b2a2:b3;b4a3:b5;b6a4:b1;b2;b3a5:b4;b5;b6a6:b1;b2;b3;b4a7:b2;b3;b4;b5;b6Additionallythereshouldbeanedgefromb1toc1andfromb2toc2andsoforth.Theheuristicisactuallya(logn)approximationalgorithm.Fortheupperboundnotethatthealgorithmcorrespondstothegreedysetcoveralgorihm,whereedgesaretheelementstobecoveredandeachnodevrepresentsasetcontainingtheedgesincidenttothisnode.Bycorollary35:5wegettheupperbound.ForthelowerboundconsiderthebipartitegraphG=(V[W;E)constructedasfollows.Initially,letV=fv1;:::vngandW=fw1;:::wng.Firstconnectvitowiforalli.Thenaddbn=2cnodestoWandconnecteachofthesetoexactlytwonodesofVnotconnectedtoanyotheroftheaddednodes.Simirlarly,continueaddingbn=3cnodesansoon.Finally,Vcontainsnnodesand课后答案网Wcontains(nHn)nodes.Clearly,Vistheoptimalvertexcover,howeverthealgorithmwill(ifunlucky)selectW.Thuswehaveshownalowerboundof(logn)ontheapproximationfactor.35:1-4Toconstructanoptimalvertexcoverforatreesimplypickanodevsuchthatvhasatleastoneleaf.Selectvandremovevandallverticesandedgesincidenttovandcontinueuntilnomoreverticesareleft.Sincetheedgesincidenttotheleafsofwww.hackshp.cnvneedstobecoveredandwecandothisoptimallybyselectingvthealgorithmndstheoptimalcover.35:1-5Thecliqueproblemandvertexcoverproblemisrelatedthroughareduction.This,however,doesnotimplythatthereisaconstantratioboundapproximationalgorithmsincethereductionsmayaltertheratiopolynomially.35:2-2Wetransformaninstanceofthetravellingsalesmanintoanotherinstancethatsatiesthetriangleequality.Letkbethesumofweightsofalledges.Byaddingktoalledgesweobtainaninstancethatsatiesthetriangleinequalitysincekdominatesthesums.Theoptimaltourremainsun-changedsincealltourscontainthesamenumberofedgesandwethereforesimplyaddednktoalltours.Thisdoesnotcontradicttheorem35:3sincetheratioboundofthetransformedproblemdoesnotgiveaconstantratioboundontheoriginalproblem.50若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn 课后答案网：www.hackshp.cn35:5-4WecanmodifytheapproximationschemetondavaluegreaterthantthatisthesumofsomesubsetS0ofalistSbyrunningtheapproximationalgorithmandthensummingtheelementsofthecomplementlistS-S0.课后答案网www.hackshp.cn51若侵犯了您的版权利益，敬请来信告知！www.hackshp.cn'