Mastering Algorithms with Perl [NOOK Book]

Overview

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:

  • Fuzzy pattern matching for text (identify misspellings!)
  • Finding correlations in ...
See more details below
Mastering Algorithms with Perl

Available on NOOK devices and apps  
  • NOOK Devices
  • Samsung Galaxy Tab 4 NOOK
  • NOOK HD/HD+ Tablet
  • NOOK
  • NOOK Color
  • NOOK Tablet
  • Tablet/Phone
  • NOOK for Windows 8 Tablet
  • NOOK for iOS
  • NOOK for Android
  • NOOK Kids for iPad
  • PC/Mac
  • NOOK for Windows 8
  • NOOK for PC
  • NOOK for Mac
  • NOOK for Web

Want a NOOK? Explore Now

NOOK Book (eBook)
$17.99
BN.com price
(Save 43%)$31.99 List Price

Overview

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:

  • Fuzzy pattern matching for text (identify misspellings!)
  • Finding correlations in data
  • Game-playing algorithms
  • Predicting phenomena such as Web traffic
  • Polynomial and spline fitting
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.

Read More Show Less

Editorial Reviews

Library Journal
Perl is very similar to C in syntax, and while Perl doesn't have the speed of complied C, it has been getting much faster. It also is one of the most portable languages, available for most hardware with no changes in code. It is free, which makes it very attractive to developers. This guide covers everything from data structures, sorting and searching, to sets and matrices, to cryptography, probability, and statistics. Readers must already know Perl, so this is recommended for advanced programming collections. Copyright 1999 Cahners Business Information.
Read More Show Less

Product Details

  • ISBN-13: 9781449307196
  • Publisher: O'Reilly Media, Incorporated
  • Publication date: 8/18/1999
  • Sold by: Barnes & Noble
  • Format: eBook
  • Edition number: 1
  • Pages: 706
  • Sales rank: 1,235,633
  • File size: 7 MB

Meet the Author


Jon Orwant is editor and publisher of The Perl Journal, a founding director of The Perl Institute, and the author of two books besides this one: Macmillan's Perl 5 Interactiveu and O'Reilly's upcoming Manipulating Text with Perl. He is a doctoral candidate at MIT, a Media Lab IBM Fellow, and a member of the Media Lab's Electronic Publishing Group. He has lectured internationally on user modeling and electronic newspapers, and has represented the Media Laboratory on television and radio.

Jarkko Hietaniemi got his MSc in Computer Science from the Helsinki University of Technology while herding its UNIX infrastructure and heard there of some new language called Perl. He has been an active Perl 5 language and libraries developer since the very early days and is the creator and master librarian of CPAN: the Comprehensive Perl Archive Network. His real paid job is a research engineer for the Communication Systems Laboratory of the Nokia Research Center.

John Macdonald (jmm@elegant.com) has been using Perl since 1988 for a suite of system administration tools. His background also includes work on compilers, Unix kernal internals, and device drivers.

Read More Show Less

Table of Contents

TOC:

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 INDEX:

Symbols
Numbers
2-3 trees, 79
2-D image modules, 464
3-D modeling, 466
32-bit checksumming, 368
& (binary and) operator, 216
&& (logical and) operator, 240
<=> (spaceship) operator, 105
* (multiplication) operator, 257
@ for array names, 2
\ (backslash)
   creating references, 5
   symmetric difference operator, 219
'' backtick characters, 410
! (logical not) operator, 240
{} (braces)
   code blocks, 3
   repetition quantifiers, 356
[] for character classes, 356
^ (anchor) metacharacter, 355
$ (dollar sign)
   $&, $<oq>, $' variables, 357
   anchor metacharacter, 355
   scalar names, 2
. (any-character) metacharacter, 357
# for hash names, 2
-> (arrow) operator, 35
<*p> (pi), 470
+ (addition) operator, 252
?= assertion, 356
"" operator, 277, 299
_ (underscore) and numeric comparison, 107
| (vertical bar)
   || (logical or) operator, 210, 240
   alternation operator, 356
   binary or operator, 216

A
A* algorithm, 200-202
a/an determination, 393
Aas, Gisle, 369, 535
ab_minimax(), 188
Abigail, 352
accepting input, 395-396
accessors, 32
active data access (transforming data), 526
Adams, Carlisle, 543
adapting algorithms, 5
add() (MD5), 536
add_chinese(), 516
add_edge(), 276, 292
add_path(), 276, 293
add_vertex(), 276, 291
add_vertices(), 290
addfile() (MD5), 536
adding
   addition (+) operator, 252
   constants to matrices, 248-251
   matrices together, 251-254
addresses (street), data structures for, 27, 31
Adelson-Velskii, G. M., 78
adjacency lists, 287-301
adjacency matrices, 288
Advanced Encryption Standard (AES), 543
AES (Advanced Encryption Standard), 543
agrep utility, 382
Albanowski, Kenneth, 107
Algorithm::Diff module, 386
Algorithm::TransitiveClosure module, 352
algorithms, 1-23
   adapting to your needs, 5
   efficiency (see efficiency of algorithms)
   encryption, 527
      DES, 528
      SSLeay module, available in, 546
   general references on, 649
   generality of, 6-8
   recurrent themes, 20-23
Alias module, 36
all_of(), 569, 586
all-pairs shortest paths (APSPs), 333, 339-342
allocation, 62
   array size, 37, 43
   (see also garbage collection)
alpha-beta pruning, 187-189, 192
alphabet rotations (encryption), 542
alphabets of lines, searching, 362
Alphaville connectivity example, 322
alternation (|) operator, 356
amatch(), 383, 387
ambiguity of artificial languages, 395
analysis of variance (ANOVA), 617-620
ancestor vertices, 315
anchoring matches, 355
and (&&) operator, 240
anonymous variables, 5
ANOVA (analysis of variance), 617-620
anova(), 619
append(), 65
   double_head package, 69
   double package, 67
approximate matching, 353, 379, 388
   Baeza-Yates-Gonnet shift-add algorithm, 379-382
   Baeza-Yates-Gonnet shift-OR algorithm, 377
   longest common subsequence (LCS), 386
   regular expressions (String::Approx), 387
   Wu-Manber k-differences algorithm, 382-387
   (see also phonetic algorithms)
approximating polynomial roots, 638-640
APSP_Floyd_Warshall(), 339
APSPs (all-pairs shortest paths), 333, 339-342
arbitrary bi-level lexicographic sorting, 114
arbitrary precision, 478
are_disjoint(), 225
area, calculating
   polygons, 430-432
   triangles, 429
arithmetic_progression(), 492
arithmetic progressions, 492
arithmetic with integers, 470-471
arrays, 2, 26, 244
   binary search in list, 162-165
   binary search in tree, 167-171
   copying, 35-37
   efficiency of, 43
   emulating sets, 205
   hashes of hashes (hohs), 29
   hashes of lists (hols), 29
      reversing element order, 118
   hashes vs., 27-29, 33
   infinite lists, 71
   inserting and deleting elements, 42-45, 47, 55, 164
   linked lists, 47-59
      circular, 60-62
      tracking both ends, 52-55
   lists of hashes (lohs), 29
   lists of lists (lols), 29, 34
      searching, 168
   multidimensional, 245
   randomly selecting elements, 579
   traversal performance, 72
   types of, 37-45
      deques (double-ended queues), 40-42, 60
      queues, 38-39
      stacks, 39
   (see also matrices)
arrow (->) operator, 35
articulation points, 320-323
articulation_points(), 321
artificial languages, 394
as_string(), 32
ASCII character set, 652-655
ASCII encoding, 363
ASCII order, 104
asymmetry of set differences, 218
asymptotic behavior, 17
Atkinson, Kevin, 480
attempts (string matching), 357
attributes, graph, 286, 299
audio, hiding messages in, 555
augmenting path, 345
authentication, 533-537, 552
   encryption vs., 559
authorization, 528-533
   guarding vs. locking data, 527
automata, finite, 395
average (see mean)
average_degree(), 297
average degree of vertices, 280
AVL trees, 78
azimuthal spherical coordinates, 429

B
back edges, 316
backderive(), 390
backreferences, 354
Backus-Naur form (BNF), 397
bad-character heuristic, 373
Baeza-Yates-Gonnet shift-add algorithm, 379-382
Baeza-Yates-Gonnet shift-OR algorithm, 377-379
bags, 241
bal_tree_add(), 83
bal_tree_del(), 84
bal_tree_find(), 82
bal_tree_join(), 85
balance (binary trees), 74, 78-91
   lookup searching and, 174
balance_tree(), 86
balanced vertices, 280
base(), 483
bases (numbers), 481-484
basic_tree_add(), 75
basic_tree_del(), 77
basic_tree_find(), 75, 82
basis functions, 648
Bellman-Ford single-source shortest paths, 337-338
Benchmark module, 11, 239
   tips and tricks, 13
   (see also efficiency of algorithms)
benchmarking (see efficiency of algorithms)
bernoulli(), 496, 594
Bernoulli distribution, 591, 594
bernoulli_expected(), 594
Bernoulli numbers, 496
bernoulli_variance(), 594
best_line(), 623, 648
best_rating() (position), 177
beta(), 594
Beta distribution, 594
beta_expected(), 594
beta_variance(), 594
Beyer, Steffen, 230, 232, 245, 352
BFS (breadth-first search), 301, 307, 310
biconnected graph components, 307
biconnected graphs, 320-323
big integer calculations, 363
/bin/sh shell file, accessing, 533
binary and (&) operator, 216
binary exclusive or (XOR) operator, 220
binary exponentation, 479
binary heaps, 92-99
binary mask Rabin-Karp, 368
binary numbers, 481
binary or (|) operator, 216
binary_range_string(), 164
binary search
   in list, 2-5, 162-165
   stemming with, 389
   in tree, 167-171
binary_search(), 2-5
binary_search_file(), 6
binary_string(), 163
binary trees, 73-91, 314
   adding and removing elements, 75, 80
   balance, 74, 78-91
      lookup searching and, 174
   heaps, 91-101
      binary heaps, 92-99
      Heap modules, 99
      Janus heaps, 99
   Manhattan intersections, 440
   merging, 85-86
   preorder, postorder, inorder, 314
   rotating, 87
   searching, 75-78, 81, 167-171
   wider than binary, 168
binomial(), 585, 594, 611
binomial distribution, 585-589, 594
binomial_expected(), 594
binomial_variance(), 594
birthday conundrum, 570
bit masks, 221
Bit::Vector module, 230
bit_vector_to_hash_set(), 209, 238
bit vectors, 484
   emulating sets, 206-209
      counting members, 222
      set differences, 221
      set relations, 225-227
      union and intersection, 216
bits, 481-484
block unit size (encryption), 547
Blowfish encryption algorithm, 543
BNF (Backus-Naur form), 397
bottom-up parsing, 398, 404
bottom-up programming strategy, 22
boundaries, 449-456
   bounding boxes, 450-451
   convex hull, 452-456
bounding_box(), 450
bounding_box_of_points(), 450
bounding boxes, 450-451
Bowers, Neil, 352
boyer_moore(), 375
Boyer-Moore algorithm, 373-375
boyer_moore_good_suffix(), 374
Boyer-Moore-Horspool algorithm, 375
branch and bound method, 196-200
branch vertices, 312
breadth-first search, 193, 301, 307, 310
bridges, graph, 310-312, 320
brute-force DES cracking, 543
bsearch(), 5
B-tree algorithm, 169-171
BTree module, 171
bubble sort, 125-128, 152
   hybrid with quicksort, 148-150
bubblesmart(), 126
bubblesort(), 125
bucket sorts, 147
build_hash_tree(), 419
built-in data structures, 25
Bunce, Tim, 29
Burke, Sean M., 114
bushier trees for searching, 168
business use (cryptography), 527
bytecode, 405

C
caching, 16, 505
   finding prime numbers, 505-510
   Schwartzian Transform, 111-113
Caesar cipher, 540
calendar calculations, 489
callback functions, 303
capacity of flow network, 345
card(), 589
carriage returns, hiding messages in, 557
Cartesian coordinates (see coordinates)
cashflow(), 640
CAST encryption algorithm, 543
Catalan number, 269
catenary, 491
cauchy(), 594
Cauchy distribution, 594
cauchy_expected(), 594
causation vs. correlation, 620
ceil(), 474, 490
CFB (Cipher Feedback), 543
chaffing (encryption), 558-562
chaffmsg(), 559
chain products (matrices), 269-272
change of base law, 14
character classes, 356
characteristic polynomial, 266
characters, ASCII, 652-655
charts modules, 466
checkmessage(), 560
checksums, 362, 364-369, 534-537
   detecting local file modification, 536
   MD5 algorithm, 535
   necessary attributes, 535
   winnowing and chaffing, 558
chess, program for playing, 180
chi_square(), 595
chi square distribution, 595
chi_square_expected(), 595
chi-square test, 616-617
chi_square_variance(), 595
child vertices, 315
chisquare(), 617
choose(), 573
choose_simple(), 574
Cipher Feedback (CFB), 543
circuits, 277
circular linked lists, 60-62
   doubly-linked lists, 65-71
circumference(), 471
class stacks, explicit, 140
classes, 26
classes, graph, 279-281, 296, 316-320
   biconnected graphs, 320-323
   connectivity and, 320-326
   flow networks, 345-350
   minimum spanning trees, 326-332
      Kruskal's algorithm, 326-329, 352
      Prim's algorithm, 329-332, 335
   shortest paths, 332-342
      all-pairs (APSPs), 333, 339-342
      single-source (SSSPs), 333-338
   strongly connected graphs, 323-326
   transitive closure, 342-344
clockwise(), 435
clockwise direction, 433-435
closest pair of points, 457-464
closest_points(), 459
cmp operator, 106
cmp() (Heap modules), 100
Collatz conjecture, 523
collatz(), 523
combinations, 573-574
combinatorics, 566
combining events, 569, 581
combining matrices, 260
common divisors, 501
communication protocols, 564
commutativity
   matrix multiplication, 256
   set differences, 218-220
   set unions and intersections, 211
compare(), 8, 224
compare_bit_vectors(), 225
comparing
   comparison testing, 160
   sets, 223-227
   strings, 106
compiler-compilers, 398
compilers, 405-406
complement graph, 284
complement sets, 212
complete graph, 282
complex numbers, 485
composite numbers, 504
compress program, 421-424
compression, 411-424
   compress, gzip, pkzip, 421-424
   cryptography and, 526
   hidden messages and, 557
   Huffman encoding, 416-421
   lossless vs. lossy, 411
   run-length encoding (RLE), 412-415
Compress::Zlib module, 423
compute(), 10
computers, logging on, 526
condition number, 266
conditional probability, 589-590
congruent numbers, 511
connected components, 326
connected graph vertices, 279-281
connectivity, graphs, 320-326
   biconnected graphs, 320-323
   flow networks, 345-350
   minimum spanning trees, 326-332
      Kruskal's algorithm, 326-329, 352
      Prim's algorithm, 329-332, 335
   shortest paths, 332-342
      all-pairs (APSPs), 333, 339-342
      single-source (SSSPs), 333-338
   strongly connected graphs, 323-326
   transitive closure, 342-344
   TSP (Traveling Salesman problem), 350
constants, 470
   adding to matrices, 248-251
constructed datatypes, 34
constructors, 33
consuming input, 395
content() (double_head), 69
context, callback, 303
context-free grammars, 397-398
continuous probability distributions, 575, 591
   algorithms for (list), 592-598
   expected value, 576
   Gaussian distribution, 591, 595
   uniform, 578
Contrary program, 183
convergent series, 494
convex hull, 452-456
convex_hull_graham(), 453
Conway, Damian, 393, 407, 410
coordinates
   azimuthal spherical coordinates, 429
   polar, 488
copying arrays (lists), 35-37
correlation, 599, 620-625
   correlation coefficient, 622
   covariance, 621-622
   fitting lines to data, 622-624
correlation(), 622
count_elements(), 619
count_members(), 222
counterclockwise direction, 433-435
counting set members, 222
counting sort, 147
covariance, 621-622
CPAN modules, xiv, 101
   graph modules, 351
   graphics, 464-468
   profilers, 38
cplx(), 486
CPU time (see efficiency of algorithms)
crack program, 529
cracking (guessing) passwords, 529-532
cross edges, 317
cross product, 435
cryptography, 526-565
   authorizing data, 533-537
   authorizing passwords, 528-533
   encrypted source code, 562-564
   encryption, 538-555
   legal issues, 527
   security issues in general, 564
   steganography, 555-558
   winnowing and chaffing, 558-562
crypt() function, 529
cubic(), 268, 637
cubic equations, finding roots, 636
cubic splines, 644-647
customizing
   algorithms, 5
   data structures, 26
cycles, 301
   Euler and Hamiltonian cycles, 311
   in graphs, 277
   negative cycles, 334, 337

D
DAGs (directed acyclic graphs), 304, 312
   single-source shortest paths, 338
data
   access methods, 526
   authentication and integrity, 533-537
   discarding invalid (winnowing), 558
   hiding (steganography), 555-558
   passwords, authorizing, 528-533
   smoothing, 648
data encryption (see encryption)
Data Encryption Standard (see DES)
data link escape (DLE) character, 414
data structures, 22, 24-101
   arrays/lists (see arrays)
   binary trees, 314
      preorder, postorder, inorder, 314
      searching, 167-171
   constructed, 34
   garbage collection (see garbage collection)
   hashes (see hashes)
   heaps, 91-101
      binary heaps, 92-99
      Heap modules, 99
      Janus heaps, 99
   linked lists, 47-59
      circular, 60-62
      doubly-linked lists, 65-71
      tracking both ends, 52-55
   lookup searching and, 159, 173
   matrices (see matrices)
   sets (see sets)
   traversal performance, 72
   union-tree forests, 326
   within arrays, 37-45
dataflow analysis, 396
Date::Calc module, 489
Date::Convert module, 490
Date::GetDate module, 490
Date::Manip module, 489
dates and times, 489
datetab(), 168
daVinci package, 301
DB_File module, 170
DBL_EPSILON constant, 473
dealing cards, 589
debugging
   heaps, 101
   silencing warnings, 135
decile(), 142
decimal numbers, 481
decimal point, rounding to, 474
declaring scalars, 4
decryption (see encryption)
decrypt.xs file, 562-563
definite integrals, computing, 631-634
degree(), 297
degree of graph vertices, 279-281, 296
delete_edge(), 297
delete_edges(), 297
delete operator, 205
delete_vertex(), 297
deleting
   binary tree elements, 77, 80-81, 84
   graph edges and vertices, 297-299
   linked list elements, 55, 60
   set members (subtracting), 205, 218
delimiters, balancing, 410
dense sets, 229
density, graph, 285, 296
density_limits(), 296
dependency graphs, 304
dependent events, 569
dependent variables, 620
depth-first search, 193, 301-304
   graph traversal, 309, 314
deques, 40-42
   circular linked lists vs., 60
dereferencing, 5
deriv(), 628, 638
derivatives, computing, 628-629
   Jacobian matrix, 629-631
derived graphs, 281-285
   complement graph, 284
   complete graph, 282
   graph transpose, 282
DES (Data Encryption Standard), 528, 543
   Perl implementation (SSLeay), 543
DES-EDE and DES-EDE3 encryption algorithms, 543
descendant vertices, 315
destroy() (double package), 66, 68
DESTROY(), 65, 68, 70
det_LR(), 262
determinant, matrix, 262
deterministic finite automata (DFA), 354, 396
DFA::Kleene module, 231
DFS (depth-first search), 301-304
   graph traversal, 309, 314
dictionary order, 107
die_roll(), 577
difference(), 220
difference levels (Wu-Manber), 382
differences and fuzzy matching, 379
differences, sets, 217-222
differential analysis, 543
Diffie, Whitfield, 548
digital images, secret messages in, 555
digital signatures, 537
   El Gamal public key encryption, 552
Dijkstra's single-source shortest paths, 334-337
dimensions (see size)
directed acyclic graphs (DAGs), 304, 312
   single-source shortest paths, 338
directed graphs and edges, 277-279, 291-293
directed(), 292
direction, specifying, 433-435
directional alternative hypotheses, 612
directories, searching with B-trees, 169
discrete probability distributions, 575
   algorithms for (list), 592-598
   expected value, 575
disjointed sets, 223
disk space, 9-11
   caching, 16
   lookup tables, 9
display() (position), 177
display_poker(), 587
display_poker_many(), 587
distance(), 427
distance, calculating, 426-429
distributions (see probability distributions)
divergent series, 494
divide-and-conquer strategy, 21, 134
   closest pair of points, 457
division
   modular, 513
   numeric precision and, 574
divisors, 499
   greatest common (see GCD)
DLE character, 414
Dominus, Mark-Jason, 71, 113, 171, 386, 416, 505
double package (example), 65
double-ended queues (deques), 40-42
   circular linked lists vs., 60
double_head package, 68
doubly-linked lists, 65-71
downloading files, risks, 534
dynamic programming, 22, 202
   matrix chain products, 269
dynamic variables, 36

E
eavesdropping, 529
ECB (Electronic Code Book), 543
edge_classify(), 318
edges, graph, 276-281
   adding and testing for, 291-293
   attributes, 299
   classes, 279-281, 316-320
   deleting, 297-299
   direction, 277-279
   graph density, 285, 296
   walking (see traversing graphs)
   weight/cost, 286, 334
   (see also graphs)
editing algorithms, 5
Edmonds-Karp algorithm, 348
Edmonds-Karp flow network, 307
efficiency of algorithms, 8-20
   arrays and hashes, 27-29, 33, 43
   Benchmark module, 11
   caching, 16
   dynamic allocation, 37
   floating-point numbers, 14
   heaps, 92
   linked lists, 47
      tail pointers, 54
   list traversal performance, 72
   O(N) notation, 17-20
   recursion, 21
   regular expressions, 355
   searching, 157
      lookup searches, 172-175
   sets, 243
      membership sets, 216
      power set generation, 239
   sorting, 108-116, 145-150
      bubble sort, 126
      external sorting, 150
      insertion sort, 129
      sensitivity and stability, 119
      shellsort, 132
      summary and comparison, 151-156
   string matching
      na<:i>ve searching, 361
      Rabin-Karp algorithm, 369
      tips for regular expressions, 355
   temporary variables, 14
eigen_c(), 266
eigenvalue(), 268
eigenvalues and eigenvectors, 266-269
   direct eigenvalue calculation, 268
El Gamal public key encryption, 552-554
Electronic Code Book (ECB), 543
elements of matrices, 246
elements of sets (see members of sets)
emit(), 402-403
empty set, 213
encryption, 526, 538-554
   algorithms (licensing), 527
   authentication vs., 559
   block unit size, 547
   lost/stolen keys, 564
   meet-in-the-middle attacks, 543
   one-time pads, 538-540, 543
   password storage, 528
   of Perl source code, 562-564
   product development (government restrictions), 527
   public key, 533, 543, 548-554
      El Gamal, 552-554
      private key vs., 554
      RSA, 549-552
   random numbers, 568
   shared-secret, 540-548
      Caesar cipher, 540
      differential analysis algorithm, 543
      idea-ecb algorithm, 543
      Solitaire algorithm, 542
   SSLeay module for, 543-548
   steganography vs., 555
   winnowing and chaffing, 558-562
   (see also cryptography)
encryption object, creating, 546
English stemming (see stemming)
epsilon, 472
eq statement, 359
equations, solving, 634-642
   approximating roots, 638-640
   multiple nonlinear equations, 640-642
   quadratics and cubics, 635-638
Eratosthenes, sieve of, 504
erlang(), 595
Erlang distribution, 595
erlang_expected(), 595
erlang_variance(), 595
error(), 400, 404
estimate_variance(), 614, 618
Euclidean distance, 426
euclid(), 501
Euler cycles, 311
Euler path, 311
Euler tours, 311
Euler's formula, 485
evaluate() (position), 177
events, probability of, 566, 569-571
   birthday conundrum, 570
   distributions (see probability distributions)
   multiple events, 569-571, 581
exact matching, 354
   shift-OR exact matching, 377-379
exclusive binary or (XOR) operator, 220-221
exclusive logical or (xor) operator, 210
exclusive-or (XOR), 538, 540
exhaustive search, 180-185
   alternatives to, 185-193
exists statement, 215
exp_mod(), 519
exp_recurse(), 517
exp_slow(), 517
expected_value(), 575
expected value, 575-576
   of continuous distribution, 576
expected_value_weighted(), 576
explicit stacks, 140
exponentation, 517-520
exponential(), 595
exponential distribution, 595
exponential_expected(), 595
exponential_variance(), 595
exponentiation, 479
export restrictions (cryptography), 527, 543, 559
expression(), 400-401, 403
exterior vertices, 320
external searches, 174
external sorting, 150
extract(), 98, 556
extract_bracketed(), 410
extract_codeblock(), 410
extract_multiple(), 411
extract_quotelike(), 410
extract_tagged(), 411
extract_variable(), 411
extracting submatrices, 259
extrapolation, 642-648

F
F-ratio, 617-620
factor(), 399-401
factorial(), 478, 572
factorials, 15, 574
factoring large numbers, 549
false hits (string matching), 357, 365
feedback methods (encryption), 543
fibonacci(), 494
fibonacci_iterative(), 494
Fibonacci sequence, 493
Field Programmable Gate Array (FPGA), 543
fields for sorting (see keys, sorting)
fieldsort(), 106
FIFO order, 38
file_crypt(), 547
files
   B-trees to search for, 169
   content changes, detecting, 526
   downloading, security risks, 534
   encrypting/decrypting entire, 547
   mailing (security risks), 527
Filter module, 562
filtering Perl source code, 562
finding (see searching)
finite arithmetic, 510
finite automata, 395-396
   deterministic vs. nondeterministic, 396
fitting data, 642-648
fitting lines to data, 622-624
fixed-goal searches, 193-202
   A* algorithm, 200-202
   branch and bound method, 196-200
   greedy algorithms, 195
flipping coins, 585
floating-point numbers, 14, 472, 567
   factorials and, 574
floor(), 474, 490
Flow_Ford_Fulkerson(), 347
flow networks, 345-350
Floyd-Warshall algorithm, 339-342, 352
   transitive closure, 342-344
Ford-Fulkerson method, 345-347
forward edges, 317
FPGA (Field Programmable Gate Array), 543
frac(), 480
fractions, 480
from_chinese(), 514
fuzzy (approximate) matching, 353, 379, 388
   Baeza-Yates-Gonnet shift-add algorithm, 379-382
   Baeza-Yates-Gonnet shift-OR algorithm, 377
   longest common subsequence (LCS), 386
   regular expressions (String::Approx), 387
   Wu-Manber k-differences algorithm, 382-387
   (see also phonetic algorithms)
fuzzy sets, 241

G
game interface, 176-180
gamma(), 595
gamma distribution, 595
gamma_expected(), 595
gamma_variance(), 595
garbage collection, 37, 62-65
gaussian(), 592, 595
Gaussian distribution, 566, 591, 595
Gaussian elimination, 263-265, 634
gcd(), 502
GCD (greatest common divisor), 500-503
   expressed as linear combination, 503
gcd_linear(), 503, 514
GD module, 465
gen_RSA_keys(), 550
general_chinese(), 512
generality of algorithms, 6-8
generalized Chinese remainder theorem, 511
generalized least square methods, 648
generative searching, 158, 175-202
   exhaustive search, 180-185
   game interface for, 176-180
   killer move strategy, 189, 202
   minimax search, 185-187, 193
   opening book strategy, 192
   pruning, 187-189, 192
   symmetry, 192
   transpose tables, 190-191
      pruning with, 192
geometric(), 596
geometric algorithms, 425-468
   area, perimeter, volume, 429-433
   boundaries, 449-456
      bounding boxes, 450-451
      convex hull, 452-456
   closest pair of points, 457-464
   direction, 433-435
   distance, calculating, 426-429
   general references on, 650
   inclusion within polygons, 443-449
   intersections, 435-443
      line intersection, 435-443
      Manhattan intersections, 440-443
   trigonometry, 491
geometric distribution, 591, 596
geometric_expected(), 596
geometric_progression(), 492
geometric progressions, 492
geometric_variance(), 596
German stemming, 393
get_attribute(), 299
gextri(), 124
GIF images, 465
Gimp utility, 465
GL language, 466
Glazebrook, Karl, 245, 466
Glimpse indexing system, 382
gmax(), 123
gmaxi(), 124
gmini(), 124
goldbach(), 524
Goldbach conjecture, 524
Golden Ratio, 12
good-suffix heuristic, 373, 375
goodness of fit, 624
government controls (cryptography), 527, 543, 559
grade(), 607
gradients, computing, 629-631
grading test results, 607
Graham's scan algorithm, 452-456
grammars, 396-398
   context-free, 397-398
Graph package, 273, 351
   Graph::Base class, 290, 299
   Graph::BFS class, 310
   Graph::DFS class, 309
   Graph::Directed class, 278, 293, 299
   Graph::Kruskal class, 231, 352
   Graph::Undirected class, 278, 293, 299
   (see also graphs)
graphical application development, 467
graphics, general references on, 650
graphics modules, 464-468
graphs, 273-352
   attributes, 286, 299
   classes and connectivity, 279-281, 296, 316-326
      biconnected graphs, 320-323
      flow networks, 345-350
      minimum spanning trees, 326-332
      shortest paths, 332-342
      strongly connected graphs, 323-326
      transitive closure, 342-344
      Traveling Salesman problem, 350
   CPAN modules for, 351
   creating, 290
   deleting edges and vertices, 297-299
   density, 285, 296
   derived graphs, 281-285
      complete graph, 282
      graph transpose, 282
   displaying, 299
      packages for, 301
   edges (see vertices, graph)
   general references on, 650
   isomorphism, 275, 281
   paths and bridges, 310-312, 320
   representing in computers, 287-301
   strongly connected components, 282
   traversing, 275, 301-310
      breadth-first search, 301, 307, 310
      depth-first search, 301-304, 309, 314
      implementation, 307-310
      topological sort, 304-307, 309
   vertices (see vertices, graph)
graphviz package, 301
great circle distance, 429
great_circle_distance(), 429
greatest common divisor (see GCD)
greedy search algorithms, 195
Grossman, Etienne, 393
guessing passwords, 529-532
Gurusamy, Sarathy, 36, 117
gzip utility, 421-424, 568

H
Hall, Joseph N., 106
Halting Problem, 183
Hamiltonian cycles, 311
Hamiltonian path, 311, 350
Hamming distance, 379
   Baeza-Yates-Gonnet shift-add algorithm, 379-382
hardware
   eavesdropping, 529, 532
   identification values, 532
   patents (cryptography), 527
harmonic(), 495
harmonic_approx(), 495
harmomic series, 494
has_attribute(), 299
has_vertex(), 291
hash_set_to_bit_vector(), 208
hash values, 26
hashes, 2, 26, 72
   arrays vs., 27-29, 33
   avoiding searching with, 158
   copying lists, 35-37
   emulating sets, 205-206
      counting members, 222
      power sets, 236-239
      set differences, 220
      set relations, 224
      union and intersection, 213
   graph representation, 289-301
   hashes of hashes (hohs), 29
   hashes of lists (hols), 29, 118
   Huffman encoding, 417
   inserting and deleting elements, 55
      binary search and, 164
   lists of hashes (lohs), 29
   lists of lists (lols), 29
   lookup searching and, 174
   sorting, 117-118
   token recognition, 408
hashing algorithm, 362
Hayward, Gwilym, 161
heap(), 101
Heap::Binary module, 99
Heap::Binomial module, 99
Heap::Fibonacci module, 99
heapdown(), 95-99
heapdump() (Heap modules), 101
heapify(), 97, 136
heapify_array_down(), 96-97
heapify_array_up(), 96
heaps, 91-101
   binary heaps, 92-99
   branch and bound method, 196
   caching prime numbers, 505
   efficiency of, 92
   finding maximum/minimum, 122-125
   Heap modules, 99
   heapsort, 135-136
   Janus heaps, 99
heapup(), 95-97
Hellman, Martin, 548
Heron's formula, 429
heuristic password guessing, 531
hex() function, 482
hexadecimal numbers, 481-483
Hickey, Gerard, 565
hiding data (steganography), 555-558
Hietaniemi, Jarkko, 227, 241, 351, 387, 491
hits (string matching), 357
hohs (hashes of hashes), 29
hols (hashes of lists), 29
   reversing element order, 118
Horner's rule, 363
Howland, Gary, 568
HP program, 183
huff_decode(), 416
huff_encode(), 418
huff_hash(), 417
huff_hash_subtree(), 417
Huffman encoding, 416-421
hybrid lookup searches, 171-172
hybrid sorts, 147-150
hypergeometric(), 596
hypergeometric distribution, 596
hypergeometric_expected(), 596
hypergeometric_variance(), 596
hypotheses, judging, 609

I
IDEA (International Data Encryption Algorithm), 543
idea-ecb encryption algorithm, 543
identification values, hardware, 532
identity matrix, 261
imag(), 247
image compression, hidden messages and, 557
Image::Size module, 465
ImageMagick library, 466
images, secret messages in, 555
imaginary (complex) numbers, 485
implementations of algorithms, 6
in_degree(), 297
in-degree, vertex, 279
in site (in place) sorting, 119
inclusion within polygons, 443-449
incremental sum (Rabin-Karp), 365
independent events, 569
independent variables, 620
index(), 354, 377
indices
   array and hash elements, 26, 29
   search window, 2
individuals using cryptography, 527
infinite discrete distributions, 590-591
infinite lists, 71
infinite sets, 230
infix notation, 405
inflection, 389-393
inform(), 530
Ing-Simmons, Nick, 467
inheritance, 27
initializing hash set values, 233
initializing scalars, 4
inject(), 556
inorder vertex processing, 314
ins(), 260
insensitive sorting algorithms, 119
insertion_merge(), 129, 152
insertion sort, 128-131, 152
insertion_sort(), 129
InSPEC product, 537
int(), 473
integers, 469-480
   arithmetic, 470-471
   choosing randomly, 577, 579-581
   exponentiation, 517
   rounding to, 473
integrals, computing, 631-634
integrate(), 632
integrity of data, 533-537
interior elimination (Graham's scan), 455
Internal module, 490
International Data Encryption Algorithm (IDEA), 543
internationalization and sorting, 113-114
interpolation, 642-648
interpreters, 405-406
intersection(), 213
intersections of lines, 435-443
   line intersection, 435-443
   Manhattan intersections, 440-443
intersections of sets, 211-217
   bit vectors for, 216
   hashes for, 213
intractable problems, 183-184
inverse, matrix, 261
is_dense(), 297
is_head(), 577
is_prime(), 520-522
is_source_vertex(), 297
is_sparse(), 297
is_subset(), 225
ISO encoding, 363
isomorphism, graphs, 275, 281
iterative vs. recursive algorithms, 21

J
jacobian(), 630, 640
Jacobian matrix, 629-631, 640
Janus heaps, 99
joining binary trees, 85-86
junk messages, adding (chaffing), 558

K
k-connected graphs, 286, 320
keys, encryption, 540, 542
   converting from hex to bytes, 548
   interchanging public and private, 552
   lost or stolen, 564
keys, hashes, 26
   emulating sets, 205, 213
keys, sorting, 102
killer move strategy, 189, 202
Kim, Gene, 536
k-mismatches measure, 379
   Wu-Manber algorithm, 382-387
knuth_morris_pratt(), 372
Knuth-Morris-Pratt algorithm, 395
knuth_morris_pratt_next(), 371
Knuth-Morris-Pratt algorithm, 370-372
Kruskal's minimum spanning tree, 326-329, 352
K<:o>nigsberg, 311

L
Landis, E. M., 78
laplace(), 596
Laplace distribution, 596
laplace_expected(), 596
laplace_variance(), 596
last occurrence heuristic, 373
LCM (least common multiple), 504
lcm(), 504
LCS (longest common subsequence), 386
ldump() (double_head), 70
leaf vertices, 312
least common multiple (LCM), 504
legal issues (cryptography), 526-527
Lehman, Marc, 465
Leroy, Jean-Louis, 228
Levenshtein edit distance, 379
   Wu-Manber algorithm, 382
Lewis, Glenn M., 466
lexing, 394
   modules for, 406-411
libgd library, 465
licensing (cryptography), 527
LIFO order, 39
#line directive, 563
line_intersect(), 439
line_intersection(), 436
linear(), 636
linear combination theorem, 500
linear congruential generators, 567
linear least squares method, 622
linear search, 161
linear_solve(), 643
linear_string(), 161
lines, fitting to data, 622-624
lines, searching for multiple, 362
Lingua::EN::Inflect module, 393
Lingua::PT::Conjugate module, 393
linked lists, 47-59
   adding elements to end, 47
   circular, 60-62
   doubly-linked lists, 65-71
   inserting and deleting elements, 60
   inserting elements, 55
   searching contents, 56-59
   tracking both ends, 52-55
   traversal performance, 72
links (see edges, graph; graphs)
list iterators (Set::IntSpan), 230
lists (see arrays; hashes)
literal(), 399
loaded dice, 582-589
local statement, 36
locales and sorting, 113-114
location of variables (see references)
log-linear sorting, 133-145
   heapsort, 135-136
   mergesort, 134-135, 154
   quicksort, 18, 137-141, 154
log normal distribution, 597
logarithms, 14, 484
logbase(), 484
logbase1(), logbase2(), 15
logconvert(), 484
logging on (computers), 526
logical and (&&) operator, 240
logical exclusive or (xor) operator, 210
logical not (!) operator, 240
logical or (||) operator, 210, 240
lognormal(), 597
lognormal_expected(), 597
lognormal_variance(), 597
lohs (list of hashes), 29
lols (lists of lists), 29, 34
   searching, 168
longest common subsequence (LCS), 386
lookup_array(), 10
lookup_hash(), 10
lookup searches, 158-175
   binary search in list, 162-165
   binary search in tree, 167-171
   hybrid searches, 171-172
   linear search, 161
   proportional search, 165-167
   ransack search, 161
lookup tables, 9
lossless compression, 411
lossy compression, 411
LR decompression, 263
LR matrices, 261
Lukka, Tuomas J., 245

M
Macdonald, John, 99
magic characters (encrypted scripts), 563
mailmessage(), 560
make_fieldsort() (Sort::Fields), 106
make_move() (position), 177
make utility, 306
Mandelbrot set, 486
Manfredi, Raphael, 491
manhattan_distance(), 427
Manhattan distance, 427
manhattan_intersection(), 441
Manhattan intersections, 435, 440-443
map(), 109
Marquess, Paul, 117, 170, 423, 562
match heuristic, 373
matching strings (see regular expressions)
Math modules
   Math::BigFloat module, 477-480
   Math::BigInt module, 363, 477-480
      random BigInts, 579-581
   Math::Complex module, 485, 635
   Math::Fraction module, 480
   Math::Matrix module, 245, 641
   Math::MatrixBool module, 231
   Math::MatrixReal module, 245
      adding constants to matrices, 248
      adding matrices together, 251
      creating matrices, 246
      determinants of matrices, 262
      displaying matrices, 247
      Gaussian elimination, 263
      manipulating matrix elements, 246
      matrix dimensions, 247
      matrix inversion, 261
      matrix rotation, 258
   Math::Trig module, 429, 491
   Math::TrulyRandom module, 568
mathematical constants, 470
mathematics references, 651
matrices, 244-272
   adding and multiplying constants, 248-254
   adding together, 251-254
   combining, 260
   creating, 246
   determinants, 262
   dimensions of, 247
   displaying, 247
   eigenvalues and eigenvectors, 266-269
   extracting submatrices, 259
   Gaussian elimination, 263-265, 634
   inverting, 261
   Jacobian matrix, 629-631, 640
   manipulating individual elements, 246
   multiplying together, 256-258
      chain products, 269-272
   rotating, 258
   transposing, 254-255
maxima/minima sort, 122-125
maximum(), 122
maxwell(), 597
Maxwell distribution, 597
maxwell_expected(), 597
maxwell_variance(), 597
max(), 123
McDougall, Steven, 228
MD5 checksum algorithm, 535
MD5 module, 369, 535
mean(), 613, 618
mean, 591, 600-602
mean_median(), 602
measures, statistics, 600-608
   mean, 600-602
   median, 602-603
   mode, 603-604
   standard deviation, 604-606, 608
   standard score, 606-608
   variance, 608
median(), 142, 602
median, 602-603
median, determining, 141
median-of-three technique, 140
meet-in-the-middle attacks, 543
Melax, Stan, 466
members of sets, 203
   adding and deleting, 205
   counting, 222
   subtracting/removing, 218
members_to_numbers(), 208
Memoize module, 16, 113, 505
memory
   arrays vs. linked lists, 47
   caching, 16
   external sorting, 150
merge(), 134
mergesort, 134-135, 154
mergesort_iter(), 135
mergesort_recurse(), 134
merging binary trees, 85-86
Merkle, Ralph, 548
Message-ID, hiding messages in, 557
messages, adding chunks (chaffing), 558
metaphone algorithm, 389
metastring searching, 354
methods, 26, 31
Mielke, Mark, 388
military use of cryptography, 527
Miller-Rabin test, 520-522
minima/maxima sort, 122-125
minimax search, 185-187, 193
minimum cost spanning tree, 185
minimum spanning trees (MSTs), 326-332
   Kruskal's algorithm, 326-329, 352
   Prim's algorithm, 329-332, 335
minimum(), 122
min(), 122
mismatches and fuzzy matching, 379
mod_divide(), 514
mode(), 603
mode, 603-604
modeling data, 642-648
modular arithmetic, 511
   Chinese remainder theorem, 511, 514-517
   division, 513
   exponentiation, 519
modular inverse, 514
modulus, 511
Monty Hall problem, 590
move object (game interface), 177
MST_Kruskal(), 329
MST_Prim(), 330
MSTs (minimum spanning trees), 326-332
   Kruskal's algorithm, 326-329, 352
   Prim's algorithm, 329-332, 335
multibyte character matching, 360
multibyte character sorting, 107
multidimensional arrays, 245
multidimensional Newton's method, 640-642
multiedge, graph, 277
multigraphs, 277
multiples, 499
   LCM (least common multiple), 504
multiplication (*) operator, 257
multiplying matrices together, 256-258
   chain products, 269-272
multivalued sets, 240-242
munitions (cryptography classification), 527
mutually exclusive events, 581
mutually prime numbers, 504
my statement, 4
myaccept(), 561

N
na<:i>ve matching, 357-362
naive_sequence_matcher(), 361
naive_string_matcher(), 357
nand operator, 217
National Security Agency (NSA)
   strong encryption, controlling use, 527
natural numbers, 469
negative correlation, 620, 624
negative cycles, 334, 337
negative lookahead assertion, 356
neighbor vertices, 293, 315
networks (see graphs)
new(), 33
   double package, 68
   Graph::Base class, 290
new_from_string(), 246
Newton-Raphson iteration, 638
Newton's method, 638-640
   multidimensional, 640-642
next()
   double package, 67
   infinite lists, 71
next_move() (position), 177
NFA (nondeterministic finite automata), 396
no integer directive, 471
nodes (see graphs; vertices, graph)
noise, reducing, 648
noncommutativity (see commutativity)
nondeterministic events, 568
nondeterministic finite automata (NFA), 396
nondirectional alternative hypotheses, 612
none_of(), 569
none, probability of, 569-570
nongame dynamic searches, 193-202
   A* algorithm, 200-202
   branch and bound method, 196-200
   greedy algorithms, 195
noninfinite arithmetic, 510
nonrecursive vs. recursive algorithms, 21
nonterminals (BNF), 397
nonuniform discrete distributions, 582-589
nonvalid data, discarding (winnowing), 558
nor operator, 217
normal (Gaussian) distribution, 566, 591, 595
normalization, 582
normalize(), 601
not (!) operator, 240
NP-complete, NP-hard problems, 184
NT password conventions, 529
null hypothesis, 609
null set, 213
null transitions, 396
numbers
   dates and times, 489
   factorials of fractional numbers, 15
   floating-point, 14, 472
   number systems, 469-498
      bit vectors, 484
      bits and bases, 481-484
      complex numbers, 485
      extreme size/precision, 477-480, 574
      fractions, 480
      integers and reals, 469-480
      polar coordinates, 488
      precision, 472
      Roman numerals, 491
      rounding, 473-477
      significant series, 492-498
      trigonometry, 491
   number theory, 499-525
      Chinese remainder theorem, 511, 514-517
      cryptography and, 526
   GCD (see GCD)
      integer exponentiation, 517
      modular arithmetic, 511, 513, 519
      noninfinite arithmetic, 510
      unsolved number problems, 522-525
   numeric order, 105
   numerical analysis, 626-648
      derivatives and integrals, 627-634
      interpolation, extrapolation, curve fitting, 642-648
      solving equations, 634-642
   prime numbers, 504-522
      caching, 505-510
      El Gamal key, generating, 552
      factoring, 549
      Goldbach conjecture, 524
      Miller-Rabin test, 520-522
   probability (see probability)
   random (see random numbers)
   real numbers, 14
   references on, 651
   statistics (see statistics)

O
O(N) notation, 17-20
Obfuscated Perl Contest (hiding messages), 557
objects, 26
   Address objects (example), 31
occurrence heuristic, 373
oct() function, 482
octal numbers, 481-483
odd median, 602
odd perfect numbers, 523
OFB (Output Feedback), 543
offset (pattern shift), 357
old_shellwords(), 409
one-indexing (matrices), 245
one_of(), 571
one-time pad, 538-540, 543
one_time_pad(), 540
ones(), 253
online access to programs in this book, xv
OpenGL module, 466
opening book strategy, 192
operating systems and data access, 527
operator precedence (priority), 397
optimization (see efficiency of algorithms)
optimizing parse trees, 396
or operators
   | (binary or), 216
   || (logical or), 210, 240
   XOR (binary exclusive), 220-221
   xor (exclusive logical or), 210
order of growth values, 17-20
ordering (see sorting)
ord(), 363
Orwant, Jon, 616
Ousterhout, John, 467
out_degree(), 297
out-degree, vertex, 279
Output Feedback (OFB), 543
Ozawa, Sakuro, 491

P
packet sniffing, 529
pack(), 481, 484, 548
padding fields, 535
pairwise mutually prime, 512
Palm, Hartmut, 467
paper template example (steganography), 555
parabolas, fitting to points, 644
parallel make, 306
parameter estimation, 614
parent lists, 288
parent vertices, 315
parse(), 404
parse, 400
Parse::Lex module, 406
Parse::RecDescent module, 407
parse trees, 396
parser generators, 398
parsing strings, 394-411
   finite automata, 395-396
   general references on, 650
   grammars, 396-398
      context-free, 397-398
   interpreters and compilers, 405-406
   lexing and parsing modules, 406-411
   top-down vs. bottom-up, 398-404
partial ordering (graphs), 304
partition(), 137-140
partitioning, 137-140
partitionMo3(), 148-150
pascal(), 597
Pascal distribution, 597
pascal_expected(), 597
pascal_variance(), 597
passive data access (reading data), 526
passwd program, 531
passwords, 528-533
   guessing, 529-532
   problems with use, 529-533
   testing program, 531
patents, cryptography, 527
path compression, 327
paths, graph, 310-312
   (see also shortest paths)
pattern matching, 394
   algorithms for, 357-387
      Baeza-Yates-Gonnet shift-OR, 377-379
      Boyer-Moore algorithm, 373-375
      Boyer-Moore-Horspool algorithm, 375
      Knuth-Morris-Pratt algorithm, 370-372, 395
      na<:i>ve matching, 357-362
   &nbs p;  Rabin-Karp algorithm, 362-369
      sequence matching, 360-362
      shift-op algorithms, 376-377
      summary of, 386-387
   approximate (fuzzy) matching, 353, 379
      Baeza-Yates-Gonnet shift-add algorithm, 379-382
      Baeza-Yates-Gonnet shift-OR algorithm, 377
      longest common subsequence (LCS), 386
      regular expressions (String::Approx), 387
      Wu-Manber k-differences algorithm, 382-387
   phonetic algorithms, 388-389
      metaphone algorithm (Text::Metaphone), 389
      soundex algorithm (Text::Soundex), 388-389
   Rabin-Karp algorithm
      binary mask, 368
   regular expressions (see regular expressions)
   stemming and inflection, 389-393
      Lingua::EN::Inflect module, 393
      Lingua::PT::Conjugate module, 393
      Text::German module, 393
      Text::Stem module, 392
   study(), 357
   (see also parsing strings)
pattern shift, 357
pdl(), 246
PDL module, 245
   adding matrices together, 252
   combining matrices, 260
   creating matrices, 246
   displaying matrices, 247
   eigenvalues and eigenvectors, 266-269
   extracting submatrices, 259
   manipulating matrix elements, 246
   matrix chain products, 269
   matrix dimensions, 247
   matrix multiplication, 258
   PDL::IO::FastRaw module, 250
   transposing matrices, 254
Peirce, Charles Sanders, 217
Peirce's relation, 217
percentile(), 122, 142
percentiles, 603
perfect numbers, 523
performance
   algorithms (see efficiency of algorithms)
   string matching
      na<:i>ve matching, 361
      Rabin-Karp algorithm, 369
      tips for regular expressions, 355
perimeter, polygon, 433
Perl
   encrypted code, 562-564
   implementing combinations, 573
   obtaining, xiv
   program passwords, 528
perldl shell, 266
Perl-Gimp module, 465
PerlMagick module, 466
Perl/Tk, 467
permutation(), 572
permutation vectors, 459
permutations, 571-573
Pfeifer, Ulrich, 393
PGP module, 565
PGP (Pretty Good Privacy), 543, 565
PGPLOT module, 466
Phillipps, Ian, 392
phonetic algorithms, 388-389
   metaphone algorithm (Text::Metaphone), 389
   soundex algorithm (Text::Soundex), 388-389
pi (<*p>), 470
pigeonhole principle, 514
pivot, 137-140
pkzip utility, 421-424
plane(), 642
pluralizing English words, 393
Point class (example), 26
point_in_quadrangle(), 448
point_in_triangle(), 446
points
   closest pair of, 457-464
   directives at, computing, 628-629
   fitting polynomials to, 643
   inclusion, 443-449
   intersections, 435-443
      line intersection, 435-443
      Manhattan intersections, 440-443
poisson(), 597
Poisson distribution, 597
poisson_expected(), 597
poisson_variance(), 597
poker_disp_many(), 587
Poker hand distributions, 585-589
polar coordinates, 488
Pollard-Rho algorithm, 522
poly_fit(), 643
polygon_area(), 432
polygon_perimeter(), 433
polygons
   area, 430-432
   determining inclusion, 443-449
   perimeter, 433
polynomials
   approximating roots, 638-640
   fitting to points, 643
   solving for roots, 634-642
pop operator, 38, 40
population variance estimation, 614
Portuguese verb conjugation, 393
position object (game interface), 176
positive correlation, 620, 624
positive lookahead assertion, 356
POSIX module, 473-474
postorder vertex processing, 314
pow(), 479
power sets, 235-239
powerset_iterate(), 236
powerset_recurse(), 237
precedence, operator, 397
precision (numeric), 472
   arbitrary, 478
   factorials, 574
   Taylor series, 638
predecessor vertices, 293, 315
prefix function (Knuth-Morris-Pratt), 370-371
prefix notation, 405
preorder vertex processing, 314
prepare_moves() (position), 177
prepend(), 65
   double_head package, 69
   double package, 67
Pretty Good Privacy (PGP), 565
prev() (double package), 67
primary keys, 103
prime(), 509
prime_decode(), 509
prime_encode(), 509
prime numbers, 504-522
   caching, 505-510
   El Gamal key, generating, 552
   factoring, 549
   Goldbach conjecture, 524
   Miller-Rabin test, 520-522
primes(), 505-510, 524
Prim's minimum spanning tree, 329-332
printf() function, 475-477
printkey(), 550
print() (displaying matrices), 247
print() (parsing), 402
priority, operator, 397
private key encryption, 548
   public key vs., 554
   verifying sender with, 552
probability, 566-598, 610
   of at least one, 571
   birthday conundrum, 570
   conditional probability, 589-590
   cryptography and, 526
   density functions, 575
      algorithms for (list), 592-598
   distributions, 566, 574-576
      algorithms for (list), 592-598
      Bernoulli distribution, 591, 594
      binomial distribution, 585-589, 594
      continuous, 575-576, 578
      expected value, 575-576
      geometric distribution, 591, 596
      infinite discrete, 590-591
      nonuniform discrete, 582-589
      uniform, 576-581
      variance and standard deviation, 608
   events, 569-571
   general references on, 651
   mass functions, 575
      algorithms for (list), 592-598
   permutations and combinations, 571-574
   random numbers, 567-568
   (see also statistics)
productions (of tokens), 396
profiling, 38
programs
   passwords for (see passwords)
   in this book, obtaining, xv
progressions of numbers, 492-498
proper string prefixes/suffixes, 357
proportional_binary_string_search(), 166
proportional search, 165-167
protocols, communication, 564
pruning, 187-189, 192
ps utility, 568
pseudorandom numbers, 567-568
pseudorandom order, 208-209
public key encryption, 533, 548-554
   El Gamal, 552-554
   private key vs., 554
   RSA method, 549-552
   shared-secret key vs., 543
push operator, 38, 40
Pythagorean theorem, 426

Q
q quotation operator, 563
qbsort(), 148-150
qsort(), 103
quadranges, inclusion in, 448-449
quadratic(), 635
quadratic polynomials, finding roots, 635-636
quadratic sorting algorithms, 120-133
   bubble sort, 125-128, 152
   insertion sort, 128-131, 152
   maxima and minima, 122-125
   selection sort, 120-122, 151
   shellsort, 131-133, 153
quartile(), 142
quartiles, 603
queues, 38-39
   double-ended (deques), 40-42
      circular linked lists vs., 60
quickbubblesort(), 148-150
quicksort algorithm, 18, 103, 137-141, 154
   hybrid with bubble sort, 148-150
quicksort_recurse(), 139
quotewords(), 409
qx(), 410

R
Rabin-Karp algorithm, 362-369
   binary mask, 368
rabin_karp_modulo_q(), 367
rabin_karp_sum_module_q(), 366
rabin_karp_sun_with_bigint(), 363
rabin_karp_unpack_C(), 369
radix sorts, 145-147
rand(), 567, 579
   uniform probability distributions, 577
rand_dist_perfect(), 583
rand_dist_weighted(), 584
randarray(), 579
randbigint(), 580
randfloat(), 578
randint(), 577
random bit strings (encryption), 538
random numbers, 566-568, 576
   cryptography and, 526
   El Gamal key, generating, 552
   generating prime numbers, 549
   generator seed, 567-568
   improving randomness, 568
   (see also probability distributions)
random values (prepending to passwords), 532
random variables, 574
randomized running time, 140
randomizing the pivot choice, 140
rand() function, 540
range, searching for, 164
range_check_tree(), 442
ransack search, 161
rate of change, 628
Ray, Randy J., 465
rayleigh(), 598
Rayleigh distribution, 598
rayleigh_expected(), 598
rayleigh_variance(), 598
RC2, RC4, RC5 algorithms, 543
readability of regular expressions, 355
reading data (passive access)
   transforming data (active access), 526
real numbers, 14, 469-480
records, 102
recurrent themes in algorithms, 20-23
recursion, 20
   on binary trees, 81
   closest pair of points, 457-464
   depth-first search, 301-304
      graph traversal, 309
   integer exponentiation, 517
   mergesort, 134
   power sets, generating, 236
   quicksort, 139
   top-down parsing, 399
red-black trees, 79
reduce-reduce conflicts, 404
reducing stacks, 404
redundancy, cryptography and, 526
references, 4
   counting, 62-65
   linked lists, 47-59
      circular, 60-62
      tracking both ends, 52-55
reformulating the problem, 22
regression line, 622
regular expressions, 354-357
   anchors, 355
   approximate matching (String::Approx), 387
   character classes, 356
   parsing strings, 394-411
      finite automata, 395-396
      grammars, 396-398
      interpreters and compilers, 405-406
      lexing and parsing modules, 406-411
      top-down vs. bottom-up, 398-404
   positive/negative lookahead assertions, 356
   repetition quantifiers, 356
   tips and tricks, 355
rejecting input, 395-396
relative running time, 141
relative weights, 576
relatively prime numbers, 504
relax(), 335
relaxation, 334
remainder(), 500
remainders, 499
remembered values (random number seeds), 567
remove() (double package), 68
removing (see deleting)
rendering graphs (see graphs, displaying)
Renderman module, 466
reordering (see sorting)
repetition quantifiers, 356
residual capacity, 345
resources (see efficiency of algorithms)
   guarding vs. locking, 526
reverse engineering, 564
reverse order, 106
   hash elements, 118
   linked list elements, 52-55, 59
Richardson extrapolation, 632
Riemann Zeta function, 496
rindex(), 354
Rivest, Ron, 543, 558
RLE (run-length encoding), 228, 412-415
roll_dice(), 577
rolling dice, 576-581
Roman module, 491
Roman numerals, 491
Romberg integration, 631
root(), 638
root accounts, unauthorized access, 533
roots of functions
   approximating, 638-640
   computing, 634-642
rot13(), 541
rot13 encryption, 540
rotating binary trees, 87
rotating matrices, 258
Roth, Dave, 529
round(), 474
rounding numbers, 473-477
RSA Data Security, Inc., 535
RSA public key encryption, 549-552
run-length encoding (RLE), 228, 412-415
rvals(), 253

S
s/// substitution operator, 357, 399
saddle(), 642
salt (passwords), 532
satellite data, 103
scalar multiplication, 256
scalars, 2, 25
   matching with study(), 357
scaling matrices, 257
Schertler, Roderick, 410
Schneier, Bruce, 520, 542-543
Schwartz, Randal, 109
Schwartzian Transform, 109-113
   efficiency, 115
Schwern, Michael G., 389
scripts, encrypting, 562
Search::Dict module, 389
searching, 157-202
   avoiding with hashes, 158
   binary trees, 75-78, 81
   breadth-first search, 301, 307, 310
   depth-first search, 301-304
      graph traversal, 309, 314
   efficiency, 157, 172-175
   external searches, 174
   generative searching, 158, 175-202
      exhaustive search, 180-185
      game interface for, 176-180
      killer move strategy, 189, 202
      minimax search, 185-187, 193
      opening book strategy, 192
      pruning, 187-189, 192
      symmetry, 192
      transpose tables, 190-192
   linked list contents, 56
   for list maxima/minima, 122-125
   lookup searches, 158-175
      binary search in list, 2-5, 162-165, 389
      binary search in tree, 167-171
      hybrid searches, 171-172
      linear search, 161
      ransack search, 161
   nongame dynamic (fixed-goal), 193-202
      A* algorithm, 200-202
      branch and bound method, 196-200
      greedy algorithms, 195
   proportional search, 165-167
   string matching (see pattern matching; regular expressions)
sec(), 259-260
secondary keys, 103
second-order polynomials, 635-636
secret messages, 526, 555
security (see cryptography)
seed for random number generation, 567-568
seek(), 8
selection sort, 120-122, 151
selection(), 142-145
self-inverse values (XOR), 538
self-looping vertices, 280
self-loops, 277, 313
semantics, 394
sender, authenticating, 534, 537, 552
sensitivity of sorting algorithms, 119
sequence matching, 360-362
series of numbers, 492-498
session key (encryption), 554
set_attributes(), 299
set_chinese(), 514
set inverse, 212
set product/minimum (see intersections of sets)
set sum/maximum (see unions of sets)
sets, 203-243
   bit vectors for, 206-209
      set differences, 221
      set relations, 225-227
      unions and intersections, 216
   comparing, 223-227
   complement sets, 212
   counting members, 222
   CPAN modules for, 227-232
      Bit::Vector module, 227, 230
      Set::Bag module, 241
      Set::IntegerFast module, 231
      Set::IntRange module, 227, 232
      Set::IntSpan module, 227-228, 242
      Set::Object module, 227-228
      Set::Scalar module, 227
   data structures for emulating, 203
   dense vs. sparse, 229
   differences, 217-222
   fuzzy sets, 241
   graph vertices, 326
   hashes for, 205-206
      set differences, 220
   infinite sets, 230
   multivalued sets, 240-242
   null (empty) set, 213
   of sets, 233-239
      power sets, 235-239
   unions and intersections, 209-217
   universal sets, 212
   Venn diagrams, 204
sets of lines, searching for, 362
shared-secret encryption, 540-548
   Caesar cipher, 540
   differential analysis algorithm, 543
   idea-ecb algorithm, 543
   one-time pads vs., 543
   public key encryption vs., 543
Sheffer, Henry, 217
Sheffer's relation, 217
Shell, Donald, 131
shell_quote(), 410
shellsort, 131-133, 153
shellwords(), 409
shift operator, 38, 40
shift_ADD(), 380
shift-add algorithm, 379-382
shift-op algorithms, 376-377
   shift-OR exact matching, 377-379
shift-OR exact matching, 377-379
shift_OR_exact(), 378
shift-reduce conflicts, 404
shift-reduce idiom, 404
Shorter, Kyle, 466
shortest paths, 332-342
   all-pairs (APSPs), 333, 339-342
   single-source (SSSPs), 333-338
shuffling cards, 588
sieve of Eratosthenes, 504
sign_significance(), 611
sign test, 610-612
signatures, 537
   El Gamal public key encryption, 552
significance tests, 599, 608-620
   ANOVA and F-ratio, 617-620
   chi-square test, 616-617
   sign test, 610-612
   t-test, 614-616
   z-test, 612-614
significant series, 492-498
silencing warnings, 135
single-source shortest paths (SSSPs), 333-338
sink vertex (flow network), 279, 345
size
   arrays, 37
   call stacks, quicksort, 140
   distance, calculating, 426-429
   encryption block size, 547
   matrix dimensions, 247
SKEY software, 533
Smarties candy distribution, 582
smax(), 123
smaxi(), 124
smin(), 122
smini(), 124
smoothing data, 648
social engineering, 529
software eavesdropping, 529
software patents (cryptography), 527
Solitaire algorithm, 542
solve(), 640
solving equations, 634-642
   approximating roots, 638-640
   multiple nonlinear equations, 640-642
   quadratics and cubics, 635-638
some_of(), 571
sort(), xii, 103, 155
   sets, 224
sorting, 102-156
   arbitrary bi-level lexicography, 114
   ASCII order, 104
   binary heap elements, 91
   counting sort, 147
   dictionary order, 107
   efficiency (see efficiency of algorithms, sorting)
   external sorting, 150
   hashes, 117-118
   hybrid sorts, 147-150
   internationalization and, 113-114
   linked list in reverse, 52-55, 59
   log-linear algorithms, 133-145
      heapsort, 135-136
      mergesort, 134-135, 154
      quicksort, 18, 137-141, 148-150, 154
   members of sets, 203
   numeric order, 105
   permutations, 571-573
   quadratic algorithms, 120-133
      bubble sort, 125-128, 148-150, 152
      insertion sort, 128-131, 152
      maxima and minima, 122-125
      selection sort, 120-122, 151
      shellsort, 131-133, 153
   queue order (FIFO), 38
   radix sorts, 145-147
   in reverse (see reverse order)
   Schwartzian Transform, 109-113
   Sort::ArbBiLex module, 114
   Sort::Fields module, 106
   Sort::Versions module, 106
   stability and sensitivity, 119
   stack order (LIFO), 39
   topological sort, 304-307, 309
sos_as_string(), 234
soundex algorithm, 388-389
source code, encrypted, 562-564
source vertex (flow network), 279, 345
source_vertices(), 297
space (see disk space)
space characters, hiding messages with, 557
space in regular expressions, 355
spaceship (<=>) operator, 105
Spafford, Eugene, 536
sparse graphs, 286
sparse sets, 229
speaking secret messages, 555
speed (see efficiency of algorithms)
sphere(), 642
spheres, volume of, 15
spherical distance, 429
splice operator, 42-45
spline coefficients, 645
spline_evaluate(), 645
spline_generate(), 645
splines, 644-647
spoilers (messages), 542
sprintf() function, 475-477
square_groups(), 619
square_sum(), 618
srand(), 567
SSH software, 533
SSL::Cipher::new(), 543
SSLeay module, 478, 535, 543
   encrypting with, 543-548
   generating prime numbers, 549
   idea-ecb algorithm, 543
   SSLeay::BN, 479, 521
SSSP_Dijkstra(), 335
SSSPs (single-source shortest paths), 333-338
stability of sorting algorithms, 119
stacks, 39, 140
   shift-reduce idiom, 404
standard deviation, 604-606, 608
standard_deviation(), 608
standard_deviation_data(), 605
standard score, 606-608
state machine, 307
statistics, 599-625
   correlation, 620-625
      correlation coefficient, 622
      covariance, 621-622
      fitting lines to data, 622-624
   general references on, 651
   measures, 600-608
      mean, 600-602
      median, 602-603
      mode, 603-604
      standard deviation, 604-606, 608
      standard score, 606-608
      variance, 608
   population variance estimation, 614
   significance tests, 608-620
      ANOVA and F-ratio, 617-620
      chi-square test, 616-617
      sign test, 610-612
      t-test, 614-616
      z-test, 612-614
Statistics::ChiSquare module, 616
stdinpixel(), 557
stdoutpixel(), 557
steganography, 555-558
Stein, Lincoln D., 465
stemming, 389-393
   Lingua::EN::Inflect module, 393
   Lingua::PT::Conjugate module, 393
   Text::German module, 393
   Text::Stem module, 392
straight radix sort, 145
street addresses, data structures for, 27, 31
string(), 399-400
String::Approx module, 387
String::ShellQuote module, 410
stringification, 299
strings
   comparing, 106
   compression, 411-424
      compress, gzip, pkzip, 421-424
      Huffman encoding, 416-421
      run-length encoding (RLE), 412-415
   converting data into, 299
   general references on, 650
   matching algorithms, 353-424
      approximate (fuzzy) matching, 353, 377, 379, 387
      Baeza-Yates-Gonnet shift-OR algorithm, 377-379
      Boyer-Moore algorithm, 373-375
      Boyer-Moore-Horspool algorithm, 375
      exact matching, 354
      Knuth-Morris-Pratt algorithm, 370-372, 395
      na<:i>ve matching, 357-362
      phonetic algorithms, 388-389
      Rabin-Karp algorithm, 362-369
      regular expressions, 354-357
      sequence matching, 360-362
      sets/alphabets of lines, 362
      shift-op algorithms, 376-377
      stemming and inflection, 389-393
      summary of, 386-387
   numbers represented as, 484
   parsing, 394-411
      finite automata, 395-396
      grammars, 396-398
      interpreters and compilers, 405-406
      lexing and parsing modules, 406-411
      top-down vs. bottom-up, 398-404
   searching for (see searching)
   sorting (see sorting)
   string prefixes, 357
   string suffixes, 357
strongly connected components, 282
strongly_connected_components(), 325
strongly_connected_graph(), 325
strongly connected graphs/components, 323-326
structures (see data structures)
study(), 357
sub statement, 3
submatrices, extracting, 259
subroutines (see algorithms)
subscripts, array and hash elements, 26, 29
subsets, 223
   of sets, 233-239
      power sets, 235-239
subtracting from sets, 218
successor vertices, 293, 315
sum(), 534, 619
summary scores, 610
supersets, 223
   of sets, 233-239
      power sets, 235-239
swing_left(), swing_right(), 88
symbolic computation, 627
symmetric set difference, 219
symmetry in searching, 192
symmetry of set differences, 218-220
syntax trees, 315

T
t_significance(), 624
tabs, hiding messages in, 557
tail pointer (linked lists), 52
tail recursion, 401
Tavares, Stafford, 543
Taylor series, 638
Tempest (eavesdropping methods), 529
temporary variables, 14
term(), 400
terminals (BNF), 397
ternary logic, 240
tertiary keys, 103
text (see strings)
Text::Abbrev module, 408
Text::Balanced, 410
Text::DelimMatch module, 409
Text::German module, 393
Text::Metaphone module, 389
Text::ParseWords module, 409
Text::Soundex module, 388-389
Text::Stem module, 392
three-dimensional modeling, 466
tic-tac-toe game interface, 177-180
   alpha-beta pruning, 189
   exhaustive analysis, 180
   minimax analysis, 187
   transpose tables, 190-191
tie operator, 117
time(), 568
Time::CTime module, 490
Time::Date module, 490
Time::DaysInMonth module, 490
Time::JulianDay module, 490
time measurement (uniform distributions), 578
Time::ParseDate module, 490
time resources, 9-11
Time::Timezone module, 490
times and dates, 489
timestamp, hiding messages in, 557
timethese() (Benchmark), 12, 115
tips and tricks
   Benchmark module, 13
   lookup searches, 172-175
   regular expressions, 355
Tk module, 486
to_chinese(), 514
tokens, 394, 396
   recognizing with hashes, 408
top-down parsing, 398-404
top-down programming strategy, 22
topological sort, 304-307, 309
total degree, 280
total sum (Rabin-Karp), 365
trailing spaces, hiding messages with, 557
transformation matrices, 257
transitive closure, 342-344
TransitiveClosure_Floyd_Warshall(), 344
translation, 405
transpose, graph, 282
transpose tables, 190-192
transposing matrices, 254-255
trapezoid rule, 631
Traveling Salesman problem, 184, 350
traversal order, 406
traversal performance, 72
traverse() (binary trees), 81
traversing graphs, 275, 301-310
   breadth-first search, 301, 307, 310
   depth-first search, 301-304
      graph traversal, 309, 314
   implementation, 307-310
   topological sort, 304-307, 309
tree edges, 316
trees, 312
triangle_area_heron(), 430
triangles
   area, 429
   inclusion within, 446
triconnectivity, graphs, 320
trigonometry, 491
Triple DES, 543
Tripwire program, 536
Trojan horse, 529
true hits (string matching), 357
TSP (Traveling Salesman problem), 184, 350
t-test, 614-616
ttt_analyze(), 180
ttt_analyze_table(), 190
ttt_exhaustive(), 180
ttt_exhaustive_table(), 190
two-dimensional image modules, 464
2-3 trees, 79
t(), 615

U
unconnected graph vertices, 279-281
undecidable problems, 183
undef keyword, 30
underscores and numeric comparison, 107
undirected graphs and edges, 277-279, 291-293, 317
Unicode standard, 107, 651
uniform(), 598
uniform_expected(), 598
uniform probability distributions, 576-581, 598
   continuous, 578
uniform_variance(), 598
union(), 228
unions of sets, 209-217
   bit vectors for, 216
   hashes for, 213
   universal sets, 212
union-tree forests, 326
uniqueness of set members, 203
universal sets, 212
Unix password conventions, 529
unpack(), 363, 368, 481, 484
unshift operator, 38, 40
unsolved number problems, 522-525
update() (SSLeay), 536
use constant statement, 48
use integer statement, 14, 470
use locale statement, 106
"Useless use of ... in void context" warning, 13
usernames and matching passwords, 528
/usr/dict/words file, 6-8

V
validate() (Heap modules), 101
validating data (checksums), 534-537
validation keys (winnowing and chaffing), 558
variables
   anonymous, 5
   dependent and independent, 620
   dynamic, 36
   locations of (see references)
   random variables, 574
   temporary, 14
variance, 591, 608
   ANOVA (analysis of variance), 617-620
   population, estimating, 614
variance(), 608
vec(), 206, 484
velocity(), 629
Venn diagrams, 204
Venn, John, 204
Verdret, Philippe, 406
verifying passwords (Perl program), 528
versioncmp() (Sort::Versions), 107
versions() (Sort::Versions), 107
versions of Perl, xiv
vertex_set(), 328
vertices(), 291
vertices, graph, 276-281
   adding and checking, 290
   attributes, 299
   degree and classes, 279-281
   deleting, 297-299
   graph density, 285, 296
   leaves and branches, 312
   parents, children, ancestors, descendants, 315
   predecessor, successor, neighbor, 315
   sink and source vertices, 345
   vertex sets, 326
   weight/cost, 329
   (see also graphs)
very big/small numbers, 477-480, 574
visual eavesdropping, 529
volume_novar(), 15
volume of n-dimensional sphere, 15
volume_var(), 15
VRML (Virtual Reality Markup Language), 467

W
\w metacharacter, 113
-w switch (perl), 135
walking edges (see traversing graphs)
Walsh, Norman, 409
warnings, silencing, 135
watermarks, 558
web files, downloading, 534
weekday(), 490
weight balancing, 327
weight, graph edges, 286, 334
weight, graph vertices, 329
weight_to_dist(), 582
weighted_average(), 601
weighted mean, 601
weights, normalizing, 582
while loops, 4
whitespace
   hiding messages with, 557
   in regular expressions, 355
widget toolkits, 467
Wiener, Michael, 543
Win32::AdminMisc module, 529
window, search, 2
windowing toolkits, 467
Windows NT password conventions, 529
winnowing (encryption), 558-562
words, defined, 394
words file, 6-8
Wu-Manber k-differences algorithm, 382-387

X
x operator (PDL module), 258
/x regular expression modifier, 355
XOR (binary exclusive or) operator, 220-221, 538
xor (exclusive logical or) operator, 210
XOR (exclusive-or), 540
XRSA product, 537
x-trees, 440-443

Y
Y2K compliance, 490
Young, Eric, 478, 535, 543

Z[ Top ]
z_significance_one_sided(), 613
zero-indexing (matrices), 245
zeroes(), 253
zeta_iterative(), 497
zlib library, 423
z-test, 612-614 END

Read More Show Less

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

About This Book

This book is written for two kinds of people: those who want cut and paste solutions and those who want to hone their programming skills. You'11 see how we solve some of the classic problems of computer science and why we solved them the way we did.

Theory or Practice?

Like the wolf featured on the cover, this book is sometimes fierce and sometimes playful. The fierce part is the computer science: we'll often talk like computer scientists talk and discuss problems that matter little to the practical Perl programmer. Other times, we'll playfully explain the problem and simply tell you about ready-made solutions you can find on the Internet (almost always on CPAN).

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.

Organization of This Book

The chapters in this book can be read in isolation; they typically don't require knowledge from previous chapters. However, we do recommend that you read at least Chapter 1, Introduction, and Chapter 2, Basic Data Structures, which provide the basic material necessary for understanding the rest of the book.

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.

Conventions Used in This Book

Italic
Used for filenames, directory names, URLs, and occasional emphasis.

Constant width
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.

What You Should Know Before Reading This Book

Algorithms are typically the subject of an entire upper-level undergraduate course in computer science departments. Obviously, we cannot hope to provide all of the mathematical and programming background you'll need to get the most out of this book. We believe that the best way to teach is never to coddle, but to explain complex concepts in an entertaining fashion and thoroughly ground them in applications whenever possible. You don't need to be a computer scientist to read this book, but once you've read it you might feel justified calling yourself one.

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.

What You Should Have Before Reading This Book

This book assumes you have Perl 5.004 or better. If you don't, you can download it for free from http://www.perl.com/CPAN/src.

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.

Online Information About This Book

All of the programs in this book are available online from ftp://ftp.oreilly.com/, in the directory /pub/examples/perl/algorithms/examples.tar.gz. If we learn of any errors in this book, you'll be able to find them at /pub/examples/perl/algorithms/errata.txt. ...
Read More Show Less

Customer Reviews

Average Rating 4
( 1 )
Rating Distribution

5 Star

(0)

4 Star

(1)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing 1 Customer Reviews
  • Anonymous

    Posted September 15, 2011

    No text was provided for this review.

Sort by: Showing 1 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)