算法基础：英文版

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