Error Information for Data Structures and Algorithm Analysis in C++ (3/e)
Errata
Here is the
errata list for Data Structures
and Algorithm Analysis in C++ (3/e), by Mark Allen Weiss.
Some of the errors affect the source code; updates
to the code are done automatically.
Click here to report a new error.
I'm very backlogged on these.
Please be patient for a reply. Thanks!
First printing
DATE PAGE WHO PROBLEM
-------- --- --- ----------------------------------------------------------
06/01/07 031 HEP In Fig 1.20, line 4, remove the stray semicolon
between m2 and ("hello");
07/28/09 033 HZ In line 8, the braces are missing.
06/01/07 043 KD In Def 2.4, change "all constants c" to "all positive constants c"
09/26/10 044 MT Five lines from the bottom,
max(O(f(N)),O(g(N))) should instead be O(max(f(N),g(N)))
09/26/10 045 MT Nine lines from the bottom, replace "oscillates"
with "does not exist".
11/12/05 069 MAW Change line 5 to line 15 in Exercise 2.31.
01/03/13 069 PLC In Ex. 2.33, change "maxSubSum" to "maxSumRec" in two places
06/24/10 073 MAW Change "deleting the second element" to "deleting the third element"
06/24/10 083 AA Lines, change operator[] to operator=.
01/23/06 085 A Second to last sentence in second to last paragraph,
change "itera tor" to "iterator"
07/26/06 093 PA Figure 3.20, line 16, use start and end, not from and to.
And on line 19, return end.
02/07/06 120 MAW First sentence of Sec 4.21, change "tree has at most"
to "tree node has at most"
10/10/10 126 MAW On lines 34 and 35, move the const at the end.
10/10/10 133 MT In the last sentence of the first paragraph in Section 4.3.6,
clarify that in the case of remove, the "accessed item"
refers to the replacement node in the two-item case.
02/07/06 136 MAW Last line, change .328 to 1.328.
08/01/06 138 PJV Figure 4.33, the far right node at height 7 is missing its left child.
02/22/13 146 MAW Three lines from the bottom, change "signal" to "signed"
02/07/06 147 MAW Next to last line, change "rotateWithLeftChild" to
"rotateWithRightChild"
01/01/12 148 DS Deletions in AVL tree aren't that hard. Fourth edition code
shows it can be done with one extra line of code.
10/11/10 149 MT In lines 4, 11, 19, 20 of Section 4.5, change O(N) to THETA(N).
02/07/06 149 MAW In Sec 4.5, paragraph 2, line 2, change "as long at it" to
"as long as it"
06/18/12 152 ?? The discussion in Sec 4.5 should clarify that "units" refers
to depth, though it would make more sense for it to refer
to number of nodes on access path. In terms of number of nodes
on the access path, in section 4.5.1, key 1 takes N units,
key 2 takes N units, key 3 takes N-1 units, and so on.
The total is N + sum from i=2 to N i, which is still
OMEGA( N^2 ). (The - should be =).
02/07/06 161 DH Item 5, change "L children" to L "data items"
02/07/06 162 DH Line 5, change "first level could " to "next level could"
10/16/07 168 GO Four lines from the bottom, change "two characters" to "two words"
03/20/09 170 SW On line 2, "adj[str]" is a typo and should be "adjWords[str]"
06/25/10 173 SW Figure 4.72, lines 12-15: move indenting to align with 47-48.
02/07/06 175 MAW In Exercise 4.10 change "in a binary search tree" to
"in an N node binary search tree" (with N italicized)
12/22/10 208 MAW In Exercise 5.1, change (mod()10) to mod 10
05/21/08 254 BC In Exercise 6.17, replace "full complete" with "perfect binary"
06/24/10 264 HJ On the third line of 7.2.3, replace "element comparisons"
with "tests"
11/14/05 265 MAW At start of Section 7.3, change "inversion" from italics
to boldface.
06/25/10 272 SW In the first paragraph of 7.5.1, "at most 2N" can be more
accurately stated as "less than 2N", and "at most 2 log i
(with floor function)" is more accurately stated as
"less than 2 log (N-i-1) (with floor function retained)"
09/26/06 273 HK In heapsort, the loop at line 7 can start at a.length / 2 - 1.
WD It must if arrays of length 0 are allowed.
05/21/08 275 CK In the fourth figure, move Cctr one more spot to the right.
06/25/10 293 SW Paragraph4, line 1, change "Figure 7.21" to "Figure 7.19".
02/08/06 307 MAW In Exercise 7.10, change "line 2" to "line 8" in two places.
12/22/10 319 MT Five lines from the bottom, replace 2 occurrences of big-Oh by big-Theta.
06/27/06 323 EEO In the second line from the bottom of the page, "tree" should
be replaced by "forest".
12/22/10 345 MT For completeness, we should mention how the indegrees are
computed and that it takes time O( |E| + |V| ).
12/22/10 359 MT The pseudocode would be cleaner if NOT_A_VERTEX is avoided by using
while( there is an unknown distance vertex )
Similarly, after the if( !w.known ) test, it would be
cleaner to add a line (with associated braces)
DistType cvw = cost of edge from v to w;
06/25/10 365 SW Paragraph 4, line 2, change "words to be connected" to
"first word on the ladder"
06/25/10 378 SW End of section 9.5: add closing parenthesis to make O(|E|log|V|)
12/22/10 378 MT Change DisjSet to DisjSets.
12/22/10 378 MT Add additional code to collect and return the MST edges.
05/07/13 381 MS Second line of Sec 9.6.2, change "in the example above" to Figure 9.60.
11/26/05 397 MAW In Exercise 9.2, change Section 9.1 to Section 9.2.
07/11/06 ??? MAW At the end of Chapter 9, in the references, add the
following as the best deterministic minimum spanning tree algorithm:
Bernard Chazelle: A minimum spanning tree algorithm with
Inverse-Ackermann type complexity. J. ACM 47(6): 1028-1047 (2000)
06/25/10 425 SW In Proof of lemma 10.1, the paragraphs except the first one
have wrong indent. They should be aligned with the first paragraph.
06/25/10 427 SW Paragraph 1, change "M-1 extra" to "at most M-1 extra"
06/25/10 459 SW Change "C is odd" to "A and C are odd"
08/26/09 459 MAW The 48-bit random number generator has C=11.
10/28/10 485 MAW Line 7 of the references, change [38] to [39].
06/25/10 496 SW Line 4 of the proof, change "trees have" to "queues have"
06/25/10 498 SW Change "(collection) of" to "(collection of)"
06/25/10 507 SW Change "ith youngest" to "ith oldest"
10/17/10 511 MT In the proof, AT is used as amortized time, but this is
never explicitly stated.
10/17/10 512 MT In the last line, chage R_f(T) to either R_f(root) or R(T).
10/17/10 513 MT In the first paragraph, in order to show that insert
takes O(log N) amortized time, we should also show that
the step of adding the leaf into the tree adds at
most log N to the potential. Similarly some care needs
to be taken when describing the non-splaying steps
in the deletion, which also change the potential.
The arguments are not complicated, and should have been included.
02/24/13 524 SW2 In Figure 12.8, replace lines 6 and 7 with "if( !contains( x ) )" to
fix a bug that occurs when attempting to remove from an empty tree.
06/24/13 527 GO At the end of Section 12.2.1 add a sentence: "Note that
in this last case, we can simplify because the color flip
by itself, without the rotation, yields equivalent
behavior; most importantly, either way, we would still
need to percolate up toward the root.
11/24/08 531 ME Change "coloring the root red" to "coloring the root sentinel red"
Credits
A Adam
AA Abdulhamid Alsalman
BC Brian Curless
CK Craig Kovatch
DH Dennis Hamilton
DS Dan Sleator
EEO Evelyn Obaid
GO Greg Ozbirn
HE He Jiang
HEP Hans Ekkehard Plesser
HK Heinrich Kuettler
HZ Hongyuan Zhang
KD Ketil Danielsen
MS Mallory Smith
MT Martin Tompa
ME Mitch Edelman
PA Peter Allen
PJV Peter J. van Wesep
PLC Polk Lule Contreras
SW Shi Weili
SW2 Steve Wolfman
WD William Deng
Printing History
First Printing: November 2005
Second Printing: March 2006
You can see which printing you have by looking at
the bottom of the copyright page for a sequence of numbers.
If you see
1 2 3 4 5 6 7 8 9 10
you have the first printing.