巴斯-计算机算法-第3版-习题解答1

ComputerAlgorithms,ThirdEdition,

SolutionstoSelectedExercises

SaraBaase

AllenVanGelder

February25,2000

INTRODUCTION

ThismanualcontainssolutionsfortheselectedexercisesinComputerAlgorithms:IntroductiontoDesignandAnaly­

sis,thirdedition,bySaraBaaseandAllenVanGelder.

Solutionsmanualsareintendedprimarilyforinstructors,butitisafactthatinstructorssometimesputcopiesin

campuslibrariesorontheirwebpagesforusebystudents.Forinstructorswhoprefertohavestudentsworkon

problemswithoutaccesstosolutions,wehavechosennottoincludealltheexercisesfromthetextinthismanual.The

includedexercisesarelistedinthetableofcontents.Roughlyeveryotherexerciseissolved.

Someofthesolutionswerewrittenspecificallyforthismanual;othersareadaptedfromsolutionssetshandedout

tostudentsinclasseswetaught(writtenbyourselves,teachingassistants,andstudents).

Thusthereissomeinconsistencyinthestyleandamountofdetailinthesolutions.Somemayseemtobeaddressed

toinstructorsandsometostudents.Wedecidednottochangetheseinconsistencies,inpartbecausethemanualwillbe

readbyinstructorsandstudents.Insomecasesthereismoredetail,explanation,orjustificationthanastudentmight

beexpectedtosupplyonahomeworkassignment.

Manyofthesolutionsusethesamepseudocodeconventionsusedinthetext,suchas:

1.Blockdelimiters"and")“)areomitted.Blockboundariesareindicatedbyindentation.

2.Thekeywordstaticisomittedfrommethod(functionandprocedure)declarations.Allmethodsdeclaredin

thesolutionsarestatic.

3.Classnamequalifiersareomittedfrommethod(functionandprocedure)calls.Forexample,x=cons(z/

x)mightbewrittenwhentheJavasyntaxrequiresx=IntList.cons(z,x).

4.Keywordstocontrolvisibility,public,private,andprotected,areomitted.

5.Mathematicalrelationaloperators“区,“"•二，"and"""areusuallywritten,insteadoftheirkeyboardversions.

Relationaloperatorsareusedontypeswherethemeaningisclear,suchasString,eventhoughthiswouldbe

invalidsyntaxinJava.

WethankChuckSandersforwritingmostofthesolutionsforChapter2andforcontributingmanysolutionsin

Chapter14.WethankLuoHong,agraduatestudentatUCSantaCruz,forassistingwithseveralsolutionsinChapters

9,10,11,and13.

Inafewcasesthesolutionsgiveninthismanualareaffectedbycorrectionsandclarificationstothetext.These

casesareindicatedatthebeginningofeachaffectedsolution.Theup-to-dateinformationoncorrectionsandclarifica­

tions,alongwithothersupplementarymaterialsforstudents,canbefoundattheseInternetsites:

/cseng/authors/baase

/faculty/baase

/personnel/facuity/avg.html

©Copyright2000SaraBaaseandAllenVanGelder.Allrightsreserved.

Permissionisgrantedforcollegeanduniversityinstructorstomakeareasonablenumberofcopies,freeofcharge,

asneededtoplanandadministertheircourses.Instructorsareexpectedtoexercisereasonableprecautionsagainst

further,unauthorizedcopies,whetheronpaper,electronic,orothermedia.

PermissionisalsograntedforAddison-Wesley-Longmaneditorial,marketing,andsalesstafftoprovidecopies

freeofchargetoinstructorsandprospectiveinstructors,andtomakecopiesfortheirownuse.

Othercopies,whetherpaper,electronic,orothermedia,areprohibitedwithoutpriorwrittenconsentoftheauthors.

ListofSolvedExercises

1AnalyzingAlgorithmsandProblems:PrinciplesandExamples

1.1..11.1331.2851.447

1.2..21.1541.3161.467

1.4..21.1841.3361.477

1.6..21.2041.3561.487

1.8..31.2241.3761.508

1.10......31.2341.396

1.12......31.2551.427

DataAbstractionandBasicDataStructures9

2.2..92.892.1412

2.4..92.10112.1613

2.6..92.12112.1814

RecursionandInduction17

3.2173.6173.1018

3.4173.8183.1218

Sorting19

4.2194.21214.37244.5326

4.4194.23214.40244.5527

4.6194.25224.42244.5727

4.9..194.26224.44254.5928

4.11......194.27234.45254.6128

4.13......204.29234.46254.6329

4.15......204.31234.48254.6529

4.17......204.34244.4925

4.19......214.35244.5126

SelectionandAdversaryArguments31

5.2..315.8335.14345.2135

5.4..325.10345.16345.2236

5.6..325.12345.19355.2437

DynamicSetsandSearching39

6.1..396.12416.24476.3649

6.2..396.14436.26476.3749

6.4..406.16456.28476.4050

6.6..406.18456.3047

6.8..416.20456.3248

6.10......416.22466.3449

ivListofSolvedExercises

7GraphsandGraphTraversals

745372874059

7.151

z653z3o57749

7.35115

8533257

7.45174359

72054z3457

7.6517456O

72273558

7.8517476O

72454z3759

7.1052I

7275773959z496

7.1252

8GraphOptimizationProblemsandGreedyAlgorithms63

8.1638.8648.16......658.24......67

648.18......65

8.3638.108.26......67

8.5638.12648.20......65

8.7648.14648.22......678.27......67

9TransitiveClosure,All-PairsShortestPaths69

9.2699.7719.12......729.18....,.72

9.4709.8719.14......72

9.6719.10719.16......72

10DynamicProgramming73

10.27310.97310.16.....7510.23.....78

10.47310.107410.18.....7610.26.....79

10.57310.127510.19.....77

10.77310.147510.21.....78

11StringMatching81

11.18111.88411.17.....8411.25.....86

11.28111.108411.19.....85

11.48111.128411.21.....85

11.68311.158411.23.....85

12PolynomialsandMatrices87

12.28712.88712.14.....88

12.48712.108712.16.....88

12.68712.128812.17.....88

13NP-CompleteProblems89

13.28913.149213.26.....9313.37.....96

13.48913.169213.28.....9313.39.....96

13.69113.189213.30...9413.42.....98

13.89113.209313.32.....9413.44.....99

13.109113.219313.34.....9613.47.....99

13.129113.239313.35.....9613.49.....99

ListofSolvedExercises

13.51.....9913.54.....10013.57.....10013.61.....101

13.53.....10013.55.....10013.59.....101

14ParallelAlgorithms103

14.2......10314.10.....10414.18.....10514.25.....106

14.4...一.10314.11.....10414.19.....10614.27.....107

14.5...一.10314.13.....10414.20.....10614.29.....107

14.7......10414.14.....10514.22.....10614.30.....108

14.8......10414.16.....10514.24.....10614.32.....108

viListofSolvedExercises

Chapter1

AnalyzingAlgorithmsandProblems:PrinciplesandExamples

Section1.2：JavaasanAlgorithmLanguage

1.1

Itiscorrectforinstancefieldswhosetypeisaninnerclasstobedeclaredbeforethatinnerclass(asinFigure1.2in

thetext)orafter(ashere).AppendixA.7givesanalternativetospellingoutalltheinstancefieldsinthecopymethods

(functions).

classPersonal

f

publicstaticclassName

f

StringfirstName;

StringmiddleName;

StringlastName;

publicstaticNamecopy(Namen)

f

Namen2;

n2.firstName=n.firstName;

n2.middleName=n.middleName;

n2.lastName=n.lastName;

returnn2;

publicstaticclassAddress

f

Stringstreet;

Stringcity;

Stringstate;

publicstaticAddresscopy(Addressa)；/*similartoName.copy()*/|

publicstaticclassPhoneNumber

r

intareaCode;

intprefix;

intnumber;

publicstaticPhoneNumbercopy(PhoneNumbern)；/*similartoName.copy()*/%

r

Namename;

Addressaddress;

PhoneNumberphone;

StringeMail;

publicstaticPersonalcopy(Personalp);

r

Personalp2;

p2.name=Name.copy();

p2.address=Address.copy(p.address);

p2.phone=PhoneNumber.copy(p.phone);

p2.eMail=p.eMail;

returnp2;

2Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples

Section1.3：MathematicalBackground

1.2

For0<n,wehave

in-1\_(n-1)!_-1]!(〃一自

\k)~丽~1~而三电！

(ft_1、_|n-11!_

\k1/Ik1)!|nk[!k\\n

Addthemgiving:

ln-l!!(n|fn\

k\\n^k\!yk；

For0「〃「kweusethefactthat|-0whenevera-'b.(Thereisnowaytochoosemoreelementsthantherearein

thewholeset.)Thus|晨)-0inallthesecases.IandI*areboth0,confirmingtheequation.Ifn-k,

I；}|andIareboth1,againconfirmingtheequation.(Weneedthefactthat0!11when〃一攵一1.)

L4

Itsufficestoshow:

Iogcxlog/,C-log^x.

Considerbraisedtoeachside.

bleflside.(•^log^cjlog.-x.logx

-ccx

^rightside-^log^.v_(

Soleftside=rightside.

1.6

Letx-pg!n1CLThesolutionisbasedonthefactthat2X1-'/H1•:2X.

x=0;

twoToTheX=1;

while(twoToTheX<n+1)

x+=1;

twoToTheX*=2;

returnx;

Thevaluescomputedbythisprocedureforsmallnandtheapproximatevaluesoflg[n+-1)are:

nX1g：n*1)

000.0

111.0

221.6

322.0

432.3

532.6

632.8

733.0

843.2

943.3

Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples3

1.8

Pr\SandT)Pr(SlPr^Tl

PrlS|T)一Pi\S\

-Pr\T{­-Pr\T[-

Thesecondequationissimilar.

1.10

WeknowABandD'：'C.Bydirectcounting:

PrlA<CandA-andD《Ci5/245

Pr\ACC

Pr\A<BandD<"Cl67246

Pr\ACDCCandAeBl3.'2431

eD4《BandOe。-——"__

Pr\ACBandD<C|?24"62

PrlAeBCCandQe。3/2431

Pr\BCCABandDCC)一—■一

P八AeBandDCCl6/2462

1/24_

PrB-DA《BandDdO」

Pr\ABandD-'C\6/24-6

1.12

Weassumethattheprobabilityofeachcoinbeingchosenis1/3,thattheprobabilitythatitshows“heads“afterbeing

flippedis1/2andthattheprobabilitythatitshows"tails“afterbeingflippedis1/2.Callthecoins/A,B,andC.Define

theelementaryevents,eachhavingprobability1/6,asfollows.

AHAischosenandflippedandcomesout“heads”.

ATAischosenandflippedandcomesout“tails”.

BHBischosenandflippedandcomesout“heads”.

BTBischosenandflippedandcomesout“tails”.

CHCischosenandflippedandcomesout“heads”

CTCischosenandflippedandcomesout“tails".

a)BHandCHcauseamajoritytobe“heads”，sotheprobabilityis1/3.

b)Noeventcausesamajoritytobe“heads"，sotheprobabilityis0.

c)AH,BH,CHandCTcauseamajoritytobe"heads”,sotheprobabilityis2/3.

1.13

Theentryinrowi,columnjistheprobabilitythatD,willbeatD；.

221812

36-3636

122216

--

363636

1212422

183636-

--

3620

76

22

--

36

NotethatD\beats。2,。2beatsD3,D3beats£)4,andD4beatsD].

4Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples

1.153.

Theproofisbyinductiononn,theupperlimitofthesum.Thebasecaseis0.Then£3i2-0,and2"，•J~=0.

Sotheequationholdsforthebasecase.For-0,assumetheformulaholdsforn1.

n

£?_层h?二1；工3〃二1二山4n

丁£6

・1

2/-6〃2-6〃―24-3〃2-6〃4-3—〃-1

2/-3〃2―n6〃22/73—3〃2—〃

-一-

666

1.18

ConsideranytworealswCz.Weneedtoshowthatf\vv)f(z\；thatis,f[z[f[vv),0.Sincef\x\isdifferentiable,

itiscontinuous.WecallupontheMeanValueTheorem(sometimescalledtheTheoremoftheMean),whichcanbe

foundinanycollegecalculustext.Bythistheoremthereissomepointy,suchthatw''yz,forwhich

[Zwj

Bythehypothesisofthelemma,/1yl>0.Also,Izvv)>0.Therefore,f(z)f\w\>0.

1.20

Letlabbreviatethephrase,4tislogicallyequivalentto”.WeusetheidentityrrA-Aasneeded.

糊4M>B[才M.lx^\A\xl,所疝(byEq.1.24)

=IHVBlxjj(byEq.1.21)

=力I(byDeMorgan'slaw,Eq.1.23).

Section1.4：AnalyzingAlgorithmsandProblems

1.22

Thetotalnumberofoperationsintheworstcaseis472-2;theyare:

ComparisonsinvolvingK:n

Comparisonsinvolvingindex:nII

Additions:n

Assignmentstoindex:nI1

1.23

a)

if(a<b)

if(b<c)

median=b;

elseif(a<c)

median=c;

else

median=a;

elseif(a<c)

median=a;

elseif(b<c)

median=c;

else

median=b;

Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples5

b)Disthesetofpermutationsofthreeitems.

c)Worstcase=3;average=21.

d)Threecomparisonsareneededintheworstcasebecauseknowingthemedianofthreenumbersrequiresknowing

thecompleteorderingofthenumbers.

1.25

Solution1.Pairuptheentriesandfindthelargerofeachpair;ifnisodd,oneelementisnotexamined|n'?\

comparisons).ThenfindthemaximumamongthelargerelementsusingAlgorithm1.3,includingtheunexamined

elementifnisodd(J112]-1comparisons).Thisisthelargestentryintheset.Thenfindtheminimumamong

thesmallerelementsusingtheappropriatemodificationofAlgorithm1.3,againincludingtheunexaminedelementif

nisodd(|l/iI1j/2]1comparisons).Thisisthesmallestentryintheset.Whethernisoddoreven,thetotalis

|-1:.Thefollowingalgorithminterleavesthethreesteps.

/**Precondition:n>0.*

if(odd(n))

min=E[n-1];

max=E[n-1];

elseif(E[n-2]<E[n-1])

min=E[n-2];

max=E[n-1];

else

max=E[n-2];

min=E[n-1];

for(i=0;i<=n-3;i=i+2)

if(E[i]<E[i+1])

if(E[i]<min)min=E[i]；

if(E[i+1]>max)max=E[i+1];

else

if(E[i]>max)max=E[i];

if(E[i+1]<min)min=E[i+1];

Solution2.WhenweassignthisproblemaftercoveringDivideandConquersortingalgorithmsinChapter4,many

studentsgivethefollowingDivideandConquersolution.(Butmostofthemcannotshowformallythatitdoesroughly

3〃,2comparisons.)

Ifthereareatmosttwoentriesintheset,comparethemtofindthesmallerandlarger.Otherwise,breakthesetin

halves,andrecursivelyfindthesmallestandlargestineachhalf.Thencomparethelargestkeysfromeachhalftofind

thelargestoverall,andcomparethesmallestkeysfromeachhalftofindthesmallestoverall.

AnalysisofSolution2requiresmaterialintroducedinChapter3.Therecuirenceequationforthisprocedure,

assumingnisapowerof2,is

Winj=1for/?=2

W\n[-2WI-2forn>2

Therecursiontreecanbeevaluateddirectly.Itisimportantthatthenonrecursivecostsinthen'lleavesofthistree

are1each.Thenonrecursivecostsinthe〃，2-1internalnodesare2each.Thisleadstothetotalof3〃，2—2forthe

specialcasethatnisapowerof2.Morecarefulanalysisverifiestheresult「3〃’2-2"foralln.Theresultcanalsobe

provenbyinduction.

Section1.5：ClassifyingFunctionsbyTheirAsymptoticGrowthRates

1.28

lrim-PI川-r--i.im+等+…4券谭）一仅＞0.

n

6Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples

1.31

Thesolutionherecombinesparts(a)and(b).Thefunctionsonthesamelineareofthesameasymptoticorder.

IglgH

lg〃・In

、所

n

/£

n2-Ign

n3

〃一九3+7〃5

2«-12/:

n\

1.33

Let/-n.Forsimplicityweshowacounter-exampleinwhichanonmonotonicfunctionisused.Considerthe

functionh\nI:

nforoddn

(1forevenn

Clearlyh\n：「O\/In：：.But加加？。sohn\「0f\：.Therefore,h\n\「Of\-0/1A/：I.Itremainsto

showthath\n\iZo\Butthisfollowsbythefactthath\nl-1foroddintegers.

Withmoredifficultyh\canbeconstructedtobemonotonic.Forall%1,leth\beconstantontheintervalkk•'

1

n''i\k¥IFr-1)andleth\—内onthisinterval.Thuswhen〃—/，人(小'/]-1,butwhenn—(k-1)^'1,

h\n[ff\riy-//(l〃：11),whichtendsto0asngetslarge.

1.35

Property1:SupposefC01gl.Therearec0and〃osuchthatforn>〃o,f\n\<2cglny.Thenforn>〃o,

gi川(n[.Theotherdirectionisprovedsimilarly.

Property2:fC0ig)meansfr0\g厂。ByProperty1,T门0\力，sog「0i.

Property3:Lemma1.9ofthetextgivestransitivity.Property2givessymmetry.Sinceforanyf.fC0(/),wehave

reflexivity.

Property4:Weshow0(f•gl-。maxif.gll.Theotherdirectionissimilar.Leth厂0\f•g{.Therearec>0and

nosuchthatforn>n()th\n{•'clfgHThenforn->“0,h\〃广-2cmaxi八gln\.

1.37

ln2?，w,n2

WewilluseL'H6pital'sRule,soweneedtodifferentiate2〃.Observethat2"-ie：一e.Letc=ln2X0.7.

Thederivativeof-'isen,so,usingthechainrule,wefindthatthederivativeof2"isc2n.Now,usingL'H6pitai'sRule

repeatedly,

lim空q.=lim普=。

lim——lim---2n

〃，82〃n•«<»c2"nkooc28法2〃

sincekisconstant.

1.39

.J1foroddn.nforoddn

f(gln\―

/Jn|-<Inforevennforevenn

Therearealsoexamplesusingcontinuousfunctionsonthereals,aswellasexamplesusingmonotonicfunctions.

Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples7

Section1.6：SearchinganOrderedArray

1.42

Therevisedprocedureis:

intbinarysearch(int[]Ezintfirst,intlast,intK)

1.if(last<first)

2.index=-1;

3.elseif(last==first)

4.if(K==E[first])

5.index=first;

6.else

7.index=-1;

8.else

9.intmid=(first+last)/2;

10.if(KE[mid])

11.index=binarysearch(E,first,mid,K);

12.else

13.index=binarysearch(E,mid+1,last,K);

14.returnindex;

ComparedtoAlgorithm1.4(BinarySearch)inthetext,thisalgorithmcombinesthetestsoflines5and7intoonetest

online10,andtheleftsubrangeisincreasedfrommidItomid,becausemidmightcontainthekeybeingsearched

for.Anextrabasecaseisneededinlines3-7,whichtestsforexactequalitywhentherangeshrinkstoasingleentry.

Actually,ifwecanassumethepreconditionfirst•二last,thenlines1-2canbedispensedwith.Thisprocedure

propagatesthatpre