Algorithm Design

Foundations, Analysis, and Internet Examples

by
Michael T. Goodrich and Roberto Tamassia

Table of Contents

Part I. Fundamental Tools

• 1. Algorithm Analysis, 3

  • 1.1 Methodologies for Analyzing Algorithms, 5
    • Requirements for a General Analysis Methodology, 6
    • 1.1.1 Pseudo-Code, 7
      • An Example of Pseudo-Code, 7
      • Using Pseudo-Code to Prove Algorithm Correctness, 7
      • What Is Pseudo-Code?, 8
    • 1.1.2 The Random Access Machine (RAM) Model, 9
      • RAM Machine Model Definition, 9
    • 1.1.3 Counting Primitive Operations, 10
      • Average-Case and Worst-Case Analysis, 11
    • 1.1.4 Analyzing Recursive Algorithms, 12
  • 1.2 Asymptotic Notation, 13
    • 1.2.1 The ``Big-Oh'' Notation, 13
      • Using the Big-Oh Notation, 16
    • 1.2.2 ``Relatives'' of the Big-Oh, 16
      • Big-Omega and Big-Theta, 16
      • Some Words of Caution, 17
      • ``Distant Cousins'' of the Big-Oh: Little-Oh and Little-Omega, 18
    • 1.2.3 The Importance of Asymptotics, 19
      • Ordering Functions by Their Growth Rates, 20
  • 1.3 A Quick Mathematical Review, 21
    • 1.3.1 Summations, 21
    • 1.3.2 Logarithms and Exponents, 23
      • The Floor and Ceiling Functions, 24
    • 1.3.3 Simple Justification Techniques, 24
      • By Example, 24
      • The ``Contra'' Attack, 25
      • Induction, 25
      • Loop Invariants, 27
    • 1.3.4 Basic Probability, 28
      • Independence, 28
      • Conditional Probability, 29
      • Random Variables and Expectation, 29
      • Chernoff Bounds, 30
  • 1.4 Case Studies in Algorithm Analysis, 31
    • 1.4.1 A Quadratic-Time Prefix Averages Algorithm, 32
    • 1.4.2 A Linear-Time Prefix Averages Algorithm, 33
  • 1.5 Amortization, 34
    • The Clearable Table Data Structure, 34
    • Amortizing an Algorithm's Running Time, 35
    • 1.5.1 Amortization Techniques, 36
      • The Accounting Method, 36
      • Potential Functions, 37
    • 1.5.2 Analyzing an Extendable Array Implementation, 39
  • 1.6 Experimentation, 42
    • 1.6.1 Experimental Setup, 42
      • Choosing the Question, 42
      • Deciding What to Measure, 43
      • Generating Test Data, 44
      • Coding the Solution and Performing the Experiment, 44
    • 1.6.2 Data Analysis and Visualization, 45
      • The Ratio Test, 45
      • The Power Test, 46
  • 1.7 Exercises, 47

  2. Basic Data Structures, 55

  • 2.1 Stacks and Queues, 57
    • 2.1.1 Stacks, 57
      • The Stack Abstract Data Type, 57
      • A Simple Array-Based Implementation, 57
      • Using Stacks for Procedure Calls and Recursion, 59
      • Recursion, 60
    • 2.1.2 Queues, 61
      • The Queue Abstract Data Type, 61
      • A Simple Array-Based Implementation, 61
      • Using Queues for Multiprogramming, 63
  • 2.2 Vectors, Lists, and Sequences, 65
    • 2.2.1 Vectors, 65
      • The Vector Abstract Data Type, 65
      • A Simple Array-Based Implementation, 66
    • 2.2.2 Lists, 68
      • Positions and Node-Based Operations, 68
      • The List Abstract Data Type, 69
      • Linked List Implementation, 70
    • 2.2.3 Sequences, 73
      • The Sequence Abstract Data Type, 73
      • Iterators, 74
  • 2.3 Trees, 75
    • 2.3.1 The Tree Abstract Data Type, 77
    • 2.3.2 Tree Traversal, 78
      • Assumptions, 78
      • Depth and Height, 79
      • Preorder Traversal, 81
      • Postorder Traversal, 82
    • 2.3.3 Binary Trees, 84
      • The Binary Tree Abstract Data Type, 84
      • Properties of Binary Trees, 84
      • Traversals of a Binary Tree, 86
      • Preorder Traversal of a Binary Tree, 86
      • Postorder Traversal of a Binary Tree, 86
      • Inorder Traversal of a Binary Tree, 87
      • A Unified Tree Traversal Framework, 87
      • The Euler Tour Traversal of a Binary Tree, 88
    • 2.3.4 Data Structures for Representing Trees, 90
      • A Vector-Based Structure for Binary Trees, 90
      • A Linked Structure for Binary Trees, 92
      • A Linked Structure for General Trees, 93
  • 2.4 Priority Queues and Heaps, 94
    • 2.4.1 The Priority Queue Abstract Data Type, 94
      • Comparators, 95
    • 2.4.2 PQ-Sort, Selection-Sort, and Insertion-Sort, 96
      • PQ-Sort: Using a Priority Queue to Sort, 96
      • Using a Priority Queue Implemented with an Unordered Sequence, 97
      • Selection-Sort, 97
      • Using a Priority Queue Implemented with a Sorted Sequence, 98
      • Insertion-Sort, 98
    • 2.4.3 The Heap Data Structure, 99
      • Implementing a Priority Queue with a Heap, 100
      • The Vector Representation of a Heap, 101
      • Insertion, 102
      • Up-Heap Bubbling after an Insertion, 102
      • Removal, 104
      • Down-Heap Bubbling after a Removal, 104
      • Performance, 106
    • 2.4.4 Heap-Sort, 107
      • Implementing Heap-Sort In-Place, 107
      • Bottom-Up Heap Construction, 109
      • The Locator Design Pattern, 112
      • Locator-Based Priority Queue Methods, 112
      • Extending the Priority Queue ADT, 113
      • Comparison of Different Priority Queue Implementations, 113
  • 2.5 Dictionaries and Hash Tables, 114
    • 2.5.1 The Unordered Dictionary ADT, 114
      • Log Files, 115
    • 2.5.2 Hash Tables, 116
      • Bucket Arrays, 116
      • Analysis of the Bucket Array Structure, 117
    • 2.5.3 Hash Functions, 117
      • Hash Codes, 118
      • Summing Components, 118
      • Polynomial Hash Codes, 118
      • An Experimental Hash Code Analysis, 119
    • 2.5.4 Compression Maps, 119
      • The Division Method, 119
      • The MAD Method, 120
    • 2.5.5 Collision-Handling Schemes, 120
      • Separate Chaining, 121
      • Load Factors and Rehashing, 122
      • Open Addressing, 123
      • Linear Probing, 123
      • Quadratic Probing, 124
      • Double Hashing, 124
    • 2.5.6 Universal Hashing, 125
  • 2.6 Java Example: Heap, 128
  • 2.7 Exercises, 131

  3. Search Trees and Skip Lists, 139

  • 3.1 Ordered Dictionaries and Binary Search Trees, 141
    • 3.1.1 Sorted Tables, 142
      • Binary Search, 142
    • 3.1.2 Binary Search Trees, 145
    • 3.1.3 Searching in a Binary Search Tree, 146
      • Analysis of Binary Tree Searching, 147
    • 3.1.4 Insertion in a Binary Search Tree, 148
    • 3.1.5 Removal in a Binary Search Tree, 149
    • 3.1.6 Performance of Binary Search Trees, 151
  • 3.2 AVL Trees, 152
    • Definition, 152
    • 3.2.1 Update Operations, 154
      • Insertion, 154
      • Removal, 157
    • 3.2.2 Performance, 158
  • 3.3 Bounded-Depth Search Trees, 159
    • 3.3.1 Multi-Way Search Trees, 159
      • Searching in a Multi-Way Tree, 161
      • Data Structures for Multi-Way Search Trees, 161
      • Performance Issues for Multi-Way Search Trees, 162
    • 3.3.2 (2,4) Trees, 163
      • Insertion in a (2,4) Tree, 164
      • Performance of (2,4) Tree Insertion, 166
      • Removal in a (2,4) Tree, 167
      • Performance of a (2,4) Tree, 169
    • 3.3.3 Red-Black Trees, 170
      • Insertion in a Red-Black Tree, 172
      • Removal in a Red-Black Tree, 177
      • Performance of a Red-Black Tree, 184
  • 3.4 Splay Trees, 185
    • 3.4.1 Splaying, 185
      • When to Splay, 189
    • 3.4.2 Amortized Analysis of Splaying, 191
  • 3.5 Skip Lists, 195
    • Randomizing Data Structures and Algorithms, 195
    • Skip List Definition, 195
    • 3.5.1 Searching, 197
    • 3.5.2 Update Operations, 198
      • Insertion, 198
      • Removal, 199
      • Maintaining the Top-most Level, 200
    • 3.5.3 A Probabilistic Analysis of Skip Lists, 200
      • Bounding Height in a Skip List, 201
      • Analyzing Search Time in a Skip List, 201
      • Space Usage in a Skip List, 202
  • 3.6 Java Example: AVL and Red-Black Trees, 202
    • 3.6.1 Java Implementation of AVL Trees, 206
    • 3.6.2 Java Implementation of Red-Black Trees, 209
  • 3.7 Exercises, 212

  4. Sorting, Sets, and Selection, 217

  • 4.1 Merge-Sort, 219
    • 4.1.1 Divide-and-Conquer, 219
      • Using Divide-and-Conquer for Sorting, 219
      • Merging Two Sorted Sequences, 221
      • The Running Time of Merge-Sort, 223
    • 4.1.2 Merge-Sort and Recurrence Equations, 224
  • 4.2 The Set Abstract Data Type, 225
    • Sets and Some of Their Uses, 225
    • Fundamental Methods of the Set ADT, 225
    • 4.2.1 A Simple Set Implementation, 226
      • Performance of Generic Merging, 226
    • 4.2.2 Partitions with Union-Find Operations, 227
      • Sequence Implementation, 227
      • Performance of the Sequence Implementation, 228
    • 4.2.3 A Tree-Based Partition Implementation, 229
      • Defining a Rank Function, 230
      • Amortized Analysis, 231
      • The Ackermann Function, 234
  • 4.3 Quick-Sort, 235
    • Running Time of Quick-Sort, 236
    • 4.3.1 Randomized Quick-Sort, 237
  • 4.4 A Lower Bound on Comparison-Based Sorting, 239
  • 4.5 Bucket-Sort and Radix-Sort, 241
    • 4.5.1 Bucket-Sort, 241
      • Stable Sorting, 242
    • 4.5.2 Radix-Sort, 242
  • 4.6 Comparison of Sorting Algorithms, 244
  • 4.7 Selection, 245
    • 4.7.1 Prune-and-Search, 245
    • 4.7.2 Randomized Quick-Select, 245
    • 4.7.3 Analyzing Randomized Quick-Select, 246
  • 4.8 Java Example: In-Place Quick-Sort, 248
  • 4.9 Exercises, 251

  5. Fundamental Techniques, 257

  • 5.1 The Greedy Method, 259
    • 5.1.1 The Fractional Knapsack Problem, 259
    • 5.1.2 Task Scheduling, 261
      • Correctness of Greedy Task Scheduling, 262
  • 5.2 Divide-and-Conquer, 263
    • 5.2.1 Divide-and-Conquer Recurrence Equations, 263
      • The Iterative Substitution Method, 264
      • The Recursion Tree, 265
      • The Guess-and-Test Method, 266
      • The Master Method, 268
    • 5.2.2 Integer Multiplication, 270
    • 5.2.3 Matrix Multiplication, 272
  • 5.3 Dynamic Programming, 274
    • 5.3.1 Matrix Chain-Product, 274
      • Defining Subproblems, 275
      • Characterizing Optimal Solutions, 275
      • Designing a Dynamic Programming Algorithm, 276
      • Analyzing the Matrix Chain-Product Algorithm, 277
    • 5.3.2 The General Technique, 278
    • 5.3.3 The 0-1 Knapsack Problem, 278
      • A First Attempt at Characterizing Subproblems, 279
      • A Better Subproblem Characterization, 280
      • Analyzing the 0-1 Knapsack Dynamic Programming Algorithm, 281
      • Pseudo-Polynomial-Time Algorithms, 281
  • 5.4 Exercises, 282

  Part II. Graph Algorithms

  6. Graphs, 287

  • 6.1 The Graph Abstract Data Type, 289
    • 6.1.1 Graph Methods, 293
      • General Methods, 294
      • Methods Dealing with Directed Edges, 294
      • Methods for Updating Graphs, 295
  • 6.2 Data Structures for Graphs, 296
    • 6.2.1 The Edge List Structure, 296
      • Vertex Objects, 296
      • Edge Objects, 297
      • The Edge List, 298
      • Performance, 298
    • 6.2.2 The Adjacency List Structure, 299
      • The Adjacency List, 299
    • 6.2.3 The Adjacency Matrix Structure, 301
  • 6.3 Graph Traversal, 303
    • 6.3.1 Depth-First Search, 303
      • Traversing a Graph via the Backtracking Technique, 303
      • Visualizing Depth-First Search, 305
      • Recursive Depth-First Search, 305
    • 6.3.2 Biconnected Components, 307
      • Equivalence Classes and the Linked Relation, 308
      • A Linked Approach to Computing Biconnected Components via DFS, 309
      • An O(nm)-Time Algorithm, 310
      • A Linear-Time Algorithm, 311
    • 6.3.3 Breadth-First Search, 313
      • Comparing BFS and DFS, 316
  • 6.4 Directed Graphs, 316
    • Reachability, 316
    • 6.4.1 Traversing a Digraph, 318
      • Testing for Strong Connectivity, 319
      • Directed Breadth-First Search, 320
    • 6.4.2 Transitive Closure, 320
      • Performance of the Floyd-Warshall Algorithm, 321
    • 6.4.3 DFS and Garbage Collection, 323
      • The Mark-Sweep Algorithm, 323
      • Performing DFS In-place, 324
    • 6.4.4 Directed Acyclic Graphs, 325
  • 6.5 Java Example: Depth-First Search, 329
    • 6.5.1 The Decorator Pattern, 329
      • Implementing the Decorator Pattern, 329
    • 6.5.2 A DFS Engine, 330
    • 6.5.3 The Template Method Design Pattern, 331
      • Definition of the Template Method Pattern, 332
      • Using the DFS Template, 332
      • Extending DFS for Path Finding, 333
      • Extending DFS for Cycle Finding, 334
  • 6.6 Exercises, 335

  7. Weighted Graphs, 339

  • 7.1 Single-Source Shortest Paths, 341
    • 7.1.1 Dijkstra's Algorithm, 342
      • A Greedy Method for Finding Shortest Paths, 342
      • Edge Relaxation, 342
      • The Details of Dijkstra's Algorithm, 343
      • Why It Works, 345
      • The Running Time of Dijkstra's Algorithm, 347
      • An Alternative Implementation for Dijkstra's Algorithm, 348
      • Comparing the Two Implementations, 348
    • 7.1.2 The Bellman-Ford Shortest Paths Algorithm, 349
      • The Details of the Bellman-Ford Algorithm, 349
    • 7.1.3 Shortest Paths in Directed Acyclic Graphs, 352
      • The Details for Computing Shortest Paths in a DAG, 352
  • 7.2 All-Pairs Shortest Paths, 354
    • 7.2.1 A Dynamic Programming Shortest Path Algorithm, 354
    • 7.2.2 Computing Shortest Paths via Matrix Multiplication, 355
      • The Weighted Adjacency Matrix Representation, 356
      • Shortest Paths and Matrix Multiplication, 356
      • Matrix Closure, 357
      • Computing the Closure of a Weighted Adjacency Matrix, 358
      • Submatrix Equations, 359
  • 7.3 Minimum Spanning Trees, 360
    • Problem Definition, 360
    • A Crucial Fact about Minimum Spanning Trees, 361
    • 7.3.1 Kruskal's Algorithm, 362
      • Implementing Kruskal's Algorithm, 365
      • A Simple Cluster Merging Strategy, 365
    • 7.3.2 The Prim-Jarnik Algorithm, 366
      • Growing a Single MST, 366
      • Analyzing the Prim-Jarnik Algorithm, 367
    • 7.3.3 Baruvka's Algorithm, 369
      • Implementing Baruvka's Algorithm, 370
      • Why Is This Algorithm Correct?, 370
      • Analyzing Baruvka's Algorithm, 372
    • 7.3.4 A Comparison of MST Algorithms, 372
  • 7.4 Java Example: Dijkstra's Algorithm, 373
  • 7.5 Exercises, 376

  8. Network Flow and Matching, 381

  • 8.1 Flows and Cuts, 383
    • 8.1.1 Flow Networks, 383
    • 8.1.2 Cuts, 385
  • 8.2 Maximum Flow, 387
    • 8.2.1 Residual Capacity and Augmenting Paths, 387
      • Residual Capacity, 387
      • Augmenting Paths, 388
    • 8.2.2 The Ford-Fulkerson Algorithm, 390
      • Implementation Details, 392
    • 8.2.3 Analyzing the Ford-Fulkerson Algorithm, 392
    • 8.2.4 The Edmonds-Karp Algorithm, 393
      • Performance of the Edmonds-Karp Algorithm, 394
  • 8.3 Maximum Bipartite Matching, 396
    • 8.3.1 A Reduction to the Maximum Flow Problem, 396
  • 8.4 Minimum-Cost Flow, 398
    • 8.4.1 Augmenting Cycles, 398
      • Adding the Flow from an Augmenting Cycle, 399
      • A Condition for Minimum-Cost Flows, 399
      • An Algorithmic Approach for Finding Minimum-Cost Flows, 399
    • 8.4.2 Successive Shortest Paths, 400
    • 8.4.3 Modified Weights, 402
  • 8.5 Java Example: Minimum-Cost Flow, 405
  • 8.6 Exercises, 412

  Part III. Internet Algorithmics

  9. Text Processing, 417

  • 9.1 Strings and Pattern Matching Algorithms, 419
    • 9.1.1 String Operations, 419
      • The Pattern Matching Problem, 420
    • 9.1.2 Brute Force Pattern Matching, 420
      • Brute-Force Pattern Matching, 420
    • 9.1.3 The Boyer-Moore Algorithm, 422
    • 9.1.4 The Knuth-Morris-Pratt Algorithm, 425
      • The Failure Function, 425
      • Performance, 427
      • Constructing the KMP Failure Function, 428
  • 9.2 Tries, 429
    • 9.2.1 Standard Tries, 429
      • Performance, 431
    • 9.2.2 Compressed Tries, 433
    • 9.2.3 Suffix Tries, 435
      • Saving Space, 436
      • Construction, 436
      • Using a Suffix Trie, 436
      • Suffix Trie Properties, 438
      • Performance, 438
    • 9.2.4 Search Engines, 439
      • Inverted Files, 439
  • 9.3 Text Compression, 440
    • 9.3.1 The Huffman Coding Algorithm, 441
    • 9.3.2 The Greedy Method Revisited, 442
  • 9.4 Text Similarity Testing, 443
    • 9.4.1 The Longest Common Subsequence Problem, 443
      • Problem Definition, 443
    • 9.4.2 Applying Dynamic Programming to the LCS Problem, 444
      • The LCS Algorithm, 445
      • Performance, 445
  • 9.5 Exercises, 447

  10. Number Theory and Cryptography, 451

  • 10.1 Fundamental Algorithms Involving Numbers, 453
    • 10.1.1 Some Facts from Elementary Number Theory, 453
      • The Greatest Common Divisor (GCD), 454
      • The Modulo Operator, 454
      • Relating the Modulo Operator and the GCD, 454
    • 10.1.2 Euclid's GCD Algorithm, 455
      • Analyzing Euclid's Algorithm, 456
      • Binary Euclid's Algorithm, 457
    • 10.1.3 Modular Arithmetic, 458
      • Fermat's Little Theorem, 459
      • Euler's Theorem, 460
      • Generators, 462
    • 10.1.4 Modular Exponentiation, 462
      • Brute-Force Exponentiation, 462
      • The Repeated Squaring Algorithm, 463
    • 10.1.5 Modular Multiplicative Inverses, 464
      • Extended Euclid's Algorithm, 464
    • 10.1.6 Primality Testing, 466
      • A Template for Primality Testing, 466
      • The Solovay-Strassen Primality Testing Algorithm, 467
      • The Rabin-Miller Primality Testing Algorithm, 470
      • Finding Prime Numbers, 471
  • 10.2 Cryptographic Computations, 471
    • Using Cryptographic Computations for Information Security Services, 472
    • 10.2.1 Symmetric Encryption Schemes, 473
      • Secret Keys, 473
      • Substitution Ciphers, 473
      • The One-Time Pad, 474
      • Other Symmetric Ciphers, 474
    • 10.2.2 Public-Key Cryptosystems, 475
    • 10.2.3 The RSA Cryptosystem, 476
      • Using RSA for Digital Signatures, 477
      • The Difficulty of Breaking RSA, 478
      • Analysis and Setup for RSA Encryption, 478
    • 10.2.4 The El Gamal Cryptosystem, 479
      • The Discrete Logarithm, 479
      • El Gamal Encryption, 479
      • El Gamal Decryption, 479
      • Using El Gamal for Digital Signatures, 480
      • Analysis of El Gamal Encryption, 480
  • 10.3 Information Security Algorithms and Protocols, 481
    • 10.3.1 One-way Hash Functions, 481
    • 10.3.2 Timestamping and Authenticated Dictionaries, 482
      • Authenticated Dictionaries, 482
      • Hash Trees, 482
    • 10.3.3 Coin Flipping and Bit Commitment, 483
    • 10.3.4 The Secure Electronic Transaction (SET) Protocol, 484
      • Properties of the SET Protocol, 484
    • 10.3.5 Key Distribution and Exchange, 486
      • Digital Certificates, 486
      • Certificate Revocation, 486
      • Using Public Keys for Symmetric Key Exchange, 487
      • Diffie-Hellman Secret Key Exchange, 487
  • 10.4 The Fast Fourier Transform, 488
    • 10.4.1 Primitive Roots of Unity, 489
    • 10.4.2 The Discrete Fourier Transform, 491
      • The Inverse Discrete Fourier Transform, 491
      • The Convolution Theorem, 492
    • 10.4.3 The Fast Fourier Transform Algorithm, 495
      • The Correctness of the FFT Algorithm, 496
      • Analyzing the FFT Algorithm, 497
    • 10.4.4 Multiplying Big Integers, 497
  • 10.5 Java Example: FFT, 500
    • A Recursive FFT Implementation, 500
    • Avoiding Repeated Array Allocation, 502
    • The Inverse Shuffle, 502
    • Precomputing Roots of Unity and Other Optimizations, 503
    • An Iterative FFT Implementation, 504
    • Computing the FFT in Place, 504
    • Avoiding Recursion, 504
    • Experimental Results, 506
  • 10.6 Exercises, 508

  11. Network Algorithms, 511

  • 11.1 Complexity Measures and Models, 513
    • 11.1.1 The Networking Protocol Stack, 513
    • 11.1.2 The Message-Passing Model, 514
    • 11.1.3 Complexity Measures for Network Algorithms, 516
  • 11.2 Fundamental Distributed Algorithms, 517
    • 11.2.1 Leader Election in a Ring, 517
      • Asynchronous Leader Election, 520
    • 11.2.2 Leader Election in a Tree, 521
      • Asynchronous Leader Election in a Tree, 521
      • Synchronous Leader Election in a Tree, 523
      • Performance of Tree Leader Election Algorithms, 523
    • 11.2.3 Breadth-First Search, 523
      • Synchronous BFS, 524
      • Asynchronous BFS, 525
      • Performance, 527
    • 11.2.4 Minimum Spanning Trees, 528
      • Baruvka's Algorithm in a Distributed Setting, 528
  • 11.3 Broadcast and Unicast Routing, 530
    • 11.3.1 The Flooding Algorithm for Broadcast Routing, 530
      • Flooding with a Hop Counter, 530
      • Flooding with Sequence Numbers, 531
      • Analysis of Flooding Algorithms, 531
    • 11.3.2 The Distance Vector Algorithm for Unicast Routing, 532
      • Distributed Relaxation, 532
      • Performance, 533
      • Correctness of the Distance Vector Algorithm, 533
      • Analysis of the Distance Vector Algorithm, 533
    • 11.3.3 The Link-State Algorithm for Unicast Routing, 534
      • Comparison of Broadcast and Unicast Routing Algorithms, 534
  • 11.4 Multicast Routing, 535
    • 11.4.1 Reverse Path Forwarding, 535
      • Pruning, 536
      • Performance, 536
    • 11.4.2 Center-Based Trees, 537
      • Performance, 538
    • 11.4.3 Steiner Trees, 538
      • Analysis, 540
  • 11.5 Exercises, 541

  Part IV. Additional Topics

  12. Computational Geometry, 547

  • 12.1 Range Trees, 549
    • Two-Dimensional Range-Search Queries, 549
    • 12.1.1 One-Dimensional Range Searching, 550
      • Performance, 551
    • 12.1.2 Two-Dimensional Range Searching, 553
  • 12.2 Priority Search Trees, 556
    • 12.2.1 Constructing a Priority Search Tree, 557
    • 12.2.2 Searching in a Priority Search Tree, 558
    • 12.2.3 Priority Range Trees, 560
  • 12.3 Quadtrees and k-D Trees, 561
    • 12.3.1 Quadtrees, 561
      • Answering Range Queries with a Quadtree, 562
      • Performance, 562
    • 12.3.2 k-D Trees, 563
      • Using k-d Trees for Nearest Neighbor Searching, 564
  • 12.4 The Plane Sweep Technique, 565
    • 12.4.1 Orthogonal Segment Intersection, 565
      • One-Dimensional Range Searching Revisited, 565
      • A Collection of Range-Searching Problems, 566
      • The Plane-Sweep Segment Intersection Algorithm, 566
      • Performance, 568
    • 12.4.2 Finding a Closest Pair of Points, 568
      • A Plane-Sweep Algorithm, 569
  • 12.5 Convex Hulls, 572
    • 12.5.1 Representations of Geometric Objects, 572
      • Lines, Segments, and Polygons, 573
    • 12.5.2 Point Orientation Testing, 574
    • 12.5.3 Basic Properties of Convex Hulls, 576
    • 12.5.4 The Gift Wrapping Algorithm, 578
      • Performance, 579
    • 12.5.5 The Graham Scan Algorithm, 580
      • Performance, 581
  • 12.6 Java Example: Convex Hull, 583
  • 12.7 Exercises, 587

  13. NP-Completeness, 591

  • 13.1 P and NP, 593
    • 13.1.1 Defining the Complexity Classes P and NP, 594
      • Decision Problems, 594
      • Problems and Languages, 594
      • The Complexity Class P, 595
      • The Complexity Class NP, 595
      • An Alternate Definition of NP, 596
      • The P = NP Question, 597
    • 13.1.2 Some Interesting Problems in NP, 597
  • 13.2 NP-Completeness, 599
    • 13.2.1 Polynomial-Time Reducibility and NP-Hardness, 600
    • 13.2.2 The Cook-Levin Theorem, 600
  • 13.3 Important NP-Complete Problems, 603
    • 13.3.1 CNF-Sat and 3Sat, 605
      • CNF-Sat, 605
      • 3Sat, 607
    • 13.3.2 Vertex-Cover, 608
    • 13.3.3 Clique and Set-Cover, 610
      • Clique, 610
      • Set-Cover, 611
    • 13.3.4 Subset-Sum and Knapsack, 612
      • Subset-Sum, 612 <
      • Knapsack, 614
    • 13.3.5 Hamiltonian-Cycle and TSP, 615
      • Hamiltonian-Cycle, 615
      • TSP, 617
  • 13.4 Approximation Algorithms, 618
    • 13.4.1 Polynomial-Time Approximation Schemes, 619
      • A Fully Polynomial-Time Approximation Scheme for Knapsack. 619
      • Analysis of the PTAS for Knapsack, 621
    • 13.4.2 A 2-Approximation for Vertex-Cover, 622
    • 13.4.3 A 2-Approximation for a Special Case of TSP, 623
      • The Triangle Inequality, 623
      • The Approximation Algorithm, 623
      • Analysis of the TSP Approximation Algorithm, 624
    • 13.4.4 A Logarithmic Approximation for Set-Cover, 625
      • A Greedy Approach, 625
      • Analyzing the Greedy Set-Cover Algorithm, 625
  • 13.5 Backtracking and Branch-and-Bound, 627
    • 13.5.1 Backtracking, 627
      • Filling in the Details, 628
      • A Backtracking Algorithm for CNF-Sat, 629
      • Java Example: A Backtracking Solution for Subset-Sum, 630
    • 13.5.2 Branch-and-Bound, 632
      • A Branch-and-Bound Algorithm for TSP, 633
      • Java Example: A Branch-and-Bound Solution for Knapsack, 634
  • 13.6 Exercises, 638

  14. Algorithmic Frameworks, 643

  • 14.1 External-Memory Algorithms, 645
    • The Memory Hierarchy, 645
    • Caches and Disks, 646
    • 14.1.1 Hierarchical Memory Management, 646
      • Caching and Blocking, 647
      • A Model for External Searching, 648
    • 14.1.2 (a,b) Trees and B-Trees, 649
      • A Better Approach, 649
      • (a,b) Trees, 650
      • Insertion and Removal in an (a,b) Tree, 651
      • B-Trees, 652
      • Parameterizing B-trees for External Memory, 653
    • 14.1.3 External-Memory Sorting, 654
      • A Lower Bound for External-Memory Sorting, 654
      • Multi-way Merge-Sort, 654
      • Achieving ``Near'' Machine Independence, 656
  • 14.2 Parallel Algorithms, 657
    • 14.2.1 Parallel Models of Computation, 657
      • Parallel Efficiency, 657
      • Versions of the PRAM Model, 658
    • 14.2.2 Simple Parallel Divide-and-Conquer, 659
    • 14.2.3 Sequential Subsets and Brent's Theorem, 659
      • Brent's Theorem, 660
    • 14.2.4 Recursive Doubling, 661
      • Parallel Prefix, 662
    • 14.2.5 Parallel Merging and Sorting, 664
    • 14.2.6 Finding the Diameter of a Convex Polygon, 665
  • 14.3 Online Algorithms, 667
    • The Renter's Dilemma, 667
    • 14.3.1 Caching Algorithms, 668
      • A Worst-Case Competitive Analysis of FIFO and LRU, 670
      • The Randomized Marker Algorithm, 671
      • Competitive Analysis for a Randomized Online Algorithm, 671
    • 14.3.2 Auction Strategies, 674
      • Competitive Analysis for a Maximization Problem, 674
      • Randomized Thresholding, 675
    • 14.3.3 Competitive Search Trees, 676
      • Energy-Balanced Binary Search Trees, 676
      • Biased Energy-Balanced Search Trees, 677
  • 14.4 Exercises, 680

  A. Useful Mathematical Facts, 685

  • Logarithms and Exponents, 685
  • Integer Functions and Relations, 686
  • Summations, 687
  • Useful Mathematical Techniques, 688

  Bibliography, 689

  Index. 698