Mastering Algorithms with Perl
by Jon Orwant, Jarkko Hietaniemi & John Macdonald

This errata page lists errors outstanding in the most recent printing.  

If you have any error reports or technical questions, you can send them to
booktech@oreilly.com.  (Please specify the printing date of your copy.)

This page was updated on March 16, 2006.

Here's a key to the markup:

        [page-number]: serious technical mistake
        {page-number}: minor technical mistake
        <page-number>: important language/formatting problem
        (page-number): language change or minor formatting problem
        ?page-number?: reader question or request for clarification



Confirmed errors:



(xv) Remove the word "usually" from the first line of the second paragraph. 
                      

(xv)  3rd paragraph;
This section points readers to ftp://ftp.oreilly.com/pub/examples/perl/algorithm/
for examples AND errata.  It should point them towards the book's web page (where
there are links for examples, errata, etc), like all other O'Reilly books -
http://www.oreilly.com/catalog/maperl/


(xvi) 1st Paragraph
In the first paragraph, add Andi Karrer to the alphabetical list of reviewers; many of the mistakes below 
are ones that he found when preparing the German translation of the book.


(2) First full paragraph, line 8: change "an $" to "a $".



{12}  formula;
In the quadratic formula, the "2a" in the denominator needs to be enclosed in
parentheses.  When $a == 1, it doesn't show, but in general...

Change
  return (-$b + sqrt($b*$b - 4*$a * $c)) / 2*$a;
to
  return (-$b + sqrt($b*$b - 4*$a * $c)) / (2*$a);



(17) Fifth line from bottom: 
Change 
"algorithm takes for a" to "algorithm takes for".



[21] IN PRINT: Second code sample, second line;
"return sqrt (1.5707963267949..."

SHOULD BE:
"return sqrt (6.28318530718..."



{34} To clarify, add # in square miles after area => 130119,



(38) Eight line from the bottom;
change "thousand bytes" to "kilobytes"



(65) In the seventh to last line, change "before or after" to 
     "after or before"



(79) First line after figure: change "so it is completely" to "so they are
     completely"


{84,85,87} Move all the code snippets on these pages four spaces to the left.



{115} IN PRINT: Upper half of page, program output;
"pa svenska: Mayer
 pa svenska: Mattson"

and

"auf Deutsch: Mayer
 auf Deutsch: Mattson"

SHOULD BE:
"pa svenska: Mattson
 pa svenska: Mayer"

and

"auf Deutsch: Mattson
 auf Deutsch: Mayer"



(135) Change "halving N elements takes Theta(N) rounds" to "halving N
      elements takes Theta(log N) rounds". ("Theta" should be the 
      capital Greek letter, of course.)


{135}
Change "halving N elements takes Theta(N) rounds" to "halving N elements takes Theta(log N) rounds". 
("Theta" should be the capital Greek letter, of course.)



(155) In the figure, "oredered" should be spelled "ordered".


{156} In Table 4-2, in the "shell" line, add a right parenthesis after the superscript.




(244) Change introductory quote to:
                             
	Unfortunately, no one can be told what the Matrix is.
                                                  --Morpheus


(248) 
Add this sentence to the end of the paragraph immediately before the subhead "Adding a Constant to a Matrix", 
italicizing the first "x" in "x-axis" and the "y" in "y-axis":
The x-axis increases from left to right (as you would expect), and the y-axis increases from top to bottom 
(as you might not expect). So the pixel in the upper left corner is element (0, 0) and the pixel in the lower 
right corner is element (411, 350).


[258] Near the bottom of the page, there are two code lines beginning with $a and $b. 
Add a semicolon to the end of each of those lines.


{259}In Figure 7-11,
 the leftmost vertex of the triangle is off. It should be at (-0.7, 0.7), not (-0.7, -0.7).


(262)
Last full text paragraph: change "of one of" to "of certain of".


(270)
Third paragraph: Replace "That's called" with "This is an approximation to".


[271]
In the middle of the page, the word orders appears in a line of code. It should be parens.


{277}
Middle of page: the sentence following "This displays an ASCII representation" should be a-b,b-c,c-d.


(311)
The first sentence of the third paragraph terminates prematurely: it should end with "can be odd."


(311)  2nd paragraph;

In the first sentence, change "would passes" to "would pass"


(320) IN PRINT: "Biconnectivity" section, third paragraph, last sentence;
"...there must not be no single point of failure." 

SHOULD BE:
"...there must be no single point of failure."


(320)  4th paragraph;
In my printing (August 1999, First Edition), there's a bunch of extra whitespace in
"Removing it disconnects the graph into islands: _____ see Figure 8-42."


{359, 360}
On each of these pages, the line print naive_string_matcher( "abcdefgh", "def" ), should be changed to print naive_string_matcher( "abcdefgh", "def" ), " ",


{361}
To add the space shown in the output, add " ", to the end of the line print naive_sequence_matcher( \@a, \@b ),.


{364}
Second prose paragraph: change "This trick is the Horner's rule." to "This trick is Horner's rule."


[380]
In the shift_ADD() subroutine, replace use integer; with
my $maxbits =  32;
my $Sigma   = 256;


{390}
Halfway through the find_word() subroutine, add a semicolon to the end of my $line = <WORDS>.


[403]
There are serious problems with the top down parsing code. A fixed version is available at ftp://ftp.media.mit.edu/pub/orwant/wolf/ch09.tar.gz.


{406}
At the bottom of page (in the Parse::Lex example code) change $token->getstring to $token->text. 
(The module's method name changed.)


[417]
On this page, change: node->left to node->{left}, node->right to node->{right}, and node->value to node->{value}.
There are eight instances in all; four at the top of the page and four in the middle-bottom.


(430) Figure change: in Figure 10-3, the equation:

	A=sqrt[(s-a)(s-b)(s-c)]

Should read:

	A=sqrt[s(s-a)(s-b)(s-c)]


(433) IN PRINT: "Direction" section, first paragraph, first sentence;
"...(counterclockwise), this is useful..."

SHOULD BE:
"...(counterclockwise); this is useful..."


{428}
In the formula at the bottom of the page, change the line below the big summation sign from "k = 1" to "i = 1".



[432]
The results of the first invocation of polygon_area() should be 5. 
The second invocation should read print polygon_area( 0, 1, 1, 0, 0, 2, 3, 2, 2, 3 ), "\n";.


[436]
Immediately after sub line_intersection {, insert the line  use constant epsilon => 1e-14;, 
left-aligned with the my on the next line.



[442]  range_check_tree implementation;
The implementation of range_check_tree is buggy: $horizontal_hi should be [
$horizontal->[2] ], and the comparisons in the middle section should be done against
$vertical_x, not $horizontal.

The solution in the next page is clearly wrong, since (1, 4) is not an intersection
point in Figure 10-10, which is right. The correct answer is:

    3 1 3 2 5 4 4 4 3 4

I copy a correct implementation:

sub range_check_tree {
    my ( $tree, $horizontal, $compare ) = @_;

    my @range         = ();     # The return value.
    my $node          = $$tree;
    my $vertical_x    = $node->{val};
    my $horizontal_lo = [ $horizontal->[ 0 ] ];
    my $horizontal_hi = [ $horizontal->[ 2 ] ];

    return unless defined $$tree;

    push @range, range_check_tree( \$node->{left}, $horizontal, $compare )
        if defined $node->{left};

    push @range, $vertical_x->[ 0 ], $horizontal->[ 1 ]
         if $compare->( $horizontal_lo, $vertical_x ) <= 0 &&
            $compare->( $horizontal_hi, $vertical_x ) >= 0;

    push @range, range_check_tree( \$node->{right}, $horizontal,
                                   $compare )
        if defined $node->{right};

    return @range
}



{449}
After the last Perl statement, add another one:
print "(6, 2): ", point_in_quadrangle( 6, 2,  @quadrangle ), "\n";


(450)  1st paragraph;
The last sentence reads, "Three bounding boxes are shown in Figure 10-16,"
but there is only one bounding box, and the caption seems to concur.


{460}
In the center of the page, change C<__closest_points_recurse> to C<_closest_points_recurse>.


[465]
At the end of the program, replace print GIF $gif; with print GIF $gif->gif;.


{471}, middle of the page, 
change the nine instances of "e6" to "e3"

In the last line of that program, change " km/h" to " million meters per hour"


At the bottom of the page, change the program output to:

The speed of Pluto is 21 million meters per hour
The speed of Saturn is 34 million meters per hour
The speed of Mars is 87 million meters per hour
The speed of Uranus is 24 million meters per hour
The speed of Jupiter is 47 million meters per hour
The speed of Earth is 107 million meters per hour
The speed of Venus is 126 million meters per hour
The speed of Neptune is 17 million meters per hour
The speed of Mercury is 172 million meters per hour


[474]
Change the two lines that begin sub floor and sub ceil to:
sub floor { int( ($_[0] - int($_[0])) + 1 ) + int($_[0]) - 1 }
sub ceil  { int( ($_[0] - int($_[0])) - 1 ) + int($_[0]) + 1 }


{486-487}
The fractal program and image are correct, but the image is squashed a little bit because 
a rectangular region of the complex plane is being displayed in a square canvas. 
To unsquash the image, change these lines on page 486:
use constant RIGHT => 0.5;
use constant TOP => 1.25;
use constant BOTTOM => -1.25;


(491)
In the last line of the first prose paragraph after the Roman Numerals subhead, 
change $TEXT to $text.


(493)
In the first prose paragraph after The Fibonacci Sequence subhead, 
move "(grotesquely inbred)" to the end of the next sentence, making it 
"After the third month, five (grotesquely inbred)."


(506) Line 33 of the code;
                       $high = $mid -1
Should be:
                       $high = $mid-1;


{507} line 11;
        if ($ci < $#primes)
should be:
        if ($ci < $#heap)


{510} 4th line;
delete:
           $num     -= $div * $prime;


(522)
In the third prose paragraph of Unsolved Problems, 
change "number of solutions, of which this is the smallest:" 
to "number of solutions, of which the first one to be found was:"

Why? As Andi Karrer points out:
Noam Elkies found 2682440^4+15365639^4+18796760^4=20615673^4 in 1987 and thereby refuted Euler's conjecture, that there are no solutions for n=4. But in early 1988 Roger Frye 
showed by exhaustive search that 95800^4+217519^4+414560^4=422481^4 is the solution 
with the smallest d. See http://www.chez.com/powersum/euler88.ps.


(529)  "Hardware eavesdropping" section; 
The second sentence contains a typo.  Instead of "eavesdopper", it should read 
"eavesdropper".


{530}
Change the line that reads #!/bin/perl -nle to #!/usr/bin/perl -nl.


{536}
Change the line that reads use SSLeah; to use SSLeay;.


[541]
Change the line that reads $val = tr/a-zA-Z/n-za-mN-ZA-M/; 
to $val =~ tr/a-zA-Z/n-za-mN-ZA-M/;



(543)  last paragraph;
. . . NIST (National Institute fo Standards . . .

should be

. . . NIST (National Institute for Standards . . .


[550-551]
In the printkey() subroutine at the bottom of the page, change the line 
my ( *HANDLE, $n, $k ) = @_; 
into these two lines:
local *HANDLE = shift;
my ($n, $k)   = @_;

Remove the $ from before the HANDLE on the last line. 
On page 551, in the readkey() subroutine at the top of the page, change 
my *HANDLE = shift; 
to local *HANDLE = shift;.


{553} Third line from top: 
change "cannot encrypt with the public key instead" 
to "cannot encrypt with the private key instead".


(568) Now  reads:
	
	...the encryption in an early version of Netscape's web 
	browser was compromised because because of their bad seed.

Should read:

	...the encryption in an early version of Netscape's web 
	browser was compromised because of their bad seed.



{583} Top of page: 
change the line 
print "$k = $v\n"; 
to 
print "$key = $value\n";


{583} Bottom of page: 
change the line 
for (1..100) { print rand_dist(\%a) } 
to 
for (1..100) { print rand_dist_perfect(\%a) }.


[584] Middle of page. 
Change this loop:
    while( my( $key, $weight ) = ( each %$dist ) ) {
        return $key if ($running_weight += $weight) >= $rand;
    }

to this:
    foreach my $key (@$key_order) {
        return $key if ($running_weight += $dist->{$key}) >= $rand;
    }

Bottom of page. Change
@smartie_order = sort { $dist->{$a} <=> $dist->{$b} } keys %smartie_weights;
for (@smartie_order) { $smartie_weight += $smartie_weight{$_} }

to this:
@smartie_order = sort { $smartie_weights{$a} <=> $smartie_weights{$b} }
    keys %smartie_weights;
for (@smartie_order) { $smartie_weight += $smartie_weights{$_} }


{587} Middle of page: 
Change the line 
poker_disp_many( 
to 
display_poker_many(.


{589} Bottom of page: Immediately below "Sample output:", 
there are a list of two-character items. Insert " of " between the two characters. 
For instance, 5C should become 5 of C, and so on for the other 29 character pairs.


[602] Middle of page: 
Delete the prose paragraph beginning "You can also write" and the four lines of code after the paragraph.


{606} Bottom formula: 
change z to zi.

Middle three prose paragraphs: 
change both instances of 5.124 to 7.805. 
Change -10 to 16 and 10 to 16; 
change -5 to 8 and 5 to 8; 
change "However, we'd" to "We'd". 
Change the text between "The actual figure" to "as it well might not:" to the following:

The actual figure is 4+(2*3)+(3*4)+(4*1)+(5*2) = 36, also about the expected value. However, it is not certain that falling pennies would follow a Gaussian distribution:


{613} Middle of page: 
Remove one of the right parentheses after $expected_mean.


{616} Top of page, in the three lines after the prose sentence, 
change:
use Statistics::Table::t

($lo, $hi) = t_significance($t, $degrees, $tails);
print "The probability that your data is due to chance: \n";

to
use Statistics::Table::t;

($lo, $hi) = t_significance($t, scalar(@data) - 1, 1);
print "The probability that your data are not due to chance: \n";




(618,620)
The program is correct, but so that the (made up) data forms a significant example, change 
the data on page 618 (the four lines beginning with $designs) as follows.

In the first row, change 34 to 14.
In the third row, change the first 25 to 32, 18 to 19, 26 to 36, and the final 25 to 34.

Then at the top of page 620, change F is 2.98880804190097 to F is 8.97825767131245.




[622]  2nd paragraph;
In the correlation sub, the following line is present:

sqrt(((@$array1ref * $sum1_squared) - ($sum1 ** 2)) *
     ((@$array1ref * $sum2_squared) - ($sum2 ** 2)));

The second mention of @$array1ref should be @$array2ref.




(623) First line, 
change x-intercept to y-intercept.


{623, 624}
In Figures 15-3 and 15-4, the first number on the x-axis should be 0, not 2500.


{624}
Immediately before the first line of code, add:
use Statistics::Table::t;
Change if ($hi <= 0.05) { to:
if ($lo >= 0.95) {


{628} Second prose paragraph from bottom: 
change both occurrences of 1.2 to 1.4 
change 6000 to 7000
and change "== 7887.20, respectively." to ", which is about 11595.5.". 
(There's no monospace in the replacement text.)


{629} In the code example at the top of the page (after "Now we can call deriv()..."), 
make the following changes:
Change the two instances of 0.1 to 0.01
Change 366 to 365
Change 6.45 to 6.46
Change both occurrences of print to printf "%.2f\n",.


{631} In the line beginning @jacobian, 
replace [\&f, \&g] with [\&f, \&g, \&h]. 
In the code's output, replace 
266666668.176214 (which is what Digital Unix reports) 
with 
NaN (which is what Red Hat Linux and Solaris report).


{635} Middle of page: 
in the prose paragraph beginning "The roots will then be", change c/a to c/q.


{640} First prose paragraph (beginning "Suppose your company's revenues"): 
change the first occurrence of log($x) to 100*log($x) and change x3-log(x) to x3-100log(x). 
Change the sentence 
"When will your company run out of money?" 
to 
"When will your company start to earn money?" 

In the next full prose paragraph, change the second sentence to:

If we change our initial low guess from a 2 to a 1, it fails: root(\&cashflow, 1, 100, .001) returns
nothing at all, because the subroutine returns early if the function value at both guesses are 
positive. If it didn't, it would reach the maximum number of iterations without finding a root.


{641} Top of page: 
Remove the # in front of sub solve, and remove $error_var, from the line beginning my ($i, ....


{643}
In the third line of sub poly_fit, change:
my($i, $j, $y, @solution)
to
my($i, $j, $x, $y).



(651)
First entry of Other References: change "Gary" to "Garey".


(657)
Change "# for hash names" to "% for hash names".


(678)
Add entry for "Sarathy, Gurusamy", duplicating the index entry for "Gurusamy, Sarathy".