My absolute favorite for this kind of interview preparation is Steven SkienaOs The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace A graph problems are -- they should be part of every working programmerOs toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. A every 1 O 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 SkienaOs Algorithm Design Manual retains its title as the best and most comprehensive practical algorithm guide to help identify and solve problems. A Every programmer should read this book, and anyone working in the field should keep it close to hand. A This is the best investment A a programmer or aspiring programmer can make. (Harold Thimbleby, Times Higher Education)It is wonderful to open to a random spot and discover aninteresting 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.a a(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.a 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.aThe reader-friendlyaAlgorithm Design Manualaprovides straightforward access to combinatorial algorithms technology, stressing design over analysis.a The first part, Practical Algorithm Design, provides accessible instruction on methods for designing and analyzing computer algorithms.a 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.aNEWato the third edition:a--aNew and expanded coverageaof randomized algorithms, hashing, divide and conquer, approximation algorithms, and quantum computinga-- Providesafull online supportafor lecturers, includingaan improved website componentawith lecture slides and videosa--aFull color illustrations and codeainstantly clarify difficult conceptsa-- Includes several new war storiesarelating experiences from real-world applicationsa-- Overa100 new problems, including programming-challenge problems from LeetCode and Hackerrank.a-- Providesaup-to-date linksaleading to the best implementations available in C, C++, and JavaaAdditional Learning Tools:a-- Contains a unique catalog identifying the 75 algorithmic problems that arise most often in practice, leading the reader down the right path to solve thema-- Exercises include job interview problems from major software companiesa-- Highlighted take home lessons emphasize essential conceptsa-- The no theorem-proof style provides a uniquely accessible and intuitive approach to a challenging subjecta-- Many algorithms are presented with actual code (written in C)a-- Provides comprehensive references to both survey articles and the primary literatureaWritten by a well-known algorithms researcher who received the IEEE Computer Science and Engineering Teaching Award, this substantially enhanced third edition ofaThe Algorithm Design Manualais an essential learning tool for students and professionals needed a solid grounding in algorithms.aa Professor Skiena is also the author of the popular Springer texts,aThe Data Science Design ManualaandaProgramming Challenges: The Programming Contest Training Manual.
{*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-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
Accessing your eBook through Kortext
Once purchased, you can view your eBook through the Kortext app, available to download for Windows, Android and iOS devices. Once you have downloaded the app, your eBook will be available on your Kortext digital bookshelf and can even be downloaded to view offline anytime, anywhere, helping you learn without limits.
In addition, you'll have access to Kortext's smart study tools including highlighting, notetaking, copy and paste, and easy reference export.
To download the Kortext app, head to your device's app store or visit https://app.kortext.com to sign up and read through your browser.
NB: eBook is only available for a single-user licence (i.e. not for multiple / networked users).
