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

PAGEPAGE28Thisfilecontainstheexercises,hints,andsolutionsforChapter3ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms,”2ndedition,A.Levitin.Theproblemsthatbechallengingforatleastsomestudentsaremarked[>;thosethatmightbedifficultforamajorityofstudentsare►.Exercises3.1a.anexampleofanalgorithmthatshouldnotbeconsideredanapplicationofthebrute-forceapproach.anexampleofaproblemthatcannotbesolvedabrute-forcealgorithm.a.Whatistheefficiencyofthebrute-forcealgorithmforcomputinganasafunctionofn?Asafunctionofthenumberofbitsinthebinaryrepresentationofn?b.Ifyouaretocomputeanmodmwherea>1andnisalargepositiveinteger,howwouldyoucircumventtheproblemofaverylargemagnitudeofan?ofthealgorithmsinProblems4,5,and6ofExercises2.3,tellwhetherornotthealgorithmisbasedonthebrute-forceapproach.a.Designabrute-forcealgorithmforcomputingtheofapolynomialp(x)=anxn+an−1xn−1+...+a1x+a0atagivenpointx0anddetermineitsworst-caseefficiencyclass.IfthealgorithmdesignedisinΘ(n2),designalinearalgorithmforthisproblem.Isitpossibletodesignanalgorithmwithabetterthanlinearefficiencyforthisproblem?SortthelistE,X,A,M,P,L,Einalphabeticalorderselectionsort.Isselectionsortstable?(ThedefinitionofastablesortingalgorithminSection1.3.)IsitpossibletoimplementselectionsortforlinkedlistswiththesameΘ(n2)efficiencyasthearrayversion?SortthelistE,X,A,M,P,L,Einalphabeticalorderbubblesort.a.thatifbubblesortnoexchangesonitspassthroughalist,thelistissortedandthealgorithmcanbestopped.apseudocodeofthemethodthatincorporatesthisthattheworst-caseefficiencyoftheversionisquadratic.Isbubblesortstable?Alternatingdisksaof2ndisksofcolors,ndarkandnlight.Theyalternate:dark,light,dark,light,andsoon.togetallthedarkdiskstotheright-handend,andallthelightdiskstotheleft-handend.Theonlyaretoarethosewhichinterchangethepositionsofneighboringdisks.Designanalgorithmforsolvingthispuzzleanddeterminethenumberofmovesitmakes.[Gar99],p.75HintstoExercises3.1a.Thinkofalgorithmsthatimpressedwiththeirefficiencyand/orsophistication.Neithercharacteristicisindicativeofabrute-forcealgorithm.Surprisingly,itisnotaveryeasyquestiontoanswer.Mathemati-calproblems(includingthosestudiedinsecondaryschoolandcollegecourses)areagoodsourceofexamples.a.Thefirstquestionallbutansweredinthesection.Expressingtheasafunctionofthenumberofbitscanbedoneusingtheformularelatingthemetrics.b.Howcanwecompute(ab)modm?Ithelpstodonetheexercisesinquestion.a.Themoststraightforwardalgorithm,whichisbasedonsubstitutingx0intotheformula,isquadratic.Analyzingwhatunnecessarycomputationsthequadraticalgorithmdoesshouldleadtoabetter(linear)algorithm.coefficientsdoesapolynomialofdegreenCancomputeitsatanarbitrarypointwithoutprocessingallofthem?Justtracethealgorithmontheinputgiven.(Itdoneforanotherinputinthesection.)Althoughthemajorityofelementarysortingalgorithmsarestable,donotrushwithanswer.AgeneralremarkaboutstabilitymadeinSection1.3,wherethenotionofstabilityisintroduced,couldbehelpful,too.Generallyspeaking,implementinganalgorithmforalinkedlistposesprob-lemsifthealgorithmrequiresaccessingthelist’selementsnotinasequen-tialorder.Justtracethealgorithmontheinputgiven.(Seeanexampleinthesection.)a.Alistissortedifandonlyifallitsadjacentelementsareinacorrectorder.AddabooleanflagtoregisterthepresenceorabsenceofIdentifyworst-caseinputsfirst.Canbubblesortchangetheorderofequalelementsinitsinput?Thinkingaboutthepuzzleasasorting-likeproblemandnotleadtothemostsimpleandefficientsolution.SolutionstoExercises3.1a.Euclid’salgorithmandthestandardalgorithmforfindingthebinaryrepresentationofanintegerareexamplesfromthealgorithmspreviouslymentionedinthisbook.Thereare,ofcourse,moreexamplesinitsotherchapters.Solvingnonlinearequationsorcomputingdefiniteintegralsareex-amplesofproblemsthatcannotbesolvedexactly(exceptforspecialin-stances)algorithm.a.M(n)=n≈2bwhereM(n)isthenumberofmultiplicationsmadethebrute-forcealgorithmincomputinganandbisthenumberofbitsinthen’sbinaryrepresentation.Hence,theefficiencyislinearasafunctionofnandexponentialasafunctionofb.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]ofthecoefficientsofapolynomialofdegreen,// storedfromthetothehighestandanumberx//Output:Thevalueofthepolynomialatthepointxp←0.0fori←ndownto0dopower←1forj←1toidopower←power∗xp←p+P[i]∗powerreturnpwillmeasuretheinput’ssizethepolynomial’sdegreen.Theba-sicoperationofthisalgorithmisamultiplicationofnumbers;thenumberofmultiplicationsM(n)dependsonthepolynomial’sdegreeAlthoughitisnotdifficulttofindthetotalnumberofmultiplicationsinthisalgorithm,cancountjustthenumberofmultiplicationsinthealgorithm’sinner-mostlooptofindthealgorithm’sefficiencyclass:2n i n2M(n)=区区1=区i==n(n+1)∈Θ(n2).i=0j=1 Thealgorithmisveryinefficient:recomputepowersofxagainandagainasiftherenorelationshipamongthem.Thus,theobviousisbasedoncomputingconsecutivepowersmoreIfproceedfromthehighesttermtothecouldcomputexi−1usingxibutthisrequireadivisionandhenceaspecialtreatmentforx=0.canfromthetermtothehighestandcomputexiusingxi−1.Sincethesecondalternativeusesmultiplicationsinsteadofdivisionsanddoesnotrequirespecialtreatmentforx=0,itisbothmoreefficientandcleaner.Itleadstothefollowingalgorithm:AlgorithmBetterBruteForcePolynomialEvaluation(P[0..n],x)//ThealgorithmcomputesthevalueofpolynomialPatagivenpointx//bythe“lowest-to-highestterm”algorithm//Input:ArrayP[0..n]ofthecoefficientsofapolynomialofdegreen,// fromthetothehighest,andanumberx//Output:Theofthepolynomialatthepointxp←P[0];power←1fori←1tondopower←power∗xp←p+P[i]∗powerreturnpThenumberofmultiplicationshereisnM(n)=区2=2ni=1(whilethenumberofadditionsisn),i.e.,wehavealinearalgorithm.Note:Horner’sRulediscussedinSection6.5needsonlynmultiplications(andnadditions)tosolvethisproblem.No,becausealgorithmforanarbitrarypolynomialofdegreenatanarbitrarypointxprocessallitsn+1coefficients.(Notethatwhenx=1,p(x)=an+an−1+...+a1+a0,needsatleastnadditionstobecomputedcorrectlyforarbitraryan,an−1,...,a0.)EXEXAMPLEAXEMPLEAEXMPLEAEEMPLXAEELPMXAEELMPXAEELMPXSelectionsortisnotstable:Intheprocessofexchangingelementsthatarenotadjacenttoother,thealgorithmcanreverseanorderingofequals.helit1,11,1isuhnp.hprinninghelltltndsppnginbedoneasefficientlywithalinkedlistaswithanE,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//numberofadjacentpairstobecomparedsflag←true//swapflagwhilesflagdosflag←falseforj←0tocount−1doifA[j+1]<A[j]swapA[j]andA[j+1]sflag←truecount←count−1Theworst-caseinputswillbestrictlydecreasingarrays.them,theversionwillthesamecomparisonsastheoriginalversion,inthetexttobequadratic.Bubblesortisstable. ItfollowsfromthefactthatitprovidedA[j+1]<A[j].5.Hereisasimpleandefficient(infact,optimal)algorithmforthisproblem:Startingwiththefirstandendingwiththelastlightdisk,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,forafixedn,theofp(0≤p≤1)forwhichthisformulayieldsthelargestofCavg(n)andthesmallestofCavg(n).GadgetstestingAfirmtodeterminethehighestfloorofitsn-storyheadquartersfromwhichagadgetcanfallwithnoimpactonthegadget’sThefirmhasidenticalgadgetstoexperimentwith.Designanalgorithminthebestefficiencyclasscantosolvethisproblem.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-forcealgorithmforthisproblemanddetermineitsefficiencyclass.Designamorealgorithmforthisproblem[Gin04].FindApopulardiversionintheUnitedStates,Find,asksthetofindofagivensetofwordsinasquaretablefilledwithsingleletters.Acanreadhorizontally(leftorright),vertically(upororalonga45degreediagonal(inofthefourdirections),formedconsecutivelyadjacentcellsofthetable;itwraparoundthetable’sboundariesbutitmustreadinthesamedirectionwithnozigzagging.Thesamecellofthetablebeusedindifferentbut,inagiventhesamecellbeusednomorethanonce.acomputerprogramforsolvingthispuzzle.BattleshipgameaprogramforplayingBattleship(aclassicstrat-egygame)onthecomputerwhichisbasedonaversionofbrute-forcepatternmatching.Therulesofthegameareasfollows.Thereareopponentsinthegame(inthiscase,aandthecomputer).Thegameisonidenticalboardstablesofsquares)onopponentplaceshisorherships,notseentheopponent.hasfiveships,ofoccupiesacertainnumberofsquaresontheboard:a(2squares),asubmarine(3squares),acruiser(3squares),abattleship(4squares),andanaircraftcarrier(5squares).shipisplacedeitherhorizontallyorwithnoshipstouchingother.Thegameistheopponentstakingturns“shooting”atother’sships.Aresultofeveryshotisaseitherahitoramiss.Incaseofahit,thegetstogoagainandplayinguntilthismisses.Thegoalistosinkalltheoppo-nent’sshipsbeforetheopponentsucceedsindoingitfirst.sinkaship,allsquaresoccupiedtheshipbehit.)HintstoExercises3.2Modifytheanalysisofthealgorithm’sversioninSection2.1.Asafunctionofp,whatkindoffunctionisCavg?Solveasimplerproblemwithasinglegadgetfirst.Thendesignabetterthanlinearalgorithmfortheproblemwithgadgets.TheofthisquotefromMahatmaGandhiismorethoughtingthanthisdrill.input,oneiterationofthealgorithmyieldsalltheinformationneedtothequestion.Itwillsufficetolimitsearchforanexampletobinarytextsandpatterns.useeitherbitstringsoranaturallanguagetextforthevisual-izationprogram.Itbeagoodideatoimplement,asanoption,aforalloccurrencesofagivenpatterninatext.Theanswer,surprisingly,isyes.a.agivenoccurrenceofAinthetext,whatarethesubstringsneedtob.agivenoccurrenceofBinthetext,whatarethesubstringsneedtoprogramBeespeciallycarefulaboutapossibilityofreaddiagonallywithwrappingaroundthetable’sborder.A(very)brute-forcealgorithmcansimplyshootatadjacentfeasiblecellsstartingat,oneofthecornersoftheboard.Cansuggestabetterstrategy?canrelativeefficienciesofdifferentstrategiesmakingprogramsimplementingthemother.)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’scoefficientisnegativeforn>1,thefunctionisstrictlydecreasingonthe0≤p≤1fromnto(n+1)/2.Hencep=0andp=1areitsmaximumandminimumpoints,onthis(Ofcourse,thisistheshouldexpect:Thenumberofcomparisonsshouldbethelargestwhentheprobabilityofasuccessfulsearchis0,anditshouldbethesmallestwhentheprobabilityofasuccessfulsearchis1.)√Dropthefirstgadgetfromfloors「√nl2「√nlandsoonuntileitherthefloori「nladropfromthegadgetmalfunctionisreachedornofloorinthissequenceisencounteredbeforethetopofthe√√ √ buildingisreached.Intheformercase,thefloortobefoundishigherthan(i−1)「nlandthani「nl.So,dropthesecondgadgetfromfloors(i−1)「nl+1,(i−1)「nl+2,andsoonuntilthefirstflooradropfromthegadgetmalfunctionisreached.Thefloor√ √ √√immediatelypreceedingthatflooristhefloorinquestion.Ifnodropinthefirst-passsequenceresultedinthegadget’sfailure,thefloorinquestionis√√higherthani「nl,thelasttriedfloorofthatsequence.Hence,thesuccessiveexaminationoffloorsi「√nl1i「nl2andsoon√eitherafailureisregisteredorthelastfloorisreached.Thenumberoftimesthetwogadgetsaredroppeddoesn’texceed「√nl+「nl,whichputsitinO(√n).√43comparisons.Thealgorithmwill47−6+1=42trials:Inthefirstone,theGofthepatternwillbealignedagainstthefirstTofthetext;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.(Asaspecificexample,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.3Candesignamoreefficientalgorithmthantheonebasedonthebrute-forcestrategytosolvetheclosest-pairproblemfornpointsx1,...,xnontherealline?Letx1<x2<...<xnberealnumbersrepresentingcoordinatesofnvillageslocatedalongastraightroad.Apostofficeneedstobebuiltinoneofthesevillages.Designanefficientalgorithmtofindthepost-officelocationminimizingthedistancethevillagesandthepostoffice.Designanefficientalgorithmtofindthepost-officelocationminimizingthemaximumdistancefromavillagetothepostoffice.a.[>ThereareseveralalternativetodefineadistancepointsP1=(x1,y1)andP2=(x2,y2).Inparticular,theManhattanisdefinedasdM(P1,P2)=|x1−x2|+|y1−y2|.ProvethatdMsatisfiesthefollowingaxiomsthateverydistancefunctionmustsatisfy: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.OddpiefightTherearen≥3peoplepositionedinafield(Euclideanplane)sothathasauniquenearestneighbor.personhasacreampie.asignal,everybodyhurleshisorherpieatthenearestneighbor.Assumingthatnisoddandthatnobodycanmisshisorhertarget,trueorfalse:Thereremainsatleastonepersonnothitapie?[Car79].Theclosest-pairproblemcanbeposedink-dimensionalspaceinwhichheuidndsebnopsP1=(1,...,1)ndP11=1 k1,..,1)isdnds1 kIkd(P1,P11)=�区(x1−x11)2.s ss=1Whatisthetime-efficiencyclassofthebrute-forcealgorithmforthek-dimensionalclosest-pairproblem?Findthehullsofthefollowingsetsandidentifytheirextremepoints(iftheyalineasquaretheboundaryofasquareastraightlineDesignalinear-timealgorithmtodetermineextremepointsofthehullofasetofn>1pointsintheplane.Whatmodificationneedstobemadeinthebrute-forcealgorithmfortheproblemtohandlemorethanpointsonthesamestraightline?aprogramimplementingthebrute-forcealgorithmforthehullproblem.Considerthefollowingsmallinstanceofthelinearprogrammingproblem:maximize 3x+5ysubjectto x+y≤4x+3y≤6x≥0,y≥0intheCartesianplane,theproblem’sde-finedasthesetofpointssatisfyingalltheproblem’sconstraints.Identifytheregion’sextremepoints.Solvetheoptimizationproblemgivenusingthefollowingtheorem:Alinearprogrammingproblemwithanonemptyboundedfeasibleregionhasasolution,whichcanbefoundatoneoftheextremepointsofitsfeasibleregion.HintstoExercises3.3SortingnrealnumberscanbedoneinO(nlogn)time.a.Solvingtheproblemforn=2andn=3shouldleadtothecriticalinsight.b.Whereputthepostofficeifitwouldnottobeatoneofthevillagelocations?.krirtsiiii)ysngbicrptisflueu.theManhattandistance,thepointsinquestionaredefinedequation|x−0|+|y−0|=1.canstartthepointsinthepositivequadrantofthecoordinatesystem(i.e.,thepointsforwhichx,y≥0)andthentherestusingthesymmetries.Theassertionisfalse.canchoose,P1(0,0),P2(1,0)andfindP3tocompleteacounterexample.itmathematicalinduction.shouldbeafunctionofparameters:nandk.Aspecialcaseofthisproblem(fork=2)solvedinthetext.Reviewtheexamplesgiveninthesection.Someoftheextremepointsofahullareeasiertofindthanothers.IfthereareotherpointsofagivensetonthestraightlinethroughPiandPj,whichofallthesepointsneedtobepreservedforfurtherprocessing?programshouldforsetofndistinctpoints,includingsetswithcolinearpoints.a.Thesetofpointssatisfyinginequalityax+by≤cisthehalf-planeofthepointsononesideofthestraightlineax+by=c,includingallthepointsonthelineitself.Sketchsuchahalf-planeforeachoftheinequal-itiesandfindtheirintersection.Theextremepointsaretheverticesofthepolygonobtainedinparta.Computeandcomparetheoftheobjectivefunctionattheex-tremepoints.SolutionstoExercises3.3Sortthenumbersinascendingorder,computethedifferencesad-numbersinthesortedlist,andfindthesmallestdifference.IfsortingisdoneinO(nlogn)time,therunningtimeoftheentirealgorithmwillbeinO(nlogn)+Θ(n)+Θ(n)=O(nlogn).a.Ifputthepostofficeatlocationxi,thedistanceitnandallthepointsx1<x2<...<xnisgiventheformula1艺n nnxi|.Sincethenumberofpointsnstaysthesame,n1andminimize艺n |xj−xi|.toconsiderthecasesofandoddnseparately.Letnbeeven.Considerfirstthecaseofn=2.Thesum|x1−x|+|x2−x|isequaltox2−x1,thelengthoftheintervalwiththeendpointsatx1andx2,foranypointxofthisinterval(includingtheendpoints),anditislargerthanx2−x1foranypointxoutsideofthisinterval.Thisimpliesthatforanyevenn,thesumn区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-postofficedidn’ttobeatoneofthelocations.)Indeed,ifputthepostofficeatlocationxitotheleftofm,thelongestdistancefromalletohepteudben−i;hsdineismnilrterightmostamongpoints.Ifputthepostofficeatlocationxitotherightofm,thelongestdistancefromavillagetothepostofficewouldbexi−x1;thisdistanceisminimalfortheleftmostamongsuchpoints.AlgorithmPostOffice1(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−1ThetimeefficiencyofthisalgorithmisO(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,thepointsinquestionaredefinedtheequation|x−0|+|y−0|=1,i.e.,|x|+|y|=1.Thegraphofthisequationistheboundaryofthesquarewithitsverticesat(1,0),(0,1),(−1,0),and(−1,−1).theEuclideandistance,thepointsinquestionaredefinedtheequa-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