Overview

Full Product Details

Author:   Steven S. Skiena
Publisher:   Springer Nature Switzerland AG
Imprint:   Springer Nature Switzerland AG
Edition:   3rd ed. 2020
Weight:   1.404kg
ISBN:  

9783030542580

ISBN 10:   3030542580
Pages:   793
Publication Date:   07 October 2021
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of Contents

{*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

Reviews

Author Information

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.”  

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions