Errata

"We define next[$j]...such that the suffix of length $k-1 is still a proper suffix of the pattern." Should the second "suffix" be "prefix"? And might be clearer if "text" were inserted before the first "suffix".

The line:

(Perl Data Language) module, a huge package...

should be

PDL (Perl Data Language) module, a huge package...

20 min. should be 8 min.

actually this is the error of the errata web page:

Change -10 to 16 and 10 to 16;
change -5 to 8 and 5 to 8;

....should be:

Change -10 to -16 and 10 to 16;
change -5 to -8 and 5 to 8;

The url:

"ftp://ftp.media.mit.edu/pub/orwant/wolf/ch09.tar.gz"

...on the errata web page should change to:

"http://examples.oreilly.com/9781565923980/ch09.tar.gz".

The correction of the constant from 1.5... to 6.28318530718 has not been made in the code "factorial" provided online.

Also, the recursive and approximate versions return 0 for the value of 0!, rather than 1.

(I will try to provide corrected code later.)

Original print

# ? $cmp->($val, $tree->{val})
# : $val <=> $tree->{val};

should be

? $cmp->($tree->{val},$val)
: $tree->{val} <=> $val;
if ( $relation != 0 ) {
# Not this node, go down the tree.

The statements "my $high = $index * 2 + 1" and "my $try = $index * 2" should be changed to instead read "my $high = $index *2 + 2" and "my $try = $index * 2 + 1".

When I run the sample code that I downloaded from the site, it produces the correct final output. But upon closer inspection, the intermediate state is wrong. Check the order of @$array after the first pass in heapsort(), but before the second pass (that is, after the first foreach loop containing the first call to heapify(), but before the second foreach loop containing the second call to heapify()). There are two instances where the parent is not larger than one of its children, but should be.

In case the sample code on the site has changed, the sample input it was using (when I downloaded it) was, "I have a holographic chocolate bar. No really. I'm supposed to save it because it's like art or something. But I'm really hungry and I've been checking these examples all day. I think I deserve a reward."

I'm not sure whether minor errors the intermediate state ultimately don't matter, and if the second heapify() pass will always smooth them out, or if we just got lucky with the sample input that was chosen.

"try" should be "try-1."

The comment "Compute the larger root of a quadratic polynomial" isn't correct.
The root found isn't necessarily the larger one. For instance:

f(x) = -x^2 + 2x + 3

The roots are 3 and -1, and the subroutine will return -1.

I believe the last line of the code sample contains an error. My copy of the
book has:

bruteforce => 'forloop(0, 1)' });

However, I believe that the word forloop should be changed to "bruteforce" so
the code looks like:

bruteforce => bruteforce(0, 1)' });

The comment says "node" could be undef, but it can't.

caption for "d" should be "shell = 2"

for ( my $i = length $array->[ 0 ] - 1; $i >= 0; $i-- ) {
seems should be
for ( my $i = length ($array->[ 0 ]) - 1; $i >= 0; $i-- ) {

pass is h=1, which would then be called Insertion Sort, and that is not
Shell's sort. If you don't believe me, se Table 1 P.382 of "The Art...,
Volume 3: Sorting and Searching", 2nd Ed. Also, there is a missing ')' on the
Shell's sort line of Table 4-2.

In the subroutine binary_string:

my ($low, $high) = (0, calar@$array));

should be:

my ($low, $high = (0, scalar(@$array));

30km should be 12km.

The conclusion for the branch and bound algorithm states that the best route
goes thru Wolfbane Corners. It should be Sula Junction. Also, the run chart
shows the cost of urchin -> wolfbane corners -> sula center to be 44, it
should be 46.

Best route from Urchin to Sula Center is to go through "Sula Junction", not
through "Wolfbane Corners." And, on the chart right above the paragraph, the
'Cost So Far' column of the route Urchin->Wolfbane Corners -> Sula Center
should be 56, not 44 as in the book, nor 46 which a reader pointed out on the
unconfirmed errata.

print "g = $g
";
a-b,b-c,c-d,d-e

should be:

print "g = $g
";
a-c,b-c,c-d

I also agree with another readers' comment that the ASCII representation for Figure 8-4 should be:

g = a-c,b-c,c-d

There's no edge defined between vertices a and b. The inclusion of a-b in the list of edges is incorrect.

The "" operator is not overloaded in the base class. Delete
from the word "all" to the end of the line in the first sentence
of the final paragraph. The complete first sentence of the
final paragraph should read:

We overload the "" operator in the two derived classes, Graph::Directed
and Graph::Undirected.

error in the First Edition, Aug 1999

Since there is no node 'f' in the picture,
there should be no node 'f' mentioned in the annotations.

n[ i ][ j ] =
m[ i ][ k ] ||
( m[ i ][ k ] && m[ k ][ j ] )

should be:

n[ i ][ j ] =
m[ i ][ j ] ||
( m[ i ][ k ] && m[ k ][ j ] )

I think there is a significant optimization to be had in
Graph::Base::TransitiveClosure_Floyd_Warshall.

The speedup is sufficient (hours become minutes, in my case), that it could be
construed as an error.

Consider the central loop:

# Do the O(N**3) loop.
for ( my $k = 0; $k < @V; $k++ ) {
my @nC = ( '' ) x @V; # new @C

for ( my $i = 0; $i < @V; $i++ ) {
for ( my $j = 0; $j < @V; $j++ ) {
vec( $nC[ $i ], $j, 1 ) =
vec( $C[ $i ], $j, 1 ) |
vec( $C[ $i ], $k, 1 ) & vec( $C[ $k ], $j, 1 );
}
}

@C = @nC; # Update the closure.
}

I believe that

1) The adjacency matrix C can be modified in-place, and more significantly: 2)
The the vec( $C[ $], $k, 1) test can be broken out of the innermost loop. This
can be much faster.

The modified code would look something like:

# Do the O(N**3) loop.
for ( my $k = 0; $k < @V; $k++ ) {
for ( my $i = 0; $i < @V; $i++ ) {
next unless vec( $C[ $i ], $k, 1 );
for ( my $j = 0; $j < @V; $j++ ) {
vec( $C[ $i ], $j, 1 ) |= vec( $C[ $k ], $j, 1 );
}
}
}

equivalent to Rabin-Karp. In fact, the Perl construct only sums the ascii
values of each character in the string and is thus much weaker than RK.

Should

my $m = knuth_morris_pratt_next( $P );
my ($n, $i, $j) = (length($T), 0, 0);
my @next;

be

my ($m, @next) = knuth_morris_pratt_next( $P );
my ($n, $i, $j) = (length($T), 0, 0);

The token INTEGER will not match 0. Perhaps this is an old example supplied
with the module, or perhaps it could be renamed to POSITIVE_INTEGER (or
NATURAL) to match its function.

#!/usr/bin/perl -pi.bak
s/(x10)(.)(.)/ $2 x (ord($3) || 256) /eg;
should be:
#!/usr/bin/perl -pi.bak
s/(x10)(.)(.)/ $2 x (ord($3) || 256) /seg;

The code snippet:

$a->{value} <=> $b->{value}

gives a warning (non-numeric in ncmp) because the value is sometimes a string,
not a single character. [This is online in the file ch9/huffman.]

Also, in the online example, in ch9/huffman-example, sub get_bit is defined as:

sub get_bit {
return $bit{shift @bits};
}

but this generates a "Use of unitialized value" warning when it runs off the
end of @bits. Instead, something like this is warranted:

sub get_bit {
defined( @bits ) ? return $bit{shift @bits} : undef;
}

The picture erroneously has an "a" in the left child of the root node where it
should apparently be an "f".

The if() statement lacks a check for the "equality" case, so closest_points

GD no longer works with GIF files. PNG is the new format.

print GIF $gif;

should read:

print GIF $gif->gif;

Otherwise, the file will not correctly as a GIF. It will just write as ascii
with jibberish.

your computer are ones. Other than the obvious "you need to be root to do
this", on some hardware architechtures this is a *really bad idea* that will
cause you pain. I once spent several hours pounding my head into a wall with
an hp300, where the machine would crash when trying to use its serial card,
but only if the X server had been started. I had to resort to my guru to
figure this one out, and he had to scratch his head for a minute before he
figured it out.

Turns out the hp300 maps device memory into the first 16 mb of /dev/mem, and
the serial card in question uses activate on read registers. X's magic cookie
auth generates its random number seed by checksumming /dev/mem. Reading from
/dev/mem caused the card to change state without the OS knowing about it. Oops.

In the code for the non-recursive exponential subroutine "exp_fast" there is a
block that tests whether or not the variable representing the power is odd. At
the end of this conditional block the variable ($j) is decremented, which
would cause it to become an even number. Presumably this is done so that the
division by 2 which immediately follows does not coerce $j into a
floating-point number. This would be Perl's normal behavior, however, since
the entire subroutine falls under the scope of a "use integer" pragma there is
no danger of integer-to-float conversion. Consequently, the $j-- is not needed.

$seen{$n} should be 'my'-ed in the subroutine.

smartie_weight = 0;
@smartie_order = sort { $dist->{$a} <=> $dist->{$b} } keys %smartie_weights;
for (@smartie_order) { $smartie_weight += $smartie_weight{$_} }

As it is right now, @smartie_order would contain nothing since $dist is a part
of the subroutine rand_dist_weighted.

It should read:

@smartie_order = sort { $smartie_weights{$a} <=> $smartie_weights{$b} } keys
%smartie_weights;

While not an error, the linear search in this routine can be made a tad faster by
sorting the large weights first:

$key_order = [ sort { $dist->{$b} <=> $dist->{$a} } keys %$dist ]

Likewise for the "@smartie_order =" line at the bottom of the page.

replace with

return(0) if ((($p == 0) && ($k != 0)) || (($p == 1) && ($k != $n)));
return(1) if ((($p == 1) && ($k == $n)) || (($p == 0) && ($k == 0)));

or something equivalent but more beautiful. At present some cases

$p==1, $k!=$n gets return1 rather than 0
$p==1, $k==$n gets undefined rather than 1
$p==0, $k!=$n gets undefined rather than 0

tested on Perl 5.005_03 built for i686-linux

The authors egregiously misinterpret the probability density (mass) function
for continuous distributions. To compute probabilities from a density
function, it is necessary to integrate the function over some range, not
simply to evaluate the density at a point. As an example of the sort of
nonsense that can result from the authors' error, if we reduce the variance in
the example on page 592 to 0.1 and compute gaussian(0, 0, 0.1), we arrive at
the conclusion that 126% of leaflets will hit the target. Let r be the sum of
the radii of the target and a leaflet; the correct answer is the integral of
the Gaussian(0, 0.1) density from -r to +r.

The line:
my @array = sort @$arrayref;

Should be written:

my @array = sort { $a <=> $b } @$arrayref;

Otherwise the array is not numerically sorted and the answer is wrong.

the page is mathematically, but _NOT_ numerically equivalent to the formula on
p. 604. In fact, an understanding of the differences between these two
formulae is a common screening question for hiring scientific programmers.
Since many readers may try to implement the second formula, it would be a
service if the text provided a warning that the two methods can give different
results.

$confidence += binomial ($trials, $hits, $probability)

should read

$confidence += binomial ($trials, $_, $probability)

The formula given for computation of the z statistic is:

(mean of data - expected mean)/standard deviation.

It seems to me that it should be:

(mean of data - expected mean)/(standard deviation / sqrt (sample size)).

(The code presented in the middle of the page is right, since it uses the
good formula).

It is written that "the estimate of the standard error of the mean is the
square root of the estimate of the population variance". It seems to me that
this is false. The estimate of the standard error of the mean is the square
root of the estimate of the population variance, divided by the square root of
the sample size.

$b/abs($b) will fail if $b is 0. As a replacement, $b <=> 0 will not fail and
is about 20% faster on my machine. It might need an explanation in the prose,
however.

The code on p. 637 includes $sgn = $b/abs($b) if $b, which doesn't fail but
could also be sped up.

$coeffs[$i] = ($delta - 1) / @points;

should read

$coeffs[$i] = ($delta - 1) / $temp;

Accordingly, the example on the next page 647 should be:

Spline coefficients: 0 -8.8 11.2 0
[-1.00, 1.00]
[-0.50, 2.05]
[0.00, 2.00]
[0.50, 0.35]
[1.00, -1.00]
[1.50, -0.20]
[2.00, 2.00]
[2.50, 4.20]
[3.00, 5.00]

The error is so minor that the difference is invisible in Figure 16-3, however.

On line 2, the code reads:


my $coeffs = spline_generate @points;

It should read:

my $coeffs = spline_generate(@points);