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

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
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
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
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
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?
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
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
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
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

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
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
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
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?
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
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
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
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
General References for Algorithms Graphs, Graphics, and Geometry String Processing and Parsing Numerical Methods General Mathematics Probability and Statistics Other References

Content preview from Mastering Algorithms with Perl

Preface

Perl’s popularity has soared in recent years. It owes its appeal first to its technical superiority: Perl’s unparalleled portability, speed, and expressiveness have made it the language of choice for a million programmers worldwide.

Those programmers have extended Perl in ways unimaginable with languages controlled by committees or companies. Of all languages, Perl has the largest base of free utilities, thanks to the Comprehensive Perl Archive Network (abbreviated CPAN; see http://www.perl.com/CPAN/).The modules and scripts you’ll find there have made Perl the most popular language for web, text, and database programming.

But Perl can do more than that. You can solve complex problems in Perl more quickly, and in fewer lines, than in any other language.

This ease of use makes Perl an excellent tool for exploring algorithms. Computer science embraces complexity; the essence of programming is the clean dissection of a seemingly insurmountable problem into a series of simple, computable steps. Perl is ideal for tackling the tougher nuggets of computer science because its liberal syntax lets the programmer express his or her solution in the manner best suited to the task. (After all, Perl’s motto is There’s More Than One Way To Do It.) Algorithms are complex enough; we don’t need a computer language making it any tougher.

Most books about computer algorithms don’t include working programs. They express their ideas in quasi-English pseudocode instead, which allows the discussion ...