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.