基本信息
印刷日期：2009-9-7
圖書簡介
本書是算法設計暢銷書的最新版本，是設計實用且高效算法的最全面指導書。本書揭密了算法的設計與分析，以簡單易懂的寫作風格，介紹了各種算法技術，著重強調了算法分析，全書包括兩大部分，“技術”部分介紹了設計和分析計算機算法的各種方法，“資源”部分給出了大量的參考資源，以及算法實現的各種資源，還提供了各種教學資源和參考材料，這些資源對讀者很有參考價值。
書籍目錄
1 Itroduction to Algorithm Design.............. 3
1．I Robothur Optimization…………………．5
1．2 Selecting the RigMJobs…………………．．9
1．3 Reasoning about Correctness………………．．11
1．4 Modeling the Problem……………………19
1．S About the stories……………………22
1．6 rstOYy：PSyChiCMOd6lillg………………．．23
1．7 Exercises…………………………．．27
2 Algorithm Analysis..........................................31
2．I The RAM Model of Computation………………31
2．Z The Big ohNotation……………………．34
2．3GrowthRatesandDomlnanceRelatlons…………．．37
2．4WorkingwiththeBigOh…………………．40
2．SReasoningAboutEfficiency…………………41
2．6LogarithmsandTheirApplications……………．．46
2．7ProPertiesofLogarithms…………………．．50
2．8rstory：MysteryofthePyramids……………．51
2．9Ad、ncedAnalysis（”）……………………54
2．10Exercises…………………………．．57
3Datastructures65
3．IContlguousvs．LlnhdDataStructures……………66
xiiCONTENTS
3．2StacksandQueues……………………．．71
3．3Dictionaries…………………………72
3．4Blnarysearchlees……………………．．77
3．SPriorityQueues………………………．83
3．6rstory：Strippingliangulations……………．85
3．7Hashingandstrings……………………．89
3．SSpecializedDatastructures…………………93
3．9rStory：String’e：Up3．10Exercises…………………………．．98
4Sortingandsearching103
4．IAPPlicationsofsorting……………………104
4．2Pragmaticsofsorting……………………．107
4．3H6&PSOFt：kstSOftlllgV18D8t8StfllCtllY6S…………108
4．4VrStory：GIVemeaTicktonallAirPlalle………．．118
4．SM6fg6SOft：SOftlllgbyDIVld6－llld－COllqll6ll…………120
4．6Qulcksort：SortingbyRandomization……………123
4．7DIStyiblltiollSOYt：SOYtillgVi8BllChtillg…………．．129
4．8rstory：SkienafortheDefense……………．．131
4．9BlnarySearchandRelatedAlgorithms……………132
4．10Divide－and－Conquer……………………．．135
4．11Exercises…………………………．．139
SGraphThaversal145
5．IFlavorsofGraphs………………………146
5．ZDatastructuresforGraphs…………………151
5．3rStofy：IWSS8VICtithOfMOOW6’SL8iYV…………155
5．4rStory：GettingtheG：anh………………．．158
5．slaversingaGraph……………………．．161
5．6Breadth－Firstsearch……………………．162
5．7ApplicationsofBreadth－FirstSearch……………．166
5．SDepth－Firstsearch……………………．．169
5．9ApplicationsofDepth－FirstSearch……………．．172
5．10Depth－FirstSearchonDirectedGraphs…………．．178
5．11EXer…………………………．．184
6WeightedGraphAlgorithmslgl
6．IMlnlmumSPanninglees…………………．192
6．2WaYStory：NOthillgbutNetS………………．．202
6．3ShortestPaths………………………．．205
6．4WarStcry：DialingforDocumes……………．．212
6．5NetworkFlowsandBipartiteMatching…………．．217
6．6DeslgnGraPhs，NotAlgorithms………………．222
6．7Exercises…………………………．．225
CONTENTSxiii
7．IBacktraching…………………………231
7．2SearchPruning………………………．238
7．3Sud。ku……………………………239
7．4rstory：CoveringChessboards………………244
7．SHeuristicsearchMethods…………………．247
7．6WafStofy：OillyitisNOtfiR3diO……………．．260
7．7rstory：AnnealingArrs………………．．263
7．SOtherHeuristicsearchMethods………………266
7．9Parallelorithms……………………．．267
7．10rStory：GoingNowherekst………………．268
7．11Exercises…………………………．．270
SDgnamlcProgramming273
8．ICachingvs．Computation…………………．274
8．ZAPProxlmatestringMatching………………．．280
8．3Lngestlncreasingsequence…………………289
8．4rstory：EvolutionoftheLobster……………．291
8．SThePartitionProblem……………………294
8．6ParsingCoext一eeGrammars………………298
8．7LlmltatlonsofDynamicProgramming：TSP…………301
8．8rStofy：Whst’SPSStisPfolog………………304
8．9rStory：IXtCompressionforBarCodes………．．307
8．10Exercises…………………………．．310
9．IProblemsandReductions…………………．317
9．ZReductionsforAlgorithms…………………．319
9．3ElementaryHardnessReductions………………323
9．4Satisfiability…………………………328
9．SCreatlVeReductiolls……………………．330
9．6TheArtofProvingHardness………………．．334
9．7rStory：HardAgainsttheCIcCk……………．．337
9．8WarSy：AndThenlFailed………………．．339
9．9P．…………………………．．
9．10DealingwithNP－completeProblems……………．344
9．11Exercises…………………………．．350
10HowtoDesignAlgorithms356
11TheHitchhiker’sGuidetoAlgorithms361
11ACatalogofAlgorithmicProblems363
.
xlvCONTENTS
12DataStructures366
12.IDictionaries..............................367
12.ZPriorityQueues......'.....................373
12'3SuffixTreesandArrays........................377
12'4GraphData
CONTENTSxv
15.1IDracingTrees.............................517
15'12PlanaritvDetectionandEmbedding520
JDetectionandEmbedding................520
16GraphProblems:HardProblems523
16.ICIique...............................25
16.ZIndependeniSet............................528
16.3VertexCover..............................530
16.4TraillingSalesmanProblem.....................533
16.SHamiItonianCyc1e..........................538
16.6Graphpartition............................541
16.7VertexCoIoring............................544
16.SEdgeCoIoring.............................548
16'9Graph
.
xviCONTENTS
19AlgorithmicResources657
19.ISofiwareSystems...........................657
l9.ZDataSources..............................663
19'3OnlineBibliographicResources...................663
19.4ProfessionalConsultingServices...................664
Bibliography665
Index709
