算法設(shè)計(jì)與分析基礎(chǔ)課后習(xí)題答案solu3

PAGEPAGE28This?lecontainstheexercises,hints,andsolutionsforChapter3ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms,”2ndedition,A.Levitin.Theproblemsthatbechallengingforatleastsomestudentsaremarked[>;thosethatmightbedi?cultforamajorityofstudentsare?.Exercises3.1a.anexampleofanalgorithmthatshouldnotbeconsideredanapplicationofthebrute-forceapproach.anexampleofaproblemthatcannotbesolvedabrute-forcealgorithm.a.Whatisthee?ciencyofthebrute-forcealgorithmforcomputinganasafunctionofn?Asafunctionofthenumberofbitsinthebinaryrepresentationofn?b.Ifyouaretocomputeanmodmwherea>1andnisalargepositiveinteger,howwouldyoucircumventtheproblemofaverylargemagnitudeofan?ofthealgorithmsinProblems4,5,and6ofExercises2.3,tellwhetherornotthealgorithmisbasedonthebrute-forceapproach.a.Designabrute-forcealgorithmforcomputingtheofapolynomialp(x)=anxn+an?1xn?1+...+a1x+a0atagivenpointx0anddetermineitsworst-casee?ciencyclass.IfthealgorithmdesignedisinΘ(n2),designalinearalgorithmforthisproblem.Isitpossibletodesignanalgorithmwithabetterthanlineare?ciencyforthisproblem?SortthelistE,X,A,M,P,L,Einalphabeticalorderselectionsort.Isselectionsortstable?(Thede?nitionofastablesortingalgorithminSection1.3.)IsitpossibletoimplementselectionsortforlinkedlistswiththesameΘ(n2)e?ciencyasthearrayversion?SortthelistE,X,A,M,P,L,Einalphabeticalorderbubblesort.a.thatifbubblesortnoexchangesonitspassthroughalist,thelistissortedandthealgorithmcanbestopped.apseudocodeofthemethodthatincorporatesthisthattheworst-casee?ciencyoftheversionisquadratic.Isbubblesortstable?Alternatingdisksaof2ndisksofcolors,ndarkandnlight.Theyalternate:dark,light,dark,light,andsoon.togetallthedarkdiskstotheright-handend,andallthelightdiskstotheleft-handend.Theonlyaretoarethosewhichinterchangethepositionsofneighboringdisks.Designanalgorithmforsolvingthispuzzleanddeterminethenumberofmovesitmakes.[Gar99],p.75HintstoExercises3.1a.Thinkofalgorithmsthatimpressedwiththeire?ciencyand/orsophistication.Neithercharacteristicisindicativeofabrute-forcealgorithm.Surprisingly,itisnotaveryeasyquestiontoanswer.Mathemati-calproblems(includingthosestudiedinsecondaryschoolandcollegecourses)areagoodsourceofexamples.a.The?rstquestionallbutansweredinthesection.Expressingtheasafunctionofthenumberofbitscanbedoneusingtheformularelatingthemetrics.b.Howcanwecompute(ab)modm?Ithelpstodonetheexercisesinquestion.a.Themoststraightforwardalgorithm,whichisbasedonsubstitutingx0intotheformula,isquadratic.Analyzingwhatunnecessarycomputationsthequadraticalgorithmdoesshouldleadtoabetter(linear)algorithm.coe?cientsdoesapolynomialofdegreenCancomputeitsatanarbitrarypointwithoutprocessingallofthem?Justtracethealgorithmontheinputgiven.(Itdoneforanotherinputinthesection.)Althoughthemajorityofelementarysortingalgorithmsarestable,donotrushwithanswer.AgeneralremarkaboutstabilitymadeinSection1.3,wherethenotionofstabilityisintroduced,couldbehelpful,too.Generallyspeaking,implementinganalgorithmforalinkedlistposesprob-lemsifthealgorithmrequiresaccessingthelist’selementsnotinasequen-tialorder.Justtracethealgorithmontheinputgiven.(Seeanexampleinthesection.)a.Alistissortedifandonlyifallitsadjacentelementsareinacorrectorder.Addaboolean?agtoregisterthepresenceorabsenceofIdentifyworst-caseinputs?rst.Canbubblesortchangetheorderofequalelementsinitsinput?Thinkingaboutthepuzzleasasorting-likeproblemandnotleadtothemostsimpleande?cientsolution.SolutionstoExercises3.1a.Euclid’salgorithmandthestandardalgorithmfor?ndingthebinaryrepresentationofanintegerareexamplesfromthealgorithmspreviouslymentionedinthisbook.Thereare,ofcourse,moreexamplesinitsotherchapters.Solvingnonlinearequationsorcomputingde?niteintegralsareex-amplesofproblemsthatcannotbesolvedexactly(exceptforspecialin-stances)algorithm.a.M(n)=n≈2bwhereM(n)isthenumberofmultiplicationsmadethebrute-forcealgorithmincomputinganandbisthenumberofbitsinthen’sbinaryrepresentation.Hence,thee?ciencyislinearasafunctionofnandexponentialasafunctionofb.b.Performallthemultiplicationsmodulom,i.e.,aimodm=(ai?1modm·amodm)modmfori=1,...,n.1Problem4(computes藝ni2):1Problem5(computestherangeofanarray’svalues):yesProblem6(checkswhetheramatrixissymmetric):yesa.HereisapseudocodeofthemoststraightforwardAlgorithmBruteForcePolynomialEvaluation(P[0..n],x)//ThealgorithmcomputesthevalueofpolynomialPatagivenpointx//bythe“highest-to-lowestterm”brute-forcealgorithm//Input:ArrayP[0..n]ofthecoe?cientsofapolynomialofdegreen,// storedfromthetothehighestandanumberx//Output:Thevalueofthepolynomialatthepointxp←0.0fori←ndownto0dopower←1forj←1toidopower←power?xp←p+P[i]?powerreturnpwillmeasuretheinput’ssizethepolynomial’sdegreen.Theba-sicoperationofthisalgorithmisamultiplicationofnumbers;thenumberofmultiplicationsM(n)dependsonthepolynomial’sdegreeAlthoughitisnotdi?cultto?ndthetotalnumberofmultiplicationsinthisalgorithm,cancountjustthenumberofmultiplicationsinthealgorithm’sinner-mostloopto?ndthealgorithm’se?ciencyclass:2n i n2M(n)=區(qū)區(qū)1=區(qū)i==n(n+1)∈Θ(n2).i=0j=1 Thealgorithmisveryine?cient:recomputepowersofxagainandagainasiftherenorelationshipamongthem.Thus,theobviousisbasedoncomputingconsecutivepowersmoreIfproceedfromthehighesttermtothecouldcomputexi?1usingxibutthisrequireadivisionandhenceaspecialtreatmentforx=0.canfromthetermtothehighestandcomputexiusingxi?1.Sincethesecondalternativeusesmultiplicationsinsteadofdivisionsanddoesnotrequirespecialtreatmentforx=0,itisbothmoree?cientandcleaner.Itleadstothefollowingalgorithm:AlgorithmBetterBruteForcePolynomialEvaluation(P[0..n],x)//ThealgorithmcomputesthevalueofpolynomialPatagivenpointx//bythe“l(fā)owest-to-highestterm”algorithm//Input:ArrayP[0..n]ofthecoe?cientsofapolynomialofdegreen,// fromthetothehighest,andanumberx//Output:Theofthepolynomialatthepointxp←P[0];power←1fori←1tondopower←power?xp←p+P[i]?powerreturnpThenumberofmultiplicationshereisnM(n)=區(qū)2=2ni=1(whilethenumberofadditionsisn),i.e.,wehavealinearalgorithm.Note:Horner’sRulediscussedinSection6.5needsonlynmultiplications(andnadditions)tosolvethisproblem.No,becausealgorithmforanarbitrarypolynomialofdegreenatanarbitrarypointxprocessallitsn+1coe?cients.(Notethatwhenx=1,p(x)=an+an?1+...+a1+a0,needsatleastnadditionstobecomputedcorrectlyforarbitraryan,an?1,...,a0.)EXEXAMPLEAXEMPLEAEXMPLEAEEMPLXAEELPMXAEELMPXAEELMPXSelectionsortisnotstable:Intheprocessofexchangingelementsthatarenotadjacenttoother,thealgorithmcanreverseanorderingofequals.helit1,11,1isuhnp.hprinninghelltltndsppnginbedonease?cientlywithalinkedlistaswithanE,X,A,M,P,L,E??E ?X ?A M P L E??E A X ? M P L EE A M X ? P L EE A M P X ? L EE A M P L X ? EE A M P L E |X???E ?A M P L E????A E ?M?P ?L E?A E M L P ?EA E M L E |PA?A?E?M?LAELMAELEA?E?L?EAEE|LA?E?E?L? E|MThealgorithmcanbestoppedhere(seethenextquestion).a.i(0≤i≤n?2)ofbubblesortcanberepresentedthediagram:?A0,...,Aj?Aj+1,...,An?i?1≤|An?i≤...≤An?1?intheirfinalpositionsIftherearenoswapsduringthispass,thenA0≤A1≤...≤Aj≤Aj+1≤...≤An?i?1,withthelarger(moreaccurately,notsmaller)elementsinpositionsn?ithroughn?1beingsortedduringthepreviousiterations.Hereisapseudocodefortheversionofbubblesort:AlgorithmBetterBubbleSort(A[0..n?1])//ThealgorithmsortsarrayA[0..n?1]byimprovedbubblesort//Input:AnarrayA[0..n?1]oforderableelements//Output:ArrayA[0..n?1]sortedinascendingordercount←n?1//numberofadjacentpairstobecompareds?ag←true//swap?agwhiles?agdos?ag←falseforj←0tocount?1doifA[j+1]<A[j]swapA[j]andA[j+1]s?ag←truecount←count?1Theworst-caseinputswillbestrictlydecreasingarrays.them,theversionwillthesamecomparisonsastheoriginalversion,inthetexttobequadratic.Bubblesortisstable. ItfollowsfromthefactthatitprovidedA[j+1]<A[j].5.Hereisasimpleande?cient(infact,optimal)algorithmforthisproblem:Startingwiththe?rstandendingwiththelastlightdisk,itwithofthei(1≤i≤n)darkdiskstotheleftofit.Theithiterationofthealgorithmcanbeillustratedthefollowingdiagram,in1sand0scorrespondtothedarkandlightdisks,respectively.00..011..11010..10 ? 00..0011..1110..10、、Thetotalnumberofmadeisequalto

i=n(n+1)/2.Exercises3.2Fhecaseiftheprobabilityofasuccessfulsearchisp(0≤p≤1).AsinSection2.1,thenumberofcomparisonsmadesequential(withoutasentinel,understandardassumptionsaboutitsinputs)istheformulaCavg(n)=

p(n+1)2 +n(1?p),wherepistheprobabilityofasuccessfulsearch.Determine,fora?xedn,theofp(0≤p≤1)forwhichthisformulayieldsthelargestofCavg(n)andthesmallestofCavg(n).GadgetstestingA?rmtodeterminethehighest?oorofitsn-storyheadquartersfromwhichagadgetcanfallwithnoimpactonthegadget’sThe?rmhasidenticalgadgetstoexperimentwith.Designanalgorithminthebeste?ciencyclasscantosolvethisproblem.Determinethenumberofcharactercomparisonsmadethebrute-forcealgorithminsearchingforthepatternGANDHIinthetextTHERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEEDsmetelnhfheitis7hrtsnisnbeforethestarts.)comparisons(bothsuccessfulandunsuccessful)aremadethebrute-forcestring-matchingalgorithminsearchingforofthefollowingpatternsinthebinarytextof1000zeros?a.00001b.10000c.01010anexampleofatextoflengthnandapatternoflengthmthatconstitutestheworst-caseinputforthebrute-forcestring-matchingal-gorithm.Exactlycharactercomparisonsaremadeforsuchinput?avisualizationprogramforthebrute-forcestring-matchingalgo-rithm.Insolvingthestring-matchingproblem,therebeincomparingpatternandtextcharactersright-to-leftinsteadofleft-to-right?Considertheproblemofcounting,inagiventext,thenumberofsubstringsthatstartwithanAandendwithaB.example,therearefoursuchsubstringsinDesignabrute-forcealgorithmforthisproblemanddetermineitse?ciencyclass.Designamorealgorithmforthisproblem[Gin04].FindApopulardiversionintheUnitedStates,Find,askstheto?ndofagivensetofwordsinasquaretable?lledwithsingleletters.Acanreadhorizontally(leftorright),vertically(upororalonga45degreediagonal(inofthefourdirections),formedconsecutivelyadjacentcellsofthetable;itwraparoundthetable’sboundariesbutitmustreadinthesamedirectionwithnozigzagging.Thesamecellofthetablebeusedindi?erentbut,inagiventhesamecellbeusednomorethanonce.acomputerprogramforsolvingthispuzzle.BattleshipgameaprogramforplayingBattleship(aclassicstrat-egygame)onthecomputerwhichisbasedonaversionofbrute-forcepatternmatching.Therulesofthegameareasfollows.Thereareopponentsinthegame(inthiscase,aandthecomputer).Thegameisonidenticalboardstablesofsquares)onopponentplaceshisorherships,notseentheopponent.has?veships,ofoccupiesacertainnumberofsquaresontheboard:a(2squares),asubmarine(3squares),acruiser(3squares),abattleship(4squares),andanaircraftcarrier(5squares).shipisplacedeitherhorizontallyorwithnoshipstouchingother.Thegameistheopponentstakingturns“shooting”atother’sships.Aresultofeveryshotisaseitherahitoramiss.Incaseofahit,thegetstogoagainandplayinguntilthismisses.Thegoalistosinkalltheoppo-nent’sshipsbeforetheopponentsucceedsindoingit?rst.sinkaship,allsquaresoccupiedtheshipbehit.)HintstoExercises3.2Modifytheanalysisofthealgorithm’sversioninSection2.1.Asafunctionofp,whatkindoffunctionisCavg?Solveasimplerproblemwithasinglegadget?rst.Thendesignabetterthanlinearalgorithmfortheproblemwithgadgets.TheofthisquotefromMahatmaGandhiismorethoughtingthanthisdrill.input,oneiterationofthealgorithmyieldsalltheinformationneedtothequestion.Itwillsu?cetolimitsearchforanexampletobinarytextsandpatterns.useeitherbitstringsoranaturallanguagetextforthevisual-izationprogram.Itbeagoodideatoimplement,asanoption,aforalloccurrencesofagivenpatterninatext.Theanswer,surprisingly,isyes.a.agivenoccurrenceofAinthetext,whatarethesubstringsneedtob.agivenoccurrenceofBinthetext,whatarethesubstringsneedtoprogramBeespeciallycarefulaboutapossibilityofreaddiagonallywithwrappingaroundthetable’sborder.A(very)brute-forcealgorithmcansimplyshootatadjacentfeasiblecellsstartingat,oneofthecornersoftheboard.Cansuggestabetterstrategy?canrelativee?cienciesofdi?erentstrategiesmakingprogramsimplementingthemother.)Isstrategybetterthantheonethatshootsatrandomlygeneratedcellsoftheopponent’sboard?SolutionstoExercises3.2a.Cworst(n)=n+1.2b.Cavg(n)=(2?p)(n+1).InthemanneralmostidenticaltotheanalysisinSection2.1,obtain2p p p pCavg(n)=[1·n+2·n+...+i·n+...+n·n]+(n+1)·(1?p)p= n[1+2+...+i+...+n]+(n+1)(1?p)= pn(n+1)+(n+1)(1?p)=(2?p)(n+1).n 2 2Theexpression2222p(n+1)+n(1?p)=pn+1+n?np=n?p(n?n+1)=n?n?1p2222isalinearfunctionofp.Sincethep’scoe?cientisnegativeforn>1,thefunctionisstrictlydecreasingonthe0≤p≤1fromnto(n+1)/2.Hencep=0andp=1areitsmaximumandminimumpoints,onthis(Ofcourse,thisistheshouldexpect:Thenumberofcomparisonsshouldbethelargestwhentheprobabilityofasuccessfulsearchis0,anditshouldbethesmallestwhentheprobabilityofasuccessfulsearchis1.)√Dropthe?rstgadgetfrom?oors「√nl2「√nlandsoonuntileitherthe?oori「nladropfromthegadgetmalfunctionisreachedorno?oorinthissequenceisencounteredbeforethetopofthe√√ √ buildingisreached.Intheformercase,the?oortobefoundishigherthan(i?1)「nlandthani「nl.So,dropthesecondgadgetfrom?oors(i?1)「nl+1,(i?1)「nl+2,andsoonuntilthe?rst?ooradropfromthegadgetmalfunctionisreached.The?oor√ √ √√immediatelypreceedingthat?ooristhe?oorinquestion.Ifnodropinthe?rst-passsequenceresultedinthegadget’sfailure,the?oorinquestionis√√higherthani「nl,thelasttried?oorofthatsequence.Hence,thesuccessiveexaminationof?oorsi「√nl1i「nl2andsoon√eitherafailureisregisteredorthelast?oorisreached.Thenumberoftimesthetwogadgetsaredroppeddoesn’texceed「√nl+「nl,whichputsitinO(√n).√43comparisons.Thealgorithmwill47?6+1=42trials:Inthe?rstone,theGofthepatternwillbealignedagainstthe?rstTofthetext;inthelastone,itwillbealignedagainstthelastspace.Onbutonetrial,thealgorithmwilloneunsuccessfulcomparison;ononetrial–whentheGftetnisliditheGfhetitlleocomparisons. thetotalnumberofcharactercomparisonswillbe41·1+1·2=43.a.thepattern00001,thealgorithmwillmakefoursuccessfulandunsuccessfulcomparisononofitstrialsandthenshiftthepatternonepositiontothe0000000000000000100001etc.00001ThetotalnumberofcharactercomparisonswillbeC=5·996=4980.thepattern10000,thealgorithmwilloneunsuccessfulcom-parisononofitstrialsandthenshiftthepatternonepositiontotheright:0000000000001000010000etc.10000ThetotalnumberofcharactercomparisonswillbeC=1·996=996.thepattern01010,thealgorithmwillonesuccessfulandoneunsuccessfulcomparisononofitstrialsandthenshiftthepat-ternonepositiontotheright:0000000000000101001010etc.01010ThetotalnumberofcharactercomparisonswillbeC=2·996=1,992.Thetextcomposedofnzerosandthepattern0...01isanexampleof,theworst-caseinput.Thealgorithmwillm(n?m+1)comparisonsoninput.Comparingpairsofthepatternandtextcharactersrigh-to-leftcanfartherpatternshiftsafteramismatch.ThisisthemaininsightthestringmatchingalgoirthmsdiscussedinSection7.2arebasedon.(Asaspeci?cexample,considersearchingforthepattern11111inthetextofonethousandzeros.)a.NotethatthenumberofdesiredsubstringsthatstartswithanAatapositioni(0≤i<n?1)inthetextisequaltothenumberofB’stotherightofthatposition.Thisleadstothefollwingsimplealgorithm:Initializetheofthedesiredsubstringsto0.Scanthetextlefttorightdoingthefollowingforeverycharacterexceptthelastone:IfanAisencountered,thenumberofalltheB’sfollowingitandaddthisnumbertotheofdesiredsubstrings.Afterthescanends,returnthelastoftheFortheworstcaseofthetextcomposedofnA’s,thetotalnumberofcharactercomparisonsisn+(n?1)+...+2=n(n+1)/2?1∈Θ(n2).b.NotethatthenumberofdesiredsubstringsthatendswithaBatagivenpositioni(0<i≤n?1)inthetextisequaltothenumberofA’stotheleftofthatposition.Thisleadstothefollwingalgorithm:InitializetheofthedesiredsubstringsandthecountofA’sen-to0.Scanthetextlefttorightuntilthetextisexhaustedanddothefollowing.IfanAisencountered,incrementtheA’sifaBisencountered,addthecurrentoftheA’stothedesiredsubstringAfterthetextisexhausted,returnthelastofthedesiredsubstringcount.Sincethealgorithmmakesasinglepassthroughagiventextspendingconstanttimeoneachofitscharacters,thealgorihtmislinear.Exercises3.3Candesignamoree?cientalgorithmthantheonebasedonthebrute-forcestrategytosolvetheclosest-pairproblemfornpointsx1,...,xnontherealline?Letx1<x2<...<xnberealnumbersrepresentingcoordinatesofnvillageslocatedalongastraightroad.Aposto?ceneedstobebuiltinoneofthesevillages.Designane?cientalgorithmto?ndthepost-o?celocationminimizingthedistancethevillagesandtheposto?ce.Designane?cientalgorithmto?ndthepost-o?celocationminimizingthemaximumdistancefromavillagetotheposto?ce.a.[>Thereareseveralalternativetode?neadistancepointsP1=(x1,y1)andP2=(x2,y2).Inparticular,theManhattanisde?nedasdM(P1,P2)=|x1?x2|+|y1?y2|.ProvethatdMsatis?esthefollowingaxiomsthateverydistancefunctionmustsatisfy:dM(P1,P2)≥0forpointsP1andP2anddM(P1,P2)=0ifandonlyifP1=P2;dM(P1,P2)=dM(P2,P1);dM(P1,P2)≤dM(P1,P3)+dM(P3,P2)forP1,P2,andP3.b.Sketchallthepointsinthex,ycoordinateplanewhoseManhattandistancetotheorigin(0,0)isequalto1.DothesamefortheEuclideandistance.c.[>Trueorfalse:Asolutiontotheclosest-pairproblemdoesnotdependonwhichofthetwometrics–dE(Euclidean)ordM(Manhattan)–isused.Oddpie?ghtTherearen≥3peoplepositionedina?eld(Euclideanplane)sothathasauniquenearestneighbor.personhasacreampie.asignal,everybodyhurleshisorherpieatthenearestneighbor.Assumingthatnisoddandthatnobodycanmisshisorhertarget,trueorfalse:Thereremainsatleastonepersonnothitapie?[Car79].Theclosest-pairproblemcanbeposedink-dimensionalspaceinwhichheuidndsebnopsP1=(1,...,1)ndP11=1 k1,..,1)isdnds1 kIkd(P1,P11)=?區(qū)(x1?x11)2.s ss=1Whatisthetime-e?ciencyclassofthebrute-forcealgorithmforthek-dimensionalclosest-pairproblem?Findthehullsofthefollowingsetsandidentifytheirextremepoints(iftheyalineasquaretheboundaryofasquareastraightlineDesignalinear-timealgorithmtodetermineextremepointsofthehullofasetofn>1pointsintheplane.Whatmodi?cationneedstobemadeinthebrute-forcealgorithmfortheproblemtohandlemorethanpointsonthesamestraightline?aprogramimplementingthebrute-forcealgorithmforthehullproblem.Considerthefollowingsmallinstanceofthelinearprogrammingproblem:maximize 3x+5ysubjectto x+y≤4x+3y≤6x≥0,y≥0intheCartesianplane,theproblem’sde-?nedasthesetofpointssatisfyingalltheproblem’sconstraints.Identifytheregion’sextremepoints.Solvetheoptimizationproblemgivenusingthefollowingtheorem:Alinearprogrammingproblemwithanonemptyboundedfeasibleregionhasasolution,whichcanbefoundatoneoftheextremepointsofitsfeasibleregion.HintstoExercises3.3SortingnrealnumberscanbedoneinO(nlogn)time.a.Solvingtheproblemforn=2andn=3shouldleadtothecriticalinsight.b.Whereputtheposto?ceifitwouldnottobeatoneofthevillagelocations?.krirtsiiii)ysngbicrptisflueu.theManhattandistance,thepointsinquestionarede?nedequation|x?0|+|y?0|=1.canstartthepointsinthepositivequadrantofthecoordinatesystem(i.e.,thepointsforwhichx,y≥0)andthentherestusingthesymmetries.Theassertionisfalse.canchoose,P1(0,0),P2(1,0)and?ndP3tocompleteacounterexample.itmathematicalinduction.shouldbeafunctionofparameters:nandk.Aspecialcaseofthisproblem(fork=2)solvedinthetext.Reviewtheexamplesgiveninthesection.Someoftheextremepointsofahullareeasierto?ndthanothers.IfthereareotherpointsofagivensetonthestraightlinethroughPiandPj,whichofallthesepointsneedtobepreservedforfurtherprocessing?programshouldforsetofndistinctpoints,includingsetswithcolinearpoints.a.Thesetofpointssatisfyinginequalityax+by≤cisthehalf-planeofthepointsononesideofthestraightlineax+by=c,includingallthepointsonthelineitself.Sketchsuchahalf-planeforeachoftheinequal-itiesand?ndtheirintersection.Theextremepointsaretheverticesofthepolygonobtainedinparta.Computeandcomparetheoftheobjectivefunctionattheex-tremepoints.SolutionstoExercises3.3Sortthenumbersinascendingorder,computethedi?erencesad-numbersinthesortedlist,and?ndthesmallestdi?erence.IfsortingisdoneinO(nlogn)time,therunningtimeoftheentirealgorithmwillbeinO(nlogn)+Θ(n)+Θ(n)=O(nlogn).a.Ifputtheposto?ceatlocationxi,thedistanceitnandallthepointsx1<x2<...<xnisgiventheformula1藝n nnxi|.Sincethenumberofpointsnstaysthesame,n1andminimize藝n |xj?xi|.toconsiderthecasesofandoddnseparately.Letnbeeven.Consider?rstthecaseofn=2.Thesum|x1?x|+|x2?x|isequaltox2?x1,thelengthoftheintervalwiththeendpointsatx1andx2,foranypointxofthisinterval(includingtheendpoints),anditislargerthanx2?x1foranypointxoutsideofthisinterval.Thisimpliesthatforanyevenn,thesumn區(qū)j|=1n2121]j=1isminimizedwhenxbelongstoeachoftheintervals[x1,xn]?[x2,xn?1]?...?2,1.fxstbenefhepisin,ihr2r1lstheproblem.Letn>1beodd. Then,thesum藝n |xj?x|isminimizedwhenxx「n/21,thepointforwhichthenumberofthegivenpointstotheleftofitisequaltothenumberofthegivenpointstotherightofit.ethepit1helhmlltlldhenlstheproblemforn’saswell.asortedlistimplementedasaneincnbendin)tieyimlyrtrnigheh.ltoftheSection5.6providesamoregeneraldiscussionofalgorithmsforcomputingthemedian.)Assumingthatthepointsx1,x2,...,xnaregiveninincreasingorder,theisthepointxithatistheclosesttom=(x1+xn)/2,themiddlepointx1andxn.(Themiddlepointbetheobvioussolutionifthepost-posto?cedidn’ttobeatoneofthelocations.)Indeed,ifputtheposto?ceatlocationxitotheleftofm,thelongestdistancefromalletohepteudben?i;hsdineismnilrterightmostamongpoints.Ifputtheposto?ceatlocationxitotherightofm,thelongestdistancefromavillagetotheposto?cewouldbexi?x1;thisdistanceisminimalfortheleftmostamongsuchpoints.AlgorithmPostO?ce1(P)//Input:ListPofn(n≥2)pointsx1,x2,...,xninincreasingorder| ? //Output:xithatminimizesmaxxj xiamongallx1,x2,...,x| ? 1≤j≤nm←(x1+xn)/2i←1whilexi<mdoi←i+1ifxi?x1<xn?xi?1returnxielsereturnxi?1Thetimee?ciencyofthisalgorithmisO(n).a.dM(P1,P2)=|x1?x2|+|y1?y2|,thefollowing:(i)dM(P1,P2)=|x1?x2|+|y1?y2|≥0anddM(P1,P2)=0ifandonlyifbothx1=x2andy1=y2,i.e.,P1andP2coincide.(ii)dM(P1,P2)=|x1?x2|+|y1?y2|=|x2?x1|+|y2?y1|=dM(P2,P1).(iii)dM(P1,P2)=|x1?x2|+|y1?y2|=|(x1?x3)+(x3?x2)|+|(y1?y3)+(y3?y2)|≤|x1?x3|+|x3?x2|+|y1?y3|+|y3?y2|=d(P1,P3)+d(P3,P2).theManhattandistance,thepointsinquestionarede?nedtheequation|x?0|+|y?0|=1,i.e.,|x|+|y|=1.Thegraphofthisequationistheboundaryofthesquarewithitsverticesat(1,0),(0,1),(?1,0),and(?1,?1).theEuclideandistance,thepointsinquestionarede?nedtheequa-tion (x?0)2+(y?0)2=1,i.e.,x2+y2=1.Thegraphofthisequationisthecircumferenceofradius1andthecenterat(0,0).ConsiderpointsP1(0,0),P2(1,0),and,P3(1,3).Then24(1)2 (32dE(P1,P2)=1anddE(P3,P1)=dE(P3,P2)=

+ <1.2 4Therefore,fortheEuclideandistance,thetwoclosestpointsareeitherP1andP3orP2andP3.FortheManhattandistance,wehave1 3 5dM(P1,P2)=1anddM(P3,P1)=dM(P3,P2)=2+4=4>1.Therefore,fortheManhattandistance,thetwoclosestpointsareP1andP2.inductionthattherewillremainatleastonepersonnothitapie.Thebasisstepiseasy:Ifn=3,thepersonswiththesmallestpairwisedistancethemthrowatother,whilethethirdpersonthrowsatoneofthem(whoeveriscloser).Therefore,thisthirdpersonremains“unharmed”.theinductivestep,assumethattheassertionistru