There have been dozens of books on programming algorithms, but never before has there been one that uses Perl. Whether you are an amateur programmer or know a wide range of algorithms in other languages, this book will teach you how to carry out traditional programming tasks in a high-powered, efficient, easy-to-maintain manner with Perl. Topics range in complexity from sorting and searching to statistical algorithms, numerical analysis, and encryption

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.

Preface

xi

1. Introduction

1

(23)

What Is an Algorithm?

1

(7)

Efficiency

8

(12)

Recurrent Themes in Algorithms

20

(4)

2. Basic Data Structures

24

(22)

Perl's Built-in Data Structures

25

(1)

Build Your Own Data Structure

26

(1)

A Simple Example

27

(10)

Perl Arrays: Many Data Structures in One

37

(9)

3. Advanced Data Structures

46

(56)

Linked Lists

47

(13)

Circular Linked Lists

60

(2)

Garbage Collection in Perl

62

(3)

Doubly-Linked Lists

65

(6)

Infinite Lists

71

(1)

The Cost of Traversal

72

(1)

Binary Trees

73

(18)

Heaps

91

(1)

Binary Heaps

92

(7)

Janus Heap

99

(1)

The Heaps Module

99

(2)

Future CPAN Modules

101

(1)

4. Sorting

102

(55)

An Introduction to Sorting

102

(17)

All Sorts of Sorts

119

(32)

Sorting Algorithms Summary

151

(6)

5. Searching

157

(46)

Hash Search and Other Non-Searches

158

(1)

Lookup Searches

159

(16)

Generative Searches

175

(28)

6. Sets

203

(41)

Venn Diagrams

204

(1)

Creating Sets

205

(4)

Set Union and Intersection

209

(8)

Set Differences

217

(5)

Counting Set Elements

222

(1)

Set Relations

223

(4)

The Set Modules of CPAN

227

(6)

Sets of Sets

233

(7)

Multivalued Sets

240

(2)

Sets Summary

242

(2)

7. Matrices

244

(29)

Creating Matrices

246

(1)

Manipulating Individual Elements

246

(1)

Finding the Dimensions of a Matrix

247

(1)

Displaying Matrices

247

(1)

Adding or Multiplying Constants

248

(6)

Transposing a Matrix

254

(2)

Multiplying Matrices

256

(3)

Extracting a Submatrix

259

(1)

Combining Matrices

260

(1)

Inverting a Matrix

261

(1)

Computing the Determinant

262

(1)

Gaussian Elimination

263

(3)

Eigenvalues and Eigenvectors

266

(3)

The Matrix Chain Product

269

(3)

Delving Deeper

272

(1)

8. Graphs

273

(80)

Vertices and Edges

276

(5)

Derived Graphs

281

(5)

Graph Attributes

286

(1)

Graph Representation in Computers

287

(14)

Graph Traversal

301

(9)

Paths and Bridges

310

(2)

Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants

312

(4)

Edge and Graph Classes

316

(35)

CPAN Graph Modules

351

(2)

9. Strings

353

(72)

Perl Builtins

354

(3)

String-Matching Algorithms

357

(31)

Phonetic Algorithms

388

(1)

Stemming and Inflection

389

(5)

Parsing

394

(17)

Compression

411

(14)

10. Geometric Algorithms

425

(44)

Distance

426

(3)

Area, Perimeter, and Volume

429

(4)

Direction

433

(2)

Intersection

435

(8)

Inclusion

443

(6)

Boundaries

449

(8)

Closest Pair of Points

457

(7)

Geometric Algorithms Summary

464

(1)

CPAN Graphics Modules

464

(5)

11. Number Systems

469

(30)

Integers and Reals

469

(11)

Strange Systems

480

(11)

Trigonometry

491

(1)

Significant Series

492

(7)

12. Number Theory

499

(27)

Basic Number Theory

499

(5)

Prime Numbers

504

(18)

Unsolved Problems

522

(4)

13. Cryptography

526

(40)

Legal Issues

527

(1)

Authorizing People with Passwords

528

(5)

Authorization of Data: Checksums and More

533

(5)

Obscuring Data: Encryption

538

(17)

Hiding Data: Steganography

555

(3)

Winnowing and Chaffing

558

(4)

Encrypted Perl Code

562

(2)

Other Issues

564

(2)

14. Probability

566

(33)

Random Numbers

567

(2)

Events

569

(2)

Permutations and Combinations

571

(3)

Probability Distributions

574

(2)

Rolling Dice: Uniform Distributions

576

(6)

Loaded Dice and Candy Colors: Nonuniform Discrete Distributions

582

(7)

If the Blue Jays Score Six Runs: Conditional Probability

589

(1)

Flipping Coins Over and Over: Infinite Discrete Distributions

590

(1)

How Much Snow? Continuous Distributions

591

(1)

Many More Distributions

592

(7)

15. Statistics

599

(27)

Statistical Measures

600

(8)

Significance Tests

608

(12)

Correlation

620

(6)

16. Numerical Analysis

626

(23)

Computing Derivatives and Integrals

627

(7)

Solving Equations

634

(8)

Interpolation, Extrapolation, and Curve Fitting

642

(7)

A. Further Reading

649

(3)

B. ASCII Character Set

652

(5)

Index

657

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Mastering Algorithms with Perl

9781565923980

1565923987

Supplemental Materials

Summary

Author Biography

Table of Contents

Supplemental Materials

Rewards Program