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 4 Contents 9 Introduction to Algorithm Design 15 Robot Tour Optimization 17 Selecting the Right Jobs 21 Reasoning about Correctness 23 Modeling the Problem 31 About the War Stories 34 War Story: Psychic Modeling 35 Exercises 39 Algorithm Analysis 43 The RAM Model of Computation 43 The Big Oh Notation 46 Growth Rates and Dominance Relations 49 Working with the Big Oh 52 Reasoning About Efficiency 53 Logarithms and Their Applications 58 Properties of Logarithms 62 War Story: Mystery of the Pyramids 63 Advanced Analysis (*) 66 Exercises 69 Data Structures 77 Contiguous vs. Linked Data Structures 78 Stacks and Queues 83 Dictionaries 84 Binary Search Trees 89 Priority Queues 95 War Story: Stripping Triangulations 97 Hashing and Strings 101 Specialized Data Structures 105 War Story: String 'em Up 106 Exercises 110 Sorting and Searching 115 Applications of Sorting 116 Pragmatics of Sorting 119 Heapsort: Fast Sorting via Data Structures 120 War Story: Give me a Ticket on an Airplane 130 Mergesort: Sorting by Divide-and-Conquer 132 Quicksort: Sorting by Randomization 135 Distribution Sort: Sorting via Bucketing 141 War Story: Skiena for the Defense 143 Binary Search and Related Algorithms 144 Divide-and-Conquer 147 Exercises 151 Graph Traversal 157 Flavors of Graphs 158 Data Structures for Graphs 163 War Story: I was a Victim of Moore's Law 167 War Story: Getting the Graph 170 Traversing a Graph 173 Breadth-First Search 174 Applications of Breadth-First Search 178 Depth-First Search 181 Applications of Depth-First Search 184 Depth-First Search on Directed Graphs 190 Exercises 196 Weighted Graph Algorithms 203 Minimum Spanning Trees 204 War Story: Nothing but Nets 214 Shortest Paths 217 War Story: Dialing for Documents 224 Network Flows and Bipartite Matching 229 Design Graphs, Not Algorithms 234 Exercises 237 Combinatorial Search and Heuristic Methods 242 Backtracking 243 Search Pruning 250 Sudoku 251 War Story: Covering Chessboards 256 Heuristic Search Methods 259 War Story: Only it is Not a Radio 272 War Story: Annealing Arrays 275 Other Heuristic Search Methods 278 Parallel Algorithms 279 War Story: Going Nowhere Fast 280 Exercises 282 Dynamic Programming 285 Caching vs. Computation 286 Approximate String Matching 292 Longest Increasing Sequence 301 War Story: Evolution of the Lobster 303 The Partition Problem 306 Parsing Context-Free Grammars 310 Limitations of Dynamic Programming: TSP 313 War Story: What's Past is Prolog 316 War Story: Text Compression for Bar Codes 319 Exercises 322 Intractable Problems and Approximation Algorithms 328 Problems and Reductions 329 Reductions for Algorithms 331 Elementary Hardness Reductions 335 Satisfiability 340 Creative Reductions 342 The Art of Proving Hardness 346 War Story: Hard Against the Clock 349 War Story: And Then I Failed 351 P vs. NP 353 Dealing with NP-complete Problems 356 Exercises 362 How to Design Algorithms 368 A Catalog of Algorithmic Problems 373 Data Structures 376 Dictionaries 377 Priority Queues 383 Suffix Trees and Arrays 387 Graph Data Structures 391 Set Data Structures 395 Kd-Trees 399 Numerical Problems 403 Solving Linear Equations 405 Bandwidth Reduction 408 Matrix Multiplication 411 Determinants and Permanents 414 Constrained and Unconstrained Optimization 417 Linear Programming 421 Random Number Generation 425 Factoring and Primality Testing 430 Arbitrary-Precision Arithmetic 433 Knapsack Problem 437 Discrete Fourier Transform 441 Combinatorial Problems 444 Sorting 446 Searching 451 Median and Selection 455 Generating Permutations 458 Generating Subsets 462 Generating Partitions 466 Generating Graphs 470 Calendrical Calculations 475 Job Scheduling 478 Satisfiability 482 Graph Problems: Polynomial-Time 485 Connected Components 487 Topological Sorting 491 Minimum Spanning Tree 494 Shortest Path 499 Transitive Closure and Reduction 505 Matching 508 Eulerian Cycle/Chinese Postman 512 Edge and Vertex Connectivity 515 Network Flow 519 Drawing Graphs Nicely 523 Drawing Trees 527 Planarity Detection and Embedding 530 Graph Problems: Hard Problems 533 Clique 535 Independent Set 538 Vertex Cover 540 Traveling Salesman Problem 543 Hamiltonian Cycle 548 Graph Partition 551 Vertex Coloring 554 Edge Coloring 558 Graph Isomorphism 560 Steiner Tree 565 Feedback Edge/Vertex Set 569 Computational Geometry 572 Robust Geometric Primitives 574 Convex Hull 578 Triangulation 582 Voronoi Diagrams 586 Nearest Neighbor Search 590 Range Search 594 Point Location 597 Intersection Detection 601 Bin Packing 605 Medial-Axis Transform 608 Polygon Partitioning 611 Simplifying Polygons 614 Shape Similarity 617 Motion Planning 620 Maintaining Line Arrangements 624 Minkowski Sum 627 Set and String Problems 630 Set Cover 631 Set Packing 635 String Matching 638 Approximate String Matching 641 Text Compression 647 Cryptography 651 Finite State Machine Minimization 656 Longest Common Substring/Subsequence 660 Shortest Common Superstring 664 Algorithmic Resources 667 Software Systems 667 Data Sources 673 Online Bibliographic Resources 673 Professional Consulting Services 674 Bibliography 675 Index 718 ....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 . 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. Front Matter....Pages I-XVI Front Matter....Pages 1-1 Introduction to Algorithm Design....Pages 3-30 Algorithm Analysis....Pages 31-64 Data Structures....Pages 65-102 Sorting and Searching....Pages 103-144 Graph Traversal....Pages 145-190 Weighted Graph Algorithms....Pages 191-229 Combinatorial Search and Heuristic Methods....Pages 230-272 Dynamic Programming....Pages 273-315 Intractable Problems and Approximation Algorithms....Pages 316-355 How to Design Algorithms....Pages 356-360 Front Matter....Pages 361-361 A Catalog of Algorithmic Problems....Pages 363-365 Data Structures....Pages 366-392 Numerical Problems....Pages 393-433 Combinatorial Problems....Pages 434-474 Graph Problems: Polynomial-Time....Pages 475-522 Graph Problems: Hard Problems....Pages 523-561 Computational Geometry....Pages 562-619 Set and String Problems....Pages 620-656 Algorithmic Resources....Pages 657-664 Back Matter....Pages 665-730 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