Algorithm Design

Michael T. Goodrich is a mathematician and computer scientist. He is a Chancellor's Professor and the chair of Department of Computer Science, of Donald Bren School of Information and Computer Sciences, a school of University of California, Irvine. Roberto Tamassia is the author of Algorithm Design: Foundations, Analysis, and Internet Examples, published by Wiley.

• I Fundamental Tools 11 Algorithm Analysis 31.1 Methodologies for Analyzing Algorithms  51.2 Asymptotic Notation 131.3 A Quick Mathematical Review  211.4 Case Studies in Algorithm Analysis  311.5 Amortization  341.6 Experimentation  421.7 Exercises  472 Basic Data Structures 552.1 Stack sand Queues  572.2 Vectors, Lists, and Sequences  652.3 Trees  752.4 Priority Queues and Heaps  942.5 Dictionaries and Hash Tables  1142.6 Java Example: Heap  1282.7 Exercises  1313 Search Trees and Skip Lists 1393.1 Ordered Dictionaries and Binary Search Trees  1413.2 AVL Trees  1523.3 Bounded-Depth Search Trees  1593.4 Splay Trees  1853.5 Sk i p Lists  1953.6 Java Example: AVL and Red-Black Trees  2023.7 Exercises  2124 Sorting, Sets, and Selection 2174.1 Merge-Sort  2194.2 The Set Abstract Data Type  2254.3 Quick -Sort  2354.4 A Lower Bound on Comparison-Based Sorting  2394.5 Buck et-Sort and Radix-Sort  2414.6 Comparison of Sorting Algorithms  2444.7 Selection  2454.8 Java Example: In-Place Quick -Sort  2484.9 Exercises  2515 Fundamental Techniques 2575.1 The GreedyMethod  2595.2 Divide-and-Conquer  2635.3 Dynamic Programming  2745.4 Exercises  282II Graph Algorithms 2856 Graphs 2876.1 The Graph Abstract Data Type  2896.2 Data Structures for Graphs  2966.3 Graph Traversal  3036.4 Directed Graphs  3166.5 Java Example: Depth-First Search  3296.6 Exercises  3357 Weighted Graphs 3397.1 Single-Source Shortest Paths  3417.2 All-Pairs Shortest Paths  3547.3 Minimum Spanning Trees  3607.4 Java Example: Dijk stra’s Algorithm  3737.5 Exercises  3768 Network Flow and Matching 3818.1 Flows and Cuts  3838.2 Maximum Flow  3878.3 Maximum BipartiteMatching  3968.4 Minimum-Cost Flow  3988.5 Java Example: Minimum-Cost Flow  4058.6 Exercises  412III Internet Algorithmics 4159 Text Processing 4179.1 Strings and PatternMatching Algorithms  4199.2 Tries  4299.3 Text Compression  4409.4 Text Similarity Testing  4439.5 Exercises  44710 Number Theory and Cryptography 45110.1 Fundamental Algorithms Involving Numbers  45310.2 Cryptographic Computations  47110.3 Information Security Algorithms and Protocols  48110.4 The Fast Fourier Transform  48810.5 Java Example: FFT  50010.6 Exercises  50811 Network Algorithms 51111.1 ComplexityMeasures and Models  51311.2 Fundamental Distributed Algorithms  51711.3 Broadcast and Unicast Routing  53011.4 Multicast Routing  53511.5 Exercises  541IV Additional Topics 54512 Computational Geometry 54712.1 Range Trees  54912.2 Priority Search Trees  55612.3 Quadtrees and k-D Trees  56112.4 The Plane Sweep Technique  56512.5 Convex Hulls  57212.6 Java Example: Convex Hull  58312.7 Exercises  58713 NP-Completeness 59113.1 P and NP  59313.2 NP-Completeness  59913.3 Important NP-Complete Problems  60313.4 Approximation Algorithms  61813.5 Back track i ng and Branch-and-Bound  62713.6 Exercises  63814 Algorithmic Frameworks 64314.1 External-Memory Algorithms  64514.2 Parallel Algorithms  65714.3 Online Algorithms  66714.4 Exercises  680A Useful Mathematical Facts 685Bibliography 689Index 698