Errata and Clarifications
Data Structures and Algorithms in Java
Michael T. Goodrich and Roberto Tamassia
The entries in grey are corrected and
are expected to appear in printings 6 and higher.
The entries in blue
are also corrected, but are not expected to appear until
printings 7 and higher. Contrary to what
was previously indicated on this page, the corrected entries in
grey
did not appear in printing 5.
Preface
-
Page vi (thanks to Joseph O'Rourke)
In the fourth paragraph,
replace "feshman-sophomore"
with "freshman-sophomore".
Chapter 1
- Page 13 (thanks to Thierry Lecroq, Lorin
Johnson, and P. G.)
-
In line 4 after figure 1.5, replace "superclass T
of S" with "superclass S of T".
- Figure 1.6 (thanks to Franck van Breugel)
Replace "base" by "b".
- Code Fragment 1.4 (thanks to Mikkel Nygaard)
The case i1>i2 ought to give a BadFibonacciParameterException
as well.
- Code Fragment 1.6 (thanks to Mikkel Nygaard)
The words "default" and "for" should not be in
boldface.
- Page 27 (thanks to Mikkel Nygaard)
In the second paragraph, replace "Gamma, et al.
book." with "Gamma, et al."
Chapter 2
- Page 36, Example 2.2 (thanks to Mikkel
Nygaard)
4th case uses only rules 2 and 3, 7th case uses
only rule 5, and 8th and 10th case also use rule 5..
- Page 39, Example 2.6 (thanks to Mikkel
Nygaard)
Replace "for some positive integer i" with "for
some integer i"
- Page 40, Example 2.7 (thanks to Mikkel
Nygaard)
Replace "for some positive integer i" with "for
some integer i"
- Page 40, Example 2.8 (thanks to Mikkel
Nygaard)
Replace "But, since n > 2," with "But,"
- Page 42, Code Fragment 2.3 (thanks to Jian
Huang and Thierry Lecroq)
Replace "if x <- A[i] then"
with "if x = A[i]
then"
- Page 45 and related references in pages 46 and
48 (thanks to Woody Anderson and P. G.)
- Replace "5n -1" with "5n".
- Replace "7n - 3" with "7n - 2".
- Page 49, Paragraph preceding proposition 2.16
(thanks to Mikkel Nygaard)
Replace "applying big-Oh definition directly
to simply a" with "applying the big-Oh definition directly to obtain a"
- Page 51, Paragraph preceding Example 2.20
(thanks to Tybon Wu)
In the second sentence (definition of w(n)),
replace "g(n) >= cf(n)" with "g(n)
<= cf(n)".
- Page 51, Justification of Example 2.20 (thanks
to P. G. and Tybon Wu)
Replace "n0 = 12/c + 6" with "n0
= (12 + 6)/c".
- Page 58, Exercise R-2.2 (thanks to Syam
Vasireddy and P. G.)
Replace "N" with "n0".
- Page 59, Exercise R-2.10 (thanks to Surong
and P. G.)
Replace "W(n)" with
"W(f(n))".
- Page 63, Exercise C-2.11 (thanks to Lylan
Masterman)
In the induction step, replace "F(n+2)"
with "F(n-2)".
- Page 63 Chapter Notes (thanks to P. G.)
Replace "CPU can" with "CPU to".
Chapter 3
-
Code Fragment 3.1 (thanks to Thierry Lecroq)
In the comment to method top(), replace "elemet" with "element".
- Page 71, Table 3.1 (thanks to Mikkel Nygaard)
In the caption , replace "array, is determined"
with "array, determined"
- Page 77 (thanks to Mikkel Nygaard)
In the last paragraph of Section 3.1, replace
"arithmetic expression" with "arithmetic expressions".
- Page 78 (thanks to Mikkel Nygaard)
In the first paragraph, replace "in a stack"
with "in a queue"
- Page 81 (thanks to Mikkel Nygaard)
In the caption of Figure 3.4 and in the second
to last paragraph, replace "(r <= f )" with "(r < f )".
- Page 82, Table 3.2 (thanks to Mikkel
Nygaard)
In the caption of the table, replace "in the
stack" with "in the queue".
-
Code Fragment 3.12 (thanks to Franck van
Breugel)
Replace "...elements if the stack" by "...elements of the stack".
- Page 95 (thanks to Thierry Lecroq andFranck
van Breugel)
In the fourth line of the first paragraph, replace
"Some" with "some".
- Page 101, Code Fragment 3.15 (thanks
to Theuns Smith)
Replace "until (k = i) or done"
with "until (k > i) or done".
Chapter 4
- Page 115 (thanks to Finn Smith)
In the first sentence of the second paragraph,
change "is a called a" to "is called a".
- Page 115, Example 4.1 (thanks
to Mikkel Nygaard)
Replace "rank-based insert and delete operations"
with "rank-based operations".
- Page 116 (thanks to Injong Rhee)
In the description of method insertElementAtRank,
replace "if if" with "if".
-
Code Fragment 4.2 (thanks to Fei Tan, Thierry
Lecroq, Lawrence Brown, Franck van Breugel, and Mikkel Nygaard)
-
In the first comment in method insertElemAtRank, replace "rank
size()" with "rank == size()"
-
The second and third comments in method removeElemAtRank should
be swapped.
-
It is difficult to see why method nodeAtRank(rank) works correctly
when rank==size(). For improved readability, the else part could
be replaced with
else { // scan backward from the tail
node = trailer;
for (int i=0; i < size()-rank ; i++)
node = node.getPrev();
}
In the caption, replace "checkRank" with "nodeAtRank".
Page 125, Example 4.2 (thanks to Mikkel
Nygaard)
Replace "(5,2,3,8)" with "(5,2,7,8)".
Page 126 (thanks to Kevin Lo and Mikkel
Nygaard)
In the first sentence of the first paragraph,
replace "deque" with "queue".
Page 127, Code Fragment 4.3 (thanks to Joseph Leichter and Mikkel
Nygaard)
-
The method setNext should be listed under update methods, and
not under accessor methods.
-
Replace "Accesor" with "Accessor".
Page 129, Code Fragment 4.4 (thanks to Mikkel
Nygaard)
-
Replace "old value of element" with "old element".
-
Replace "rack" with "rank".
checkRank should be a method of a ranked sequence, not a positional
one. It belongs to Code Fragment 4.2.
Page 133, Table 4.4 (thanks to J.
P. Pretti)
The running time of replaceElemAtRank
is O(n), and not O(1), in the doubly linked list implementation.
Page 136, Code Fragment 4.8 (thanks to Syam Vasireddy and Mikkel
Nygaard)
-
In method bubbleSort1, replace "positionAtRank" with
"atRank". Also, replace "j=0" with "j=1" and use "j-1"
and "j" in place of "j" and "j+1".
-
In method bubbleSort2, replace "s.firstPosition()" with
"s.first()" and "else prec = succ;" with "prec = succ;".
Page 138 (thanks to Mikkel Nygaard)
In the second paragraph, replace "isEmpty"
with "!isEmpty()"
and "pop" y "pop()".
Page 140, Exercise C-4.2 (thanks to Injong
Rhee)
Replace "seq.insertAtRank(i/2)+1,Integer(i));"
with "seq.insertAtRank(i/2,Integer(i));".
Chapter 5
- Page 145, Figure 5.2 (thanks to Mikkel
Nygaard)
In the caption, replace "Electronic R’Us" with
"Electronics R’Us".
- Page 147 (thanks to Freyr Thorarinsson)
In the first line of the third paragraph, replace
"each internal node has" with "each node has".
- Page 149 (thanks to Franck van Breugel
and Mikkel Nygaard)
In the definition of method container,
replace "container(): return a..." with "container():
Return a...".
- Page 150
(thanks to Franck van Breugel)
In the definition of method replace,
replace "replace(v,e): Replace the elements..." with "replace(v,e):
Replace the element...".
- Page 152 (thanks to Mikkel Nygaard)
In the last paragraph of Section 5.2, replace
"to answer some interesting problems" with "to solve some interesting problems".
- Page 154 (thanks to Mikkel Nygaard)
In the first paragraph, replace "dv
<= h +1 <= n" with "dv <= h <= n-1".
-
Java Code Fragments in Section 5.2 (thanks to Frank Dehne, Fei
Tan, Franck van Breugel and Mikkel Nygaard)
Most Java code fragments in Section 5.2 have small inconsistencies.
The corrections below were offered by Franck van
Breugel.
Similar corrections were suggested by Mikkel
Nygaard.
public static int depth(SimpleTree tree, Position node) {
if (tree.isRoot(node)) {
return 0;
} else {
return (1 + depth(tree, tree.parent(node)));
}
}
Code Fragment 5.4
Replace public int height1(SimpleTree T) { by public static
int height1(SimpleTree T) {.
Code Fragment 5.5
-
Replace public int height2(SimpleTree T, Position v) { by public
static int height2(SimpleTree T, Position v) {.
-
Replace T.height(w) by height2(T,w).
Code Fragment 5.7
-
Replace public void preorderPrint(SimpleTree T, Position v) {
by public static void preorderPrint(SimpleTree T, Position v) {.
-
Replace T.element(v) by v.element().toString().
Code Fragment 5.8
Replace public void parentheticRepresentation(SimpleTree T, Position
v) { by public static void parentheticRepresentation(SimpleTree
T, Position v) {.
Code Fragment 5.11
-
Replace public int totalSize(SimpleTree T, Position v) { by public
static int totalSize(SimpleTree T, Position v) {.
-
Replace "T.element(v)" with"v.element()".
Page 157, Figure 5.8 (thanks to Mikkel
Nygaard)
Replace "S._America" with "S.America".
Page 164 and Code fragment 5.12 (thanks
to Jeremy Frens)
Method sibling(Position v) should be
added to the binary tree ADT and corresponding Java interface.
Page 164 (thanks to Franck van Breugel)
In the definition of method removeAboveExternal,
replace "if v is an internal node" with "if v is an internal
node or v is the root".
Page 164 (thanks to Mikkel Nygaard)
In the last paragraph, replace "from this superclass."
with "from this superinterface."
Page 165, Code Fragment 5.12 (thanks
to Franck van Breugel and Mikkel Nygaard)
Replace:
"public void removeAboveExternal(Position v)"
with
"public Object removeAboveExternal(Position v)".
Page 171, Code Fragment 5.18 (thanks to
Joseph Leichter, Ben Master, and Ray Prisament)
Replace
"recursively tour the right subtree of v by calling
EulerTour(T, T.leftChild(v))"
with
"recursively tour the right subtree of v by calling
EulerTour(T, T.rightChild(v))"
Code Fragment 5.19 (thanks to Steve Goldman and Mikkel Nygaard)
-
In the first comment line, replace "binary T treee" with "binary tree T".
-
Replace "the operator at the" with "the operator at an".
-
Replace:
"public void printExpression(BinaryTree T, Position v)"
with
"public static void printExpression(BinaryTree T, Position v)".
Page 173, Code Fragment 5.20 (thanks to Thierry
Lecroq and Franck van Breugel)
In the first comment line, replace "algorthims" with "algorithms".
Page 177, Code Fragment 5.25 (thanks to Mikkel Nygaard)
Replace "operator at the internal node" with "operator at an internal
node".
Page 178, last paragraph, and Exercise R-5.17
(thanks to J. P. Pretti and Jackie Qing Chen)
Replace "2(n-1)/2" with "2(n+1)/2-1".
Page 180, Table 5.1 (thanks to Jeremy
Frens, Matei David and Mikkel Nygaard)
- The running time of removeAboveExternal(v)
is in general O(n). However, if both children of v are external,
as is always the case for a heap, it runs in O(1) time.
- In the caption, replace "O(2(n-1)/2)"
with "O(2(n+1)/2)".
Page 180 (thanks to Mikkel Nygaard)
In the last paragraph, replace "the element stored
at v, the parent of v, the left child of v, and the right child of v, respectively"
with "the element stored at v, the left child of v, the right child of
v, and the parent of v, respectively".
Code Fragment 5.27 (thanks to Yusuke Naito, Akimichi Inaba, Micah
Johnson, Jeremy Eisenga and Mikkel Nygaard)
-
In method isInternal, it is better to replace "||" with "&&".
Using "||" is correct but less robust than "&&".
-
In method expandExternal, replace "size++;" with "size
+= 2;"
-
Checks of Position-objects’ validity is missing and so is code
for throwing exceptions in methods leftChild, rightChild,
parent,
and expandExternal.
Page 184 (thanks to Mikkel Nygaard)
In the first paragraph, replace the entire second
sentence with "We make some observations about these and other binary tree
methods below.".
Page 184 (thanks to Franck van Breugel)
In the paragraph preceding Table 5.2, replace
"the the" with "the".
Page 186 (thanks to J. P. Pretti)
In the second list item, replace "external node
of T" with "external node of T that does not have a sibling following it".
Page 194, Exercise R-5.6 (thanks to Mikkel
Nygaard)
Replace "Code Fragment 5.7" with "Code Fragment
5.10".
Page 195, Exercise R-5.7 (thanks to Mikkel
Nygaard)
Replace "the same same order" with "the same
order".
Page 195, Exercise R-5.11 (thanks to Injong
Rhee)
In list item 6, replace "n and k"
with "n and h".
Page 196, Exercise R-5.13 (thanks to Corey
Hanson, Milo Beckler, Edwin Colby and Kenny Hunt)
The formula should be: "De
+ 1 = aDi + bn".
Page 196, Exercise R-5.14 (thanks to Mikkel
Nygaard)
Replace "Code Fragment 5.7" with "Code Fragment 5.10".
Page 198, Exercise C-5.6 (thanks to Mikkel
Nygaard)
- Replace "the hth node visited" with "the kth
node visited".
- In item 3, replace "assigns y-coordinates"
with "assigns x-coordinates".
Page 199, Exercise C-5.11 (thanks to Theis
Rauhe)
Replace "and positions(o) such that"
with "and children(v) such that".
Page 199, Exercise C-5.12 (thanks to Mikkel
Nygaard)
Replace "Table 5.2" with "Table 5.1".
Page 202, Chapter Notes
The Euler tour traversal technique was introduced
by Tarjan and Vishkin, motivated by the design of parallel algorithms [R.
Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm,
SIAM
J. Comput. 14, 862-874 (1985)].
Chapter 6
- Page 205 (thanks to Franck van Breugel)
-
In the third sentence of the last paragraph, replace
"the the" with "the".
- Page 206 (thanks to Franck van Breugel
and Mikkel Nygaard)
In the first paragraph, replace "that it must
satisfy" with "that the comparison rule is defined for every pair of keys
and it must satisfy".
-
Figure 6.5 (thanks to Ming-En Cho and Keith Schmidt)
The blue node in part (a) should contain the item (8,W).
- Page 207, Code Fragment 6.1 (thanks to
Keith Schmidt and Thierry Lecroq)
The second while loop should read:
while P is not empty do
e <- P.removeMinElement() {remove a smallest element from P}
S.insertLast(e) {add the element to the end of S}
Page 223 (thanks to Franck van Breugel)
In the second sentence of the last paragraph,
replace "the the" with "the".
Page 235 (thanks to Franck van Breugel)
In the definition of method isContained,
replace "Input: none;" by "Input: None;"..
Chapter 7
- Page 259 (thanks to Franck van Breugel)
In the paragrapg above Figure 7.4, replace "...the
method findElement runs ..." with "...the method insertItem
runs ...".
-
Code Fragment 7.4 (thanks to Joseph Leichter)
The implementation of method findElement is incorrect. Statement return
key(pos); should be replaced with return element(pos);
-
Code Fragment 7.5 (thanks to Adam Leventhal)
The implementation of method remove is incorrect for the case when
the key is at a node with internal children. The item at position parent(remPos)
should replace the item at position swapPos before removeAboveExternal(remPos)
is performed.
-
Code Fragments 7.4-7.5 (thanks to Joseph Leichter)
The instance variable actionPos is meant to be used by classes extending
SimpleBinarySearchTree to identify the position where the previous search,
insertion, or deletion has taken place. Position actionPos has the intended
meaning provided it is used right after executing methods findElement,
insertItem or remove on the superclass.
- Page 253 (thanks to Mikkel Nygaard)
In the first paragraph, replace "any operation
must first" with "any operation that must first".
- Page 267 (thanks to Mikkel Nygaard)
In line 4, insert "+2" in front of the big ")".
-
Figure 7.9 (thanks to Keith Schmidt)
In parts (b) and (d), the left-to-right order of the subtrees should
always be T0, T1, T2, T3.
-
Figure 7.11 (thanks to J. P. Pretti)
The sequences should be numbered S0, ..., S5.
- Page 287 (thanks to Woody Anderson)
In the definition of the hash function h(k)=(ak+b)
mod N, parameter a should be chosen such that a mod N != 0.
Chapter 8
-
Page 306, Figure 8.3 (thanks to Barbara Zarzycka)
In parts (q) and (r), replace "64" with "63".
-
Page 307, Figure 8.4 (thanks to Barbara Zarzycka)
In parts (s), (t), and (u), replace "64" with "63".
- Page 314 (thanks to Keith Schmidt)
In the specification of method isEqual(B), replace
"Input: Two set objects;" with "Input: Set;"
- Page 325, Figure 8.9 (thanks to Chris Morley)
In parts (f) and (g), the indices l and r should be exchanged,
since the swap with the pivot is performed after the indices cross.
- Page 327 (thanks to Keith Schmidt)
In the right hand side of the equation defining
si(n), replace "n-2i-1" with "n-(2i-1)"
- Page 335 (thanks to Michael Fried)
The last line of the first paragraph should read
"Randomized quick-select is described in Code
Fragment 8.9."
Chapter 9
- Page 346 (thanks to Mikkel Nygaard)
In the last paragraph, remove the phrase "which
is the same as the number of the adjacent vertices".
- Page 349, Example 9.9 (thanks to Barbara
Zarzycka)
Replace "path though" with "path through".
- Page 349, Example 9.9 (thanks to
Mikkel Nygaard)
Replace "go though" with "go through".
- Page 351 (thanks to Keith Schmidt)
In the last line (description of method isDirected(e)),
replace "an only" with "and only".
- Page 356 (thanks to Mikkel Nygaard)
In line 11, replace "and adds the follows additional"
with "plus the following additional".
- Page 363 (thanks to Mikkel Nygaard)
In last paragraph, replace "Proposition ‘9.12"
with "Proposition 9.12".
-
Page 367, Code Fragment 9.2 (thanks to Jonathan Mohr)
The second occurrence of the statement mark(nextEdge); is redundant.
-
Page 368, Code Fragment 9.3 (thanks to Benoit Hudson)
In methods isMarked(Vertex v) and isMarked(Edge e),
replace contains with containsKey.
- Page 371, Code Fragment 9.7 (thanks to
Mikkel Nygaard)
In method traverseBack, remove the statement:
Enumeration pathVerts = path.elements();
- Page 372
(thanks to Keith Schmidt)
In the second line of the first paragraph, replace
"of graph" with "of a graph".
-
Code Fragment 9.11 and Proposition 9.22 (thanks
to Benoit Hudson, Rebecca Sun, and Craig Mac Donald)
The code fragment and justification are correct. However, for consistency
with the example in Figure 9.12, a stack should be used instead of a queue
in Algorithm TopologicalSort.
- Page 374, Proposition 9.15
(thanks to Robert Altshuler)
In the second list item, replace "Computing a
spanning tree of G" with "Computing a spanning tree of G,
if G is connected".
- Page 378, Proposition 9.16 (thanks to Mikkel
Nygaard)
Replace "and every vertex of Vs
is reachable from s" with "and every vertex reachable from s
belongs
to Vs".
Chapter 10
Page 404, Proposition 10.2 (thanks to Mikkel
Nygaard)
Replace "such that that the weight" with "such
that the weight".
Chapter 11
- Page 442 (thanks to Mikkel Nygaard)
In line 6 of Section 11.1, replace "based one
the well-known" with "based on one of the well-known".
- Page 443
(thanks to Derek Davies and Mikkel Nygaard)
- In the fourth line of the second paragraph, replace
"form form" with "form".
- In line 18, replace "P[0]P[1] . . . p[m-1]"
with "P[0]P[1] . . . P[m-1]".
- Page 444 (thanks to Mikkel Nygaard)
In lines 18-19, replace "Input: A string Q of
length m; Output: true if Q is a prefix of S, false otherwise." with "Input:
String; Output: Boolean.".
- Page 445 (thanks to Mikkel Nygaard)
- In the definition of setCharAt, replace
"Input: An integer i and a character ch; Output: Sets the ith character
in S to be ch." with "Input:
Integer (i) and character (ch); Output: None."
- In the last paragraph of Section 11.1.2, note
that both append(Q) and insert(i, Q) run in O(n +m) time.
- Page 446, Code Fragment 11.1 (thanks
to Derek Davies)
-
Replace "if j <- m -
1 then" with "if j = m - 1 then".
- Page 447, Figure 11.1 (thanks to Mikkel
Nygaard)
There are 12 comparisons omitted (not 11). Hence,
the algorithm performs 28 character comparisons in all.
- Page 448 (thanks to J. P. Pretti)
In the second paragraph, the KMP failure function
should be initialized as f(0) = 0.
- Page 450, line 14 (thanks to Mikkel Nygaard)
- In line 14, since on exit from the while-loop, i
= n, replace "k <= n-1" with "k <= n".
- In line 24, replace "hence, total the number" with
"hence, the total number".
- Page 451, Code Fragment 11.3 (thanks
to Andy Schwerin, Rebecca Sun, J. P. Pretti and Mikkel Nygaard)
- Insert the statement f(0) <- 0 before the while-loop.
- Replace "P[j] = T[i]" with "P[j] = P[i]".
- Page 454 (thanks to Thierry Lecroq)
In the second line of the third paragraph, replace
"P against P" with "P against T".
- Page 460 (thanks to Thierry Lecroq and
Mikkel Nygaard)
- In the fourth line of the first paragraph, replace
"q in T" with "r in T".
- In line 15, replace "a state q has no" with "a state
q that has no".
- Page 462, Figure 11.5 (thanks to Mikkel
Nygaard)
Part (e) should be revised as follows:
- remove the e-transition
from the start to the end state of the FSA for a;
- add a new start state q1 and a
new final state qf.;
- add e-transitions from
q1 to the start of the FSA for a,
from q1 to qf, and from the final state
of the FSA for a to qf..
- Page 464 (thanks to Mikkel Ricky)
In line 15, replace"the processing the string"
with "the processing of the string".
- Page 466, Exercise C-11.8 (thanks to Mikkel
Nygaard)
Replace "used the Boyer-Moore" with "used in
the Boyer-Moore".
Chapter 12
- Page 479 (thanks to Finn Smith)
In line 8 of the first paragraph, replace "parition"
with "partition".
-
Pages 480 and 481, Code Fragments 12.2 and 12.3
(thanks to Keld Helsgaun)
Replace "self" with "this".
- Page 496 (thanks to Mikkel
Nygaard)
Replace "i=1"
in the summations with "i=0".
- Page 497, line -3 and page 498, line
-4
of first paragraph
(thanks to Guy Tremblay)
Replace "Case 3" with "Case 1".
- Page 498 (thanks to Guy Tremblay)
In the formula for IJ, all the terms within
square brackets should be added.
- Page 499 (thanks to Mikkel
Nygaard)
Replace "A[k,j]" with "B[k,j]".
- Page 505, line 8 and page 506, line 4
(thanks to Thierry Lecroq)
Replace "L[n,m]" with "L[n-1,m-1]".
- Page 505, Code Fragment 12.5 (thanks to Mikkel
Nygaard)
Replace "n-1"
in the second for loop with "m-1".
- Page 508 (thanks to Mikkel
Nygaard)
Replace "B[n,w]" with "B[k,w]" in the
second to last line.
Chapter 13
- Page 523 (thanks to J. P. Pretti)
In the second line of the fourth list item, replace
"1, ..., k" with "1, ..., d".
- Page 531 (thanks to J. P. Pretti)
In the deletion algorithm, only immediate siblings
of the underflow node v can participate in transfers and fusions.
- Page 534, Caption of Figure 13.8 (thanks
to Mark Handy)
Replace "red-black have black depth 3" with "red-black
tree have 4 ancestors; hence, black depth 3".
- Page 536 (thanks to Mark Handy and Rebecca
Sun)
The description of the insertion algorithm should
consider the case of an insertion into an empty red-black tree (i.e., a
red-black tree consisting of a single external node). To take this case
into account, replace the sentence
"We color z red and its children black."
with
"If z is the root of T, we color z black, else
we color z red. Also, we color the children of z black."
and replace the sentence
Indeed, if the parent v of z is red, ..."
with
Indeed, if z is not the root of T and the parent
v of z is red, ..."
Note that Code Fragment 13.1 correctly takes
this special case into account.
-
Figure 13.10 (thanks to Mark Handy)
In the top two structures of part (a), the left-to-right order of the
keys stored at the nodes should be reversed.
- Page 542 (thanks to Mark Handy)
The description of the deletion algorithm should
consider the case when the node v storing the item to remove is red and
has an external child w. To take this case into account, replace
"If r is red, we color it black and we are done."
with
"If v was red (and thus r is black), or if r
is red (and thus v was black), we color r black and we are done."
-
Figure 13.17 (thanks to Russell Cole)
In part (b), node x should be colored blue (indicating a red node)
and node y should be colored black (indicating a black node).
Chapter 15
- Page 621, Proposition 15.5 (thanks to Woody
Anderson and Ry Wharton)
- Replace "going counterclockwise from p" with
"going counterclockwise from a".
- Page 623, Code Fragment 15.2 (thanks to
Keith Schmidt)
- In the if test, replace "point(prev)" with "(point(prev)".
- In the last line, replace "S.remove(last())" with
"S.remove(S.last())" and "duplicate copy" with "copy".
- Page 640
(thanks to Lane Belling)
In the third line of the second paragraph, replace
"as a their" with "as their".
Chapter 16
- Page 656 (thanks to Mikkel
Nygaard)
Replace "j=0" with "j=1"
in the summation.
- Page 662 (thanks to Mikkel
Nygaard)
Replace "f(b)" with "g(b)"
on line 16.
in the summation.
Appendix A
- Page 674
(thanks to Claude Anderson)
In the second paragraph, replace "where use"
with "where we use".\
- Page 674 (thanks to Franck van Breugel)
Replace "...and three methods, one of which is
the class constructor, one is a procedure..." by "...two constructors and
two methods, one is a procedure...".
- Page 676
(thanks to Claude Anderson)
In the second paragraph, replace "We have already
given" with "We give below".
- Pages 676 and 680 (thanks to Eileen Head)
In the definition of the protected
modifier, change "same class" to "same package".
- Page 677 (thanks to Franck van Breugel)
In the definition of static, replace
"static instance variable" with "static variable".
- Page 678; (thanks to Thierry Lecroq,
Claude Anderson and Franck van Breugel)
- Underscores are allowed in variable names.
- In line 5 of the first paragraph, replace "C/alling"
with "Calling".
- Page 687 (thanks to Franck van Breugel)
In the operators precedence table:
- The prefix operators and assignment operators are
processed right-to-left. All the other operators are processed left-to-right.
- The operators for assignment, op assignment, bitwise
assignment and boolean assignment should be joined into a single precedence
class.
- Page 698 (thanks to Franck van Breugel)
Replace "return x_ / 10;" by "return
x / 10;".
- Page 698 (thanks toEileen Head, Jian Huang
and Thierry Lecroq)
In the definition of class HashPoint, replace
"hashPoint" with "HashPoint" and "hashFunc"
with "hashValue".
- Page 698 (thanks to Franck van Breugel)
In the first sentence of the Implicit Casting
section replace "...explicit cast, that is, a cast that is not syntactically..."
with "...explicit cast, that is, a cast that is syntactically...".
- Page 701 (thanks to Steve Goldman, Craig
Mac Donald, Thierry Lecroq, P. G. and Franck van Breugel)
In the definition of interface Person,
replace "Geometric" with "Person".
- Page 701 (thanks to Franck van Breugel)
In the first comment of the code at the top of
the page, replace "i1 was..." with "i was ...".
- Page 704 (thanks to Franck van Breugel)
In the first paragraph of section A.8.1, replace
"An thrown exception..." by "A thrown exception...".
Appendix B
- Page 710, Proposition B.2 (thanks to Jack
Snoeyink)
The inequality holds only for x > -1.
- Page 711, Proposition B.3 (thanks to Jack
Snoeyink)
The upper bound (<=) holds only for x <
1.
- Page 711, Proposition B.4 (thanks to Jack
Snoeyink)
The upper bound (<=) does not hold, e.g.,
for x = -n.
-
Page 713, Proposition B.15 (thanks to
Murray Tyler)
The numerator on the righthand side
should read a - (n + 1)a^(n + 1) + na^(n + 2).
- Page 715 Justification of Example B.22 (thanks
to Thierry Lecroq)
Replace "49/2" with "49/4".
Michael
Goodrich,
Roberto Tamassia
Last modified: .