The Algorithm Design Manual

by Steven S. Skiena

Overview

"My absolute favorite for this kind of interview preparation is Steven Skiena’s The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace … graph problems are — they should be part of every working programmer’s toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. … every 1 – pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types." (Steve Yegge, Get that Job at Google)

"Steven Skiena’s Algorithm Design Manual retains its title as the best and most comprehensive practical algorithm guide to help identify and solve problems. … Every programmer should read this book, and anyone working in the field should keep it close to hand. … This is the best investment … a programmer or aspiring programmer can make." (Harold Thimbleby, Times Higher Education)

"It is wonderful to open to a random spot and discover an interesting algorithm. This is the only textbook I felt compelled to bring with me out of my student days.... The color really adds a lot of energy to the new edition of the book!" (Cory Bart, University of Delaware)

"The is the most approachable book on algorithms I have." (Megan Squire, Elon University)

—-

This newly expanded and updated third edition of the best-selling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficiency. It serves as the primary textbook of choice for algorithm design courses and interview self-study, 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, Practical Algorithm Design, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, the Hitchhiker's Guide to Algorithms, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations, and an extensive bibliography.

NEW to the third edition:

— New and expanded coverage of randomized algorithms, hashing, divide and conquer, approximation algorithms, and quantum computing

— Provides full online support for lecturers, including an improved website component with lecture slides and videos

— Full color illustrations and code instantly clarify difficult concepts

— Includes several new "war stories" relating experiences from real-world applications

— Over 100 new problems, including programming-challenge problems from LeetCode and Hackerrank.

— Provides up-to-date links leading to the best implementations available in C, C++, and Java

Additional Learning Tools:

— 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

— Exercises include "job interview problems" from major software companies

— Highlighted "take home lessons" emphasize essential concepts

— The "no theorem-proof" style provides a uniquely accessible and intuitive approach to a challenging subject

— Many algorithms are presented with actual code (written in C)

— Provides comprehensive references to both survey articles and the primary literature

Written by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this substantially enhanced third edition of The Algorithm Design Manual is an essential learning tool for students and professionals needed a solid grounding in algorithms. Professor Skiena is also the author of the popular Springer texts, The Data Science Design Manual and Programming Challenges: The Programming Contest Training Manual.

Product Details

ISBN-13:	9783030542580
Publisher:	Springer International Publishing
Publication date:	10/06/2020
Series:	Texts in Computer Science
Edition description:	3rd ed. 2020
Pages:	793
Sales rank:	1,030,097
Product dimensions:	7.01(w) x 9.25(h) x (d)

About the Author

Dr. Steven S. Skiena is Distinguished Teaching Professor of Computer Science at Stony Brook University, with research interests in data science, natural language processing, and algorithms. He was awarded the IEEE Computer Science and Engineering Undergraduate Teaching Award “for outstanding contributions to undergraduate education ...and for influential textbooks and software.”

Table of Contents

Introduction to Algorithm Design

Algorithm Analysis

Data Structures

Sorting and Searching

Divide and Conquer

Randomized Algorithms and Hashing

Graph Traversal

Weighted Graph Algorithms

Combinatorial Search and Heuristic Methods

Dynamic Programming

NP-Completeness

Dealing with Hard Problems

How to Design Algorithms

14 A Catalog of Algorithmic Problems 437

15 Data Structures 439

15.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

15.2 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

15.3 Sux Trees and Arrays . . . . . . . . . . . . . . . . . . . . . . . 448

15.4 Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 452

15.5 Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 456

15.6 Kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

16 Numerical Problems 465

16.1 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . . . 467

16.2 Bandwidth Reduction . . . . . . . . . . . . . . . . . . . . . . . . 470

16.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 472

16.4 Determinants and Permanents . . . . . . . . . . . . . . . . . . . 475

16.5 Constrained/Unconstrained Optimization . . . . . . . . . . . . . 478

16.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 482

16.7 Random Number Generation . . . . . . . . . . . . . . . . . . . . 486

16.8 Factoring and Primality Testing . . . . . . . . . . . . . . . . . . . 490

16.9 Arbitrary-Precision Arithmetic . . . . . . . . . . . . . . . . . . . 493

16.10Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 497

16.11Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . 501

17 Combinatorial Problems 505

17.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506

17.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

17.3 Median and Selection . . . . . . . . . . . . . . . . . . . . . . . . . 514

17.4 Generating Permutations . . . . . . . . . . . . . . . . . . . . . . 517

17.5 Generating Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 521

17.6 Generating Partitions . . . . . . . . . . . . . . . . . . . . . . . . 524

17.7 Generating Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 528

17.8 Calendrical Calculations . . . . . . . . . . . . . . . . . . . . . . . 532

17.9 Job Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534

17.10Satisability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

18 Graph Problems: Polynomial-Time 541

18.1 Connected Components . . . . . . . . . . . . . . . . . . . . . . . 542

18.2 Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 546

18.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . 549

18.4 Shortest Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554

18.5 Transitive Closure and Reduction . . . . . . . . . . . . . . . . . . 559

18.6 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

18.7 Eulerian Cycle/Chinese Postman . . . . . . . . . . . . . . . . . . 565

18.8 Edge and Vertex Connectivity . . . . . . . . . . . . . . . . . . . . 568

16 CONTENTS

18.9 Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

18.10Drawing Graphs Nicely . . . . . . . . . . . . . . . . . . . . . . . 574

18.11Drawing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

18.12Planarity Detection and Embedding . . . . . . . . . . . . . . . . 581

19 Graph Problems: NP-Hard 585

19.1 Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586

19.2 Independent Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

19.3 Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591

19.4 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . 594

19.5 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . 598

19.6 Graph Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601

19.7 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604

19.8 Edge Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608

19.9 Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . 610

19.10Steiner Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614

19.11Feedback Edge/Vertex Set . . . . . . . . . . . . . . . . . . . . . . 618

20 Computational Geometry 621

20.1 Robust Geometric Primitives . . . . . . . . . . . . . . . . . . . . 622

20.2 Convex Hull . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626

20.3 Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630

20.4 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 634

20.5 Nearest Neighbor Search . . . . . . . . . . . . . . . . . . . . . . . 637

20.6 Range Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641

20.7 Point Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644

20.8 Intersection Detection . . . . . . . . . . . . . . . . . . . . . . . . 648

20.9 Bin Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652

20.10Medial-Axis Transform . . . . . . . . . . . . . . . . . . . . . . . . 655

20.11Polygon Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 658

20.12Simplifying Polygons . . . . . . . . . . . . . . . . . . . . . . . . . 661

20.13Shape Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . 664

20.14Motion Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

20.15Maintaining Line Arrangements . . . . . . . . . . . . . . . . . . . 671

20.16Minkowski Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

21 Set and String Problems 677

21.1 Set Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678

21.2 Set Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682

21.3 String Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 685

21.4 Approximate String Matching . . . . . . . . . . . . . . . . . . . . 688

21.5 Text Compression . . . . . . . . . . . . . . . . . . . . . . . . . . 693

21.6 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697

21.7 Finite State Machine Minimization . . . . . . . . . . . . . . . . . 702

21.8 Longest Common Substring/Subsequence . . . . . . . . . . . . . 706

21.9 Shortest Common Superstring . . . . . . . . . . . . . . . . . . . . 709

CONTENTS 17

22 Algorithmic Resources 713

22.1 Algorithm Libraries . . . . . . . . . . . . . . . . . . . . . . . . . 713

22.1.1 LEDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713

22.1.2 CGAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714

22.1.3 Boost Graph Library . . . . . . . . . . . . . . . . . . . . . 714

22.1.4 Netlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 714

22.1.5 Collected Algorithms of the ACM . . . . . . . . . . . . . 715

22.1.6 GitHub and SourceForge . . . . . . . . . . . . . . . . . . . 715

22.1.7 The Stanford GraphBase . . . . . . . . . . . . . . . . . . 715

22.1.8 Combinatorica . . . . . . . . . . . . . . . . . . . . . . . . 716

22.1.9 Programs from Books . . . . . . . . . . . . . . . . . . . . 716

22.2 Data Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717

22.3 Online Bibliographic Resources . . . . . . . . . . . . . . . . . . . 718

22.4 Professional Consulting Services . . . . . . . . . . . . . . . . . . 718

23 Bibliography 719

Index 771

Editorial Reviews

From the reviews of the second edition:

“This is detailed and timeless book that I keep reaching for. A useful book that I can not keep access to long enough. It is a important book to have in your library. Unlike other algorithm books that I have the algorithms are written independent of any programming language.” (Mary Anne, Cats and Dogs with Data, maryannedata.com, April, 2014)

“The Algorithm Design Manual by Steven Skiena is aimed at two groups of people: students and professionals. … It is written in an informal style that I found pleasant and engaging. … The book’s unique structure makes it more likely to be immediately useful to the practitioner who has problem to solve and wants to quickly make progress … . the book succeeds admirably. … would be helpful to the student who has never seen this material before. … Overall, I recommend this book warmly.” (Neelakantan Kartha, The Book Review Column, 2011)

“Algorithms are the very heart of computing … . This book is about right for most people. … Each of the topics is treated in a readable informal style with lots of asides and accounts of personal experiences - ‘war stories’ in implementing algorithms. … If you want to use it as a course textbook then there are lots of exercises at the end of every chapter. Highly recommended.” (Mike James, I Programmer, September, 2009)

"Addressing the main difficulties of solving problems, this book goes far beyond the design of algorithms. It is essential for scientists, engineers, and any professionals who aim to solve problems, with a noticeable emphasis on real problems. It will not only serve as a valuable undergraduate textbook, but it will also become an irreplaceable reference guide for most professionals in the area." (Carlos Linares Lopez, Computing Reviews, February, 2009)

"Skiena focuses on the practical aspects of algorithm design and use. … this work fills an important gap in the knowledge of CS practitioners and students. … this book is suitable as a text for an undergraduate algorithms class, but also as an invaluable reference for the practicing programmer. … This second edition has updated the bibliography to include recent works, making it an extensive bibliography. The index is also thorough and very useful for finding specific problems." (William Fahle, ACM Computing Reviews, December, 2008)

"For a decade, Steven Skiena’s Algorithm Design Manual retained its title as the best and most comprehensive practical algorithm guide to help identify and solve problems. It is now available in an improved second edition that is worth buying simply for the updates. … Every programmer should read this book, and anyone working in the field should keep it close to hand. … Would I recommend it? Absolutely. This is the best investment … a programmer or aspiring programmer can make." (Harold Thimbleby, Times Higher Education, November, 2008)

"My absolute favorite for this kind of interview preparation is Steven Skiena’s The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace … graph problems are -- they should be part of every working programmer’s toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. … every 1 – pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types." (Steve Yegge, Steve Yegge’s Blog, March, 2008)

"...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, an extensive bibliography … make the book an invaluable resource for everyone interested in the subject." (ACM Computing Reviews)

From the Publisher