The errata list is a list of errors and their corrections that were found after the product was released. If the error was corrected in a later version or reprint the date of the correction will be displayed in the column titled "Date Corrected".
The following errata were submitted by our customers and approved as valid errors by the author or editor.
Version |
Location |
Description |
Submitted By |
Date submitted |
Date corrected |
Printed |
Page 152
First paragraph, second sentence. |
Says "BREADTH-FIRST SEARCH stores its state in a stack" but it should be a queue.
Note from the Author or Editor: The second sentence should contain the following: "BREADTH-FIRST SEARCH stores its state in a queue, and ..."
|
Anonymous |
Oct 08, 2010 |
|
PDF |
Page 80
Figure 4-12 |
The two topmost arrays in the figure has two '16' items, but arrays below have only one '16' and a '6' instead.
Looks like one of 16's in the top two arrays is typo and should be 6.
Note that Figure 4-13 also has similar errors.
Note from the Author or Editor: In Figure 4-12, on the top-two lines, the cells "...|13|16|5|..." should be "...|13|6|5|..."
In Figure 4-13, on the first line, the cells "...|13|16|5|..." should be "...|13|6|5|..."
Note that the code in the ADK which creates these images has the proper values, so this was a transcription error.
|
Kazuya Sakakihara |
Sep 05, 2010 |
|
Printed |
Page 113;133
1st sentence;Step 2 |
- on page 113, the sentence "The input to Binary Search is a indexed collection A of elements". This should read "The input to Binary Search is a sorted indexed collection A of elements"
- in the discussion of red-black trees on page 131-133, the explanation of the example unclear or the diagram is incorrect. On page 133, the text reads"In Step 2 the colors of the nodes are updated to ensure condition 4 of red-black trees." However, condition 4 is violated fro node 17 which has one red and one black child node. Then "In Step 3 the tree is rotated to the right to ensure condition 5 of red-black trees." But the diagram shown in Step 2 doesn't seem to violate the condition that every simple path from a node to one of its descendant leaf nodes contains the same number of black nodes. [My guess is that the diagram in Step 2 is the culprit, that the node labeled 17 was meant to be colored black.]
Note from the Author or Editor: on page 113, the sentence "The input to BINARY SEARCH is an indexed collection A of elements" should read "The input to BINARY SEARCH is an ordered, indexed collection A of elements"
Figure 5-11 shows the resulting steps when inserting the key 14 into the red-black tree. You can confirm these steps using existing animations of red-black tree algorithms. One such animation can be found at http://gauss.ececs.uc.edu/RedBlack/redblack.html and this shows what happens within the fixAfterInsertion method of the algs.model.tree.BalancedTree class.
|
David Grinstein |
Jun 15, 2010 |
|
Printed |
Page 24
Example Listing 2-1 |
On line 5 of the algorithm, it should be >= not <=, otherwise the algorithm is useless and will always return 1.
Note from the Author or Editor: Line 5 should read "while (high - low >= 2)"
|
Andrew Horsman |
Mar 17, 2010 |
|
Printed |
Page 275
The first comment in the handleEventPoint method of Example 9-3 |
Missing a period at the end of the following sentence.
Find segments, if they exist, to left (and right) of ep in linestate
|
Kyungwon Chun |
Nov 28, 2009 |
|
Printed |
Page 266
the last sentence |
the two data set distributions
should be
the three data set distributions
|
Kyungwon Chun |
Nov 27, 2009 |
|
Printed |
Page 229
In the description of network flow criteria |
The mathematical representations of ?capacity constraint(0≤f(u,v)≤c(u,v))? and ?skew symmetry(f(u,v)=-f(v,u))? are conflict each other.
Note from the Author or Editor: While preparing the Japanese translation of "Algorithms in a Nutshell" we ran into the same issue. In the end, we decided to
rewrite the text associated with Skew Symmetry as follows:
Each edge (u,v) has a defined flow f(u,v). For mathematical
convenience, one can define for this edge that f(v,u) = -f(u,v).
Doing so enables network flow algorithms to add flows together
when determining the net flow from vertex u to v.
In network graphs, each edge is directed. Using Figure 8-2 as an
example (p. 228) up to 10 units can "flow" from the source vertex
s and vertex v1. In this instance 5 units are actually flowing from
s to v1. Now how do we represent this information?
We start on p. 228 by saying "Each edge (u,v) has a flow f(v,u)
that defines the number of units of the commodity that flows from
u to v. An edge also has a capacity c(u,v) that constrains the
maximum number of units that can flow over that edge."
So we try to associate values with EDGES. Thus:
edge(s,v1).flow = 5
edge(s,v1).capacity = 10
This is a bit unwieldy to write in practice, so it is conveniently
shortened to be:
f(s,v1)=5
c(s,v1)=10
but the assumption is always that there is a specific edge under
consideration. Internally within the algorithm (see structures in
Figure 8-4 on p. 233) you will see that EdgeInfo contains both
"capacity" and "flow" attributes.
For this edge from s to v1, we can conveniently state that there
are "-5" units flowing from v1 back to s.
The mistake in the text as written is that it becomes confusing to
think of f(u,v) having a negative value, especially when
considering the capacity constraint earlier. The trick is that this
is just a convention and applies only to a single edge.
In Figure 8-2 you can see that
edge(v2,v4).flow=2 meaning 2 units are flowing from v2 to v4
edge(v4,v2).flow=0 meaning 0 units are flowing from v4 to v2
However, if the network graph began having 3 units flow from
v4 to v2 (allowed by the capacity) you would see the following:
edge(v2,v4).flow=2
edge(v4,v2).flow=3
Given the "edge from v2 to v4" we can state that f(v2,v4)=2 and
f(v4,v2)=-2.
Given the "edge from v4 to v2" we can state that f(v4,v2)=3 and
f(v2,v4)=-3.
|
Kyungwon Chun |
Nov 23, 2009 |
|
Printed |
Page 219
the lower-right text in the Figure 7-21 |
'X can at least force --2 score ...'
should be
'X can at least force -2 score ...'
|
Kyungwon Chun |
Nov 05, 2009 |
|
Printed |
Page 205
title row of table 7-4 and the equations below the table |
sDFS2(n) and DFS2(n)
should be
sDFS(2n) and DFS(2n)
,respectively.
|
Kyungwon Chun |
Nov 03, 2009 |
|
Printed |
Page 201
last row, 2nd column of Table 7-3 |
Ignore blank cell.
is better to be
Ignore center cell.
Note from the Author or Editor: Let's make this instead:
"Ignore center cell and treat blank cell as zero"
Thanks to Toshiaki Kurokawa for suggesting this improvement.
|
Kyungwon Chun |
Nov 02, 2009 |
|
Printed |
Page 139
in <Storage Issues> |
On page 139 in "Algorithms in a nutshell" (George T. Heineman) is a mistake:
in <Storage Issues> ... of 256MB, creating a two-dimensional matrix new int[4096][4096 exceeds ...
int[4096][4096] => 4096*4096*4 (4 bytes for integer in java) gives total 64MB, and not 256MB and DOESN'T exceed the availabe memory!!
Note from the Author or Editor: To confirm this errata, run the following Java code
public class Main {
public static void main (String []args) {
int[][] a = new int[4096][4096];
}
}
as follows
java -Xmx64m Main
On my PC, this shows an out of memory error. However, run as
java -Xmx65m Main
and the program works without any problems.
|
Anonymous |
Oct 14, 2009 |
|
Printed |
Page 168
The first line in the block comment at Example 6-8 |
Output path as vector of vertices ...
should be
Output path as a list of vertices ...
|
Kyungwon Chun |
Sep 29, 2009 |
|
Printed |
Page 144
line 1 of depthFirstSearch(G,s) in the Figure 6-9 |
foreachv∈V do
should be
foreach v∈V do
Note from the Author or Editor: There could be some extra space between the "foreach" and "v" on line 1 of the description of DEPTH-FIRST SEARCH
|
Kyungwon Chun |
Sep 26, 2009 |
|
Printed |
Page 123
1st line |
approximately 4.6 times
should be
approximately 3.6 times
|
Kyungwon Chun |
Sep 20, 2009 |
|
Printed |
Page 135
the last reference |
Redundant quotation mark on the last reference.
"GPERF: A Perfect Hash Function Generator," Proceedings of the Second C++ Conference":
->
"GPERF: A Perfect Hash Function Generator," Proceedings of the Second C++ Conference:
|
Kyungwon Chun |
Aug 23, 2009 |
|
Printed |
Page 109
Example 5-3 and the paragraph above it. |
'SEQUENTIAL SORT' should be 'SEQUENTIAL SEARCH'.
|
Kyungwon Chun |
Aug 08, 2009 |
|
Printed |
Page 36
Table 2-6 |
The elapsed time of op1 at the input size of 100,000 on the implementation A is reduced compared to one at the input size of 1,000.
Note from the Author or Editor: The intent of this made-up example is to show how different implementations of the same data structure can lead to wildly different performance.
It would be distinctly unlikely for 100,000 operations on A to take 0.0016 ms where 1,000 operations on A required 0.008 ms.
This should have been "0.016" ms for 100,000 operations, resulting in a total of 4,100 ms for the row of A on 100,000.
The point is the same, however, showing how orders of magnitude difference can occur simply by an ill-advised selection of data structure.
|
Kyungwon Chun |
Jul 23, 2009 |
|
Printed |
Page 324
the eqn. to calculate a standard deviation |
the RHS of the eqn. should be square rooted.
Note from the Author or Editor: In the equation for standard deviation on p. 324, the entire right hand side should be within a square root (as mentioned in the immediately following text).
|
Kyungwon Chun |
Jul 19, 2009 |
|
Printed |
Page 89
7th line of Example 4-9 |
/* Find largest element of A[idx], A[left], and A[right]. *
should be
/* Find largest element of A[idx], A[left], and A[right]. */
|
Kyungwon Chun |
Jul 16, 2009 |
|
Printed |
Page 71
2nd paragraph from the bottom |
the k=8th largest element
should be
the k=8th (smallest) element
Note from the Author or Editor: There can be only one largest element (by definition!). Our use of the phrase "8th largest element" was short-hand to refer to the 8th element if all elements were arranged in order increasing from smallest to largest. In the future, we will avoid this phrase.
|
Kyungwon Chun |
Jul 14, 2009 |
|
Printed |
Page 332
Example A-8 |
The square brackets should be parentheses and helper function sub1 is not defined in Example A-7 or the code repository. Thus the largeAdd function in Example A-8 should be as follows.
(define (largeAdd probSize)
(let loop ((i probSize)
(total 0))
(if (= i 0)
total
(loop (- i 1) (+ i total)))))
Note from the Author or Editor: The Scheme interpreter we used was "MzScheme version 207, Copyright (c) 2004 PLT Scheme, Inc."
In MzScheme, the 'sub1' function is already defined (and it works as expected) and you can use square brackets (i.e. []) interchangeably with parentheses in order to enhance the visual representation of Scheme code.
|
Kyungwon Chun |
Jul 02, 2009 |
|
Printed |
Page 330
The paragraph above Example A-6 |
(used in Chapter 1)
should be
(used in Chapter 2)
|
Kyungwon Chun |
Jul 02, 2009 |
|
Printed |
Page 25
2nd paragraph |
f'(x)=x*cos(x)+sin(x)-5-sin(x)=x*cos(x)-5
should be
f'(x)=x*cos(x)+sin(x)-5+sin(x)=x*cos(x)+2*sin(x)-5
Note from the Author or Editor: Thank you! That explains why this example required 7 iterations when I felt it should have arrived at the answer much more quickly.
Once this change is made, then Table 2-2 shows how the number of accurate digits doubles with each iteration; this is the quick convergence one expects from newton's method.
<code>
0.0 , 0
-0.2 , [101111111100100]1100110011001100110011001100110011001100110011010
-[0.1893]3246315242908 , [101111111100100000111]1000000101111010000101001111100100010001110
-[0.18930275]828926596 , [1011111111001000001110110001001010100001]111100101000111100001010
-[0.1893027580583891] , [1011111111001000001110110001001010100001011100111010001000000010]
</code>
|
Kyungwon Chun |
Jun 30, 2009 |
|
PDF |
Page 15
2nd paragraph from the bottom of the "The Effect of Encoding on Performance" sidebar |
Missing 'i' in 'manipulaton' of 'using string manipulaton operations.'
|
Kyungwon Chun |
Jun 02, 2009 |
|
Printed |
Page 71
3rd paragraph from the last |
if k > p+1
The k-th element of A is the (k-p)th element of A[p+1, right].
should be changed to
if k > p+1
The k-th element of A is the (k-p-1)th element of A[p+1, right].
|
Diko Dong-il Ko |
Jun 01, 2009 |
|
Printed |
Page 1
page 137 Figure 6-1 |
The image shows examples of Graphs. There are three examples
(A) House of Tudors
(B) Airline Schedule
(C) Computer network
The book mixes up B and C in the description as it matches a picture of the United States with "Computer Network" and a LAN with "Airline Schedule"
First Edition
978-0-596-51624-6
|
Matt Kelly |
May 30, 2009 |
|
|
87
Fig 4-14 line 9 |
There is no variable i in this function. It should be idx instead of i.
Now: Swap A[i] and A[largest]
Correct: Swap A[idx] and A[largest]
;-)
Note from the Author or Editor: on page 87, in line 9 of the description of the heapify method for HEAP SORT, replace "swap A[i] and A[largest]" with "swap A[idx] and A[largest]".
|
marstein1 |
Apr 16, 2009 |
|
Printed |
Page 245
Image associated with Iteration 4 for Maximum Flow (the left column) |
There is a small typo in the final image associated with Iteration 4 of Ford-Fulkerson in computing the network flow. Specifically, there should be 200 units flowing from vertex 1 to vertex 3.
Note from the Author or Editor: There is a small typo in the final image associated with Iteration 4 of Ford-Fulkerson in computing the Maximum Flow. Specifically, there should be 200 units flowing from vertex 1 to vertex 3.
|
George T. Heineman |
Apr 01, 2009 |
|
Printed |
Page 319
Text |
Reference to chapter 11 should be chapter 10.
|
Rixs |
Feb 13, 2009 |
|
Printed |
Page 282
diagram |
Diagram of kd-tree omits labels on lines V, H.
Note from the Author or Editor: Within Figure 9-19(a) you can see little vertical and horizontal lines within the circles representing the nodes of the kd-tree; these lines designate whether a node is a vertical partition or a horizontal partition.
|
Rixs |
Feb 13, 2009 |
|
Printed |
Page 191
Text |
"dark-gray" board states referred to in diagram should be light grey.
Note from the Author or Editor: Replace "The 20 dark-gray board states in the figure are board states..." with "The 20 light-gray board states in the figure are board states..."
|
Rixs |
Feb 13, 2009 |
|
Printed |
Page 120
Last paragraph |
I assuming "upcming" was intended to read "upcoming".
|
Jon Bauman |
Feb 01, 2009 |
|