Preface xi
1 AlgorithmAnalysis 1
1.1 Analyzing Algorithms 3
1.2 A Quick Mathematical Review 19
1.3 A Case Study in Algorithm Analysis 29
1.4 Amortization 34
1.5 Exercises 42
Part I: Data Structures
2 BasicDataStructures 51
2.1 Stacks and Queues 53
2.2 Lists 60
2.3 Trees 68
2.4 Exercises 84
3 BinarySearchTrees 89
3.1 Searches and Updates 91
3.2 Range Queries 101
3.3 Index-Based Searching 104
3.4 Randomly-Constructed Search Trees 107
3.5 Exercises 110
4 BalancedBinarySearchTrees 115
4.1 Ranks and Rotations 117
4.2 AVL Trees 120
4.3 Red-Black Trees 126
4.4 Weak AVL Trees 130
4.5 Splay Trees 139
4.6 Exercises 149
5 PriorityQueuesandHeaps 155
5.1 Priority Queues 157
5.2 PQ-Sort, Selection-Sort, and Insertion-Sort 158
5.3 Heaps 163
5.4 Heap-Sort 174
5.5 Extending Priority Queues 179
5.6 Exercises 182
6 HashTables 187
6.1 Maps 189
6.2 Hash Functions 192
6.3 Handling Collisions and Rehashing 198
6.4 Cuckoo Hashing 206
6.5 Universal Hashing 212
6.6 Exercises 215
7 Union-FindStructures 219
7.1 Union-Find and its Applications 221
7.2 A List-Based Implementation 225
7.3 A Tree-Based Implementation 228
7.4 Exercises 236
Part II: Sorting and Selection
8 Merge-SortandQuick-Sort 241
8.1 Merge-Sort 243
8.2 Quick-Sort 250
8.3 A Lower Bound on Comparison-Based Sorting 257
8.4 Exercises 259
9 FastSortingandSelection 265
9.1 Bucket Sort and Radix Sort 267
9.2 Selection 270
9.3 Weighted Medians 276
9.4 Exercises 279
Part III: Fundamental Techniques
10 The Greedy Method 283
10.1 The Fractional Knapsack Problem 286
10.2 Task Scheduling 289
10.3 Text Compression and Huffman Coding 292
10.4 Exercises 298
11 Divide-and-Conquer 303
11.1 Recurrences and the Master Theorem 305
11.2 Integer Multiplication 313
11.3 Matrix Multiplication 315
11.4 The Maxima-Set Problem 317
11.5 Exercises 319
12 Dynamic Programming 323
12.1 Matrix Chain-Products 325
12.2 The General Technique 329
12.3 Telescope Scheduling 331
12.4 Game Strategies 334
12.5 The Longest Common Subsequence Problem 339
12.6 The 0-1 Knapsack Problem 343
12.7 Exercises 346
Part IV: Graph Algorithms
13 Graphs and Traversals 353
13.1 Graph Terminology and Representations 355
13.2 Depth-First Search 365
13.3 Breadth-First Search 370
13.4 Directed Graphs 373
13.5 Biconnected Components 386
13.6 Exercises 392
14 Shortest Paths 397
14.1 Single-Source Shortest Paths 399
14.2 Dijkstra?s Algorithm 400
14.3 The Bellman-Ford Algorithm 407
14.4 Shortest Paths in Directed Acyclic Graphs 410
14.5 All-Pairs Shortest Paths 412
14.6 Exercises 418
15 Minimum Spanning Trees 423
15.1 Properties of Minimum Spanning Trees 425
15.2 Kruskal?s Algorithm 428
15.3 The Prim-Jarn´ýk Algorithm 433
15.4 Bar°uvka?s Algorithm 436
15.5 Exercises 439
16 Network Flow and Matching 443
16.1 Flows and Cuts 445
16.2 Maximum Flow Algorithms 452
16.3 Maximum Bipartite Matching 458
16.4 Baseball Elimination 460
16.5 Minimum-Cost Flow 462
16.6 Exercises 469
Part V: Computational Intractability
17 NP-Completeness 473
17.1 P and NP 476
17.2 NP-Completeness 483
17.3 CNF-SAT and 3SAT 489
17.4 VERTEX-COVER, CLIQUE, and SET-COVER 492
17.5 SUBSET-SUM and KNAPSACK 496
17.6 HAMILTONIAN-CYCLE and TSP 499
17.7 Exercises 502
18 Approximation Algorithms 507
18.1 The Metric Traveling Salesperson Problem 511
18.2 Approximations for Covering Problems 515
18.3 Polynomial-Time Approximation Schemes 518
18.4 Backtracking and Branch-and-Bound 521
18.5 Exercises 525
Part VI: Additional Topics
19 Randomized Algorithms 529
19.1 Generating Random Permutations 531
19.2 Stable Marriages and Coupon Collecting 534
19.3 Minimum Cuts 539
19.4 Finding Prime Numbers 546
19.5 Chernoff Bounds 551
19.6 Skip Lists 557
19.7 Exercises 563
20 B-Trees and External-Memory 569
20.1 External Memory 571
20.2 (2,4) Trees and B-Trees 574
20.3 External-Memory Sorting 590
20.4 Online Caching Algorithms 593
20.5 Exercises 600
21 Multi-Dimensional Searching 603
21.1 Range Trees 605
21.2 Priority Search Trees 609
21.3 Quadtrees and k-D Trees 614
21.4 Exercises 618
22 Computational Geometry 623
22.1 Operations on Geometric Objects 625
22.2 Convex Hulls 630
22.3 Segment Intersection 638
22.4 Finding a Closest Pair of Points 642
22.5 Exercises 646
23 String Algorithms 651
23.1 String Operations 653
23.2 The Boyer-Moore Algorithm 656
23.3 The Knuth-Morris-Pratt Algorithm 660
23.4 Hash-Based Lexicon Matching 664
23.5 Tries 669
23.6 Exercises 680
24 Cryptography 685
24.1 Greatest Common Divisors (GCD) 687
24.2 Modular Arithmetic 691
24.3 Cryptographic Operations 699
24.4 The RSA Cryptosystem 703
24.5 The El Gamal Cryptosystem 706
24.6 Exercises 708
25 The Fast Fourier Transform 711
25.1 Convolution 713
25.2 Primitive Roots of Unity 715
25.3 The Discrete Fourier Transform 717
25.4 The Fast Fourier Transform Algorithm 721
25.5 Exercises 727
26 Linear Programming 731
26.1 Formulating the Problem 734
26.2 The Simplex Method 739
26.3 Duality 746
26.4 Applications of Linear Programming 750
26.5 Exercises 753
A UsefulMathematicalFacts 761
Bibliography 765
Index 774
