Mastering Algorithms with Perl

Jon Orwant is president of Readable Publications, Inc. He founded The Perl Journal in 1995 and served as the sole editor, publisher, accountant, designer, and postal antagonizer until 1999. He has been on the technical committee of all of O'Reilly's Perl conferences (where he is the emcee of the Internet Quiz Show), and he speaks frequently about Perl, most recently at the first YAPC on Rebuilding Post-Apocalyptic Civilization with Perl. He is currently an MIT Media Laboratory IBM Fellow, creating programs that create programs that play games. His other research interests are user modeling and electronic publishing. He gives frequent talks about Media Lab research, most recently on the promise and perils of Internet gambling. In 1993, he created the world's first Internet stock-picking game. His Markov-model based Rock-Paper-Scissors program has been undefeated since 1997. He also performs professional voice-overs. A court injunction from the Commonwealth of Massachusetts prohibits him from cooking or otherwise assisting in the preparation of any foodstuff meant for human consumption. 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.

'An O'Reilly book, and what a good one it is. And what a fun one too: a book on algorithms for Perl. Yowza! As far as I know, this is a first. But otherwise this standard O'Reilly fare: well written, well edited, well designed (note the wolf on the cover), all you will expect and get from this publisher time and time again. And no, I don't haved shares in O'Reilly!' - Julian Bucknall, Developers Review, June 2000. '...and the authors show every sign of enjoying themselves in writing it. It's a great read, as much for the byways it opens up as for the possibility of using it to attack real-world problems. It marks a sort of coming of age for the language and most people who use Perl as a day to day 'Swiss army chainsaw' will enjoy it.' - Fiachra O Marcaigh, Irish Times, February 21st 2000

• Preface. Chapter 1. Introduction What Is an Algorithm? Efficiency Recurrent Themes in Algorithms. Chapter 2. Basic Data Structures Perl's Built-in Data Structures Build Your Own Data Structure A Simple Example Perl Arrays: Many Data Structures in One. Chapter 3. Advanced Data Structures Linked Lists Circular Linked Lists Garbage Collection in Perl Doubly-Linked Lists Infinite Lists The Cost of Traversal Binary Trees Heaps Binary Heaps Janus Heap The Heaps Module Future CPAN Modules. Chapter 4. Sorting An Introduction to Sorting All Sorts of Sorts Sorting Algorithms Summary. Chapter 5. Searching Hash Search and Other Non-Searches Lookup Searches Generative Searches. Chapter 6. Sets Venn Diagrams Creating Sets Set Union and Intersection Set Differences Counting Set Elements Set Relations The Set Modules of CPAN Sets of Sets Multivalued Sets Sets Summary. Chapter 7. Matrices Creating Matrices Manipulating Individual Elements Finding the Dimensions of a Matrix Displaying Matrices Adding or Multiplying Constants Transposing a Matrix Multiplying Matrices Extracting a Submatrix Combining Matrices Inverting a Matrix Computing the Determinant Gaussian Elimination Eigenvalues and Eigenvectors The Matrix Chain Product Delving Deeper. Chapter 8. Graphs Vertices and Edges Derived Graphs Graph Attributes Graph Representation in Computers Graph Traversal Paths and Bridges Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants Edge and Graph Classes CPAN Graph Modules. Chapter 9. Strings Perl Builtins String-Matching Algorithms Phonetic Algorithms Stemming and Inflection Parsing Compression. Chapter 10. Geometric Algorithms Distance Area, Perimeter, and Volume Direction Intersection Inclusion Boundaries Closest Pair of Points Geometric Algorithms Summary CPAN Graphics Modules. Chapter 11. Number Systems Integers and Reals Strange Systems Trigonometry Significant Series. Chapter 12. Number Theory Basic Number Theory Prime Numbers Unsolved Problems. Chapter 13. Cryptography Legal Issues Authorizing People with Passwords Authorization of Data: Checksums and More Obscuring Data: Encryption Hiding Data: Steganography Winnowing and Chaffing Encrypted Perl Code Other Issues. Chapter 14. Probability Random Numbers Events Permutations and Combinations Probability Distributions Rolling Dice: Uniform Distributions Loaded Dice and Candy Colors: Nonuniform Discrete Distributions If the Blue Jays Score Six Runs: Conditional Probability Flipping Coins Over and Over: Infinite Discrete Distributions How Much Snow? Continuous Distributions Many More Distributions. Chapter 15. Statistics Statistical Measures Significance Tests Correlation. Chapter 16. Numerical Analysis Computing Derivatives and Integrals Solving Equations Interpolation, Extrapolation, and Curve Fitting Appendix A. Further Reading Appendix B. ASCII Character Set Index