Mastering Algorithms with Perl Book

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
downlo