Mastering Algorithms with Perl

Table of Contents......Page 2
Preface......Page 8
Organization of This Book......Page 9
Conventions Used in This Book......Page 10
Acknowledgments......Page 11
What Is an Algorithm?......Page 13
A Sample Algorithm: Binary Search......Page 14
Adapting Algorithms......Page 17
Generality......Page 18
Efficiency......Page 20
Space Versus Time......Page 21
Benchmarking......Page 23
Floating- Point Numbers......Page 25
Temporary Variables......Page 26
Caching......Page 28
N) Notation......Page 29
Recursion......Page 32
Dynamic Programming......Page 33
2 Basic Data Structures......Page 34
Perl\'s Built- in Data Structures......Page 35
Build Your Own Data Structure......Page 36
A Simple Example......Page 37
Lols and Lohs and Hols and Hohs......Page 39
Objects......Page 41
Shortcuts......Page 44
Perl Arrays: Many Data Structures in One......Page 47
Queues......Page 48
Deques......Page 49
Still More Perl Arrays......Page 51
3 Advanced Data Structures......Page 55
Linked Lists......Page 56
Linked List Implementations......Page 60
Tracking Both Ends of Linked Lists......Page 61
Additional Linked List Operations......Page 64
Circular Linked Lists......Page 68
Garbage Collection in Perl......Page 71
Doubly- Linked Lists......Page 74
Infinite Lists......Page 80
Binary Trees......Page 81
Keeping Trees Balanced......Page 87
Heaps......Page 100
Binary Heaps......Page 101
The Heap Modules......Page 108
Future CPAN Modules......Page 110
An Introduction to Sorting......Page 111
Perl\'s Sort Function......Page 112
Numeric Order......Page 113
Sort:: Fields......Page 114
Dictionary Order......Page 115
Sorting Efficiency......Page 117
Sorting Hashes Is Not What You Might Think......Page 125
All Sorts of Sorts......Page 127
Quadratic Sorting Algorithms......Page 128
Log- Linear Sorting Algorithms......Page 143
Beating O ( N log N)......Page 155
Sorting Algorithms Summary......Page 161
Sorts......Page 162
Shellsort......Page 163
How Well Did We Do?......Page 164
5 Searching......Page 167
Hash Search and Other Non- Searches......Page 168
Lookup Searches......Page 169
Ransack Search......Page 170
Linear Search......Page 171
Binary Search in a List......Page 172
Proportional Search......Page 175
Bushier Trees......Page 177
Lists of Lists......Page 178
B- Trees......Page 179
Lookup Search Recommendations......Page 181
Generative Searches......Page 184
Game Interface......Page 185
Exhaustive Search......Page 189
Alternatives to Exhaustive Search in Games......Page 194
Nongame Dynamic Searches......Page 202
Venn Diagrams......Page 212
Creating Sets Using Hashes......Page 213
Creating Sets Using Bit Vectors......Page 214
Union......Page 218
Intersection......Page 219
Complement Set......Page 220
Set Union and Intersection Using Hashes......Page 221
Union and Intersection Using Bit Vectors......Page 225
Set Difference......Page 226
Set Symmetric Difference......Page 227
Set Differences Using Hashes......Page 228
Set Differences Using Bit Vectors......Page 229
Counting Set Elements......Page 230
Set Relations......Page 231
Set Relations Using Hashes......Page 232
Set Relations Using Bit Vectors......Page 234
The Set Modules of CPAN......Page 235
Set:: Scalar......Page 236
Set:: IntSpan......Page 237
Bit:: Vector......Page 238
Set:: IntRange......Page 240
Sets of Sets......Page 241
Power Sets......Page 243
Power Sets Using Hashes......Page 244
Multivalued Logic......Page 249
Bags......Page 250
Sets Summary......Page 251
7 Matrices......Page 252
Creating Matrices......Page 253
Displaying Matrices......Page 254
Adding or Multiplying Constants......Page 255
Adding a Constant to a Matrix......Page 256
Adding a Matrix to a Matrix......Page 259
Transposing a Matrix......Page 262
Multiplying Matrices......Page 264
Extracting a Submatrix......Page 267
Combining Matrices......Page 268
Inverting a Matrix......Page 269
Computing the Determinant......Page 270
Gaussian Elimination......Page 271
Computing Eigenvalues......Page 274
The Matrix Chain Product......Page 277
8 Graphs......Page 280
Vertices and Edges......Page 283
Edge Direction......Page 284
Vertex Degree and Vertex Classes......Page 286
Graph Transpose......Page 288
Complete Graph......Page 289
Complement Graph......Page 290
Density......Page 292
Graph Attributes......Page 293
Graph Representation in Computers......Page 294
Our Graph Representation......Page 296
Graph Traversal......Page 308
Depth- First Search......Page 309
Topological Sort......Page 311
Implementing Graph Traversal......Page 314
The Seven Bridges of Königsberg......Page 317
Graph Biology: Trees, Forests, DAGS, Ancestors, and Descendants......Page 319
Parents and Children......Page 321
Edge Classes......Page 323
Biconnectivity......Page 326
Strongly Connected Graphs......Page 330
Minimum Spanning Trees......Page 333
Shortest Paths......Page 339
Transitive Closure......Page 350
Flow Networks......Page 352
Traveling Salesman Problem......Page 358
CPAN Graph Modules......Page 359
9 Strings......Page 360
Regular Expressions......Page 361
String- Matching Algorithms......Page 364
Naïve Matching......Page 365
Rabin- Karp......Page 369
Knuth- Morris- Pratt......Page 377
Boyer- Moore......Page 380
Shift- Op......Page 383
Baeza- Yates- Gonnet Shift- OR Exact Matching......Page 384
Baeza- Yates- Gonnet Shift- Add......Page 386
Wu- Manber k- differences......Page 389
Longest Common Subsequences......Page 393
String:: Approx......Page 394
Text:: Soundex......Page 395
Stemming and Inflection......Page 396
Modules for Stemming and Inflection......Page 400
Parsing......Page 401
Finite Automata......Page 402
Grammars......Page 403
Parsing Up and Down......Page 405
Interpreters and Compilers......Page 412
Modules for Lexing and Parsing......Page 413
Compression......Page 418
Run- Length Encoding......Page 419
Huffman Encoding......Page 422
Compress, GNU Gzip, Pkzip......Page 427
10 Geometric Algorithms......Page 430
Euclidean Distance......Page 431
Manhattan Distance......Page 432
Maximum Distance......Page 433
Triangle......Page 434
Polygon Area......Page 435
Polygon Perimeter......Page 437
Direction......Page 438
Line Intersection......Page 440
Point in Polygon......Page 448
Point in Triangle......Page 451
Point in Quadrangle......Page 453
Bounding Box......Page 454
Convex Hull......Page 457
Closest Pair of Points......Page 461
CPAN Graphics Modules......Page 469
2- D Images......Page 470
3- D Modeling......Page 471
Widget/ GUI Toolkits......Page 472
Constants......Page 473
Pure Integer Arithmetic......Page 474
Precision......Page 475
Rounding Numbers......Page 477
Very Big, Very Small, and Very Precise Numbers......Page 481
Bits and Bases......Page 484
Bit Vectors......Page 488
Complex Numbers......Page 489
Polar Coordinates......Page 492
Dates and Times......Page 493
Trigonometry......Page 495
Significant Series......Page 496
The Fibonacci Sequence......Page 497
Harmonic Series......Page 499
The Riemann Zeta Function and Bernoulli Numbers......Page 500
12 Number Theory......Page 502
Basic Number Theory......Page 503
Greatest Common Divisor......Page 504
GCD: Linear Combination......Page 506
Least Common Multiple......Page 507
Caching: Another Example......Page 508
Noninfinite Arithmetic......Page 513
Chinese Remainder Theorem......Page 514
Modular Division......Page 516
Chinese Remainder Theorem Revisited......Page 517
Integer Exponentiation......Page 520
Modular Exponentiation......Page 521
Miller- Rabin: Prime Generation Revisited......Page 523
Is the Collatz Conjecture False?......Page 525
Is There an Odd Perfect Number?......Page 526
Is the Goldbach Conjecture False?......Page 527
13 Cryptography......Page 528
Legal Issues......Page 529
Authorizing People with Passwords......Page 530
Password Hazards......Page 531
Authorization of Data: Checksums and More......Page 535
Perfect Encryption:......Page 539
The One- Time Pad......Page 540
Shared- Secret Encryptions......Page 542
Analysis of Shared- Secret Encryption......Page 545
Encrypting with SSLeay......Page 546
RSA Public Key Encryption......Page 549
El Gamal Public Key Encryption......Page 553
Choosing between Public Key and Private Key......Page 555
Hiding Data: Steganography......Page 556
Winnowing and Chaffing......Page 559
Encrypted Perl Code......Page 563
Other Issues......Page 564
Random Numbers......Page 566
Better Randomness......Page 567
Will the Blue Jays Win, and Will the Stock Market Go Up?......Page 568
Will Neither the Blue Jays Win nor the Stock Market Go Up?......Page 569
Will the Blue Jays Win or the Stock Market Go Up?......Page 570
Permutations......Page 571
Combinations......Page 572
Expected Value......Page 574
Rolling Dice: Uniform Distributions......Page 576
Measuring Time: Uniform Continuous Distributions......Page 577
Picking Random Biglnts......Page 578
Loaded Dice and Candy Colors: Nonuniform Discrete Distributions......Page 581
Flipping a Coin: The Binomial Distribution......Page 584
The Binomial Distribution in Poker......Page 585
The Vaunted Monty Hall Problem......Page 589
Flipping Coins Over and Over: Infinite Discrete Distributions......Page 590
Many More Distributions......Page 591
The Cauchy Distribution......Page 593
The Gaussian ( Normal) Distribution......Page 594
The Laplace Distribution......Page 595
The Poisson Distribution......Page 596
15 Statistics......Page 597
The Mean......Page 598
The Median......Page 600
The Mode......Page 601
Standard Deviation......Page 602
The Standard Score......Page 604
Significance Tests......Page 606
How Sure Is Sure?......Page 607
The Sign Test......Page 608
The z- test......Page 609
The t- test......Page 611
The Chi- square Test......Page 613
ANOVA and the F- test......Page 614
Correlation......Page 617
Computing the Covariance......Page 618
Fitting a Line to Your Data......Page 619
16 Numerical Analysis......Page 622
Computing the Derivative at a Particular Point......Page 623
Computing the Jacobian......Page 625
Computing Definite Integrals......Page 627
Simple Roots: Quadratics and Cubics......Page 630
Approximating Roots......Page 633
Multiple Nonlinear Equations......Page 636
Fitting a Polynomial to a Set of Points......Page 638
Splines......Page 640
Data Smoothing......Page 643
General References for Algorithms......Page 644
String Processing and Parsing......Page 645
Other References......Page 646
B  ASCII Character Set......Page 647
Index......Page 650
Numbers......Page 651
A......Page 652
B......Page 656
C......Page 661
D......Page 667
E......Page 673
F......Page 678
G......Page 680
H......Page 684
I......Page 687
L......Page 690
M......Page 694
N......Page 699
O......Page 702
P......Page 704
Q......Page 712
R......Page 713
S......Page 718
T......Page 730
U......Page 733
V......Page 734
W......Page 736
Z......Page 737
Colophon......Page 738