The Algorithm Design Manual

....The most comprehensive guide to designing practical and efficient algorithms!.... The Algorithm Design Manual, Second Edition "...the book is an algorithm-implementation treasure trove, and putting all of these implementations in one place was no small feat. The list of implementations [and] extensive bibliography make the book an invaluable resource for everyone interested in the subject." --ACM Computing Reviews "It has all the right ingredients: rich contents, friendly, personal language, subtle humor, the right references, and a plethora of pointers to resources." -- P. Takis Metaxas, Wellesley College "This is the most approachable book on algorithms I have." -- Megan Squire, Elon University, USA This newly expanded and updated second edition of the best-selling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students. The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography. NEW to the second edition: • Doubles the tutorial material and exercises over the first edition • Provides full online support for lecturers, and a completely updated and improved website component with lecture slides, audio and video • Contains a unique catalog identifying the 75 algorithmic problems that arise most often in practice, leading the reader down the right path to solve them • Includes several NEW " war stories" relating experiences from real-world applications • Provides up-to-date links leading to the very best algorithm implementations available in C, C++, and Java ADDITIONAL Learning Tools: • Exercises include "job interview problems" from major software companies • Highlighted take-home lesson boxes emphasize essential concepts • Provides comprehensive references to both survey articles and the primary literature • Exercises point to relevant programming contest challenge problems • Many algorithms presented with actual code (written in C) as well as pseudo-code • A full set of lecture slides and additional material available at www.algorist.com Written by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this new edition of The Algorithm Design Manual is an essential learning tool for students needing a solid grounding in algorithms, as well as a special text/reference for professionals who need an authoritative and insightful guide. Professor Skiena is also author of the popular Springer text, Programming Challenges: The Programming Contest Training Manual Preface To the Reader To the Instructor Acknowledgments Caveat Contents Part I Practical Algorithm Design 1 Introduction to Algorithm Design 1.1 Robot Tour Optimization 1.2 Selecting the Right Jobs 1.3 Reasoning about Correctness 1.3.1 Expressing Algorithms 1.3.2 Problems and Properties 1.3.3 Demonstrating Incorrectness 1.3.4 Induction and Recursion 1.3.5 Summations 1.4 Modeling the Problem 1.4.1 Combinatorial Objects 1.4.2 Recursive Objects 1.5 About the War Stories 1.6 War Story: Psychic Modeling 1.7 Exercises 2 Algorithm Analysis 2.1 The RAM Model of Computation 2.1.1 Best, Worst, and Average-Case Complexity 2.2 The Big Oh Notation 2.3 Growth Rates and Dominance Relations 2.3.1 Dominance Relations 2.4 Working with the Big Oh 2.4.1 Adding Functions 2.4.2 Multiplying Functions 2.5 Reasoning About Efficiency 2.5.1 Selection Sort 2.5.2 Insertion Sort 2.5.3 String Pattern Matching 2.5.4 Matrix Multiplication 2.6 Logarithms and Their Applications 2.6.1 Logarithms and Binary Search 2.6.2 Logarithms and Trees 2.6.3 Logarithms and Bits 2.6.4 Logarithms and Multiplication 2.6.5 Fast Exponentiation 2.6.6 Logarithms and Summations 2.6.7 Logarithms and Criminal Justice 2.7 Properties of Logarithms 2.8 War Story: Mystery of the Pyramids 2.9 Advanced Analysis (*) 2.9.1 Esoteric Functions 2.9.2 Limits and Dominance Relations 2.10 Exercises 3 Data Structures 3.1 Contiguous vs. Linked Data Structures 3.1.1 Arrays 3.1.2 Pointers and Linked Structures 3.1.3 Comparison 3.2 Stacks and Queues 3.3 Dictionaries 3.4 Binary Search Trees 3.4.1 Implementing Binary Search Trees 3.4.2 How Good Are Binary Search Trees? 3.4.3 Balanced Search Trees 3.5 Priority Queues 3.6 War Story: Stripping Triangulations 3.7 Hashing and Strings 3.7.1 Collision Resolution 3.7.2 Efficient String Matching via Hashing 3.7.3 Duplicate Detection Via Hashing 3.8 Specialized Data Structures 3.9 War Story: String 'em Up 3.10 Exercises 4 Sorting and Searching 4.1 Applications of Sorting 4.2 Pragmatics of Sorting 4.3 Heapsort: Fast Sorting via Data Structures 4.3.1 Heaps 4.3.2 Constructing Heaps 4.3.3 Extracting the Minimum 4.3.4 Faster Heap Construction (*) 4.3.5 Sorting by Incremental Insertion 4.4 War Story: Give me a Ticket on an Airplane 4.5 Mergesort: Sorting by Divide-and-Conquer 4.6 Quicksort: Sorting by Randomization 4.6.1 Intuition: The Expected Case for Quicksort 4.6.2 Randomized Algorithms 4.6.3 Is Quicksort Really Quick? 4.7 Distribution Sort: Sorting via Bucketing 4.7.1 Lower Bounds for Sorting 4.8 War Story: Skiena for the Defense 4.9 Binary Search and Related Algorithms 4.9.1 Counting Occurrences 4.9.2 One-Sided Binary Search 4.9.3 Square and Other Roots 4.10 Divide-and-Conquer 4.10.1 Recurrence Relations 4.10.2 Divide-and-Conquer Recurrences 4.10.3 Solving Divide-and-Conquer Recurrences (*) 4.11 Exercises 5 Graph Traversal 5.1 Flavors of Graphs 5.1.1 The Friendship Graph 5.2 Data Structures for Graphs 5.3 War Story: I was a Victim of Moore's Law 5.4 War Story: Getting the Graph 5.5 Traversing a Graph 5.6 Breadth-First Search 5.6.1 Exploiting Traversal 5.6.2 Finding Paths 5.7 Applications of Breadth-First Search 5.7.1 Connected Components 5.7.2 Two-Coloring Graphs 5.8 Depth-First Search 5.9 Applications of Depth-First Search 5.9.1 Finding Cycles 5.9.2 Articulation Vertices 5.10 Depth-First Search on Directed Graphs 5.10.1 Topological Sorting 5.10.2 Strongly Connected Components 5.11 Exercises 6 Weighted Graph Algorithms 6.1 Minimum Spanning Trees 6.1.1 Prim’s Algorithm 6.1.2 Kruskal’s Algorithm 6.1.3 The Union-Find Data Structure 6.1.4 Variations on Minimum Spanning Trees 6.2 War Story: Nothing but Nets 6.3 Shortest Paths 6.3.1 Dijkstra’s Algorithm 6.3.2 All-Pairs Shortest Path 6.3.3 Transitive Closure 6.4 War Story: Dialing for Documents 6.5 Network Flows and Bipartite Matching 6.5.1 Bipartite Matching 6.5.2 Computing Network Flows 6.6 Design Graphs, Not Algorithms 6.7 Exercises 7 Combinatorial Search and Heuristic Methods 7.1 Backtracking 7.1.1 Constructing All Subsets 7.1.2 Constructing All Permutations 7.1.3 Constructing All Paths in a Graph 7.2 Search Pruning 7.3 Sudoku 7.4 War Story: Covering Chessboards 7.5 Heuristic Search Methods 7.5.1 Random Sampling 7.5.2 Local Search 7.5.3 Simulated Annealing 7.5.4 Applications of Simulated Annealing 7.6 War Story: Only it is Not a Radio 7.7 War Story: Annealing Arrays 7.8 Other Heuristic Search Methods 7.9 Parallel Algorithms 7.10 War Story: Going Nowhere Fast 7.11 Exercises 8 Dynamic Programming 8.1 Caching vs. Computation 8.1.1 Fibonacci Numbers by Recursion 8.1.2 Fibonacci Numbers by Caching 8.1.3 Fibonacci Numbers by Dynamic Programming 8.1.4 Binomial Coefficients 8.2 Approximate String Matching 8.2.1 Edit Distance by Recursion 8.2.2 Edit Distance by Dynamic Programming 8.2.3 Reconstructing the Path 8.2.4 Varieties of Edit Distance 8.3 Longest Increasing Sequence 8.4 War Story: Evolution of the Lobster 8.5 The Partition Problem 8.6 Parsing Context-Free Grammars 8.6.1 Minimum Weight Triangulation 8.7 Limitations of Dynamic Programming: TSP 8.7.1 When are Dynamic Programming Algorithms Correct? 8.7.2 When are Dynamic Programming Algorithms Efficient? 8.8 War Story: What's Past is Prolog 8.9 War Story: Text Compression for Bar Codes 8.10 Exercises 9 Intractable Problems and Approximation Algorithms 9.1 Problems and Reductions 9.1.1 The Key Idea 9.1.2 Decision Problems 9.2 Reductions for Algorithms 9.2.1 Closest Pair 9.2.2 Longest Increasing Subsequence 9.2.3 Least Common Multiple 9.2.4 Convex Hull (*) 9.3 Elementary Hardness Reductions 9.3.1 Hamiltonian Cycle 9.3.2 Independent Set and Vertex Cover 9.3.3 Clique 9.4 Satisfiability 9.4.1 3-Satisfiability 9.5 Creative Reductions 9.5.1 Integer Programming 9.5.2 Vertex Cover 9.6 The Art of Proving Hardness 9.7 War Story: Hard Against the Clock 9.8 War Story: And Then I Failed 9.9 P vs. NP 9.9.1 Verification vs. Discovery 9.9.2 The Classes P and NP 9.9.3 Why is Satisfiability the Mother of All Hard Problems? 9.9.4 NP-hard vs. NP-complete? 9.10 Dealing with NP-complete Problems 9.10.1 Approximating Vertex Cover 9.10.2 The Euclidean Traveling Salesman 9.10.3 Maximum Acyclic Subgraph 9.10.4 Set Cover 9.11 Exercises 10 How to Design Algorithms Part II The Hitchhiker's Guide to Algorithms 11 A Catalog of Algorithmic Problems 12 Data Structures 12.1 Dictionaries 12.2 Priority Queues 12.3 Suffix Trees and Arrays 12.4 Graph Data Structures 12.5 Set Data Structures 12.6 Kd-Trees 13 Numerical Problems 13.1 Solving Linear Equations 13.2 Bandwidth Reduction 13.3 Matrix Multiplication 13.4 Determinants and Permanents 13.5 Constrained and Unconstrained Optimization 13.6 Linear Programming 13.7 Random Number Generation 13.8 Factoring and Primality Testing 13.9 Arbitrary-Precision Arithmetic 13.10 Knapsack Problem 13.11 Discrete Fourier Transform 14 Combinatorial Problems 14.1 Sorting 14.2 Searching 14.3 Median and Selection 14.4 Generating Permutations 14.5 Generating Subsets 14.6 Generating Partitions 14.7 Generating Graphs 14.8 Calendrical Calculations 14.9 Job Scheduling 14.10 Satisfiability 15 Graph Problems: Polynomial-Time 15.1 Connected Components 15.2 Topological Sorting 15.3 Minimum Spanning Tree 15.4 Shortest Path 15.5 Transitive Closure and Reduction 15.6 Matching 15.7 Eulerian Cycle/Chinese Postman 15.8 Edge and Vertex Connectivity 15.9 Network Flow 15.10 Drawing Graphs Nicely 15.11 Drawing Trees 15.12 Planarity Detection and Embedding 16 Graph Problems: Hard Problems 16.1 Clique 16.2 Independent Set 16.3 Vertex Cover 16.4 Traveling Salesman Problem 16.5 Hamiltonian Cycle 16.6 Graph Partition 16.7 Vertex Coloring 16.8 Edge Coloring 16.9 Graph Isomorphism 16.10 Steiner Tree 16.11 Feedback Edge/Vertex Set 17 Computational Geometry 17.1 Robust Geometric Primitives 17.2 Convex Hull 17.3 Triangulation 17.4 Voronoi Diagrams 17.5 Nearest Neighbor Search 17.6 Range Search 17.7 Point Location 17.8 Intersection Detection 17.9 Bin Packing 17.10 Medial-Axis Transform 17.11 Polygon Partitioning 17.12 Simplifying Polygons 17.13 Shape Similarity 17.14 Motion Planning 17.15 Maintaining Line Arrangements 17.16 Minkowski Sum 18 Set and String Problems 18.1 Set Cover 18.2 Set Packing 18.3 String Matching 18.4 Approximate String Matching 18.5 Text Compression 18.6 Cryptography 18.7 Finite State Machine Minimization 18.8 Longest Common Substring/Subsequence 18.9 Shortest Common Superstring 19 Algorithmic Resources 19.1 Software Systems 19.1.1 LEDA 19.1.2 CGAL 19.1.3 Boost Graph Library 19.1.4 GOBLIN 19.1.5 Netlib 19.1.6 Collected Algorithms of the ACM 19.1.7 SourceForge and CPAN 19.1.8 The Stanford GraphBase 19.1.9 Combinatorica 19.1.10 Programs from Books 19.2 Data Sources 19.3 Online Bibliographic Resources 19.4 Professional Consulting Services Bibliography Index This Expanded And Updated Second Edition Of A Classic Bestseller Continues To Take The Mystery Out Of Designing And Analyzing Algorithms And Their Efficacy And Efficiency. Expanding On The Highly Successful Formula Of The First Edition, The Book Now Serves As The Primary Textbook Of Choice For Any Algorithm Design Course While Maintaining Its Status As The Premier Practical Reference Guide To Algorithms. New: (1) Incorporates Twice The Tutorial Material And Exercises. (2) Provides Full Online Support For Lecturers, And A Completely Updated And Improved Website Component With Lecture Slides, Audio And Video. (3) Contains A Highly Unique Catalog Of The 75 Most Important Algorithmic Problems. (4) Includes New War Stories And Interview Problems, Relating Experiences From Real-world Applications. Unique, Handy Reference Package With A Practical, Hands-on Appeal To A Wide Audience This Classic Bestseller Has Been Expanded And Updated With Twice The Original Tutorial Material And Exercises Contains A Highly Unique Catalog Of The 75 Most Important Algorithmic Problems Additional Useful Information Such As Lecture Slides And Updates Available Via Author's Website. I. Practical Algorithm Design. Introduction To Algorithm Design -- Algorithm Analysis -- Data Structures -- Sorting And Searching -- Graph Traversal -- Weighted Graph Algorithms -- Combinatorial Search And Heuristic Methods -- Dynamic Programming -- Intractable Problems And Approximations -- How To Design Algorithms -- Ii. The Hitchhiker's Guide To Algorithms. A Catalog Of Algorithmic Problems -- Data Structures -- Numerical Problems -- Combinatorial Problems -- Graph Problems: Polynomial-time -- Graph Problems: Hard Problems -- Computational Geometry -- Set And String Problems -- Algorithmic Resources. Steven S. Skiena. Previous Ed.: 1997. Includes Bibliographical References (p. [665]-707) And Index. Most professional programmers that I’ve encountered are not well prepared to tacklealgorithmdesignproblems.Thisisapity,becausethetechniquesofalgorithm design form one of the core practical technologies of computer science. Designing correct, e?cient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge: • Techniques – Good algorithm designers understand several fundamental - gorithm design techniques, including data structures, dynamic programming, depth-?rst search, backtracking, and heuristics. Perhaps the single most - portantdesigntechniqueismodeling,theartofabstractingamessyreal-world application into a clean problem suitable for algorithmic attack. • Resources – Good algorithm designers stand on the shoulders of giants. Ratherthanlaboringfromscratchtoproduceanewalgorithmforeverytask, they can ?gure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imp- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide su?cient source material to model most any application. This book is intended as a manual on algorithm design, providing access to combinatorial algorithm technology for both students and computer professionals. This expanded and updated second edition of a classic bestseller continues to take the mystery out of designing and analyzing algorithms and their efficacy and efficiency. Expanding on the highly successful formula of the first edition, the book now serves as the primary textbook of choice for any algorithm design course while maintaining its status as the premier practical reference guide to algorithms. This new edition: (1) Incorporates twice the tutorial material and exercises; (2) Provides full online support for lecturers, and a completely updated and improved website component with lecture slides, audio and video; (3) Contains a highly unique catalog of the 75 most important algorithmic problems; (4) Includes new war stories and interview problems, relating experiences from real-world applications--Back cover Unique, handy reference package with a practical, hands-on appeal to a wide audience The new edition of this classic bestseller has been expanded and updated with twice the original tutorial material and exercises Contains a highly unique catalog of the 75 most important algorithmic problems Additional useful information such as lecture slides and updates available via author's website