Algorithm Design and Applications

Michael T. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, Bioinformatics, and geometric computing. He has pioneered and led research on efficient solutions to a number of fundamental problems, including sorting, convex hull construction, linear programming, privacy-preserving data access, network traceback, and data authentication.

• Preface xi1 AlgorithmAnalysis 11.1 Analyzing Algorithms 31.2 A Quick Mathematical Review 191.3 A Case Study in Algorithm Analysis 291.4 Amortization 341.5 Exercises 42Part I: Data Structures2 BasicDataStructures 512.1 Stacks and Queues 532.2 Lists 602.3 Trees 682.4 Exercises 843 BinarySearchTrees 893.1 Searches and Updates 913.2 Range Queries 1013.3 Index-Based Searching 1043.4 Randomly-Constructed Search Trees 1073.5 Exercises 1104 BalancedBinarySearchTrees 1154.1 Ranks and Rotations 1174.2 AVL Trees 1204.3 Red-Black Trees 1264.4 Weak AVL Trees 1304.5 Splay Trees 1394.6 Exercises 1495 PriorityQueuesandHeaps 1555.1 Priority Queues 1575.2 PQ-Sort, Selection-Sort, and Insertion-Sort 1585.3 Heaps 1635.4 Heap-Sort 1745.5 Extending Priority Queues 1795.6 Exercises 1826 HashTables 1876.1 Maps 1896.2 Hash Functions 1926.3 Handling Collisions and Rehashing 1986.4 Cuckoo Hashing 2066.5 Universal Hashing 2126.6 Exercises 2157 Union-FindStructures 2197.1 Union-Find and its Applications 2217.2 A List-Based Implementation 2257.3 A Tree-Based Implementation 2287.4 Exercises 236Part II: Sorting and Selection8 Merge-SortandQuick-Sort 2418.1 Merge-Sort 2438.2 Quick-Sort 2508.3 A Lower Bound on Comparison-Based Sorting 2578.4 Exercises 2599 FastSortingandSelection 2659.1 Bucket Sort and Radix Sort 2679.2 Selection 2709.3 Weighted Medians 2769.4 Exercises 279Part III: Fundamental Techniques10 The Greedy Method 28310.1 The Fractional Knapsack Problem 28610.2 Task Scheduling 28910.3 Text Compression and Huffman Coding 29210.4 Exercises 29811 Divide-and-Conquer 30311.1 Recurrences and the Master Theorem 30511.2 Integer Multiplication 31311.3 Matrix Multiplication 31511.4 The Maxima-Set Problem 31711.5 Exercises 31912 Dynamic Programming 32312.1 Matrix Chain-Products 32512.2 The General Technique 32912.3 Telescope Scheduling 33112.4 Game Strategies 33412.5 The Longest Common Subsequence Problem 33912.6 The 0-1 Knapsack Problem 34312.7 Exercises 346Part IV: Graph Algorithms13 Graphs and Traversals 35313.1 Graph Terminology and Representations 35513.2 Depth-First Search 36513.3 Breadth-First Search 37013.4 Directed Graphs 37313.5 Biconnected Components 38613.6 Exercises 39214 Shortest Paths 39714.1 Single-Source Shortest Paths 39914.2 Dijkstra’s Algorithm 40014.3 The Bellman-Ford Algorithm 40714.4 Shortest Paths in Directed Acyclic Graphs 41014.5 All-Pairs Shortest Paths 41214.6 Exercises 41815 Minimum Spanning Trees 42315.1 Properties of Minimum Spanning Trees 42515.2 Kruskal’s Algorithm 42815.3 The Prim-Jarn´ýk Algorithm 43315.4 Bar°uvka’s Algorithm 43615.5 Exercises 43916 Network Flow and Matching 44316.1 Flows and Cuts 44516.2 Maximum Flow Algorithms 45216.3 Maximum Bipartite Matching 45816.4 Baseball Elimination 46016.5 Minimum-Cost Flow 46216.6 Exercises 469Part V: Computational Intractability17 NP-Completeness 47317.1 P and NP 47617.2 NP-Completeness 48317.3 CNF-SAT and 3SAT 48917.4 VERTEX-COVER, CLIQUE, and SET-COVER 49217.5 SUBSET-SUM and KNAPSACK 49617.6 HAMILTONIAN-CYCLE and TSP 49917.7 Exercises 50218 Approximation Algorithms 50718.1 The Metric Traveling Salesperson Problem 51118.2 Approximations for Covering Problems 51518.3 Polynomial-Time Approximation Schemes 51818.4 Backtracking and Branch-and-Bound 52118.5 Exercises 525Part VI: Additional Topics19 Randomized Algorithms 52919.1 Generating Random Permutations 53119.2 Stable Marriages and Coupon Collecting 53419.3 Minimum Cuts 53919.4 Finding Prime Numbers 54619.5 Chernoff Bounds 55119.6 Skip Lists 55719.7 Exercises 56320 B-Trees and External-Memory 56920.1 External Memory 57120.2 (2,4) Trees and B-Trees 57420.3 External-Memory Sorting 59020.4 Online Caching Algorithms 59320.5 Exercises 60021 Multi-Dimensional Searching 60321.1 Range Trees 60521.2 Priority Search Trees 60921.3 Quadtrees and k-D Trees 61421.4 Exercises 61822 Computational Geometry 62322.1 Operations on Geometric Objects 62522.2 Convex Hulls 63022.3 Segment Intersection 63822.4 Finding a Closest Pair of Points 64222.5 Exercises 64623 String Algorithms 65123.1 String Operations 65323.2 The Boyer-Moore Algorithm 65623.3 The Knuth-Morris-Pratt Algorithm 66023.4 Hash-Based Lexicon Matching 66423.5 Tries 66923.6 Exercises 68024 Cryptography 68524.1 Greatest Common Divisors (GCD) 68724.2 Modular Arithmetic 69124.3 Cryptographic Operations 69924.4 The RSA Cryptosystem 70324.5 The El Gamal Cryptosystem 70624.6 Exercises 70825 The Fast Fourier Transform 71125.1 Convolution 71325.2 Primitive Roots of Unity 71525.3 The Discrete Fourier Transform 71725.4 The Fast Fourier Transform Algorithm 72125.5 Exercises 72726 Linear Programming 73126.1 Formulating the Problem 73426.2 The Simplex Method 73926.3 Duality 74626.4 Applications of Linear Programming 75026.5 Exercises 753A UsefulMathematicalFacts 761Bibliography 765Index 774