I Foundations
Introduction 3
l The Role of Algorithms in Computing 5
l.l Algorithms 5
l.2 Algorithms as a technology 10
2 Getting Started I5
2.l Insertion sort 15
2.2 Analyzing algorithms 21
2.3 Designing algorithms 27
3 Growth of Functions 41
3.l Asymptotic notation 41
3.2 Standard notations and common functions 51
4 Recurrences 62
4.l The substitution method 63
4.2 The recursion-tree method 67
4.3 The master method 73
4.4 Proof of the master theorem 76
5 Probabilistic Analysis and Randomized Algorithms
5.l The hiring problem 91
5.2 Indicator random variables 94
5.3 Randomized algorithms 99
5.4 Probabi1istic analysis and further uses of indicator 106
II Sorting and Order Statistics Introduction 123
6 Heapsort 127
6.l Heaps I27
6.2 Maintaining the heap property 130
6.3 Building a heap 132
6.4 The heapsort algorithm 135
6.5 Priority queues 138
7 Quicksort 145
7.l Description of quicksort 145
7.2 Performance ofquicksort 149
7.3 A randomized version of quicksort 153
7.4 Analysis ofquicksort 55
8 Sorting in Linear Time 165
8.l Lower bounds for sorting 165
8.2 Counting sort i68
8.3 Radix sort 170
8.4 Bucket sort 174
9 Medians and Order Statistics 183
9.1 Minimum and maximum 184
9.2 Selection in expected linear time 185
9.3 Selection in worst-case linear time 189
III Data Structures Introduction 197
10 Elementary Data Structures 200
l0.l Stacks and queues 200
l0.2 Linked lists 204
l0.3 Implementing pointers and objects 209
l0.4 Representing rooted trees 214
11 Hash Tables 221
ll.l Direct-address tables 222
11.2 Hash tables 224
ll.3 Hash functions 229
ll.4 Open addressing 237
ll.5 Perfect hashing 24S
l2 Binary Search Trees 253
l2.l What is a binary search tree? 2S3
l2.2 Querying a binary search tree 2S6
l2.3 Insertion and deletion 261
l2.4 Randoinly built binary search trees 265
13 Red-Black Thees 273
l3.l Properties of red-black trees 273
l3.2 Rotations 277
l3.3 Insertion 280
l3.4 Deletion 288
14 Augmenting Data Structures 302
l4.l Dynamic order statistics 302
l4.2 How to augment a data structure 308
l4.3 Interval trees 311
IV Advanced Desthe and Analysis Techniques Introduction 321
15 Dynamic Programming J2J
l5.l Assembly--line scheduling 324
l5.2 Matrix-chain multiplication 331
l5.3 Elements of dynamic programming 339
15.4 Longest common subsequence 350
l5.5 Optimal binary search trees 356
l6 Greedy Algorithms 370
l6.l An activity-selection problem 371
l6.2 Elements of the greedy strategy 379
l6.3 Huffman codes 385
l6.4 Theoretical foundations for greedy methods 393
16.5 A task-scheduling problem 399
17 Amortized Analysis 405
l7.1 Aggregate analysis 406
17.2 The accounting method 410
17.3 The potential method 412
l7.4 Dynamic tables 416
V Advanced Data Structures Introduction 431
18 B-Trees 434
18.l Definition of B--trees 438
l8.2 Basic operations on B-trees 44j
l8.3 Deleting a key from a B--tree 449
19 Binomial Heaps 455
l9.l Binomial trees and binomial heaps 457
19.2 Operations on binomial heaps 461
20 Fibonacci Heaps 476
20.l Structure of Fibonacci heaps 477
20.2 Mergeable-heap operations 479
20.3 Decreasing a key and deleting a node 489
20.4 Bounding the maximum degree 493
21 Data Structures for Disjoint Sets 498
2l.l Disjoint--set operations 498
2l.2 Linked-list representation of disjoint sets 501
2l.3 Disjoint--set forests 505
2l.4 Analysis of union by rank with path compression 50 VI Graph Algorithms Introduction 525
22 Elementary Graph Algorithms 527
22.l Representations of graphs 527
22.2 Breadth-first search 531
22.3 Depth-first search 540
22.4 Topological sort 549
22.5 Strongly connected components 552
23 Minimum Spanning Trees 561
23.l Growing a minimum spanning tree 562
23.2 The algorithms of Kruskal and Prim 567
24 Single-Source Shortest Paths 580
24.l The Bellman-Ford algorithm 588
24.2 Single-source shortest paths in directed acyclic graphs
24.3 Dijkstra's algorithm 595
24.4 Difference constraints and shortest paths 601
24.5 Proofs of shortest-paths properties 607
25 All-Pairs Shortest Paths 620
25.l Shortest paths and matrix multiplication 622
25.2 The Floyd-Warshall a1gorithm 629
25.3 Johnson's algorithm for sparse graphs 636
26 Maximum Flow d43
26.l Flow networks 644
26.2 The Ford-Fulkerson method 651
26.3 Maximum bipartite matching 664
26.4 Push--relabel algorithms 669
26.5 The relabel--to-front a1gorithm 68I VII Selected Topics Introduction 701
27 Sorting Networks 704
27.l Comparison networks 704
27.2 The zero-one principle 709
27.3 A bitonic sorting network 712
27.4 A merging network 716
27.5 A sorting network 719
28 Matrix Operations 725
28.l Properties of matrices 725
28.2 Strassen's algorithm for matrix multiplication 735
28.3 Solving systems of linear equations 742
28.4 Inverting matrices 7S5
28.5 Symmetric positive-definite matrices and least-squares approximation760
29 Linear Programming 770
29.1 Standard and slack forms 777
29.2 Formulating problems as linear programs 785
29.3 The simplex algorithm 790
29.4 Duality 804
29.5 The initial basic feasible solution 811
30 Polynomials and the FFT 822
30.l Representation of polynomials 824
30.2 The DFT and FFT 830
30.3 Efficient FFT implementations 839
31 Number-Theoretic Algorithms 849
3l.l E1ementary numbertheoretic notions 850
31.2 Greatest common divisor 856
3l.3 Modular arithmetic 862
3l.4 Solving modular linear equations 869
3l.5 The Chinese remainder theorem 873
3l.6 Powers of an element 876
3l.7 The RSA public-key cryptosystem 881
3l.8 Primality testing 887
3l.9 Integer factorization 896
32 String Matching 906
32.l The naive string-matching algorithm 909
32.2 The Rabin-Karp algorithm 911
32.3 String matching with finite automata 916
32.4 The Knuth-Morris-Pratt algorithm 923
33 Computational Geometry 933
33.l Line--segment properties 934
33.2 Determining whether any pair of segments intersects 940
33.3 Finding the convex hull 947
33.4 Finding the c1osest pair of points 957
34 NP-Completeness 966
34.1 Polynomial time 971
34.2 Polynomial-time verification 979
34.3 NP-completeness and reducibility 984
34.4 NP--completeness proofs 995
34.5 NP-complete problems 1003
35 Approximation Algorithms 1022
35.l The vertex-cover problem 1024
35.2 The traveling-salesman problem 1027
35.3 The set-covering problem 1033
35.4 Randomization and linear programming ]039
35.5 The subset-sum problem 1043
VH APPendir: Mathematical Background
Introduction 1057
A Summations 1058
A.l Summation formulas and properties 1058
A.2 Bounding summations 1062
B Sets, Etc. 1070
B.1 Sets 1070
B.2 Relations 1075
B.3 Functions 1077
B.4 Graphs 1080
B.5 Trees 1085
C Counting and Probability 1094
C.l Counting 1094
C.2 Probability 1100
C.3 Discrete random variables 1106
C.4 The geometric and binomial distributions 1112
C.5 The tails of the binomial distribution 1118
Bibliography 1127
Index 1145
鄂公网安备 42010302001612号 