数据结构与算法分析 C++版答案

数据结构与算法分析C++版答案数据结构与算法分析C++版答案数据结构与算法分析C++版答案xxx公司数据结构与算法分析C++版答案文件编号：文件日期：修订次数：第1.0次更改批准审核制定方案设计，管理制度DataStructuresandAlgorithm习题答案Prefaceii1DataStructuresandAlgorithms12MathematicalPreliminaries53AlgorithmAnalysis174Lists,Stacks,andQueues235BinaryTrees326GeneralTrees407InternalSorting468FileProcessingandExternalSorting549Searching5810Indexing6411Graphs6912ListsandArraysRevisited7613AdvancedTreeStructures82i

iiContents14AnalysisTechniques8815LimitstoComputation94

PrefaceContainedhereinarethesolutionstoallexercisesfromthetextbookAPracticalIntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.InafewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresentedinthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithmstobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintendedanswer,ratherthanusableprograms.

1DataStructuresandAlgorithmsInstructor’snote:Unliketheotherchapters,manyofthequestionsinthischapterarenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtogetstudentsthinkingaboutdatastructuresissues.Thisquestiondoesnothaveaspecificrightanswer,providedthestudentkeepstothespiritofthequestion.Studentsmayhavetroublewiththeconceptof“operations.”Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepresentation.AgoodanswerisdescribedbyProject,whereasingly-linkedlistissuggested.Themoststraightforwardimplementationstoreseachdigitinitsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplicationareimplementedbywhatamountstograde-schoolarithmetic.Foraddition,simplymarchdowninparallelthroughthetwolistsrepresentingtheoperands,ateachdigitappendingtoanewlisttheappropriatepartialsumandbringingforwardacarrybitasnecessary.Formultiplication,combinetheadditionfunctionwithanewfunctionthatmultipliesasingledigitbyaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication(notreallypractical)orbythetraditionalΘ(logn)-timealgorithmbasedonthebinaryrepresentationoftheexponent.Discoveringthisfasteralgorithmwillbebeyondthereachofmoststudents,soshouldnotberequired.AsampleADTforcharacterstringsmightlookasfollows(withthenormalinterpretationofthefunctionnamesassumed).

Chap.1DataStructuresandAlgorithmsSomeInC++,thisis1fors1<s2;0fors1=s2;intstrcmp(Strings1,Strings2)One’scomplimentstoresthebinaryrepresentationofpositivenumbers,andstoresthebinaryrepresentationofanegativenumberwiththebitsinverted.Two’scomplimentisthesame,exceptthatanegativenumberhasitsbitsinvertedandthenoneisadded(forreasonsofefficiencyinhardwareimplementation).ThisrepresentationisthephysicalimplementationofanADTdefinedbythenormalarithmeticoperations,declarations,andothersupportgivenbytheprogramminglanguageforintegers.AnADTfortwo-dimensionalarraysmightlookasfollows.Matrixadd(MatrixM1,MatrixM2);Matrixmultiply(MatrixM1,MatrixM2);Matrixtranspose(MatrixM1);voidsetvalue(MatrixM1,introw,intcol,intval);intgetvalue(MatrixM1,introw,intcol);Listgetrow(MatrixM1,introw);

OneimplementationforthesparsematrixisdescribedinSectionAnotherimplementationisahashtablewhosesearchkeyisaconcatenationofthematrixcoordinates.Everyproblemcertainlydoesnothaveanalgorithm.AsdiscussedinChapter15,thereareanumberofreasonswhythismightbethecase.Someproblemsdon’thaveasufficientlycleardefinition.Someproblems,suchasthehaltingproblem,arenon-computable.Forsomeproblems,suchasonetypicallystudiedbyartificialintelligenceresearchers,wesimplydon’tknowasolution.Wemustassumethatby“algorithm”wemeansomethingcomposedofstepsareofanaturethattheycanbeperformedbyacomputer.Ifso,thananyalgorithmcanbeexpressedinC++.Inparticular,ifanalgorithmcanbeexpressedinanyothercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall(sufficientlygeneral)computerprogramminglanguagescomputethesamesetoffunctions.Theprimitiveoperationsare(1)addingnewwordstothedictionaryand(2)searchingthedictionaryforagivenword.Typically,dictionaryaccessinvolvessomesortofpre-processingofthewordtoarriveatthe“root”oftheword.Atwentypagedocument(singlespaced)islikelytocontainabout20,000words.Ausermaybewillingtowaitafewsecondsbetweenindividual“hits”ofmis-spelledwords,orperhapsuptoaminuteforthewholedocumenttobeprocessed.Thismeansthatacheckforanindividualwordcantakeabout10-20ms.Userswilltypicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscantakeacoupleofseconds.Thus,searchmustbemuchmoreefficientthaninsertion.Theusershouldbeabletofindacitybasedonavarietyofattributes(name,location,perhapscharacteristicssuchaspopulationsize).Theusershouldalsobeabletoinsertanddeletecities.Thesearethefundamentaloperationsofanydatabasesystem:search,insertionanddeletion.Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypicaluser.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory.Ifthedatabaseismeanttosupportrangequeriesandmassdeletions,theentireoperationmaybeallowedtotakelonger,perhapsontheorderofaminute.However,thetimespenttoprocessindividualcitieswithintherangemustbeappropriatelyreduced.Inpractice,thedatarepresentationwillneedtobesuchthatitaccommodatesefficientprocessingtomeetthesetimeconstraints.Inparticular,itmaybenecessarytosupportoperationsthatprocessrangequeriesefficientlybyprocessingallcitiesintherangeasabatch,ratherthanasaseriesofoperationsonindividualcities.Studentsatthislevelarelikelyalreadyfamiliarwithbinarysearch.Thus,theyshouldtypicallyrespondwithsequentialsearchandbinarysearch.Binarysearchshouldbedescribedasbettersinceittypicallyneedstomakefewercomparisons(andthusislikelytobemuchfaster).TheanswertothisquestionisdiscussedinChapter8.Typicalmeasuresofcostwillbenumberofcomparisonsandnumberofswaps.Testsshouldincluderunningtimingsonsorted,reversesorted,andrandomlistsofvarioussizes.

Chap.1DataStructuresandAlgorithmsThefirstpartiseasywiththehint,butthesecondpartisratherdifficulttodowithoutastack.a)boolcheckstring(stringS){intcount=0;for(inti=0;i<length(S);i++)if(S[i]==’(’)count++;if(S[i]==’)’){if(count==0)returnFALSE;count--;}}if(count==0)returnTRUE;elsereturnFALSE;}b)intcheckstring(StringStr){StackS;intcount=0;for(inti=0;i<length(S);i++)if(S[i]==’(’)(i);if(S[i]==’)’){if())returni;();}}if())return-1;elsereturn();}AnswerstothisquestionarediscussedinSection.Thisissomewhatdifferentfromwritingsortingalgorithmsforacomputer,sinceperson’s“workingspace”istypicallylimited,asistheirabilitytophysicallymanipulatethepiecesofpaper.Nonetheless,manyofthecommonsortingalgorithmshavetheiranalogstosolutionsforthisproblem.Mosttypicalanswerswillbeinsertionsort,variationsonmergesort,andvariationsonbinsort.AnswerstothisquestionarediscussedinChapter8.

2MathematicalPreliminaries(a)Notreflexiveifthesethasanymembers.Onecouldargueitissymmetric,antisymmetric,andtransitive,sincenoelementviolateanyoftherules.(b)Notreflexive(foranyfemale).Notsymmetric(considerabrotherandsister).Notantisymmetric(considertwobrothers).Transitive(forany3brothers).(c)Notreflexive.Notsymmetric,andisantisymmetric.Nottransitive(onlygoesonelevel).(d)Notreflexive(fornearlyallnumbers).Symmetricsincea+b=b+a,sonotantisymmetric.Transitive,butvacuouslyso(therecanbenodistincta,b,andcwhereaRbandbRc).(e)Reflexive.Symmetric,sonotantisymmetric.Transitive(butsortofvacuous).(f)Reflexive–checkallthecases.Sinceitisonlytruewhenx=y,itistechnicallysymmetricandantisymmetric,butrathervacuous.Likewise,itistechnicallytransitive,butvacuous.Ingeneral,provethatsomethingisanequivalencerelationbyprovingthatitisreflexive,symmetric,andtransitive.(a)Thisisanequivalencethateffectivelysplitstheintegersintooddandevensets.Itisreflexive(x+xisevenforanyintegerx),symmetric(sincex+y=y+x)andtransitive(sinceyouarealwaysaddingtwooddorevennumbersforanysatisfactorya,b,andc).(b)Thisisnotanequivalence.Tobeginwith,itisnotreflexiveforanyinteger.(c)Thisisanequivalencethatdividesthenon-zerorationalnumbersintopositiveandnegative.Itisreflexivesincex˙x>0.Itissymmetricsincexy˙=yx˙.Itistransitivesinceanytwomembersofthegivenclasssatisfytherelationship.5

Chap.2MathematicalPreliminaries(d)Thisisnotanequivalancerelationsinceitisnotsymmetric.Forexample,a=1andb=2.(e)Thisisaneqivalancerelationthatdividestherationalsbasedontheirfractionalvalues.Itisreflexivesinceforalla,=0.Itissymmetricsinceif=xthen=.x.Itistransitivesinceanytworationalswiththesamefractionalvaluewillyeildaninteger.(f)Thisisnotanequivalancerelationsinceitisnottransitive.Forexample,4.2=2and2.0=2,but4.0=4.Arelationisapartialorderingifitisantisymmetricandtransitive.(a)Notapartialorderingbecauseitisnottransitive.(b)Isapartialorderingbacauseitisantisymmetric(ifaisanancestorofb,thenbcannotbeanancestorofa)andtransitive(sincetheancestorofanancestorisanancestor).(c)Isapartialorderingbacauseitisantisymmetric(ifaisolderthanb,thenbcannotbeolderthana)andtransitive(sinceifaisolderthanbandbisolderthanc,aisolderthanc).(d)Notapartialordering,sinceitisnotantisymmetricforanypairofsisters.(e)Notapartialorderingbecauseitisnotantisymmetric.(f)Thisisapartialordering.Itisantisymmetric(noviolationsexist)andtransitive(noviolationsexist).Atotalorderingcanbeviewedasapermuationoftheelements.Sincetherearen!permuationsofnelements,theremustben!totalorderings.ThisproposedADTisinspiredbythelistADTofChapter4.voidclear();voidinsert(int);voidremove(int);voidsizeof();boolisEmpty();boolisInSet(int);ThisproposedADTisinspiredbythelistADTofChapter4.NotethatwhileitissimiliartotheoperationsproposedforQuestion,thebehaviourissomewhatdifferent.voidclear();voidinsert(int);voidremove(int);voidsizeof();

7boolisEmpty();longifact(intn){Theiterativeversionrequirescarefulexaminationtounderstandwhatitdoes,ortohaveconfidencethatitworksasclaimed.(b)FibrissomuchslowerthanFibibecauseFibrre-computesthebulkoftheseriestwicetogetthetwovaluestoadd.Whatismuchworse,therecursivecallstocomputethesubexpressionsalsore-computethebulkoftheseries,anddosorecursively.Theresultisanexponentialexplosion.Incontrast,Fibicomputeseachvalueintheseriesexactlyonce,andsoitsrunningtimeisproportionalton.voidGenTOH(intn,POLEgoal,POLEt1,POLEt2,POLE*curr){if(curr[n]==goal)Putothersont1.GenTOH(n-1,t1,goal,t2,curr);move(t2,goal);GenTOH(n-1,goal,t1,t2,curr);Intheory,thisseriesapproaches,butneverreaches,0,soitwillgoonforever.Inpractice,thevalueshouldbecomecomputationallyindistinguishablefromzero,andterminate.However,thisisterribleprogrammingpractice.

Chap.2MathematicalPreliminariesvoidallpermute(intarray[],intn,intcurrpos){if(currpos==(n-1)}{printout(array);return;}for(inti=currpos;i<n;i++){swap(array,currpos,i);allpermute(array,n,currpos+1);swap(array,currpos,i);Theideaistheprintouttheelementsattheindicatedbitpositionswithintheset.Ifwedothisforvaluesintherange0to2n.1,wewillgettheentirepowerset.voidpowerset(intn){for(inti=0;i<ipow(2,n);i++){for(intj=0;j<n;j++)if(bitposition(n,j)==1)cout<<j<<"";cout<<endl;}Proof:Assumethatthereisalargestprimenumber.CallitPn,thenthlargestprimenumber,andlabelalloftheprimesinorderP1=2,P2=3,andsoon.Now,considerthenumberCformedbymultiplyingallofthenprimenumberstogether.ThevalueC+1isnotdivisiblebyanyofthenprimenumbers.C+1isaprimenumberlargerthanPn,acontradiction.Thus,weconcludethatthereisnolargestprimenumber..Note:Thisproblemisharderthanmostsophomorelevelstudentscanhandle.√Proof:Theproofisbycontradiction.Assumethat2isrational.Bydefinition,thereexistintegerspandqsuchthat√p2=,qwherepandqhavenocommonfactors(thatis,thefractionp/qisinlowestterms).Bysquaringbothsidesanddoingsomesimplealgebraicmanipulation,weget2p2=2q222q=pSincep2mustbeeven,pmustbeeven.Thus,

9222q=4(p)222q=2(p)2Thisimpliesthatq2isalsoeven.Thus,pandqarebotheven,whichcontra√dictstherequirementthatpandqhavenocommonfactors.Thus,2mustbeirrational..Theleftmostsummationsumstheintegersfrom1ton.Thesecondsummationmerelyreversesthisorder,summingthenumbersfromn.1+1=ndownton.n+1=1.Thethirdsummationhasavariablesubstitutionofi,withacorrespondingsubstitutioninthesummationbounds.Thus,itisalsothesummationofn.0=nton.(n.1)=1.Proof:(a)Basecase.Forn=1,12=[2(1)3+3(1)2+1]/6=1.Thus,theformulaiscorrectforthebasecase.(b)InductionHypothesis.2(n.1)3+3(n.1)2+(n.1)i2=.6i=1(c)InductionStep.i2i2+n2=i=1i=12(n.1)3+3(n.1)2+(n.1)2=+n62n3.6n2+6n.2+3n2.6n+3+n.12=+n62n3+3n2+n=.6Thus,thetheoremisprovedbymathematicalinduction..Proof:(a)Basecase.Forn=1,1/2=1.1/2=1/2.Thus,theformulaiscorrectforthebasecase.(b)InductionHypothesis.11=1..2i=1

Chap.2MathematicalPreliminaries(c)InductionStep.111=+iin222i=1i=111=1.+n221=1..n2Thus,thetheoremisprovedbymathematicalinduction..Proof:(a)Basecase.Forn=0,20=21.1=1.Thus,theformulaiscorrectforthebasecase.(b)InductionHypothesis.2i=2n.1.i=0(c)InductionStep.2i=2i+2ni=0i=0n=2n.1+2n+1.1=2.Thus,thetheoremisprovedbymathematicalinduction..Theclosedformsolutionis3n+,whichIdeducedbynotingthat3F(n).2n+1.3F(n)=2F(n)=3.Now,toverifythatthisiscorrect,usemathematicalinductionasfollows.Forthebasecase,F(1)=3=.2Theinductionhypothesisisthat=(3n.3)/2.i=1So,3i=3i+3ni=1i=13n.3n=+32n+1.33=.2Thus,thetheoremisprovedbymathematicalinduction.

11nTheorem(2i)=n2+n.i=1(a)Proof:WeknowfromExamplethatthesumofthefirstnoddnumbersisithevennumberissimplyonegreaterthantheithoddnumber.Sinceweareaddingnsuchnumbers,thesummustbengreater,orn2+n..(b)Proof:Basecase:n=1yields2=12+1,whichistrue.InductionHypothesis:2i=(n.1)2+(n.1).i=1InductionStep:Thesumofthefirstnevennumbersissimplythesumofthefirstn.1evennumbersplusthenthevennumber.2i=(2i)+2ni=1i=1=(n.1)2+(n.1)+2n=(n2.2n+1)+(n.1)+2n=n2.n+2n=n2+n.nThus,bymathematicalinduction,2i=n2+n..i=1Proof:52Basecase.Forn=1,Fib(1)=1<n=2,Fib(2)=1<(5).3Thus,theformulaiscorrectforthebasecase.InductionHypothesis.Forallpositiveintegersi<n,5iFib(i)<().3InductionStep.Fib(n)=Fib(n.1)+Fib(n.2)and,bytheInductionHypothesis,Fib(n.1)<(5)andFib(n.2)<(5)3355Fib(n)<()+()33555<()+()333

Chap.2MathematicalPreliminaries85=()3355<()2()33n5=.3Thus,thetheoremisprovedbymathematicalinduction..Proof:12(1+1)23=(a)Basecase.Forn=1,1=1.Thus,theformulaiscorrect4forthebasecase.(b)InductionHypothesis.22(n.1)ni3=.4i=0(c)InductionStep.n2(n.1)n2i33=+n4i=02n4.2n3+n3=+n4n4+2n3+n2=4n2(n2+2n+2)=42n2(n+1)=4Thus,thetheoremisprovedbymathematicalinduction..(a)Proof:Bycontradiction.Assumethatthetheoremisfalse.Then,eachpigeonholecontainsatmost1pigeon.Sincetherearenholes,thereisroomforonlynpigeons.Thiscontradictsthefactthatatotalofn+1pigeonsarewithinthenholes.Thus,thetheoremmustbecorrect..(b)Proof:i.Basecase.Foronepigeonholeandtwopigeons,theremustbetwopigeonsinthehole.ii.InductionHypothesis.Fornpigeonsinn.1holes,someholemustcontainatleasttwopigeons.

13iii.InductionStep.Considerthecasewheren+1pigeonsareinnholes.Eliminateoneholeatrandom.Ifitcontainsonepigeon,eliminateitaswell,andbytheinductionhypothesissomeotherholemustcontainatleasttwopigeons.Ifitcontainsnopigeons,thenagainbytheinductionhypothesissomeotherholemustcontainatleasttwopigeons(withanextrapigeonyettobeplaced).Ifitcontainsmorethanonepigeon,thenitfitstherequirementsofthetheoremdirectly..(a)Whenweaddthenthline,wecreatennewregions.But,westartwithoneregionevenwhentherearenolines.Thus,therecurrenceisF(n)=F(n.1)+n+1.(b)ThisisequivalenttothesummationF(n)=1+i=1ni.(c)Thisisclosetoasummationwealreadyknow(equation.Basecase:T(n.1)=1=1(1+1)/2.Inductionhypothesis:T(n.1)=(n.1)(n)/2.Inductionstep:T(n)=T(n.1)+n=(n.1)(n)/2+n=n(n+1)/2.Thus,thetheoremisprovedbymathematicalinduction.Ifweexpandtherecurrence,wegetT(n)=2T(n.1)+1=2(2T(n.2)+1)+1)=4T(n.2+2+1.ExpandingagainyieldsT(n)=8T(n.3)+4+2+1.Fromthis,wecandeduceapatternandhypothesizethattherecurrenceisequivalenttonT(n)=.12i=2n.1.i=0Toprovethisformulaisinfacttheproperclosedformsolution,weusemathematicalinduction.Basecase:T(1)=21.1=1.

14Chap.2MathematicalPreliminariesInductionhypothesis:T(n.1)=.1.Inductionstep:T(n)=2T(n.1)+1=2.1)+1=2n.1.Thus,asprovedbymathematicalinduction,thisformulaisindeedthecorrectclosedformsolutionfortherecurrence.(a)Theprobabilityisforeachchoice.(b)Theaveragenumberof“1”bitsisn/2,sinceeachpositionhasprobabilityofbeing“1.”(c)Theleftmost“1”willbetheleftmostbit(callitposition0)withprobability;inposition1withprobability,andsoon.Thenumberofpositionswemustexamineis1inthecasewheretheleftmost“1”isinposition0;2whenitisinposition1,andsoon.Thus,theexpectedcostisthevalueofthesummationni.2ii=1Theclosedformforthissummationis2.n+2,orjustlessthantwo.2nThus,weexpecttovisitonaveragejustlessthantwopositions.(Studentsatthispointwillprobablynotbeabletosolvethissummation,anditisnotgiveninthebook.)Thereareatleasttwowaystoapproachthisproblem.Oneistoestimatethevolumedirectly.Thesecondistogeneratevolumeasafunctionofweight.Thisisespeciallyeasyifusingthemetricsystem,assumingthatthehumanbodyisroughlythedensityofwater.Soa50Kilopersonhasavolumeslightlylessthan50liters;a160poundpersonhasavolumeslightlylessthan20gallons.(a)Imagerepresentationsvaryconsiderably,sotheanswerwillvaryasaresult.Oneexampleansweris:ConsiderVGAstandardsize,full-color(24bit)images,whichis3×640×480,orjustlessthan1Mbyteperimage.Thefulldatabaserequiressome30-35CDs.(b)Sinceweneeded30-35CDsbefore,compressingbyafactorof10isnotsufficienttogetthedatabaseontooneCD.[Notethatifthestudentpickedasmallerformat,suchasestimatingthesizeofa“typical”gifimage,theresultmightwellfitontoasingleCD.]

(IsawthisprobleminJohnBentley’sProgrammingPearls.)Approach1:ThemodelisDepthXWidthXFlowwhereDepthandWidthareinmilesandFlowisinmiles/day.TheMississippiriveratitsmouthisabout1/4milewideand100feet(1/50mile)deep,withaflowofaround15miles/hour=360miles/day.Thus,theflowisabout2cubicmiles/day.Approach2:Whatgoesoutmustequalwhatgoesin.ThemodelisAreaXRainfallwhereAreaisinsquaremilesandRainfallisin(linear)miles/day.TheMississipiwatershedisabout1000X1000miles,andtheaveragerainfalisabout40inches/year≈.1inches/day≈.000002miles/day(2X.Thus,theflowisabout2cubicmiles/day.NotethatthestudentshouldNOTbeprovidinganswersthatlookliketheyweredoneusingacalculator.Thisissupposedtobeanexerciseinestimation!Theamountofthemortgageisirrelevant,sincethisisaquestionaboutrates.However,togivesomenumberstohelpyouvisualizetheproblem,picka$100,000mortgage.Theup-frontchargewouldbe$1,000,andthesavingswouldbe1/4%eachpaymentoverthelifeofthemortgage.Themonthlychargewillbeontheremainingprinciple,beingthehighestatfirstandgraduallyreducingovertime.But,thathaslittleeffectforthefirstfewyears.Atthegrossestapproximation,youpaid1%tostartandwillsave1/4%eachyear,requiring4years.Tobemoreprecise,8%of$100,000is$8,000,while73/4%is$7,750(forthefirstyear),withalittlelessinterestpaid(andthereforesaved)infollowingyears.Thiswillrequireapaybackperiodofslightlyover4yearstosave$1000.Ifthemoneyhadbeeninvested,thenin5yearstheinvestmentwouldbeworthabout$1300(at5wouldbecloseto51/2years.Diskdriveseektimeissomewherearound10millisecondsoralittlelessin2000.RAMmemoryrequiresaround50nanoseconds–muchlessthanamicrosecond.Giventhatthereareabout30millionsecondsinayear,amachinecapableofexecutingat100MIPSwouldexecuteabout3billionbillion(3.1018)instructionsinayear.Typicalbookshavearound500pages/inchofthickness,soonemillionpagesrequires2000inchesor150-200feetofbookshelf.Thiswouldbeinexcessof50typicalshelves,or10-20bookshelves.Itiswithintherealmofpossibilitythatanindividualhomehasthismanybooks,butitisratherunusual.Atypicalpagehasaround400words(bestwaytoderivethisistoestimatethenumberofwords/lineandlines/page),andthebookhasaround500pages,sothetotalisaround200,000words.

16Chap.2MathematicalPreliminariesAnhourhas3600seconds,soonemillionsecondsisabitlessthan300hours.Agoodestimaterwillnoticethat3600isabout10%greaterthan3333,sotheactualnumberofhoursisabout10%lessthan300,orcloseto270.(Therealvalueisjustunder278).Ofcourse,thisisjustover11days.Wellover100,000,dependingonwhatyouwishtoclassifyasacityortown.Therealquestioniswhattechniquethestudentuses.(a)Thetimerequiredis1minuteforthefirstmile,then60/59minutesforthesecondmile,andsoonuntilthelastmilerequires60/1=60minutes.Theresultisthefollowingsummation.606060/i=601/i=60H60.i=1i=1(b)Thisisactuallyquiteeasy.Themanwillneverreachhisdestination,sincehisspeedapproacheszeroasheapproachestheendofthejourney.

3AlgorithmAnalysisNotethatnisapositiveinteger.5nlognismostefficientforn=1.2nismostefficientwhen2≤n≤4.10nismostefficientforalln>5.20nand2narenevermoreefficientthantheotherchoices.Bothlog3nandlog2nwillhavevalue0whenn=1.Otherwise,2isthemostefficientexpressionforalln>1.2/323n2log3nlog2nn20n4nn!.(a)n+6inputs(anadditiveamount,independentofn).(b)8ninputs(amultiplicativefactor).(c)64ninputs.100n.10n.√About(actually,3100n).n+6.(a)Thesequestionsarequitehard.Iff(n)=2n=x,thenf(2n)=22n=2(2n)2=x.(b)Theansweris2(nlog23).Extendingfrompart(a),weneedsomewaytomakethegrowthrateevenhigher.Inparticular,weseeksomewaytolog23=maketheexponentgoupbyafactorof3.Notethat,iff(n)=n)=2log23log23=3xy,thenf(2nn.So,wecombinethisobservationwithpart(a)togetthedesiredanswer.First,weneedtofindconstantscandnosuchthat1≤c×1forn>n0.Thisistrueforanypositivevaluec<1andanypositivevalueofn0(sincenplaysnoroleintheequation).Next,weneedtofindconstantscandn0suchthat1≤c×nforn>n0.Thisistruefor,say,c=1andn0=1.17

18Chap.3AlgorithmAnalysisOthervaluesforn0andcarepossiblethanwhatisgivenhere.(a)TheupperboundisO(n)forn0>0andc=c1.ThelowerboundisΩ(n)forn0>0andc=c1.(b)TheupperboundisO(n3)forn0>c3andc=c2+1.ThelowerboundisΩ(n3)forn0>c3andc=c2.(c)TheupperboundisO(nlogn)forn0>c5andc=c4+1.ThelowerboundisΩ(nlogn)forn0>c5andc=c4.(d)TheupperboundisO(2n)forn0>c7100andc=c6+lowerboundisΩ(2n)forn0>c7100andc=c6.(100isusedforconveniencetoinsurethat2n>n6)(a)f(n)=Θ(g(n))sincelogn2=2logn.(b)f(n)isinΩ(g(n))sincencgrowsfasterthanlogncforanyc.(c)f(n)isinΩ(g(n)).Dividingbothsidesbylogn,weseethatlogngrowsfasterthan1.(d)f(n)isinΩ(g(n)).Ifwetakebothf(n)andg(n)asexponentsfor2,2weget2nononesideand2log2n=(2logn)2=n2ontheother,andngrowsslowerthan2n.(e)f(n)isinΩ(g(n)).Dividingbothsidesbylognandthrowingawaytheloworderterms,weseethatngrowsfasterthan1.(f)f(n)=Θ(g(n))sincelog10and10arebothconstants.2(g)f(n)isinΩ(g(n))since2ngrowsfasterthan10n.(h)f(n)isinO(g(n)).3n=,andifwedividebothsidesby2n,weseethatgrowsfasterthan1.(a)ThisfragmentisΘ(1).(b)ThisfragmentisΘ(n)sincetheouterloopisexecutedaconstantnumberoftimes.(c)ThisfragmentisΘ(n2)sincetheloopisexecutedn2times.(d)ThisfragmentisΘ(n2logn)sincetheouterforloopcostsnlognforeachexecution,andisexecutedntimes.Theinnerloopisdominatedbythecalltosort.(e)Foreachexecutionoftheouterloop,theinnerloopisgenerat