Error Information for Data Structures and Algorithm Analysis in C++ (3/e)


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

--------  ---  ---  ----------------------------------------------------------
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
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"


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.