Algorithmexercisesafterclassanalysis(算法課后習(xí)題分析)

Algorithmdesignandanalysisexercisesanswer-SecondEdition

/WangXiaodong-hxzonlovereading,2009,05,07Thursday,

04:22P.M.algorithmdesignandAnalysisExerciseanswers-

SecondEdition/WangXiaodong,-hxzonlovereading

Titlecollection:

Intwenty-firstCentury,undergraduatecomputerprofessional

seriesofteachingmaterialsISBN:

978-7-302-16719-8CNY39.00(includingCD-ROM)publishing

issues:

Beijing-TsinghuaUniversitypress,2008carrierinformation:

420page23cmCD1personresponsible:

WangXiaodong,ChineseLibraryClassification:

TP301.6

[evaluation](atotalof1articles)participateinthe

comments

[author]WangXiaodong[authorofthesamework][translator]

[series]twenty-firstCenturyundergraduatecomputer

professionalseriesofteachingmaterials

Press口[]TsinghuaUniversitypressISBN9787302167198

[shelftime]2008-3-18

[date][]publishedFebruary200816[]formatpage420edition

[]2-1

C

Directoryoverviewchapterfirstalgorithmsintroduction

Thesecondchapter,recursionanddivideandconquerstrategy

Thethirdchapterisdynamicprogramming

Thefourthchaptergreedyalgorithm

Thefifthchapterisbacktracking

Thesixthchapter,branchandboundmethod

Theseventhchapterisprobabi1ityalgorithm

Theeighthchapter,NPcompletenesstheory

Theninthchapterisapproximatealgorithm

Thetenthchapter,algorithmoptimizationstrategy

Reference

Roundandround

SomedetailedcataloguefirstchapteralgorithmIntroduction

Exercise1-1argumentexchange

Exercise1-2methodheadersignature

Exercise1-3arraysortingdecision

Theasymptoticexpressionoffunction1-4

Thedifferencebetweenexercises1-5,0(1)and0(2)

Exercise1-7byasymptoticorderexpression

Problem1-8algorithmefficiency

Problem1-9hardwareefficiency

Exercise1-10,functionprogression

Exercise1-11n!Theorder

Exercise1-12averagecomputationtimecomplexity

Algorithmtoachievethetitle1-1statisticalproblems

Algorithmtoachievetheproblem1-2dictionaryorderproblem

Themostapproximatealgorithmthat1-3problem

Algorithmtoachievethetitleof1-4goldcoinsarrayproblem

Algorithmtoachievethemaximumgapproblem1-5

Thesecondchapter,recursionanddivideandconquerstrategy

Problem2-1nonrecursivealgorithmforHanoitowerproblem

Exercises2-27twopointsearchalgorithm

Problem2-3rewritetwosearchalgorithm

0(nmlog(3/2))algorithmforthe2-4largestinteger

multiplicationofexercises

Exercises2-55timesn/3integermultiplication19

Exercise2-6matrixmultiplication

Exercise2-7polynomialproduct

Exercise2-8fixedpointproblem0(logn)timealgorithm22

Exercise2-9lineartimealgorithmforprincipalelement

problem22

Exercise2-10.Thelineartimealgorithmfortheprincipal

elementproblemofunorderedsets

Exercise2-110(1)subspacesubarraytranspositionalgorithm

Exercise2-120(1)spacemergingalgorithm

Exercise2-13Nsegmentmergesortalgorithm

Exercise2-14naturalmergesortalgorithm

Theoptimalalgorithmfortheproblemofmaximumandminimum

ofexercise2-15

Theoptimalalgorithmforproblem2-16maximumandsublarge

valueproblems

Exercise2-17integersetsorting

Exercise2-18,K,smallelementproblem,computationtime,

lowerbound

Problem2-19nonsequentialfastsortalgorithm

Problem2-20randomizationalgorithm

Problem2-21randomizedquicksortalgorithm

Problem2-22randompermutationalgorithm

Problem2-23algorithmtai1tailinqSort

Exercise2-24usesstacktosimulaterecursion

Problem2-25algorithmselectelementdivision

Exercise2-260(nlogn)timefastsortingalgorithm

Exercise2-27,thenearesttothemediannumberofK

Exercise2-28medianofXandY

Problem2-29networkswitchdesign

Exercise2-32weightedmedianproblem

Problem2-34constructionGraycodedivideandconquer

algorithm

Exercise2-35tenniscycleschedule

Algorithmtoachievethequestion2-1pipeline(problem2-30)

Algorithmthat2-2modeproblem(2-31problem)

Algorithmtoachievethetitle2-3postofficelocationproblem

(problem2-32)

Algorithmtoachievetheproblemof2-4horseHamiltontravel

route(problem2-33)

Algorithmtoachievetheproblemofhalfthesetofquestions

2-5

Algorithmtoachievetheproblemofhalfofthe2-6singleset

problem

The2-7algorithmthatthesoldiersstandinquestion

Algorithmtoachievethequestion2-8,therearerepeated

elementsofthearrangement

Thelexicographicorderingproblemofitem2-9isstudied

Thethirdchapterisdynamicprogramming

Thefourthchaptergreedyalgorithm

Thefifthchapterisbacktracking

Thesixthchapter,branchandboundmethod

Theseventhchapterisprobabilityalgorithm

Theeighthchapter,NPcompletenesstheory

Theninthchapterisapproximatealgorithm

Thetenthchapter,algorithmoptimizationstrategy

Reference

Firstedition?Hxzon,36yuan,firstchapteralgorithm

introduction1

Exercise11argumentexchange1

Exercise12methodheadsignature1

Exercise13arraysortingdecision1

Exercise14theasymptoticexpressionoffunction2

Exercise150(1)and0(2)difference2

Exercise17byasymptoticorderexpression2

Problem18algorithmefficiency2

Problem19hardwareefficiency3

Exercise110,functionprogression3

Exercise1,lln,step4

Problem112averagecomputationtimecomplexity4

Algorithmtoachievethetitle11statisticalproblems4

Algorithmtoachievetheproblem12dictionaryorder5

13themostapproximatealgorithmthatproblem6

AlgorithmTITLE14goldcoinsarrayproblem8

Algorithmtoachievethetitle15maximumgapproblem11

Thesecondchapterisrecursionanddivideandconquerstrategy

14

Problem2.NonrecursivealgorithmforIHanoitowerproblem14

Exercises227twosearchalgorithm15

Problem23rewritetwosearchalgorithm18

Exercise24integermultiplicationof0(nmlog(3/2))algorithm

19

Exercises255timesn/3integermultiplication19

Exercise26matrixmultiplication21

Exercise27polynomialproduct21

Exercise28fixedpointproblem0(logn)timealgorithm22

Exercise29lineartimealgorithmforprincipalelementproblem

22

Exercise210.Thelinearalgorithmoftheproblemofthe

principalelementofunorderedSet22

Exercise2110(1)subspacesubarraytranspositionalgorithm

23

Exercise2120(1)spacemergingalgorithm25

Exercise213Nsegmentmergesortingalgorithm32

Exercise214naturalmergesortingalgorithm32

Problem215optimalalgorithmformaximumandminimumproblems

35

Problem216optimalalgorithmformaximumandsublarge

problems35

Exercise217integersetsort35

Exercise218,K,smallelementproblem,calculationtime,lower

bound36

Exercise219nonsequentialquicksortingalgorithm37

Exercise220randomizationalgorithm37

Problem221randomizationquicksortingalgorithm38

Problem222randompermutationalgorithm38

Problem223algorithmtailtai138inqSort

Problem224usingstacktosimulaterecursion38

Problem225algorithmselectelement39

Exercise2260(nlogn)timequicksortingalgorithm40

Exercise227,thenearesttothemediannumberofK40

Exercise2median28XandY40

Problem229networkswitchdesign41

Exercise232weightmedianproblem42

Exercise234constructionGraycodedivideandconquer

algorithm43

Exercise235tenniscycleschedule44

Algorithmtoachievethequestion21pipeline(problem230)49

Algorithm22modeproblem(exercise231)50

Algorithmtoachievethetitle23postofficelocationproblem

(exercise232)51

Algorithmtoachievetheproblemof24horseHamiltontravel

route(problem233)51

Algorithmtoachievethequestion25halfsetproblem60

Algorithmtoachievetheproblemof26singlesetsofquestions

62

Algorithm27soldiersstandinquestion63

Algorithmtoachievethequestion28,therearerepeated

elementsofthearrangementproblem63

Algorithmtoachievetheorderof29questionsdictionaryorder

65

Algorithmtoachievetheproblemof210setpartitioning(1)

67

Algorithmtoachievetheproblemof211setsdivision(two)68

Algorithmtoachievethetitleof212pairsofcolorHanoitower

problem69

Algorithmtoachievethetitle213standardtwo-dimensional

table71

Algorithmtoachievethequestion214integerfactorization

problem72

Algorithmtoachievethetitle215,thevalueofthestraight

line272

Thethirdchapterdynamicplanning76

Exercise31longestmonotoneincreasingsubsequence76

Exercise32thelongestmonotonicallyincreasingsubsequence

ofthe0(nlogn)algorithm77

Exercise37beautifulprint78

Exercise311integerlinearprogrammingproblem79

Problem312twodimensionalknapsackproblem80

Exercise314Ackermannfunction81

Exercise317shortestroute83

Exercise319bestroute83

Algorithmtoachievetheproblemof31independenttasks

optimalschedulingproblem(problem33)83

Algorithmtoachievethetitleof32coinsatleast(problem

34)85

Algorithmtoachievetheproblemof33ordinalrelationscount

problem(problem35)86

Algorithmtoachievethequestion34powercountproblem

(problem36)87

Algorithmtoachievethetitle35editdistanceproblem

(problem38)87

Algorithmtoachievetheproblemof36stonesmerger(problem

39)89

Algorithmtoachievethetitle37digitaltriangleproblem

(problem310)91

Algorithmtoachievethequestion38multiplicationtable

problem(problem313)92

Algorithmtosolvetheproblemofrentingyacht39(problem315)

93

Algorithmtoachievethetitle310carrefuelingproblem

(problem316)95

Algorithmtoachievethequestionof311circlemultiplication

(problem318)96

AlgorithmtoachieveTitle312,theleastcostofshopping

(problem320)102

Algorithmtoachievethetitleof313largestcuboidproblem

(problem321)104

Algorithmtoachievethequestion314regularexpression

matchingproblem(problem322)105

Algorithmtoachievethetitleof315pairsoftravelsalesman

problem(problem323)110

Algorithmtoachievethetitle316largestKproductproblem

(problem524)111

Algorithmtoachievethetitle317minimumMsegmentandproblem

113

Algorithmtoachievethetitle318redblacktreerednode

problem115

Thefourthchaptergreedyalgorithm123

Problem42activityarrangementproblemgreedychoice123

Problem43thegreedychoiceofknapsackproblem123

Problem44special01knapsackproblem124

Problem410programbeststorageproblem124

Exercise413optimalloadingproblemgreedyalgorithm125

Exercise418FibonaccisequenceHuffmanencoding125

Exercise419optimalprefixcodesequence125

Problem421tasksetindependence126

Problem422matrixmatroid126

Exercise423minimumweightmaximumindependentsubsetmatroid

126

Exercise427integeredgeweightPrimalgorithm126

Exercise428themostpowerfulminimumspanningtree127

Exercise429therightedgeoftheshortestpath127

Exercise430integeredgeweightDijkstraalgorithm127

Algorithmtoachievethequestion41venuearrangements

(problem41)128

Algorithmtoachievethequestion42optimalcombination

problem(problem45)129

Algorithmtoachievethequestion43beststorageoftape

(problem46)130

Algorithmtoachievethetitle44diskfilebeststorageproblem

(problem47)131

Algorithmtoachievethetitle45programstorageproblem

(problem48)132

Algorithmtoachievethequestion46optimalserviceorder

problem(problem411)133

Algorithmtoachievethequestionofmorethan47bestservice

orderproblem(problem412)134

Algorithmtoachievethetitleof48Dforestproblem(problem

414)135

Algorithmtoachievethetitle49carrefuelingproblem

(problem416)137

Algorithmtoachievesection410coverageproblem(problem417)

138

The411algorithmthatcoinproblem(exercise424)138

Algorithmtoachievethequestion412deletionnumber(problem

425)139

Algorithmtoachievetheproblem413seriesrangeproblem

(problem426)140

Algorithmtoachievethequestion414nestedboxproblem

(problem431)140

Algorithm415arbitrageproblem(project432)142

Algorithmtoachievethetitle416signalenhancementdevice

(problem517)143

Algorithmtoachievethequestionofthemaximumutilization

oftape417(problem49)144

Algorithmtoachievethetask418nonunittimescheduling

problem(problem415)145

Algorithmtoachievethetitle419multivariateHuffmancoding

problem(problem420)147

Algorithmtoachievemorethan420yuanHuffmancoding,

deformation149

Algorithmtoachievetheintersectionofquestions421section

151

Algorithmtoachievetask422timetableproblem151

Thefifthchapterisbacktrackingmethod153

Problem5-1loadingproblemsimprovedbacktracking1153

Problem5-2loadingproblemsimprovedbacktracking2154

Problem5-401theoptimalsolutionofknapsackproblem155

Problem5-5iterativebacktrackingmethodformaximumclique

problem156

Exercise5-7thecostoftravelsalesmanproblemupperbound

157

Exercise5-8theupperboundfunctionoftravelsalesman

problem158

Algorithmtoachievequestions51subsetsandproblems(problem

53)159

Algorithmtoachievetheproblemofminimumlengthof52circuit

boardarrangement(problem59)160

Algorithmtoachievethetitleof53minimumweightmachine

designproblem(problem510)163

Algorithmtoachievethequestion54athletesbestmatching

problem(exercise511)164

Algorithmtoachievethetitle55Noseparatordictionary

problem(problem512)165

Algorithmtoachievethequestion56,noandsetproblem

(problem513)167

Algorithmtoachieve57ncolorsquarecolumnproblem(problem

514)168

Algorithmtoachievethequestion58integertransformproblem

(problem515)173

Algorithmtoachievethetitle59Latinmatrixproblem(problem

516)175

Algorithmtoachievetheproblemof510setsofstones(problem

516)176

Algorithmtoachievequestions511repeatLatinmatrixproblem

(problem516)179

AlgorithmtoachieveTitle512,RomeoandJuliet'smazeproblem

181

Algorithmtoachievethetaskallocationproblem513(problem

518)183

Algorithmtoachievethetitleof514independentdiamond

checkersproblem(problem519)184

Algorithmtoachievethetitle515puzzlepuzzles(exercises

520)191

Algorithmtoachievethetitle516routingproblem(problem521)

198

Algorithmtoachievethequestion517bestschedulingproblem

(problem522)200

Algorithmtoachievethetitle518noprioritycalculation

problem(problem523)201

Algorithmtoachievethetitleof“519worldfamouspainting

exhibitionhall”(problem525)203

Algorithmtoachievethetitleof“520worldfamouspainting

Museum”(notrepeatedsurveillance)(problem526)207

Algorithmtoachievethetitleof521tribalguards(problem

56)209

Algorithmtoachievethequestion522insecterosionalgorithm

problem211

Algorithmtoachievequestions523completeringsequence

problem214

Algorithmtoachieve524discreteproblems,01stringproblems

217

Algorithm525robotpaintingproblem218

Algorithmtoachievethetitle526n2-lpuzzle221

Thesixthchapterisbranchandboundmethod229

Stackofbranchandboundmethodexercises6101knapsack

problem229

Exercise62withpriorityqueuetypebranchandboundmethod

ofthemaximumstoragestoragelivenode231

Theupperboundofthetoppointsofthe63setsofexercises

234

Exercises,64groups,toppoints,improvements,upperbounds,

235

Problem65modifythebranchandboundmethodforsolvingtravel

salesmanproblem235

Problem66,thebranchandboundmethodtosolvethetraveling

salesmanproblem,savestheresultingpermutationtree237

Problem67thequeuetypebranchandboundmethodforcircuit

boardarrangement239

Algorithmtoachievetheproblemofminimumlengthof61circuit

boardarrangementone(problem68)241

Algorithmtoachievethequestion62minimumlengthcircuit

boardarrangementproblemtwo(problem69)244

Algorithmtoachievethequestion63minimumweightvertex

coverageproblem(problem610)247

Algorithmtoachievetheproblemof64undirectedgraphmaximum

cutproblem(problem611)250

Algorithmtoachievethetitleof65minimumweightmachine

designproblem(problem612)253

Algorithmtoachievethequestion66athletesbestmatching

problem(exercise613)256

Algorithmtoachievethetitle67nqueensproblem(problem615)

259

Algorithmtoachievetheproblemof68roundarrangement

(problem616)260

Algorithmtoachievethetitle69routingproblem(problem617)

263

Algorithmtoachievethequestion610bestschedulingproblem

(problem618)265

Algorithmtoachievethetitle611noprioritycalculation

problem(problem619)268

Algorithmtoachievethetitleof“612worldfamouspainting

exhibitionhall”(problem621)271

Algorithmtoachievethetitleof613Knightsjourney274

Algorithmtoachievethetitleof614pushboxproblem275

Algorithmtoachievethetitle615graphicstransformation

problem281

Algorithmtoachievethequestion616rowcolumntransformation

problem284

AlgorithmtoachieveTitle617rearrangementN2palacequestion

285

Algorithmtoachievethetitleofthelongestdistanceproblem

290618

Theseventhchapterprobabilityalgorithm296

Problem71simulationofnormaldistributionrandomvariables

296

Exercise72randomsamplingalgorithm297

Exercise73randomlyproducesmintegers297

Exercise74setsthesizeoftheprobabilityalgorithm298

Problem75birthdayquestion299

Exercise76easytoverifytheproblemofLasVegasalgorithm

300

Exercise77simulatesanorderedlistof300byanarray

Exercise780(n3/2)Sherwoodtypesortingalgorithm300

Problem7.Existenceofproblemsolutionafter9N301

Problem711integerfactorizationalgorithm302

Exercise712nonMonteCarloalgorithmexample302

Exercise713repeattheMonteCarloalgorithm3times303

Exercise714setrandomelementalgorithm304

Exercise715byMonteCarloalgorithmtoconstructLasVegas

algorithm305

Exercise716generatePrimealgorithm306

Problem719matrixequation306

Algorithmtoachievethequestionof71modulussquareroot

problem(problem710)307

Algorithmtoachievethequestionof72primenumbertest

(problem717)309

Algorithmtoachievetheproblemof73setsofequalproblem

(problem718)309

Algorithmtoachievethequestion74inversematrixproblem

(problem720)310

Algorithmtoachievetheproductof75polynomialproduct

(problem721)311

AlgorithmtoachieveTitle76queencontrolproblem311

Algorithmtoachievethetitle7,73SAT315

Algorithmtoachievethetitle78chariotproblem316

Algorithmtoachievetheproblem79circlearrangementproblem

318

Algorithmtoachievethetitleof710Knightcontrolproblem

319

Algorithm711Knightsattack320

Theeighthchapter,NPcompletenesstheory,322

Exercise81RAMandRASPprogram322

Exercise8complexityof2RAMandRASPprograms322

Exercise83calculateNNRAMprogram322

Problem84RAMprogramwithoutMULTandDIVinstructions324

Exercise85MULTandDIVinstructioncalculationability324

Exercise8thespatialcomplexityof6RAMandRASP325

Problem87linearprogramofdeterminant325

Exercises88andsumof3bandTuringmachine325

Exercise89simulateRAMinstructions325

Exercise810calculate22nRAMprogram325

Exercise811calculateg(m,n)program326

Exercise812TuringmachinesimulationRAMupperboundontime

326

Problem813isomorphismofgraph326

Problem814Hamiltonloop327

Exercise8.Closureof15Planguages327

Exercise8.Closureof16NPlanguages328

Exercise817language20(NK)timedeterminationalgorithm328

Exercise818PCONP329

Exercise819NP=CONP329

Exercise820tautologyBooleanexpressions329

Exercise821/Pof329transferrelationship

Exercise822L/p330

Exercise823languagecompleteness330

Exercise824CONPcompleteness330

JudgeCONPtautologycomplete331exercise825

Exercise826.Thesatisfactionofdisjunctivenormalform331

Exercise8lineartimealgorithmfor272SATproblem331

Problem828integerprogrammingproblem332

Problem829dividetheproblem333

Problem830thelongestsimpleloopproblem334

Theninthchapterapproximationalgorithm336

Problem91absoluteapproximationalgorithmforplanecoloring

problem336

Problem92storageofthebestprogram336

Theoptimalvertexofthe94treeiscoveredby337

Problem95vertexcoveragealgorithmperformanceratioof339

Problem96groupconstantperformanceratioapproximation

algorithm339

Exercise99salesmanproblemconstantperformanceratio

approximationalgorithm340

Problem910bottlenecktravelsalesmanproblem340

Exercise911optimaltravelsalesmancircuitdoesnotintersect

342

Problem914setsexampleofcoveringproblems342

Approximatealgorithmforproblemmorethan916machine

schedulingproblem343

Problem9345worstcaseof17LPTalgorithm

Polynomialtimeapproximationalgorithmformorethan918

machineschedulingproblem345

Algorithmtoachievetheproblemof91travelsalesmanproblem

approximationalgorithm(exercise99)346

Algorithmtoachievetheproblem92canbeapproximated

algorithm(problem920)348

Algorithmtoachievethemaximumapproximationproblem93

algorithm(problem921)349

Algorithmtoachievetheproblemof94subsetsandthe

approximationoftheproblem(problem915)351

Algorithmtoachievethequestion95subsetsandtheproblem

ofcompletepolynomialtimeapproximationalgorithm352

Algorithmimplementationofthetitle96algorithm

greedySetCover(problem913)352

Algorithmtoachievethe"97"binpackingapproximation

algorithmFirstFit(problem919)356

Algorithmtoachievethe"98"binpackingapproximation

algorithmBestFit(problem919)358

Algorithmtoachievethe"99"binpackingapproximation

algorithmFirst,Fit,Decreasing(problem919)360

Algorithmtoachievethe"910"binpackingapproximation

algorithmBest,Fit,Decreasing(problem919)361

Approximationalgorithmforbinpackingproblemofitem911

NextFit361

Thetenthchapter,algorithmoptimizationstrategy365

Problem101algorithmobstthecorrectnessof365

Exercise