Version 
Location 
Description 
Submitted By 
Date Submitted 
Date Corrected 
Printed 
Page 1
page 137 Figure 61 
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
9780596516246

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 21 
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)5sin(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 22 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 26 
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 madeup 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 illadvised selection of data structure.

Kyungwon Chun 
Jul 23, 2009 

Printed 
Page 71
3rd paragraph from the last 
if k > p+1
The kth element of A is the (kp)th element of A[p+1, right].
should be changed to
if k > p+1
The kth element of A is the (kp1)th element of A[p+1, right].

Diko Dongil 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 shorthand 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 412 
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 413 also has similar errors.
Note from the Author or Editor: In Figure 412, on the toptwo lines, the cells "...13165..." should be "...1365..."
In Figure 413, on the first line, the cells "...13165..." should be "...1365..."
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 414 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 49 
/* 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 53 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 redblack trees on page 131133, 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 redblack 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 redblack 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 511 shows the resulting steps when inserting the key 14 into the redblack tree. You can confirm these steps using existing animations of redblack 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 twodimensional 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 69 
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 DEPTHFIRST SEARCH

Kyungwon Chun 
Sep 26, 2009 

Printed 
Page 152
First paragraph, second sentence. 
Says "BREADTHFIRST 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: "BREADTHFIRST SEARCH stores its state in a queue, and ..."

Anonymous 
Oct 08, 2010 

Printed 
Page 168
The first line in the block comment at Example 68 
Output path as vector of vertices ...
should be
Output path as a list of vertices ...

Kyungwon Chun 
Sep 29, 2009 

Printed 
Page 191
Text 
"darkgray" board states referred to in diagram should be light grey.
Note from the Author or Editor: Replace "The 20 darkgray board states in the figure are board states..." with "The 20 lightgray board states in the figure are board states..."

Rixs 
Feb 13, 2009 

Printed 
Page 201
last row, 2nd column of Table 73 
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 74 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 lowerright text in the Figure 721 
'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≤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 82 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 84 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 82 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 FordFulkerson 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 FordFulkerson 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 93 
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 kdtree omits labels on lines V, H.
Note from the Author or Editor: Within Figure 919(a) you can see little vertical and horizontal lines within the circles representing the nodes of the kdtree; 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 A6 
(used in Chapter 1)
should be
(used in Chapter 2)

Kyungwon Chun 
Jul 02, 2009 

Printed 
Page 332
Example A8 
The square brackets should be parentheses and helper function sub1 is not defined in Example A7 or the code repository. Thus the largeAdd function in Example A8 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 
