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

Errata

Here is the errata list for Data Structures and Algorithm Analysis in Java (3/e), by Mark Allen Weiss. Some of the errors affect the source code; updates to the code are done automatically. I'm very backlogged on these. Please be patient for a reply. Thanks!

All errors

  DATE   PAGE  WHO  PROBLEM
--------  ---  ---  ----------------------------------------------------------
02/08/19  013  TW   In parargraph two replace the parenthetical comment: "As shown in line 9, downcasts are 
                    not needed for string concatenation.
08/31/17  023  GO   The discussion on this page illustrating code that will not
                    compile does not apply to Java 8.  See:
                      http://docs.oracle.com/javase/8/docs/technotes/guides/language/enhancements.html#javase8
07/17/15  025  BR   Line 8 of code, change "arr.size()" to "arr.length"
               GO   Modify comment on line two accordingly.
08/26/16  025  GO   Line 26 of code: add semicolon at end; note also that findMax is in class TestProgram,
                    othewise a class name is needed to invoke the static method.
01/29/15  035  RM   Line 4, change "nearly 9,000 seconds (or two and a half hours) to
                    "nearly 90,000 seconds (or one day)"
06/06/12  038  GO   Change "plus the addition at line 3" to "plus the work at line 3"
07/01/15  045  ZD   Change "finishes with high-low >= -1" to "maintains the invariant that high-low >= -1
11/06/17  047  HG   Nine lines from bottom, change "only seven operations were performed" to 
                    "only five mod operations were performed"
03/15/17  052  MMW  Last line, remove extra parenthesis by changing ((a+b)/2) to ((a+b)/2
02/01/16  053  TF   Exercise 2.21, change "the algorithm terminates" to "the algorithm terminates
                    after remaining uncrossed numbers are output" 
01/03/13  055  PLC  In Ex 2.33, change "maxSubSum" to "maxSubRec" in two places.
02/13/12  082  SQZ  On line 30, change false to this
10/14/16  097  RL   In Exercise 3.7 add the missing return statement to return lst.
09/24/14  104  US   In Figure 4.5 (and then 4.7, 4.8, 4.10), folder cop3212
                    inadvertantly has two identical named directories (fall).
                    Change the second "fall" to "spring".
06/18/12  139  ??   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 =).
10/07/14  167  SMM  "A (| represents the start..." should read
                    "A |( represents the start..."
01/03/13  178  SN   Change line 4 to "if x is found"
01/03/13  186  SN   Change line 4 to "if x is found"
04/14/15  187  MM   In Figure 5.17, currentSize, which represents the number of
                    active+deleted items should only be incremented if the inserted
                    item does not replace an item marked as deleted.  There are
                    several simple ways to fix that.  The easiest fix is to remove
                    the ++ at line 16, and instead add at line 12:
                         if( array[ currentPos ].info == null ) ++currentSize;
04/28/22  193  AN   In Theorem 5.2, change "no bin" to "some bin".
09/25/12  195  HAE  Paragraph 2, line 2 of Section 5.7.2, change has to hash
03/22/19  196  GO   On line 4, change "available locations" to "valid locations"
10/13/12  211  GO   First sentence, change "average cost" to "constant average cost"
03/22/19  213  GO   Caption for Figure 5.51 should replace simple with Carter-Wegman 
04/15/13  222  MW   Four lines from bottom, change "in chosen" to "is chosen"
08/13/17  257  ZW   "rank" is not defined prior to use.  In binomial queues,
                    it represents the number of children of the root.
09/17/14  267  BQ   Exercise 6.35(b), change "smaller tree" to "smaller queue"
05/09/21  274  OS   In the first paragraph after Thm 7.2, remove "and selection sort"
06/21/19  276  SF   Should clarify that the increments in Figure 7.5 are not related to the subsequent
                    code in Figure 7.6.
02/08/19  288  JK   Line 37, change "performance, is generally" to "performance is, generally"
11/14/12  297  GO   Figure 7.16, line 16, should be right-2
04/16/13  298  MAW  Line 5, change "this gives as" to "this gives an"
04/16/13  309  MAW  First line of proof change "basic idea if" to "basic idea is"
04/16/13  310  MAW  End of Sec 7.11, change "amoung" to "among"
01/03/13  311  MT   Line 29: "After the first pass, the items are sorted
                    **on the least significant digit**; 4 lines later:
                    "But the previous passes ensure that when several numbers
                    enter a bucket, they enter in sorted order **according to the
                    k-1 least significant digits**."
05/30/17  312  AJ   Line 9 of Figure 7.23, change "new ArrayList<>" to "new ArrayList"
05/30/17  314  AJ   Lines 10 and 11 of Figure 7.25, change "new ArrayList<>" to "new ArrayList"
01/03/13  315  MT   Line 28: "precisely" misspelled 
02/26/18  320  JYC  The run construction example in Figure 7.28 does not exactly
                    match the prior small example as it omits 75 from the input sequence
11/03/12  344  GO   In figure 8.19, the "g" and "h" nodes are
                    exchanged in the second row the first time they appear.
12/27/21  348  GO   In the proof of lemma 8.3 cases 1 and 2 are swapped.
07/31/12  354  MAW  In caption for Fig 8.28, replace 8.22 with 8.27.
07/31/12  386  MAW  The text does not describe the code in Fig 9.38, which was
                    changed by having findChain invoke and return the result
                    of  getChainFromPreviousMap, thus altering findChain's return type.
09/17/14  391  MAW  Four lines from bottom, add a sentence prior to "But that means that..."
                    The new sentence is "Because there are no edges going from
                    s's side of the cut to t's side of the cut in Gr, there is also no
                    backflow across the cut either."
05/10/21  405  JSO  In Figure 9.68, because marking is already done,
                    replace the forward edge test with
                       if( w.parent == v )  // forward edge
04/19/13  425  MAW  Spanning to the next page, the last 7 paragraphs of the proof should be indented.
08/01/12  468  MAW  At line 26 of the code, the multiplication uses ints, os
                    a cast of c[ i ] to long should be inserted.
08/01/12  480  MAW  Line 2, C should be 11, not 13.
05/09/21  491  GO   On code lines 4 and 13 add "in the right quantity"
01/15/15  507  MAW  Exercise 10.67, change "black" to "second player"
04/20/13  508  MAW  In paragraph 3, change "[58] and" to "[58]"
04/20/13  509  MAW  In line 4, change "probably" to "provably"
04/21/13  538  MAW  Third paragraph of reference, change "seach" to "search"
02/23/13  548  SW   In Figure 12.8, replace lines 10 and 11 with "if( !contains( x ) )"
                    to fix a big that incorrectly handles remove from an empty splay tree.
06/24/13  550  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.
01/19/13  561  MAW  Section 12.4.1, paragraph 2: starting in Java 7, update 6,
                    substring no longer shares the character array with the main
                    string, so the space utilization is in fact quadratic.
04/21/13  562  MAW  Caption in Figure 12.22, change "Indices" to "indices"
04/21/13  562  MAW  Line 4, change "binary searches suffix" to "binary searches suffice"
04/21/13  566  MAW  In item #3, change "each leaf keeps" to "each node keeps" and
                    "down the internal node" to "down the tree"
04/21/13  570  MAW  Change "Figure 12.30, how" to "Figure 12.30 shows how"

Credits

AJ   Arihan Jalan
AN   Abhijit Nandy
BQ   Brian Quanz
BR   Bill Roberts
GO   Greg Ozbirn
HAE  Henry A Etlinger
HG   Huaien Guo
JK   Jason Kao
JSO  Joaquin Silveira Ocampo
JYC  Jason Yu Chen
MM   Mario Marchand
MMW  Marc Michel Weiss
MT   Martin Tompa
OS   Oren Steinberg
PLC  Polk Lule Contreras
RQ   Ramoni Lasisi
RM   Ruth Mazurek
SF   Satchel Frost
SMM  Sara Miner More
SN   Son Nguyen
SQZ  Si Q. Zheng
SW   Steve Wolfman
TF   Trevor Fancher
TW   Thomas Whitley
US   Uday Singh
ZD   Zhanrong Du
ZW   Zhu Wensi

Printing History

First Printing: November 2011
You can see which printing you have by looking at the bottom of the copyright page for a sequence of numbers. If you see
15 14 13 12 11 -- CRW -- 10 9 8 7 6 5 4 3 2 1
you have the first printing.