Errata for Algorithms in a Nutshell

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.

Color Key: Serious Technical Mistake Minor Technical Mistake Language or formatting error Typo Question Note Update

Version Location Description Submitted By Date Submitted Date Corrected
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
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 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 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
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 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 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
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
Safari Books Online
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 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 109
Example 5-3 and the paragraph above it.

'SEQUENTIAL SORT' should be 'SEQUENTIAL SEARCH'.

Kyungwon Chun  Aug 08, 2009
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 120
Last paragraph

I assuming "upcming" was intended to read "upcoming".

Jon Bauman  Feb 01, 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 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 144
line 1 of depthFirstSearch(G,s) in the Figure 6-9

foreachv&#8712;V do should be foreach v&#8712;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 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
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 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 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 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 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 229
In the description of network flow criteria

The mathematical representations of ‘capacity constraint(0&#8804;f(u,v)&#8804;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 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 266
the last sentence

the two data set distributions should be the three data set distributions

Kyungwon Chun  Nov 27, 2009
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 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 319
Text

Reference to chapter 11 should be chapter 10.

Rixs  Feb 13, 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 330
The paragraph above Example A-6

(used in Chapter 1) should be (used in Chapter 2)

Kyungwon Chun  Jul 02, 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