Synopses & Reviews
Synopsis
{*DRAFT*}
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-Har
Synopsis
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.
Synopsis
"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 thi