- Shopping Bag ( 0 items )
Many programmers would love to use Perl for projects that involve heavy lifting, but miss the many traditional algorithms that ...
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:
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
This part algorithm-textbook, part how-to-manual is loaded with valuable information for programmers. It falls somewhere between advanced Perl concepts and the classic computer science text on algorithms; it provides a detailed practical analysis, not a rigorous exposition of algorithmic theory. For this advanced guide, you should understand Perl and programming basics.
About This Book;
Comments and Questions;
Chapter 1: Introduction;
1.1 What Is an Algorithm?;
1.3 Recurrent Themes in Algorithms;
Chapter 2: Basic Data Structures;
2.1 Perl’s Built-in Data Structures;
2.2 Build Your Own Data Structure;
2.3 A Simple Example;
2.4 Perl Arrays: Many Data Structures in One;
Chapter 3: Advanced Data Structures;
3.1 Linked Lists;
3.2 Circular Linked Lists;
3.3 Garbage Collection in Perl;
3.4 Doubly-Linked Lists;
3.5 Infinite Lists;
3.6 The Cost of Traversal;
3.7 Binary Trees;
3.9 Binary Heaps;
3.10 Janus Heap;
3.11 The Heap Modules;
3.12 Future CPAN Modules;
Chapter 4: Sorting;
4.1 An Introduction to Sorting;
4.2 All Sorts of Sorts;
4.3 Sorting Algorithms Summary;
Chapter 5: Searching;
5.1 Hash Search and Other Non-Searches;
5.2 Lookup Searches;
5.3 Generative Searches;
Chapter 6: Sets;
6.1 Venn Diagrams;
6.2 Creating Sets;
6.3 Set Union and Intersection;
6.4 Set Differences;
6.5 Counting Set Elements;
6.6 Set Relations;
6.7 The Set Modules of CPAN;
6.8 Sets of Sets;
6.9 Multivalued Sets;
6.10 Sets Summary;
Chapter 7: Matrices;
7.1 Creating Matrices;
7.2 Manipulating Individual Elements;
7.3 Finding the Dimensions of a Matrix;
7.4 Displaying Matrices;
7.5 Adding or Multiplying Constants;
7.6 Transposing a Matrix;
7.7 Multiplying Matrices;
7.8 Extracting a Submatrix;
7.9 Combining Matrices;
7.10 Inverting a Matrix;
7.11 Computing the Determinant;
7.12 Gaussian Elimination;
7.13 Eigenvalues and Eigenvectors;
7.14 The Matrix Chain Product;
7.15 Delving Deeper;
Chapter 8: Graphs;
8.1 Vertices and Edges;
8.2 Derived Graphs;
8.3 Graph Attributes;
8.4 Graph Representation in Computers;
8.5 Graph Traversal;
8.6 Paths and Bridges;
8.7 Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants;
8.8 Edge and Graph Classes;
8.9 CPAN Graph Modules;
Chapter 9: Strings;
9.1 Perl Builtins;
9.2 String-Matching Algorithms;
9.3 Phonetic Algorithms;
9.4 Stemming and Inflection;
Chapter 10: Geometric Algorithms;
10.2 Area, Perimeter, and Volume;
10.7 Closest Pair of Points;
10.8 Geometric Algorithms Summary;
10.9 CPAN Graphics Modules;
Chapter 11: Number Systems;
11.1 Integers and Reals;
11.2 Strange Systems;
11.4 Significant Series;
Chapter 12: Number Theory;
12.1 Basic Number Theory;
12.2 Prime Numbers;
12.3 Unsolved Problems;
Chapter 13: Cryptography;
13.1 Legal Issues;
13.2 Authorizing People with Passwords;
13.3 Authorization of Data: Checksums and More;
13.4 Obscuring Data: Encryption;
13.5 Hiding Data: Steganography;
13.6 Winnowing and Chaffing;
13.7 Encrypted Perl Code;
13.8 Other Issues;
Chapter 14: Probability;
14.1 Random Numbers;
14.3 Permutations and Combinations;
14.4 Probability Distributions;
14.5 Rolling Dice: Uniform Distributions;
14.6 Loaded Dice and Candy Colors: Nonuniform Discrete Distributions;
14.7 If the Blue Jays Score Six Runs: Conditional Probability;
14.8 Flipping Coins Over and Over: Infinite Discrete Distributions;
14.9 How Much Snow? Continuous Distributions;
14.10 Many More Distributions;
Chapter 15: Statistics;
15.1 Statistical Measures;
15.2 Significance Tests;
Chapter 16: Numerical Analysis;
16.1 Computing Derivatives and Integrals;
16.2 Solving Equations;
16.3 Interpolation, Extrapolation, and Curve Fitting;
General References for Algorithms;
Graphs, Graphics, and Geometry;
String Processing and Parsing;
Probability and Statistics;
ASCII Character Set;
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.per1.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 complexproblemss 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 to focus on concepts without getting bogged down in implementation details. But sometimes the details are what matter -- the inefficiencies of a bad implementation sometimes cancel the speedupthat a good algorithm provides. The devil is in the details.
And while converting ideas to programs is often a good exercise, it's also just plain time-consuming. So, in this book we've supplied you with not just explanations, but implementations as well, If you read this book carefully, you'll learn more about both algorithms and Perl.
Deciding when to be fierce and when to be playful hasn't been easy for us. For instance, every algorithms textbook has a chapter on all of the different ways to sort a collection of items. So do we, even though Perl provides its own sort() function that might be all you ever need. We do this for four reasons. First, we don't want you thinking you've Mastered Algorithms without understanding the algorithms covered in every college course on the subject. Second, the concepts, processes, and strategies underlying those algorithms will come in handy for more than just sorting, Third, it helps to know how Perl's sort() works under the hood, why its particular algorithm (quicksort) was used, and how to avoid some of the inefficiencies that even experienced Perl programmers fall prey to. Finally, sort() isn't always the best solution! Someday, you might need another of the techniques we provide.
When it comes to the inevitable tradeoffs between theory and practice, programmers' tastes vary. We have chosen a middle course, swiftly pouncing from one to the other with feral abandon. If your tastes are exclusively theoretical or practical, we hope you'll still appreciate the balanced diet you'll find here.
Chapter 1 describes the basics of Perl and algorithms, with an emphasis on speed and general problem-solving techniques.
Chapter 2 explains how to use Perl to create simple and very general representations, like queues and lists of lists.
Chapter 3, Advanced Data Structures, shows how to build the classic computer science data structures.
Chapter 4, Sorting, looks at techniques for ordering data and compares the advantages of each technique.
Chapter 5, Searching, investigates ways to extract individual pieces of information from a larger collection.
Chapter 6, Sets, discusses the basics of set theory and Perl implementations of set operations.
Chapter 7, Matrices, examines techniques for manipulating large arrays of data and solving problems in linear algebra.
Chapter 8, Graphs, describes tools for solving problems that are best represented as a graph a collection of nodes connected by edges.
Chapter 9, Strings, explains how to implement algorithms for searching, filtering, and parsing strings of text.
Chapter 10, Geometric Algorithms, looks at techniques for computing with two- and three-dimensional constructs.
Chapter 11, Number Systems, investigates methods for generating important constants, functions, and number series, as well as manipulating numbers in alternate coordinate systems.
Chapter 12, Number Theory, examines algorithms for factoring numbers, modular arithmetic, and other techniques for computing with integers.
Chapter 13, Cryptography, demonstrates Perl utilities to conceal your data from prying eyes.
Chapter 14, Probability, discusses how to use Perl for problems involving chance.
Chapter 15, Statistics, describes methods for analyzing the accuracy of hypotheses and characterizing the distribution of data.
Chapter 16, Numerical Analysis, looks at a few of the more common problems in scientific computing.
Appendix A, Further Reading, contains an annotated bibliography.
Appendix B, ASCII Character Set, lists the seven-bit ASCII character set used by default when Perl sorts strings.
Used for elements of programming languages, text manipulated by programs, code examples, and output.
Constant width bold
Used for user input and for emphasis in code.
Constant width italic
Used for replaceable values.
That said, if you don't know Perl, you don't want to start here. We recommend you begin with either of these books published by O'Reilly & Associates: Randal L. Schwartz and Tom Christiansen's Learning Perl if you're new to programming, and Larry Wall, Tom Christiansen, and Randal L. Schwartz's Programming Perl if you're not.
If you want more rigorous explanations of the algorithms discussed in this book, we recommend either Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest's Introduction to Algorithms, published by MIT Press, or Donald Knuth's The Art of Computer Programming, Volume I (Fundamental Algorithms) in particular. See Appendix A for full bibliographic information.
This book often refers to CPAN modules, which are packages of Perl code you can download for free from http://www.perl.com/CPAN/modules/by-module/. In particular, the CPAN.pm module (http://www.perl.com/CPAN/modules/by-module/CPAN) can automatically download, build, and install CPAN modules for you.
Typically, the modules in CPAN are usually quite robust because they're tested and used by large user populations. You can check the Modules List (reachable by a link from http://www.perl.com/CPAN/CPAN.html) to see how authors rate their modules; as a module rating moves through "idea," "under construction," "alpha," "beta," and finally to "Released," there is an increasing likelihood that it will behave properly.
Posted September 15, 2011
No text was provided for this review.