算法基础（英文影印版）

.1.7.1 limits 31
1.7.2 simple series 34
1.7.3 basic combinatorics 38
1.7.4 elementary probability 41
1.8 problems 48
1.9 references and further reading 55
2 elementaryalgorithmics
2.1 introduction 57
2.2 problems and instances 58
2.3 the efficiency of algorithms 59
2.4 average and worst-case analyses 61
2.5 what is an elementary operation? 64
2.6 why look for efficiency? 66
2.7 some examples 67
2.7.1 calculating determinants 68
2.7.2 sorting 68
2.7.3 multiplication of large integers 70
2.7.4 calculating the greatest common divisor 71
2.7.5 calculating the fibonacci sequence 72
2.7.6 fourier transforms 73
2.8 when is an algorithm specified? 74
2.9 problems 74
2.10 references and further reading 78
3 asymptotic notation
3.1 introduction 79
3.2 a notation for "the order of" 79
3.3 other asymptotic notation 85
3.4 conditional asymptotic notation 88
3.5 asymptotic notation with several parameters 91
3.6 operations on asymptotic notation 91
3.7 problems 92
3.8 references and further reading 97
4 analysisofalgorithms
4.1 introduction 98
4.2 analysing control structures 98
4.2.1 sequencing 98
4.2.2 "for" loops 99
4.2.3 recursive calls 101
4.2.4 "while" and "repeat" loops 102
4.3 using a barometer 104
4.4 supplementary examples 106
4.5 average-case analysis 111
4.6 amortized analysis 112
4.7 solving recurrences 116
4.7.1 intelligent guesswork 116
4.7.2 homogeneous recurrences 118
4.7.3 inhomogeneous recurrences 123
4.7.4 change of variable 130
4.7.5 range transformations 136
4.7.6 asymptotic recurrences 137
4.8 problems 139
4.9 references and further reading 146
5 some data structures
5.1 arrays, stacks and queues 147
5.2 records and pointers 150
5.3 lists 151
5.4 graphs 152
5.5 trees 154
5.6 associative tables 159
5.7 heaps 162
5.8 binomial heaps 170
5.9 disjoint set structures 175
5.10 problems 181
5.11 references and further reading 186
6 greedyalgorithms
6.1 making change (1) 187
6.2 general characteristics of greedy algorithms 188
6.3 graphs: minimum spanning trees 190
6.3.1 kruskal's algorithm 193
6.3.2 prim's algorithm 196
6.4 graphs: shortest paths 198
6.5 the knapsack problem (1) 202
6.6 scheduling 205
6.6.1 minimizing time in the system 205
6.6.2 scheduling with deadlines 207
6.7 problems 214
6.8 references and further reading 217
7 divide-and-conquer
7.1 introduction: multiplying large integers 219
7.2 the general template 223
7.3 binary search 226
7.4 sorting 228
7.4.1 sorting by merging 228
7.4.2 quicksort 231
7.5 finding the median 237
7.6 matrix multiplication 242
7.7 exponentiation 243
7.8 putting it all together: introduction to cryptography 247
7.9 problems 250
7.10 references and further reading 257
8 dynamic programming
8.1 two simple examples 260
8.1.1 calculating the binomial coefficient 260
8.1.2 the world series 261
8.2 making change (2) 263
8.3 the principle of optimality 265
8.4 the knapsack problem (2) 266
8.5 shortest paths 268
8.6 chained matrix multiplication 271
8.7 approaches using recursion 274
8.8 memory functions 276
8.9 problems 278
8.10 references and further reading 283
9 exploring graphs
9.1 graphs and games: an introduction 285
9.2 traversing trees 291
9.2.1 preconditioning 292
9.3 depth-first search: undirected graphs 294
9.3.1 articulation points 296
9.4 depth-first search: directed graphs 298
9.4.1 acyclic graphs: topological sorting 300
9.5 breadth-first search 302
9.6 backtracking 305
9.6.1 the knapsack problem (3) 306
9.6.2 the eight queens problem 308
9.6.3 the general template 311
9.7 branch-and-bound 312
9.7.1 the assignment problem 312
9.7.2 the knapsack problem (4) 315
9.7.3 general considerations 316
9.8 the minimax principle 317
9.9 problems 319
9.10 references and further reading 326
i0 probabilistic algorithms
10.1 introduction 328
10 2 probabilistic does not imply uncertain 329
10.3 expected versus average time 331
10.4 pseudorandom generation 331
10.5 numerical probabilistic algorithms 333
10.5.1 buffon's needle 333
10.5.2 numerical integration 336
10.5.3 probabilistic counting 338
10.6 monte carlo algorithms 341
10.6.1 verifying matrix multiplication 341
10.6.2 primality testing 343
10.6.3 can a number be probably prime? 348
10.6.4 amplification of stochastic advantage 350
10.7 las vegas algorithms 353
10.7.1 the eight queens problem revisited 355
10.7.2 probabilistic selection and sorting 358
10.7.3 universal hashing 360
10.7.4 factorizing large integers 362
10.8 problems 366
10.9 references and further reading 373
11 parallel algorithms
11.1 a model for parallel computation 376
11.2 some basic techniques 379
11.2.1 computing with a complete binary tree 379
11.2.2 pointer doubling 380
11.3 work and efficiency 383
11.4 two examples from graph theory 386
11.4.1 shortest paths 386
11.4.2 connected componen, ts 387
11.5 parallel evaluation of expressions 392
11.6 parallel sorting networks 397
11.6.1 the zero-one principle 399
11.6.2 parallel merging networks 400
11.6.3 improved sorting networks 402
11.7 parallel sorting 402
11.7.1 preliminaries 403
11.7.2 the key idea 404
11.7.3 the algorithm 405
11.7.4 a sketch of the details 406
11.8 some remarks on erew and crcw p-rams 406
11.9 distributed computation 408
11.10 problems 409
11.11 references and further reading 412
12 computational complexity
12.1 introduction: a simple example 414
12.2 information-theoretic arguments 414
12.2.1 the complexity of sorting 418
12.2.2 complexity to the rescue of algorithmics 421
12.3 adversary arguments 423
12.3.1 finding the maximum of an array 424
12.3.2 testing graph connectivity 425
12.3.3 the median revisited 426
12.4 linear reductions 427
12.4.1 formal definitions 430
12.4.2 reductions among matrix problems 433
12.4.3 reductions among shortest path problems 438
12.5 introduction to np-completeness 441
12.5.1 the classes p and np 441
12.5.2 polynomial reductions 445
12.5.3 np- complete problems 450
12.5.4 a few np-completeness proofs 453
12.5.5 np-hard problems 457
12.5.6 nondeterministic algorithms 458
12.6 a menagerie of complexity classes 460
12.7 problems 464
12.8 references and further reading 471
13 heuristic and approximate algorithms
13.1 heuristic algorithms 475
13.1.1 colouring a graph 475
13.1.2 the travelling salesperson 477
13.2 approximate algorithms 478
13.2.1 the metric travelling salesperson 478
13.2.2 the knapsack problem (5) 480
13.2.3 bin packing 482
13.3 np-hard approximation problems 484
13.3.1 hard absolute approximation problems 486
13.3.2 hard relative approximation problems 487
13.4 the same, only different 489
13.5 approximation schemes 492
13.5.1 bin packing revisited 493
13.5.2 the knapsack problem (6) 493
13.6 problems 496
13.7 references and further reading 500
references
index