You are previewing Mastering Algorithms with Perl.
O'Reilly logo
Mastering Algorithms with Perl

Book Description

Many programmers would love to use Perl for projects that involveheavy lifting, but miss the many traditional algorithms thattextbooks teach for other languages. Computer scientists haveidentified many techniques that a wide range of programs need, suchas:

  • Fuzzy pattern matching for text (identify misspellings!)

  • Finding correlations in data

  • Game-playing algorithms

  • Predicting phenomena such as Web traffic

  • Polynomial and spline fitting

  • Using algorithms explained in this book, you too can carry outtraditional programming tasks in a high-powered, efficient,easy-to-maintain manner with Perl. This book assumes a basicunderstanding of Perl syntax and functions, but not necessarily anybackground in computer science. The authors explain in a readablefashion the reasons for using various classic programmingtechniques, the kind of applications that use them, and -- mostimportant -- how to code these algorithms in Perl. If you are anamateur programmer, this book will fill you in on the essentialalgorithms you need to solve problems like an expert. If you havealready learned algorithms in other languages, you will besurprised at how much different (and often easier) it is toimplement them in Perl. And yes, the book even has the obligatoryfractal display program. There have been dozens of books onprogramming algorithms, some of them excellent, but never beforehas there been one that uses Perl. The authors include theeditor of The Perl Journal and master librarian of CPAN; allare contributors to CPAN and have archived much of the code in thisbook there. "This book was so exciting I lost sleep readingit." Tom Christiansen

    Table of Contents

    1. Special Upgrade Offer
    2. A Note Regarding Supplemental Files
    3. Preface
      1. About This Book
        1. Theory or Practice?
        2. Organization of This Book
        3. Conventions Used in This Book
        4. What You Should Know Before Reading This Book
        5. What You Should Have Before Reading This Book
        6. Online Information About This Book
      2. Acknowledgments
      3. Comments and Questions
    4. 1. Introduction
      1. What Is an Algorithm?
        1. A Sample Algorithm: Binary Search
          1. What do all those funny symbols mean?
          2. References
        2. Adapting Algorithms
        3. Generality
      2. Efficiency
        1. Space Versus Time
        2. Benchmarking
        3. Floating-Point Numbers
        4. Temporary Variables
        5. Caching
        6. Evaluating Algorithms: O(N) Notation
          1. Don’t cheat
      3. Recurrent Themes in Algorithms
        1. Recursion
        2. Divide and Conquer
        3. Dynamic Programming
        4. Choosing the Right Representation
    5. 2. Basic Data Structures
      1. Perl’s Built-in Data Structures
      2. Build Your Own Data Structure
      3. A Simple Example
        1. Lols and Lohs and Hols and Hohs
        2. Objects
        3. Using a Constructed Datatype
        4. Shortcuts
      4. Perl Arrays: Many Data Structures in One
        1. Queues
        2. Stacks
        3. Deques
        4. Still More Perl Arrays
    6. 3. Advanced Data Structures
      1. Linked Lists
        1. Linked List Implementations
        2. Tracking Both Ends of Linked Lists
        3. Additional Linked List Operations
      2. Circular Linked Lists
      3. Garbage Collection in Perl
      4. Doubly-Linked Lists
      5. Infinite Lists
      6. The Cost of Traversal
      7. Binary Trees
        1. Keeping Trees Balanced
          1. User-visible routines
          2. Merging
          3. The actual balancing
      8. Heaps
      9. Binary Heaps
      10. Janus Heap
      11. The Heap Modules
      12. Future CPAN Modules
    7. 4. Sorting
      1. An Introduction to Sorting
        1. Perl’s sort Function
        2. ASCII Order
        3. Numeric Order
        4. Reverse Order: From Highest To Lowest
        5. Sort::Fields
        6. Sort::Versions
        7. Dictionary Order
        8. Sorting Efficiency
          1. The Schwartzian Transform
          2. Long duration caching
          3. Deficiency: missing internationalization (locales)
          4. Sort::ArbBiLex
          5. See for yourself: use the Benchmark module
        9. Sorting Hashes Is Not What You Might Think
      2. All Sorts of Sorts
        1. Quadratic Sorting Algorithms
          1. Selection sort
          2. Minima and maxima
          3. Bubble sort
          4. Insertion sort
          5. Shellsort
        2. Log-Linear Sorting Algorithms
          1. Mergesort
          2. Heapsort
          3. Quicksort
            1. Removing recursion from quicksort
          4. Median, quartile, percentile
        3. Beating <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg" class="emphasis"><em>O</em></span>((<span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg" class="emphasis"><em>N</em></span> log log <span xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg" class="emphasis"><em>N</em></span>))
          1. Radix sorts
          2. Counting sort
          3. Hybrid sorts
            1. Bucket sort
            2. Quickbubblesort
        4. External Sorting
      3. Sorting Algorithms Summary
        1. O(N<sup xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xmlns:m="http://www.w3.org/1998/Math/MathML" xmlns:pls="http://www.w3.org/2005/01/pronunciation-lexicon" xmlns:ssml="http://www.w3.org/2001/10/synthesis" xmlns:svg="http://www.w3.org/2000/svg">2</sup>) Sorts) Sorts
          1. Selection sort
          2. Bubble sort and insertion sort
        2. Shellsort
        3. O(N log N) Sorts
          1. Mergesort
          2. Quicksort
        4. How Well Did We Do?
    8. 5. Searching
      1. Hash Search and Other Non-Searches
      2. Lookup Searches
        1. Ransack Search
        2. Linear Search
        3. Binary Search in a List
        4. Proportional Search
        5. Binary Search in a Tree
        6. Should You Use a List or a Tree for Binary Searching?
        7. Bushier Trees
        8. Lists of Lists
        9. B-Trees
        10. Hybrid Searches
        11. Lookup Search Recommendations
      3. Generative Searches
        1. Game Interface
        2. Exhaustive Search
        3. Alternatives to Exhaustive Search in Games
          1. Minimax
          2. Pruning
          3. Alpha-beta pruning
          4. Killer move
          5. Transpose tables
          6. Advanced pruning strategies
          7. Other strategies
        4. Nongame Dynamic Searches
          1. Greedy algorithms
          2. Branch and bound
          3. The A* algorithm
          4. Dynamic programming
    9. 6. Sets
      1. Venn Diagrams
      2. Creating Sets
        1. Creating Sets Using Hashes
        2. Creating Sets Using Bit Vectors
      3. Set Union and Intersection
        1. Union
        2. Intersection
        3. Set Universe
        4. Complement Set
        5. Null Set
        6. Set Union and Intersection Using Hashes
        7. Union and Intersection Using Bit Vectors
      4. Set Differences
        1. Set Difference
        2. Set Symmetric Difference
        3. Set Differences Using Hashes
        4. Set Differences Using Bit Vectors
      5. Counting Set Elements
      6. Set Relations
        1. Set Relations Using Hashes
        2. Set Relations Using Bit Vectors
      7. The Set Modules of CPAN
        1. Set::Scalar
        2. Set::Object
        3. Set::IntSpan
        4. Bit::Vector
        5. Set::IntRange
      8. Sets of Sets
        1. Power Sets
        2. Power Sets Using Hashes
      9. Multivalued Sets
        1. Multivalued Logic
        2. Fuzzy Sets
        3. Bags
      10. Sets Summary
    10. 7. Matrices
      1. Creating Matrices
      2. Manipulating Individual Elements
      3. Finding the Dimensions of a Matrix
      4. Displaying Matrices
      5. Adding or Multiplying Constants
        1. Adding a Constant to a Matrix
        2. Adding a Matrix to a Matrix
      6. Transposing a Matrix
      7. Multiplying Matrices
      8. Extracting a Submatrix
      9. Combining Matrices
      10. Inverting a Matrix
      11. Computing the Determinant
      12. Gaussian Elimination
      13. Eigenvalues and Eigenvectors
        1. Computing Eigenvalues
          1. Using PDL to calculate eigenvalues and eigenvectors
          2. Calculating easy eigenvalues directly
      14. The Matrix Chain Product
      15. Delving Deeper
    11. 8. Graphs
      1. Vertices and Edges
        1. Edge Direction
        2. Vertex Degree and Vertex Classes
      2. Derived Graphs
        1. Graph Transpose
        2. Complete Graph
        3. Complement Graph
        4. Density
      3. Graph Attributes
      4. Graph Representation in Computers
        1. Our Graph Representation
          1. Creating graphs, dealing with vertices
          2. Testing for and adding edges
          3. Returning edges
          4. Density, degrees, and vertex classes
          5. Deleting edges and vertices
          6. Graph attributes
          7. Displaying graphs
      5. Graph Traversal
        1. Depth-First Search
        2. Topological Sort
          1. make as a topological sort
        3. Breadth-First Search
        4. Implementing Graph Traversal
          1. Implementing depth-first traversal
          2. Implementing breadth-first traversal
      6. Paths and Bridges
        1. The Seven Bridges of Königsberg
      7. Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants
        1. Parents and Children
      8. Edge and Graph Classes
        1. Edge Classes
        2. Graph Classes: Connectivity
        3. Biconnectivity
        4. Strongly Connected Graphs
        5. Minimum Spanning Trees
          1. Kruskal’s minimum spanning tree
          2. Prim’s minimum spanning tree
        6. Shortest Paths
          1. Single-source shortest paths
            1. Dijkstra’s single-source shortest paths
            2. Bellman-Ford single-source shortest paths
            3. DAG single-source shortest paths
          2. All-pairs shortest paths
        7. Transitive Closure
        8. Flow Networks
          1. Ford-Fulkerson
          2. Edmonds-Karp
        9. Traveling Salesman Problem
      9. CPAN Graph Modules
    12. 9. Strings
      1. Perl Builtins
        1. Exact Matching
        2. Regular Expressions
          1. Quick tips for regular expressions: readability
          2. Quick tips for regular expressions: efficiency
          3. study()
      2. String-Matching Algorithms
        1. Naïve Matching
          1. Matching sequences
        2. Rabin-Karp
          1. Rabin-Karp is a checksum algorithm
          2. Handling huge checksums
          3. Implementing Rabin-Karp
          4. Further checksum experimentation
        3. Knuth-Morris-Pratt
        4. Boyer-Moore
        5. Shift-Op
        6. Baeza-Yates-Gonnet Shift-OR Exact Matching
        7. Approximate Matching
        8. Baeza-Yates-Gonnet Shift-Add
        9. Wu-Manber k-differences
        10. Longest Common Subsequences
        11. Summary of String Matching Algorithms
        12. String::Approx
      3. Phonetic Algorithms
        1. Text::Soundex
        2. Text::Metaphone
      4. Stemming and Inflection
        1. Modules for Stemming and Inflection
          1. Text::Stem
          2. Text::German
          3. Lingua::EN::Inflect
          4. Lingua::PT::Conjugate
      5. Parsing
        1. Finite Automata
        2. Grammars
          1. Context-free grammars
        3. Parsing Up and Down
          1. Top-down parsing
          2. Bottom-up parsing
        4. Interpreters and Compilers
        5. Modules for Lexing and Parsing
          1. Parse::Lex
          2. Parse::RecDescent
          3. Text::Abbrev
          4. Text::ParseWords
          5. Text::DelimMatch
          6. String::ShellQuote
          7. Text::Balanced
          8. Special-purpose parsers
      6. Compression
        1. Run-Length Encoding
        2. Huffman Encoding
        3. compress, GNU gzip, pkzip
    13. 10. Geometric Algorithms
      1. Distance
        1. Euclidean Distance
        2. Manhattan Distance
        3. Maximum Distance
        4. Spherical Distance
      2. Area, Perimeter, and Volume
        1. Triangle
        2. Polygon Area
        3. Polygon Perimeter
      3. Direction
      4. Intersection
        1. Line Intersection
          1. Line intersection: the general case
          2. Line intersection: the horizontal-vertical case
      5. Inclusion
        1. Point in Polygon
        2. Point in Triangle
        3. Point in Quadrangle
      6. Boundaries
        1. Bounding Box
        2. Convex Hull
      7. Closest Pair of Points
      8. Geometric Algorithms Summary
      9. CPAN Graphics Modules
        1. 2-D Images
          1. Perl-Gimp
          2. GD
          3. Image::Size
          4. PerlMagick
          5. PGPLOT
        2. Charts a.k.a. Business Graphics
        3. 3-D Modeling
          1. OpenGL
          2. Renderman
          3. VRML
        4. Widget/GUI Toolkits
          1. Perl/Tk
          2. Other windowing toolkits
    14. 11. Number Systems
      1. Integers and Reals
        1. Constants
        2. Pure Integer Arithmetic
        3. Precision
        4. Rounding Numbers
          1. Rounding up or down to an integer
          2. Rounding to the nearest integer
          3. Rounding to a particular decimal point
        5. Very Big, Very Small, and Very Precise Numbers
        6. Fractions
      2. Strange Systems
        1. Bits and Bases
        2. Bit Vectors
        3. Complex Numbers
        4. Polar Coordinates
        5. Dates and Times
        6. Roman Numerals
      3. Trigonometry
      4. Significant Series
        1. Arithmetic and Geometric Progressions
        2. The Fibonacci Sequence
        3. Harmonic Series
        4. The Riemann Zeta Function and Bernoulli Numbers
    15. 12. Number Theory
      1. Basic Number Theory
        1. Linear Combination Theorem
        2. Greatest Common Divisor
        3. GCD: Linear Combination
        4. Least Common Multiple
      2. Prime Numbers
        1. Caching: Another Example
        2. Noninfinite Arithmetic
        3. Modular Arithmetic
        4. Chinese Remainder Theorem
        5. Modular Division
        6. Chinese Remainder Theorem Revisited
          1. Treating Chinese remainders as integers
        7. Integer Exponentiation
        8. Modular Exponentiation
        9. Miller-Rabin: Prime Generation Revisited
      3. Unsolved Problems
        1. Is the Collatz Conjecture False?
        2. Is There an Odd Perfect Number?
        3. Is the Goldbach Conjecture False?
    16. 13. Cryptography
      1. Legal Issues
      2. Authorizing People with Passwords
        1. Password Hazards
      3. Authorization of Data: Checksums and More
      4. Obscuring Data: Encryption
        1. Perfect Encryption: The One-Time Pad
        2. Shared-Secret Encryptions
        3. Analysis of Shared-Secret Encryption
        4. Encrypting with SSLeay
        5. Public Key Encryption
        6. RSA Public Key Encryption
        7. El Gamal Public Key Encryption
        8. Choosing Between Public Key and Private Key
      5. Hiding Data: Steganography
      6. Winnowing and Chaffing
      7. Encrypted Perl Code
      8. Other Issues
    17. 14. Probability
      1. Random Numbers
        1. Don’t Forget to Seed Your Generator
        2. Better Randomness
      2. Events
        1. Will the Blue Jays Win, and Will the Stock Market Go Up?
        2. Will Neither the Blue Jays Win nor the Stock Market Go Up?
        3. Will the Blue Jays Win or the Stock Market Go Up?
      3. Permutations and Combinations
        1. Permutations
        2. Combinations
      4. Probability Distributions
        1. Expected Value
      5. Rolling Dice: Uniform Distributions
        1. Measuring Time: Uniform Continuous Distributions
        2. Choosing an Element from an Array
        3. Picking Random BigInts
        4. Rolling Dice Revisited: Combining Events
      6. Loaded Dice and Candy Colors: Nonuniform Discrete Distributions
        1. Flipping a Coin: The Binomial Distribution
        2. The Binomial Distribution in Poker
      7. If the Blue Jays Score Six Runs: Conditional Probability
        1. The Vaunted Monty Hall Problem
      8. Flipping Coins Over and Over: Infinite Discrete Distributions
      9. How Much Snow? Continuous Distributions
      10. Many More Distributions
        1. The Bernoulli Distribution
        2. The Beta Distribution
        3. The Binomial Distribution
        4. The Cauchy Distribution
        5. The Chi Square Distribution
        6. The Erlang Distribution
        7. The Exponential Distribution
        8. The Gamma Distribution
        9. The Gaussian (Normal) Distribution
        10. The Geometric Distribution
        11. The Hypergeometric Distribution
        12. The Laplace Distribution
        13. The Log Normal Distribution
        14. The Maxwell Distribution
        15. The Pascal Distribution
        16. The Poisson Distribution
        17. The Rayleigh Distribution
        18. The Uniform Distribution
    18. 15. Statistics
      1. Statistical Measures
        1. The Mean
        2. The Median
        3. The Mode
        4. Standard Deviation
        5. The Standard Score
        6. The Variance and Standard Deviation of Distributions
      2. Significance Tests
        1. How Sure Is Sure?
        2. The Sign Test
        3. The z-test
        4. The t-test
        5. The Chi-square test
        6. ANOVA and the F-test
      3. Correlation
        1. Computing the Covariance
        2. Computing the Correlation Coefficient
        3. Fitting a Line to Your Data
    19. 16. Numerical Analysis
      1. Computing Derivatives and Integrals
        1. Computing the Derivative at a Particular Point
        2. Computing the Jacobian
        3. Computing Definite Integrals
      2. Solving Equations
        1. Simple Roots: Quadratics and Cubics
          1. The quadratic formula
          2. Cubic equations
        2. Approximating Roots
        3. Multiple Nonlinear Equations
      3. Interpolation, Extrapolation, and Curve Fitting
        1. Fitting a Polynomial to a Set of Points
        2. Splines
          1. Cubic splines
        3. Data Smoothing
    20. A. Further Reading
      1. General References for Algorithms
      2. Graphs, Graphics, and Geometry
      3. String Processing and Parsing
      4. Numerical Methods
      5. General Mathematics
      6. Probability and Statistics
      7. Other References
    21. B. ASCII Character Set
    22. Index
    23. About the Authors
    24. Colophon
    25. Special Upgrade Offer
    26. Copyright