book

Mastering Algorithms with Perl

by Jarkko Hietaniemi, Jon Orwant, John Macdonald

August 1999

Intermediate to advanced

701 pages

19h 7m

English

O'Reilly Media, Inc.

Read now

Unlock full access

A Note Regarding Supplemental Files
Preface
About This BookTheory or Practice?Organization of This BookConventions Used in This BookWhat You Should Know Before Reading This BookWhat You Should Have Before Reading This BookOnline Information About This BookAcknowledgmentsComments and Questions
1. Introduction
What Is an Algorithm? A Sample Algorithm: Binary Search What do all those funny symbols mean?ReferencesAdapting AlgorithmsGeneralityEfficiencySpace Versus TimeBenchmarkingFloating-Point NumbersTemporary Variables Caching Evaluating Algorithms: O(N) NotationDon’t cheatRecurrent Themes in AlgorithmsRecursionDivide and ConquerDynamic ProgrammingChoosing the Right Representation
2. Basic Data Structures
Perl’s Built-in Data Structures Build Your Own Data Structure A Simple Example Lols and Lohs and Hols and Hohs Objects Using a Constructed Datatype Shortcuts Perl Arrays: Many Data Structures in One Queues Stacks Deques Still More Perl Arrays
3. Advanced Data Structures
Linked Lists Linked List Implementations Tracking Both Ends of Linked Lists Additional Linked List Operations Circular Linked Lists Garbage Collection in Perl Doubly-Linked Lists Infinite Lists The Cost of Traversal Binary Trees Keeping Trees BalancedUser-visible routinesMergingThe actual balancing Heaps Binary Heaps Janus Heap The Heap Modules Future CPAN Modules
4. Sorting
An Introduction to SortingPerl’s sort FunctionASCII OrderNumeric OrderReverse Order: From Highest To Lowest Sort::Fields Sort::Versions Dictionary OrderSorting EfficiencyThe Schwartzian TransformLong duration cachingDeficiency: missing internationalization (locales) Sort::ArbBiLex See for yourself: use the Benchmark moduleSorting Hashes Is Not What You Might ThinkAll Sorts of SortsQuadratic Sorting AlgorithmsSelection sortMinima and maximaBubble sortInsertion sortShellsortLog-Linear Sorting AlgorithmsMergesortHeapsortQuicksortRemoving recursion from quicksortMedian, quartile, percentileBeating O(N log N)Radix sortsCounting sortHybrid sortsBucket sortQuickbubblesortExternal SortingSorting Algorithms SummaryO(N2) SortsSelection sortBubble sort and insertion sortShellsortO(N log N) SortsMergesortQuicksortHow Well Did We Do?
5. Searching
Hash Search and Other Non-Searches Lookup Searches Ransack Search Linear Search Binary Search in a List Proportional Search Binary Search in a Tree Should You Use a List or a Tree for Binary Searching? Bushier Trees Lists of Lists B-Trees Hybrid Searches Lookup Search Recommendations Generative Searches Game Interface Exhaustive Search Alternatives to Exhaustive Search in Games Minimax Pruning Alpha-beta pruning Killer moveTranspose tables Advanced pruning strategies Other strategies Nongame Dynamic Searches Greedy algorithms Branch and bound The A* algorithm Dynamic programming
6. Sets
Venn Diagrams Creating Sets Creating Sets Using Hashes Creating Sets Using Bit Vectors Set Union and Intersection Union Intersection Set Universe Complement Set Null Set Set Union and Intersection Using Hashes Union and Intersection Using Bit Vectors Set Differences Set Difference Set Symmetric Difference Set Differences Using Hashes Set Differences Using Bit Vectors Counting Set Elements Set Relations Set Relations Using Hashes Set Relations Using Bit Vectors The Set Modules of CPAN Set::Scalar Set::Object Set::IntSpan Bit::Vector Set::IntRange Sets of Sets Power Sets Power Sets Using Hashes Multivalued SetsMultivalued LogicFuzzy SetsBagsSets Summary
7. Matrices
Creating MatricesManipulating Individual ElementsFinding the Dimensions of a MatrixDisplaying MatricesAdding or Multiplying ConstantsAdding a Constant to a MatrixAdding a Matrix to a MatrixTransposing a MatrixMultiplying MatricesExtracting a SubmatrixCombining MatricesInverting a MatrixComputing the DeterminantGaussian EliminationEigenvalues and EigenvectorsComputing EigenvaluesUsing PDL to calculate eigenvalues and eigenvectorsCalculating easy eigenvalues directlyThe Matrix Chain ProductDelving Deeper
8. Graphs
Vertices and Edges Edge Direction Vertex Degree and Vertex Classes Derived Graphs Graph TransposeComplete GraphComplement Graph Density Graph Attributes Graph Representation in Computers Our Graph Representation Creating graphs, dealing with vertices Testing for and adding edges Returning edges Density, degrees, and vertex classes Deleting edges and vertices Graph attributes Displaying graphs Graph Traversal Depth-First Search Topological Sortmake as a topological sort Breadth-First Search Implementing Graph TraversalImplementing depth-first traversalImplementing breadth-first traversal Paths and Bridges The Seven Bridges of Königsberg Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants Parents and ChildrenEdge and Graph Classes Edge Classes Graph Classes: Connectivity BiconnectivityStrongly Connected Graphs Minimum Spanning Trees Kruskal’s minimum spanning tree Prim’s minimum spanning tree Shortest Paths Single-source shortest paths Dijkstra’s single-source shortest pathsBellman-Ford single-source shortest pathsDAG single-source shortest paths All-pairs shortest paths Transitive Closure Flow Networks Ford-Fulkerson Edmonds-Karp Traveling Salesman Problem CPAN Graph Modules

9. Strings
Perl Builtins Exact Matching Regular Expressions Quick tips for regular expressions: readability Quick tips for regular expressions: efficiency study() String-Matching Algorithms Naïve Matching Matching sequences Rabin-Karp Rabin-Karp is a checksum algorithm Handling huge checksums Implementing Rabin-Karp Further checksum experimentation Knuth-Morris-Pratt Boyer-Moore Shift-Op Baeza-Yates-Gonnet Shift-OR Exact Matching Approximate Matching Baeza-Yates-Gonnet Shift-Add Wu-Manber k-differences Longest Common Subsequences Summary of String Matching Algorithms String::Approx Phonetic Algorithms Text::Soundex Text::Metaphone Stemming and Inflection Modules for Stemming and Inflection Text::Stem Text::German Lingua::EN::Inflect Lingua::PT::Conjugate Parsing Finite Automata Grammars Context-free grammars Parsing Up and Down Top-down parsing Bottom-up parsing Interpreters and Compilers Modules for Lexing and Parsing Parse::Lex Parse::RecDescent Text::Abbrev Text::ParseWords Text::DelimMatch String::ShellQuote Text::Balanced Special-purpose parsers Compression Run-Length Encoding Huffman Encoding compress, GNU gzip, pkzip
10. Geometric Algorithms
Distance Euclidean Distance Manhattan Distance Maximum Distance Spherical Distance Area, Perimeter, and Volume Triangle Polygon Area Polygon Perimeter Direction Intersection Line Intersection Line intersection: the general case Line intersection: the horizontal-vertical case Inclusion Point in Polygon Point in Triangle Point in Quadrangle Boundaries Bounding Box Convex Hull Closest Pair of Points Geometric Algorithms SummaryCPAN Graphics Modules2-D ImagesPerl-GimpGDImage::SizePerlMagickPGPLOTCharts a.k.a. Business Graphics3-D ModelingOpenGLRendermanVRMLWidget/GUI ToolkitsPerl/TkOther windowing toolkits
11. Number Systems
Integers and Reals Constants Pure Integer Arithmetic Precision Rounding Numbers Rounding up or down to an integer Rounding to the nearest integer Rounding to a particular decimal point Very Big, Very Small, and Very Precise Numbers Fractions Strange Systems Bits and Bases Bit Vectors Complex Numbers Polar Coordinates Dates and Times Roman Numerals Trigonometry Significant Series Arithmetic and Geometric Progressions The Fibonacci Sequence Harmonic Series The Riemann Zeta Function and Bernoulli Numbers
12. Number Theory
Basic Number Theory Linear Combination Theorem Greatest Common Divisor GCD: Linear Combination Least Common Multiple Prime Numbers Caching: Another Example Noninfinite Arithmetic Modular Arithmetic Chinese Remainder Theorem Modular Division Chinese Remainder Theorem Revisited Treating Chinese remainders as integers Integer Exponentiation Modular Exponentiation Miller-Rabin: Prime Generation Revisited Unsolved Problems Is the Collatz Conjecture False? Is There an Odd Perfect Number? Is the Goldbach Conjecture False?
13. Cryptography
Legal Issues Authorizing People with Passwords Password Hazards Authorization of Data: Checksums and More Obscuring Data: Encryption Perfect Encryption: The One-Time Pad Shared-Secret Encryptions Analysis of Shared-Secret Encryption Encrypting with SSLeay Public Key Encryption RSA Public Key Encryption El Gamal Public Key Encryption Choosing Between Public Key and Private Key Hiding Data: Steganography Winnowing and Chaffing Encrypted Perl Code Other Issues
14. Probability
Random Numbers Don’t Forget to Seed Your Generator Better Randomness Events Will the Blue Jays Win, and Will the Stock Market Go Up? Will Neither the Blue Jays Win nor the Stock Market Go Up? Will the Blue Jays Win or the Stock Market Go Up? Permutations and Combinations Permutations Combinations Probability Distributions Expected Value Rolling Dice: Uniform Distributions Measuring Time: Uniform Continuous Distributions Choosing an Element from an Array Picking Random BigInts Rolling Dice Revisited: Combining Events Loaded Dice and Candy Colors: Nonuniform Discrete Distributions Flipping a Coin: The Binomial Distribution The Binomial Distribution in Poker If the Blue Jays Score Six Runs: Conditional Probability The Vaunted Monty Hall Problem Flipping Coins Over and Over: Infinite Discrete Distributions How Much Snow? Continuous Distributions Many More Distributions The Bernoulli Distribution The Beta Distribution The Binomial Distribution The Cauchy Distribution The Chi Square Distribution The Erlang Distribution The Exponential Distribution The Gamma Distribution The Gaussian (Normal) Distribution The Geometric Distribution The Hypergeometric Distribution The Laplace Distribution The Log Normal Distribution The Maxwell Distribution The Pascal Distribution The Poisson Distribution The Rayleigh Distribution The Uniform Distribution
15. Statistics
Statistical MeasuresThe MeanThe MedianThe ModeStandard Deviation The Standard Score The Variance and Standard Deviation of DistributionsSignificance TestsHow Sure Is Sure?The Sign TestThe z-testThe t-testThe Chi-square testANOVA and the F-testCorrelationComputing the CovarianceComputing the Correlation Coefficient Fitting a Line to Your Data
16. Numerical Analysis
Computing Derivatives and IntegralsComputing the Derivative at a Particular PointComputing the JacobianComputing Definite IntegralsSolving EquationsSimple Roots: Quadratics and CubicsThe quadratic formulaCubic equationsApproximating RootsMultiple Nonlinear EquationsInterpolation, Extrapolation, and Curve FittingFitting a Polynomial to a Set of PointsSplinesCubic splinesData Smoothing
A. Further Reading
General References for Algorithms Graphs, Graphics, and Geometry String Processing and Parsing Numerical Methods General Mathematics Probability and Statistics Other References
B. ASCII Character Set
Index
About the Authors
Colophon
Copyright

Content preview from Mastering Algorithms with Perl

About the Authors

Jarkko Hietaniemi is the creator and Master Librarian of CPAN: Comprehensive Perl Archive Network. He has also been known to frequent Perl developer forums. Luckily enough, getting his MSc in CS in the field of parallel computing didn't interfere overly much with his Perl and UNIX hacking. During those savored moments of off-line time, he fancies gobbling up speculative fiction and popular science. His real life employer is Nokia Research Center.

John Macdonald has been using Perl commercially since 1988 for a suite of Unix system administration tools. His background with Unix dates back to the days when Unix was written in PDP-11 assembler and later includes representing the University of Waterloo at the first UNIX Users Meeting at City University of New York in the mid-1970s while finishing his M. Math degree. (In those days before the creation of Usenix, the people at the meeting would sit together around a single table.) In addition, his background includes work on compilers, kernel internals, device drivers and the like. He has also been observed partaking in recreational computing activities.

Jon Orwant, a well-known member of the Perl community, founded The Perl Journal and co-authored OReillys bestseller, Programming Perl, 3rd Edition.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 1565923987Errata Page

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Mastering Algorithms with Perl

by Jarkko Hietaniemi, Jon Orwant, John Macdonald

About the Authors

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.