A Practical Guide to Data Structures and Algorithms Using Java
Sally A. Goldman and Kenneth J. Goldman
Washington University in St. Louis
Errata
- Please send reports of any additional errata to sg@cse.wustl.edu
- Page 11, Figure 1.1 (reported by Rahav Dor), posted Spring 2008
- The middle child of the root should be shaded.
- Page 51, last line, posted Fall 2007
- Should end with "where o1 holds 4/3 and o2 holds 1 1/3."
- Page 151, last full sentence, posted Fall 2007
- Change to "Specifically i, which starts at position left, marks the start of the unprocessed portion of the subarray, and j, which starts at the pivot position, marks the end of the unprocessed portion of the subarray.
- Page 155, equation in second paragraph, posted Fall 2007
- Outer summation should go from i = 0 to n-2, and the inner summation should go from j = i+1 to n-1.
- Page 187, DynamicArray constructor at the bottom of the page, posted Fall 2007
- The call to super should be super(capacity, equivalenceTester);
- Page 194, line -11 (reported by Shouguo Li), posted Fall 2007
- Replace "so if there are is no predecessors" with "so if there are no predecessors"
- Page 197, line -4, posted Fall 2007
- Add a space after "null" in the first sentence of the InUse property.
- Page 237, paragraph 2, line 3 (reported by Michael Goldwasser), posted Fall 2007
- Replace "follows loc" with "precedes loc" to give "loc-1
refers to the list element that precedes loc."
- Page 285, second paragraph (reported by Brian Bies), posted Fall 2007
- Change the two occurences of "alpha" to "α"
- Page 287, Table 20.4, line for Open Addressing with α = 1/4 (reported by Brian Bies), posted Fall 2007
- Replace "4n/3" with "4/3"
- Page 291, fourth line of Competing Data Structures (reported by Brian Bies), posted Fall 2007
- Replace "1010" with "109"
- Page 293, line -2 (reported by Brian Bies), posted Fall 2007
- Replace "directed addressing" with "direct addressing"
- Page 293, end of page, posted Fall 2007
- The bottom of the page should have "Addressing must provide
this added parameter."
- Page 297, line 3 (reported by Brian Bies), posted Fall 2007
- Replace "returns truethe" with "returns true when the"
- Page 299, Marker constructor (reported by Brian Bies), posted Fall 2007
- Replace "slot ≥ table.length" with "slot > table.length" since table.length(m)
corresponds to AFT which is a legal input.
- Page 307, line 13 (reported by Brian Bies), posted Fall 2007
- Replace "deletes slots" with "deleted slots"
- Page 313, line 10 (reported by Brian Bies), posted Fall 2007
- Replace "I" with "It"
- Page 317, Table 22.2 (reported by Brian Bies), posted Fall 2007
- Since the add method first uses locate to see if the element is already in the
collection, the worst-case time complexity for add is O(n).
- Page 345, line 14 (reported by Brian Bies), posted Fall 2007
- Remove the stray "It is also necessary" that precedes "Observe that".
- Page 346, line 3 and line 9 (reported by Brian Bies), posted Fall 2007
- Change "(E element:" to "(E element):" for both decresasePriority and increasePriority.
- Page 350, line 7 (reported by Brian Bies), posted Fall 2007
- There is no need to italicize "amortized" and change "are constant" to "that are constant".
- Page 357, end of page (reported by Brian Bies), posted Fall 2007
- The last line should be followed by the line "collection is empty."
- Page 483, line 14 (reported by Rahav Dor), posted Spring 2008
- Change "e not in the collection" to "e in the collection."
- Page 509, line -5 of second paragraph (reported by Rahav Dor), posted Spring 2008
- Change "differ by less than one" to "differ by more than one."
- Page 518, line 6 (reported by Scott Bressler), posted Fall 2007
- Replace "We now discusses" by "We now discuss".
- Page 518, line 17 (reported by Scott Bressler), posted Fall 2007
- Replace "rotation (Case 2b), or a pair of rotations (Case 2b)" by
"rotation (Case 2a), or a pair of rotations (Case 2b)".
- Page 518, 3 lines above insertFixUp code (reported by Scott Bressler), posted Fall 2007
- Replace "It applies Case 2a" by "It applies Case 2b".
- Page 547, first paragraph starting at line 5 (reported by Brian Bies), posted Fall 2007
- Replace by "the array of child references plus the parent reference
requires 4(2t+1) = 8t + 4 bytes. So the total space requirement for a full
node would be about 40t bytes. Selecting t as large as possible so
40t ≤ 4096, yields a choice of t = 102. As we prove in Section 36.6,
for a B-tree of height h, 2th - 1 ≤ n ≤ (2t)h+1 - 1.
Thus a B-tree of height 5, with t = 102 holds between 22 billion
elements (when all nodes are minimum-sized) and 72 trillion elements (when
all nodes are maximum-sized).
- Page 564, figure caption (reported by Brian Bies), posted Fall 2007
- Change "t = 5" to "t = 3".
- Page 570, line -5 (reported by Rahav Dor), posted Spring 2008
- Change "of Figure 36.1 the height is 2" to "of Figure 36.1 the height is 1."
- Page 570, end of last full paragraph (reported by Brian Bies), posted Fall 2007
- Remove the "the" that is after the final sentence of the paragraph.
- Page 596, last sentence of Height property (reported by Brian Bies), posted Fall 2007
- Change "That is height is" to "That is, height is".
- Page 601, second sentence of Correctness Highlights (reported by Brian Bies), posted Fall 2007
- Change "right = head" to "right = tail".
- Page 604, line -5 (reported by Brian Bies), posted Fall 2007
- Change "2 * neededHeight" to 2 * minimumHeight".
- Page 605, line 2 in paragraph that follows the biasedCoinFlip methd (reported by Brian Bies), posted Fall 2007
- Change "biased coin flips made until a true" to "biased coin flips made until a false", and
change "occurs with probability 1/4" to "occurs with probability 3/4".
- Page 612, line -5 of prose (reported by Brian Bies), posted Fall 2007
- For consistency, put elements e, b, and s in quotes.
- Page 612, line -2 of prose (reported by Michael Goldwasser), posted Fall 2007
- Change "after to the tracker" to "after the tracker".
- Page 614, Table 38.6 (reported by Brian Bies), posted Fall 2007
- The line in the table should be moved below "successor(o)".
- Page 615, second line in C(k) recursive definition, posted Fall 2007
- A closed parenthesis is missing at the end after C(k-1).
- Page 623, line 1 (reported by Brian Bies), posted Fall 2007
- Change "and left if the rightmost bit is 1" to "and right if the rightmost bit is 1".
- Page 630 (reported by Brian Bies), posted Fall 2007
- Table 39.8 should be Figure 39.8.
- Page 630, line -9 (reported by Brian Bies), posted Fall 2007
- Change "for the suffix Tree" to "for the suffix tree".
- Page 632, Figure 39.10, posted Fall 2007
- The leaves that are descendants of the internal node labeled "(0,0)"
from left to right should be (21,24), (37,43), (0,4), (12,17), (29,35), and
(6,10).
- Page 672, caption of Figure 42.1 (reported by Rachel Herman), posted Spring 2008
- The populated example does not include cafe#, so in the first line of the caption change "cab#, cafe#, dab#,"
to "cab#, dab#,"
- Page 732, line 4 in QuadTree portion of Section 46.4 (reported by Brian Bies), posted Fall 2007
- Change "this compression" to "this comparison".
- Page 753, Table 47.5, posted Fall 2007
- Time complexity for min and max methods is O(n(k-1)/k + h). These should
be placed in their own grouping just before withinBounds. Also the time complexity for
withinBounds (when k is not treated as a constant) is O(k n(k-1)/k + h + r).
- Page 791, end of 49.2, posted Fall 2007
- Add the sentence, "If desired, a getTagComparator method could be added to provide an
application access to the comparator defined over the tags."
- Page 830, return type of removeBucket, posted Fall 2007
- The return type of removeBucket is Collection<E> (and not boolean). The
textual description for the method including the discussion of the return value is
correct.
- Page 832, bottom of page, posted Fall 2007
- Add the sentence "This class should be extended if the application needs support
of any additional methods that are specific to the wrapped tagged collection."
- Page 967, first line of last paragraph of A.4 (reported by Sam Powell), posted Spring 2008
- Change "remember are that while" to "remember that while."
- Page 981, line 1 (reported by Rahav Dor), posted Spring 2008
- Change "most goals" to "most important goals."
- Page 984, line 3, posted Fall 2007
- Θ(√(n)) can be written as Θ(√n)
- Page 984, last paragraph of B.2, posted Fall 2007
- In the definition of a polynomial time algorithm replace "c" by
"c ≥ 0," and in the definition of an exponential time algorithm replace
"a" with "a > 1."
- Page 985, 2nd to last line of B.4, posted Fall 2007
- In the definition of E[TA(x)] replace "Probability(f(x) = t)" with "Probability(TA(x) = t)"
- Page 985, line -3 (reported by Brian Bies), posted Fall 2007
- Replace "infinity" with "infinite"
- Page 987, last line of table (reported by Brian Bies), posted Fall 2007
- Under the last row (half array size) the column for the new potential should
have "s/4 - n = 0".
- Page 988, line 6, posted Fall 2007
- Change "11.4.2" to "in Section 11.4.2."
- Page 988, second paragraph, posted Fall 2007
- Remove "and the number of times the termination condition is reached when" from
the end of the last sentence.
- Page 988, third paragraph, posted Fall 2007
- In the third sentence replace "the total computation time for all the class
that do not reach the termination condition" with "the rest of the computation."
- Page 988, summation for T(n) (reported by Bill Dirkes), posted Fall 2007
- Replace "bi" with "bi"
- Page 988, line -6, posted Fall 2007
- Replace "x! = 1" with "x ≠ 1"
- Page 1010, line -14 (reported by Michael Goldwasser), posted Fall 2007
- "cubic time complexity" should be capitalized as "Cubic time complexity"