Errata for Timothy A. Budd, Classic Data Structures in Java

Errata for the Book:

Classic Data Structures in Java

by Timothy A. Budd

Published by Addison-Wesley Longman

Typos and Short Comments

ChapPagelineCommentContributor
237-18should extend Collection or Bag
237-18arguments could be Bag, not Set
366Ex 6Should have first asked to prove time is O(2^n).
5114Ex 13Chapter 9? What was I thinking???
61253getLast throws ArrayIndexException, interface specifies NoSuchElementException(rl)
6147Ex 1116 should be 26, so as to force two reallocations.
6148Ex 14Problem is, this version of bubble sort IS stable
8214Ex 11Assume all elements are unique (much harder otherwise)
14379Ex 6Exercise 6 is same as exercise 3
154073DefaultComparator is now in java.util.DefaultComparator
18481Arguments to union/intersection could be any Bag
184892Can return immediately when sentinel is encountered
18503Ex 10should ask first if subset is less than or less-than-equal
19527Ex 2Question doesn't make sense since matrix is an interface not a class
19527Ex 4Should give a hint (see below)
B537-1Comparator is now java.util.Comparator
B5383DefaultComparator is now java.util.DefaultComparator
20555Ex 7Need to specify a starting vertex

Longer Comments

Chapter 2, Page 29, Comparator
When the book was being written Java 1.1 was the norm, 1.2 was in Beta, and 1.3 was not even being considered. (And, given the confusion between the Java 1.2 and Java 2 terms, who would have predicted that the next version of the language would be 1.3?). Since Comparator and Comparable were not part of 1.1, it was necessary to include them in the jds library. However, by the time the book was published 1.2 was the norm, and 1.3 was on the near horizon. So uses of jds.util.Comparator should probably now be replaced by java.util.Comparator.

Chapter 2, Page 36, Enumeration vs Iterator
Version 1.2 of Java introduced the concept of an Iterator that is an extension of the 1.1 (and earlier) concept of an Enumertion. Should the book have used the newer concept? This is debatable, but personally I think not. The principle difference between the Enumeration and the Iterator is that the latter includes a method to remove the current element. For a number of data structures (trees, for example), this is surprizingly difficult. To have discussed this would have distracted the student from the main points being presented. (However, asking how to implement remove operations is a great source for programming exercises).

Chapter 15, Page 527, Exercise 4
Should give a hint on this or it is too hard. Show how with one query you can divide the matrix into four rectangular regions. Can you eliminate any of these? Recursively search the ones you cannot eliminate.

Acknowledgements

(rl)
Ray Lischner, Tempest Software, Corvallis Oregon