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
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
Mastering Algorithms with Perl: Practical Programming Through Computer Science
706
Mastering Algorithms with Perl: Practical Programming Through Computer Science
706eBook
Available on Compatible NOOK devices, the free NOOK App and in My Digital Library.
Related collections and offers
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
Product Details
| ISBN-13: | 9781449307196 |
|---|---|
| Publisher: | O'Reilly Media, Incorporated |
| Publication date: | 08/18/1999 |
| Sold by: | Barnes & Noble |
| Format: | eBook |
| Pages: | 706 |
| File size: | 5 MB |
About 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.
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
What People are Saying About This
This book was so exciting I lost sleep reading it.
Preface
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
ItalicUsed 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.