Mastering Algorithms with Perl

Mastering Algorithms with Perl

by Jarkko Hietaniemi, Jon Orwant, John Macdonald
Released August 1999
Publisher(s): O'Reilly Media, Inc.
ISBN: 9781565923980

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Buy on Amazon
Start your free trial

Book description

Many programmers would love to use Perl for projects that involve heavy lifting, but miss the many traditional algorithms that textbooks teach for other languages. Computer scientists have identified many techniques that a wide range of programs need, such as:

  • 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 out traditional programming tasks in a high-powered, efficient, easy-to-maintain manner with Perl.This book assumes a basic understanding of Perl syntax and functions, but not necessarily any background in computer science. The authors explain in a readable fashion the reasons for using various classic programming techniques, the kind of applications that use them, and -- most important -- how to code these algorithms in Perl.If you are an amateur programmer, this book will fill you in on the essential algorithms you need to solve problems like an expert. If you have already learned algorithms in other languages, you will be surprised at how much different (and often easier) it is to implement them in Perl. And yes, the book even has the obligatory fractal display program.There have been dozens of books on programming algorithms, some of them excellent, but never before has there been one that uses Perl.The authors include the editor of The Perl Journal and master librarian of CPAN; all are contributors to CPAN and have archived much of the code in this book there."This book was so exciting I lost sleep reading it." Tom Christiansen

Table of contents

  1. A Note Regarding Supplemental Files
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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 O(N log N)
        1. Radix sorts
        2. Counting sort
        3. Hybrid sorts
          1. Bucket sort
          2. Quickbubblesort
      4. External Sorting
    3. Sorting Algorithms Summary
      1. O(N2) 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?
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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?
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. B. ASCII Character Set
  21. Index
  22. About the Authors
  23. Colophon
  24. Copyright

Product information

  • Title: Mastering Algorithms with Perl
  • Author(s): Jarkko Hietaniemi, Jon Orwant, John Macdonald
  • Release date: August 1999
  • Publisher(s): O'Reilly Media, Inc.
  • ISBN: 9781565923980