算法基础：英文版

PREFACE
1PRELIMINARIES
1.1Introduction1
1.2Whatisanalgorithm?1
1.3Notationforprograms6
1.4Mathematicalnotation7
1.4.1Propositionalcalculus7
1.4.2Settheory8
1.4.3Integers,realsandintervals8
1.4.4Functionsandrelations9
1.4.5Quantifiers10
1.4.6Sumsandproducts11
1.4.7Miscellaneous12
1.5Prooftechnique1--Contradiction13
1.6Prooftechnique2--Mathematicalinduction16
1.6.1Theprincipleofmathematicalinduction18
1.6.2Ahorseofadifferentcolour23
1.6.3Generalizedmathematicalinduction24
1.6.4Constructiveinduction27
1.7Somereminders31
1.7.1Limits31
1.7.2Simpleseries34
1.7.3Basiccombinatorics38
1.7.4Elementaryprobability41
1.8Problems48
1.9Referencesandfurtherreading55
2ELEMENTARYALGORITHMICS
2.1Introduction57
2.2Problemsandinstances58
2.3Theefficiencyofalgorithms59
2.4Averageandworst-caseanalyses61
2.5Whatisanelementaryoperation?64
2.6Whylookforefficiency?66
2.7Someexamples67
2.7.1Calculatingdeterminants68
2.7.2Sorting68
2.7.3Multiplicationoflargeintegers70
2.7.4Calculatingthegreatestcommondivisor71
2.7.5CalculatingtheFibonaccisequence72
2.7.6Fouriertransforms73
2.8Whenisanalgorithmspecified?74
2.9Problems74
2.10Referencesandfurtherreading78
3ASYMPTOTICNOTATION
3.1Introduction79
3.2Anotationfor"theorderof"79
3.3Otherasymptoticnotation85
3.4Conditionalasymptoticnotation88
3.5Asymptoticnotationwithseveralparameters91
3.6Operationsonasymptoticnotation91
3.7Problems92
3.8Referencesandfurtherreading97
4ANALYSISOFALGORITHMS
4.1Introduction98
4.2Analysingcontrolstructures98
4.2.1Sequencing98
4.2.2"For"loops99
4.2.3Recursivecalls101
4.2.4"While"and"repeat"loops102
4.3Usingabarometer104
4.4Supplementaryexamples106
4.5Average-caseanalysis111
4.6Amortizedanalysis112
4.7Solvingrecurrences116
4.7.1Intelligentguesswork116
4.7.2Homogeneousrecurrences118
4.7.3Inhomogeneousrecurrences123
4.7.4Changeofvariable130
4.7.5Rangetransformations136
4.7.6Asymptoticrecurrences137
4.8Problems139
4.9Referencesandfurtherreading146
5SOMEDATASTRUCTURES
5.1Arrays,stacksandqueues147
5.2Recordsandpointers150
5.3Lists151
5.4Graphs152
5.5Trees154
5.6Associativetables159
5.7Heaps162
5.8Binomialheaps170
5.9Disjointsetstructures175
5.10Problems181
5.11Referencesandfurtherreading186
6GREEDYALGORITHMS
6.1Makingchange(1)187
6.2Generalcharacteristicsofgreedyalgorithms188
6.3Graphs:Minimumspanningtrees190
6.3.1Kruskal'salgorithm193
6.3.2Prim'salgorithm196
6.4Graphs:Shortestpaths198
6.5Theknapsackproblem(1)202
6.6Scheduling205
6.6.1Minimizingtimeinthesystem205
6.6.2Schedulingwithdeadlines207
6.7Problems214
6.8Referencesandfurtherreading217
7DIVIDE-AND-CONQUER
7.1Introduction:Multiplyinglargeintegers219
7.2Thegeneraltemplate223
7.3Binarysearch226
7.4Sorting228
7.4.1Sortingbymerging228
7.4.2Quicksort231
7.5Findingthemedian237
7.6Matrixmultiplication242
7.7Exponentiation243
7.8Puttingitalltogether:Introductiontocryptography247
7.9Problems250
7.10Referencesandfurtherreading257
8DYNAMICPROGRAMMING
8.1Twosimpleexamples260
8.1.1Calculatingthebinomialcoefficient260
8.1.2TheWorldSeries261
8.2Makingchange(2)263
8.3Theprincipleofoptimality265
8.4Theknapsackproblem(2)266
8.5Shortestpaths268
8.6Chainedmatrixmultiplication271
8.7Approachesusingrecursion274
8.8Memoryfunctions276
8.9Problems278
8.10Referencesandfurtherreading283
9EXPLORINGGRAPHS
9.1Graphsandgames:Anintroduction285
9.2Traversingtrees291
9.2.1Preconditioning292
9.3Depth-firstsearch:Undirectedgraphs294
9.3.1Articulationpoints296
9.4Depth-firstsearch:Directedgraphs298
9.4.1Acyclicgraphs:Topologicalsorting300
9.5Breadth-firstsearch302
9.6Backtracking305
9.6.1Theknapsackproblem(3)306
9.6.2Theeightqueensproblem308
9.6.3Thegeneraltemplate311
9.7Branch-and-bound312
9.7.1Theassignmentproblem312
9.7.2Theknapsackproblem(4)315
9.7.3Generalconsiderations316
9.8Theminimaxprinciple317
9.9Problems319
9.10Referencesandfurtherreading326
I0PROBABILISTICALGORITHMS
10.1Introduction328
102Probabilisticdoesnotimplyuncertain329
10.3Expectedversusaveragetime331
10.4Pseudorandomgeneration331
10.5Numericalprobabilisticalgorithms333
10.5.1Buffon'sneedle333
10.5.2Numericalintegration336
10.5.3Probabilisticcounting338
10.6MonteCarloalgorithms341
10.6.1Verifyingmatrixmultiplication341
10.6.2Primalitytesting343
10.6.3Cananumberbeprobablyprime?348
10.6.4Amplificationofstochasticadvantage350
10.7LasVegasalgorithms353
10.7.1Theeightqueensproblemrevisited355
10.7.2Probabilisticselectionandsorting358
10.7.3Universalhashing360
10.7.4Factorizinglargeintegers362
10.8Problems366
10.9Referencesandfurtherreading373
11PARALLELALGORITHMS
11.1Amodelforparallelcomputation376
11.2Somebasictechniques379
11.2.1Computingwithacompletebinarytree379
11.2.2Pointerdoubling380
11.3Workandefficiency383
11.4Twoexamplesfromgraphtheory386
11.4.1Shortestpaths386
11.4.2Connectedcomponen,ts387
11.5Parallelevaluationofexpressions392
11.6Parallelsortingnetworks397
11.6.1Thezero-oneprinciple399
11.6.2Parallelmergingnetworks400
11.6.3Improvedsortingnetworks402
11.7Parallelsorting402
11.7.1Preliminaries403
11.7.2Thekeyidea404
11.7.3Thealgorithm405
11.7.4Asketchofthedetails406
11.8SomeremarksonEREWandcrcwp-rams406
11.9Distributedcomputation408
11.10Problems409
11.11Referencesandfurtherreading412
12COMPUTATIONALCOMPLEXITY
12.1Introduction:Asimpleexample414
12.2Information-theoreticarguments414
12.2.1Thecomplexityofsorting418
12.2.2Complexitytotherescueofalgorithmics421
12.3Adversaryarguments423
12.3.1Findingthemaximumofanarray424
12.3.2Testinggraphconnectivity425
12.3.3Themedianrevisited426
12.4Linearreductions427
12.4.1Formaldefinitions430
12.4.2Reductionsamongmatrixproblems433
12.4.3Reductionsamongshortestpathproblems438
12.5IntroductiontoNP-completeness441
12.5.1TheclassesPandNp441
12.5.2Polynomialreductions445
12.5.3NP-completeproblems450
12.5.4AfewNP-completenessproofs453
12.5.5Np-hardproblems457
12.5.6Nondeterministicalgorithms458
12.6Amenagerieofcomplexityclasses460
12.7Problems464
12.8Referencesandfurtherreading471
13HEURISTICANDAPPROXIMATEALGORITHMS
13.1Heuristicalgorithms475
13.1.1Colouringagraph475
13.1.2Thetravellingsalesperson477
13.2Approximatealgorithms478
13.2.1Themetrictravellingsalesperson478
13.2.2Theknapsackproblem(5)480
13.2.3Binpacking482
13.3NP-hardapproximationproblems484
13.3.1Hardabsoluteapproximationproblems486
13.3.2Hardrelativeapproximationproblems487
13.4Thesame,onlydifferent489
13.5Approximationschemes492
13.5.1Binpackingrevisited493
13.5.2Theknapsackproblem(6)493
13.6Problems496
13.7Referencesandfurtherreading500
REFERENCES
INDEX