Introduction to the design and analysis of algorithms

Cover......Page 1
Title Page......Page 4
Contents......Page 8
New to the Third Edition......Page 18
Preface......Page 20
1 Introduction......Page 28
 1.1 What Is an Algorithm?......Page 30
  Exercises 1.1......Page 34
  Ascertaining the Capabilities of the Computational Device......Page 36
  Algorithm Design Techniques......Page 38
  Methods of Specifying an Algorithm......Page 39
  Proving an Algorithm’s Correctness......Page 40
  Analyzing an Algorithm......Page 41
  Coding an Algorithm......Page 42
  Exercises 1.2......Page 44
 1.3 Important Problem Types......Page 45
  Sorting......Page 46
  String Processing......Page 47
  Combinatorial Problems......Page 48
  Numerical Problems......Page 49
  Exercises 1.3......Page 50
  Linear Data Structures......Page 52
  Graphs......Page 55
  Trees......Page 58
  Sets and Dictionaries......Page 62
 Exercises 1.4......Page 64
 Summary......Page 65
2 Fundamentals of the Analysis ofAlgorithm Efficiency......Page 68
 2.1 The Analysis Framework 68......Page 69
  Measuring an Input’s Size......Page 70
  Units for Measuring Running Time......Page 71
  Orders of Growth......Page 72
  Worst-Case, Best-Case, and Average-Case Efficiencies......Page 74
  Exercises 2.1......Page 77
  Informal Introduction......Page 79
  O-notation......Page 80
  Ω-notation......Page 81
  Useful Property Involving the Asymptotic Notations......Page 82
  Using Limits for Comparing Orders of Growth......Page 83
  Exercises 2.2......Page 85
 2.3 Mathematical Analysis of Nonrecursive Algorithms......Page 88
  Exercises 2.3......Page 94
 2.4 Mathematical Analysis of Recursive Algorithms......Page 97
  Exercises 2.4......Page 103
 2.5 Example: Computing the nth Fibonacci Number......Page 107
  Exercises 2.5......Page 110
 2.6 Empirical Analysis of Algorithms......Page 111
  Exercises 2.6......Page 116
 2.7 Algorithm Visualization......Page 118
 Summary......Page 121
3 Brute Force and Exhaustive Search......Page 124
  Selection Sort......Page 125
  Bubble Sort......Page 127
  Exercises 3.1......Page 129
  Sequential Search......Page 131
  Brute-Force String Matching......Page 132
  Exercises 3.2......Page 133
  Closest-Pair Problem......Page 135
  Convex-Hull Problem......Page 136
  Exercises 3.3......Page 140
 3.4 Exhaustive Search......Page 142
  Knapsack Problem......Page 143
  Assignment Problem......Page 146
  Exercises 3.4......Page 147
  Depth-First Search......Page 149
  Breadth-First Search......Page 152
  Exercises 3.5......Page 155
 Summary......Page 157
4 Decrease-and-Conquer......Page 158
 4.1 Insertion Sort......Page 161
  Exercises 4.1......Page 163
 4.2 Topological Sorting......Page 165
  Exercises 4.2......Page 169
  Generating Permutations......Page 171
  Generating Subsets......Page 173
  Exercises 4.3......Page 175
  Binary Search......Page 177
  Fake-Coin Problem......Page 179
  Russian Peasant Multiplication......Page 180
  Josephus Problem......Page 181
  Exercises 4.4......Page 183
 4.5 Variable-Size-Decrease Algorithms......Page 184
  Computing a Median and the......Page 185
  Interpolation Search......Page 188
  Searching and Insertion in a Binary Search Tree......Page 190
  The Game of Nim......Page 191
  Exercises 4.5......Page 193
 Summary......Page 194
5 Divide-and-Conquer......Page 196
 5.1 Mergesort......Page 199
  Exercises 5.1......Page 201
 5.2 Quicksort......Page 203
  Exercises 5.2......Page 208
 5.3 Binary Tree Traversals and Related Properties......Page 209
  Exercises 5.3......Page 212
 5.4 Multiplication of Large Integers and Strassen’s Matrix Multiplication......Page 213
  Multiplication of Large Integers......Page 214
  Strassen’s Matrix Multiplication......Page 216
  Exercises 5.4......Page 218
  The Closest-Pair Problem......Page 219
  Convex-Hull Problem......Page 222
  Exercises 5.5......Page 224
 Summary......Page 225
6 Transform-and-Conquer......Page 228
 6.1 Presorting......Page 229
  Exercises 6.1......Page 232
 6.2 Gaussian Elimination......Page 235
  LU Decomposition......Page 239
  Computing a Matrix Inverse......Page 241
  Computing a Determinant......Page 242
  Exercises 6.2......Page 243
  AVL Trees......Page 245
  2-3 Trees......Page 250
  Exercises 6.3......Page 252
 6.4 Heaps and Heapsort......Page 253
  Notion of the Heap......Page 254
  Heapsort......Page 258
  Exercises 6.4......Page 260
  Horner’s Rule......Page 261
  Binary Exponentiation......Page 263
  Exercises 6.5......Page 266
 6.6 Problem Reduction......Page 267
  Computing the Least Common Multiple......Page 268
  Counting Paths in a Graph......Page 269
  Reduction of Optimization Problems......Page 270
  Linear Programming......Page 271
  Reduction to Graph Problems......Page 273
  Exercises 6.6......Page 275
 Summary......Page 277
7 Space and Time Trade-Offs......Page 280
 7.1 Sorting by Counting......Page 281
  Exercises 7.1......Page 284
 7.2 Input Enhancement in String Matching......Page 285
  Horspool’s Algorithm......Page 286
  Boyer-Moore Algorithm......Page 290
  Exercises 7.2......Page 294
 7.3 Hashing......Page 296
  Open Hashing (Separate Chaining)......Page 297
  Closed Hashing (Open Addressing)......Page 299
  Exercises 7.3......Page 301
 7.4 B-Trees......Page 303
  Exercises 7.4......Page 306
 Summary......Page 307
8 Dynamic Programming......Page 310
 8.1 Three Basic Examples......Page 312
  Exercises 8.1......Page 317
  Memory Functions......Page 319
  Exercises 8.2......Page 323
 8.3 Optimal Binary Search Trees......Page 324
  Exercises 8.3......Page 330
  Warshall’s Algorithm......Page 331
  Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem......Page 335
  Exercises 8.4......Page 338
 Summary......Page 339
9 Greedy Technique......Page 342
 9.1 Prim’s Algorithm......Page 345
  Exercises 9.1......Page 349
 9.2 Kruskal’s Algorithm......Page 352
  Disjoint Subsets and Union-Find Algorithms......Page 354
  Exercises 9.2......Page 358
 9.3 Dijkstra’s Algorithm......Page 360
  Exercises 9.3......Page 364
 9.4 Huffman Trees and Codes......Page 365
  Exercises 9.4......Page 369
 Summary......Page 371
10 Iterative Improvement......Page 372
 10.1 The Simplex Method......Page 373
  Geometric Interpretation of Linear Programming......Page 374
  An Outline of the Simplex Method......Page 378
  Further Notes on the Simplex Method......Page 384
  Exercises 10.1......Page 386
 10.2 The Maximum-Flow Problem......Page 388
  Exercises 10.2......Page 398
 10.3 Maximum Matching in Bipartite Graphs......Page 399
  Exercises 10.3......Page 405
 10.4 The Stable Marriage Problem......Page 407
  Exercises 10.4......Page 410
 Summary......Page 411
11 Limitations of Algorithm Power......Page 414
 11.1 Lower-Bound Arguments......Page 415
  Trivial Lower Bounds......Page 416
  Adversary Arguments......Page 417
  Problem Reduction......Page 418
  Exercises 11.1......Page 420
 11.2 Decision Trees......Page 421
  Decision Trees for Sorting......Page 422
  Decision Trees for Searching a Sorted Array......Page 424
  Exercises 11.2......Page 426
 11.3 P, NP, and NP-Complete Problems......Page 428
  P and NP Problems......Page 429
  NP-Complete Problems......Page 433
  Exercises 11.3......Page 436
 11.4 Challenges of Numerical Algorithms......Page 439
  Exercises 11.4......Page 446
 Summary......Page 447
12 Coping with the Limitations of Algorithm Power......Page 450
 12.1 Backtracking......Page 451
  n-Queens Problem......Page 452
  Hamiltonian Circuit Problem......Page 453
  Subset-Sum Problem......Page 454
  General Remarks......Page 455
  Exercises 12.1......Page 457
 12.2 Branch-and-Bound......Page 459
  Assignment Problem......Page 460
  Knapsack Problem......Page 463
  Traveling Salesman Problem......Page 465
  Exercises 12.2......Page 467
 12.3 Approximation Algorithms for NP-Hard Problems......Page 468
  Approximation Algorithms for the Traveling Salesman Problem......Page 470
  Approximation Algorithms for the Knapsack Problem......Page 480
  Exercises 12.3......Page 484
 12.4 Algorithms for Solving Nonlinear Equations......Page 486
  Bisection Method......Page 487
  Newton’s Method......Page 491
  Exercises 12.4......Page 494
 Summary......Page 495
Epilogue......Page 498
  Combinatorics......Page 502
  Sum Manipulation Rules......Page 503
  Miscellaneous......Page 504
  Sequences and Recurrence Relations......Page 506
  Methods for Solving Recurrence Relations......Page 507
  Common Recurrence Types in Algorithm Analysis......Page 512
References......Page 520
Hints to Exercises......Page 530
 A......Page 572
 B......Page 573
 C......Page 575
 D......Page 576
 E......Page 577
 F......Page 578
 G......Page 579
 H......Page 580
 L......Page 581
 M......Page 583
 P......Page 584
 S......Page 587
 U......Page 589
 W......Page 590