Introduction to the design and analysis of algorithms

Cover......Page 1
Copyright Page......Page 4
Title Page......Page 5
Brief Contents......Page 7
Contents......Page 9
New to the Third Edition......Page 19
Preface......Page 21
Acknowledgments......Page 26
1 Introduction......Page 29
1.1 What Is an Algorithm?......Page 31
Exercises 1.1......Page 35
Ascertaining the Capabilities of the Computational Device......Page 37
Algorithm Design Techniques......Page 39
Methods of Specifying an Algorithm......Page 40
Proving an Algorithm’s Correctness......Page 41
Analyzing an Algorithm......Page 42
Coding an Algorithm......Page 43
Exercises 1.2......Page 45
1.3 Important Problem Types......Page 46
Sorting......Page 47
String Processing......Page 48
Combinatorial Problems......Page 49
Numerical Problems......Page 50
Exercises 1.3......Page 51
Linear Data Structures......Page 53
Graphs......Page 56
Trees......Page 59
Sets and Dictionaries......Page 63
Exercises 1.4......Page 65
Summary......Page 66
2 Fundamentals of the Analysis of Algorithm Efficiency......Page 69
2.1 The Analysis Framework......Page 70
Measuring an Input’s Size......Page 71
Units for Measuring Running Time......Page 72
Orders of Growth......Page 73
Worst-Case, Best-Case, and Average-Case Efficiencies......Page 75
Exercises 2.1......Page 78
Informal Introduction......Page 80
O-notation......Page 81
Ω-notation......Page 82
Useful Property Involving the Asymptotic Notations......Page 83
Using Limits for Comparing Orders of Growth......Page 84
Exercises 2.2......Page 86
2.3 Mathematical Analysis of Nonrecursive Algorithms......Page 89
Exercises 2.3......Page 95
2.4 Mathematical Analysis of Recursive Algorithms......Page 98
Exercises 2.4......Page 104
2.5 Example: Computing the nth Fibonacci Number......Page 108
Exercises 2.5......Page 111
2.6 Empirical Analysis of Algorithms......Page 112
Exercises 2.6......Page 117
2.7 Algorithm Visualization......Page 119
Summary......Page 122
3 Brute Force and Exhaustive Search......Page 125
Selection Sort......Page 126
Bubble Sort......Page 128
Exercises 3.1......Page 130
Sequential Search......Page 132
Brute-Force String Matching......Page 133
Exercises 3.2......Page 134
Closest-Pair Problem......Page 136
Convex-Hull Problem......Page 137
Exercises 3.3......Page 141
3.4 Exhaustive Search......Page 143
Knapsack Problem......Page 144
Assignment Problem......Page 147
Exercises 3.4......Page 148
Depth-First Search......Page 150
Breadth-First Search......Page 153
Exercises 3.5......Page 156
Summary......Page 158
4 Decrease-and-Conquer......Page 159
4.1 Insertion Sort......Page 162
Exercises 4.1......Page 164
4.2 Topological Sorting......Page 166
Exercises 4.2......Page 170
Generating Permutations......Page 172
Generating Subsets......Page 174
Exercises 4.3......Page 176
Binary Search......Page 178
Fake-Coin Problem......Page 180
Russian Peasant Multiplication......Page 181
Josephus Problem......Page 182
Exercises 4.4......Page 184
4.5 Variable-Size-Decrease Algorithms......Page 185
Computing a Median and the Selection Problem......Page 186
Interpolation Search......Page 189
Searching and Insertion in a Binary Search Tree......Page 191
The Game of Nim......Page 192
Exercises 4.5......Page 194
Summary......Page 195
5 Divide-and-Conquer......Page 197
5.1 Mergesort......Page 200
Exercises 5.1......Page 202
5.2 Quicksort......Page 204
Exercises 5.2......Page 209
5.3 Binary Tree Traversals and Related Properties......Page 210
Exercises 5.3......Page 213
5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication......Page 214
Multiplication of Large Integers......Page 215
Strassen’s Matrix Multiplication......Page 217
Exercises 5.4......Page 219
The Closest-Pair Problem......Page 220
Convex-Hull Problem......Page 223
Exercises 5.5......Page 225
Summary......Page 226
6 Transform-and-Conquer......Page 229
6.1 Presorting......Page 230
Exercises 6.1......Page 233
6.2 Gaussian Elimination......Page 236
LU Decomposition......Page 240
Computing a Matrix Inverse......Page 242
Computing a Determinant......Page 243
Exercises 6.2......Page 244
AVL Trees......Page 246
2-3 Trees......Page 251
Exercises 6.3......Page 253
6.4 Heaps and Heapsort......Page 254
Notion of the Heap......Page 255
Heapsort......Page 259
Exercises 6.4......Page 261
Horner’s Rule......Page 262
Binary Exponentiation......Page 264
Exercises 6.5......Page 267
6.6 Problem Reduction......Page 268
Computing the Least Common Multiple......Page 269
Counting Paths in a Graph......Page 270
Reduction of Optimization Problems......Page 271
Linear Programming......Page 272
Reduction to Graph Problems......Page 274
Exercises 6.6......Page 276
Summary......Page 278
7 Space and Time Trade-Offs......Page 281
7.1 Sorting by Counting......Page 282
Exercises 7.1......Page 285
7.2 Input Enhancement in String Matching......Page 286
Horspool’s Algorithm......Page 287
Boyer-Moore Algorithm......Page 291
Exercises 7.2......Page 295
7.3 Hashing......Page 297
Open Hashing (Separate Chaining)......Page 298
Closed Hashing (Open Addressing)......Page 300
Exercises 7.3......Page 302
7.4 B-Trees......Page 304
Exercises 7.4......Page 307
Summary......Page 308
8 Dynamic Programming......Page 311
8.1 Three Basic Examples......Page 313
Exercises 8.1......Page 318
8.2 The Knapsack Problem and Memory Functions......Page 320
Memory Functions......Page 322
Exercises 8.2......Page 324
8.3 Optimal Binary Search Trees......Page 325
Exercises 8.3......Page 331
Warshall’s Algorithm......Page 332
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem......Page 336
Exercises 8.4......Page 339
Summary......Page 340
9 Greedy Technique......Page 343
9.1 Prim’s Algorithm......Page 346
Exercises 9.1......Page 350
9.2 Kruskal’s Algorithm......Page 353
Disjoint Subsets and Union-Find Algorithms......Page 355
Exercises 9.2......Page 359
9.3 Dijkstra’s Algorithm......Page 361
Exercises 9.3......Page 365
9.4 Huffman Trees and Codes......Page 366
Exercises 9.4......Page 370
Summary......Page 372
10 Iterative Improvement......Page 373
10.1 The Simplex Method......Page 374
Geometric Interpretation of Linear Programming......Page 375
An Outline of the Simplex Method......Page 379
Further Notes on the Simplex Method......Page 385
Exercises 10.1......Page 387
10.2 The Maximum-Flow Problem......Page 389
Exercises 10.2......Page 399
10.3 Maximum Matching in Bipartite Graphs......Page 400
Exercises 10.3......Page 406
10.4 The Stable Marriage Problem......Page 408
Exercises 10.4......Page 411
Summary......Page 412
11 Limitations of Algorithm Power......Page 415
11.1 Lower-Bound Arguments......Page 416
Trivial Lower Bounds......Page 417
Adversary Arguments......Page 418
Problem Reduction......Page 419
Exercises 11.1......Page 421
11.2 Decision Trees......Page 422
Decision Trees for Sorting......Page 423
Decision Trees for Searching a Sorted Array......Page 425
Exercises 11.2......Page 427
11.3 P, NP, and NP-Complete Problems......Page 429
P and NP Problems......Page 430
NP-Complete Problems......Page 434
Exercises 11.3......Page 437
11.4 Challenges of Numerical Algorithms......Page 440
Exercises 11.4......Page 447
Summary......Page 448
12 Coping with the Limitations of Algorithm Power......Page 451
12.1 Backtracking......Page 452
n-Queens Problem......Page 453
Hamiltonian Circuit Problem......Page 454
Subset-Sum Problem......Page 455
General Remarks......Page 456
Exercises 12.1......Page 458
12.2 Branch-and-Bound......Page 460
Assignment Problem......Page 461
Knapsack Problem......Page 464
Traveling Salesman Problem......Page 466
Exercises 12.2......Page 468
12.3 Approximation Algorithms for NP-Hard Problems......Page 469
Approximation Algorithms for the Traveling Salesman Problem......Page 471
Approximation Algorithms for the Knapsack Problem......Page 481
Exercises 12.3......Page 485
12.4 Algorithms for Solving Nonlinear Equations......Page 487
Bisection Method......Page 488
Newton’s Method......Page 492
Exercises 12.4......Page 495
Summary......Page 496
Epilogue......Page 499
Combinatorics......Page 503
Sum Manipulation Rules......Page 504
Miscellaneous......Page 505
Sequences and Recurrence Relations......Page 507
Methods for Solving Recurrence Relations......Page 508
Common Recurrence Types in Algorithm Analysis......Page 513
References......Page 521
Hints to Exercises......Page 531
A......Page 575
B......Page 576
C......Page 578
D......Page 579
E......Page 580
F......Page 581
G......Page 582
I......Page 583
L......Page 584
M......Page 586
P......Page 587
S......Page 590
U......Page 592
W......Page 593