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

Positive line numbers count from top of page, negative from bottom of page.
110-2n should be val, also on next page(js)
1112printInt(out, n/10); // two parameters(hs)
1113Missing right parenthesis(hs)
22720insertAndExtract => getAndSet(js)
2337can invoked => can be invoked(vk)
237-18should extend Collection or Bag
237-18arguments could be Bag, not Set
2397description backwards, -1 if left is smaller, not larger(ms)
247-10removeElement should not return anything(js)
3551code doesn't work without default(js)
356-8printInt should have two arguments(hs)
3594assert greater than, not >= (brm)
366Ex 6Should have first asked to prove time is O(2^n).
47110-11for all and exists reversed, correct on p. 92(hs)
47719n2+n => n2-n(em)
48012m[i,j] should be m[i][j](rb)
5114Ex 13Chapter 9? What was I thinking???
6119-15index should begin at 1, not 2(ms)
6121-12addElement(...) => addLast(...) (vectors don't have addElement)(rs)
61253getLast throws ArrayIndexException, interface specifies NoSuchElementException(rl)
6127BoxVisitor not in source? (see comments below)(rm)
6147Ex 1116 should be 26, so as to force two reallocations.
6148Ex 14Problem is, this version of bubble sort IS stable
7160codeshould use comparator instead of equals (see below)(mo)
7179Ex 210,000 should be 1,000
81931Insert should return new link (correct in code library)(rm)
8202codeVariables x and y should be private(dc)
8204-6class Asteroid is unnecessary(dc)
82066extend => extends(dc)
8214Ex 11Assume all elements are unique (much harder otherwise)
8214PP 6.bCan't clone the individual elements (see below)(rm)
92284insert may be confusing (see below)(eb)
9230codeuse equals or compare (see below)(mo)
10258Fig 5que is incongruous name for a stack
11290Ex 6.haddElement => addElementAt(sdog)
123152constructor should be public(sdog)
12319-8for consistency, should assign getfirst to variable(ag)
1334116need cast: current = (BinaryNode) stk.getLast();
1334117recursive call needs guard, if (current.rightChild) != null(js)
143493add stk.removeLast()(mo)
14360getFirstroot.getFirst returns a node, need to get value(ak)
14379Ex 6Exercise 6 is same as exercise 3
14381-10root is deleted=>current node is deleted(jc)
15393-8need to add ``if (max != 0)'' before loop(sdog)
15404-8less than should be less-or-equal(dc)
154073DefaultComparator is now in java.util.DefaultComparator
17464what to do with non-empty collections (see below)(rm)
17473Ex 4.cGood luck. Doesn't parse
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)
B573-1Comparator is now java.util.Comparator
B5833DefaultComparator is now java.util.DefaultComparator
20555Ex 7Need to specify a starting vertex
593Entry vistor unnecessary(dc)

Longer Comments

Chapter 2, Page 39, 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 6, Page 127, box
Although the box nicely describes the visitor design pattern, the actual source that implements this behavior doesn't seem to have been included in the code for the Vector data type. Will be there in the next revision.

Chapter 7, page 160, use of equals, also Chapter 9, page 230
Although not wrong, it is debatable whether or not one should use the method equals to compare for equality in the sorted vector and sorted list. An alternative would have been to use the comparator and test for equality to zero.

Chapter 8, Page 214, Programming Project, 6.b (list clones)
I tossed this in thinking it was easy, but never tried it. When Ron Metoyer assigned it to his class, he found it was surprizingly difficult. Cloning the list is easy, but you can't clone the elements. (That is, you can make a shallow copy, but not a deep copy). In fact, neither he nor I could fine a way to use the Cloneable interface to make a deep copy. As far as I know, nobody knows how to do this.

Chapter 9, Page 228, sliplist insert
Eberhard Bertsch suggests that I may not emphasize as forcefully as I should the fact that the recursive call on insert in line 4 of page 228 does different things, depending upon how near we are to the bottom of the list. The bottom list is composed of simple DoubleLinks, while all the others are composed of SkipLinks. Depending upon the type of the lower link, it will either recursively execute the skiplink insert, or be a non-recursive call on the doublelink insert. This is a good opportunity to remind students of the concept of polymorphism, and the fact that the bit of code that will be executed in response to this call is determined dynamically, at run-time, depending upon the type of the receiver.

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.

Chapter 17, Page 464, Initializing a Map
The fact that Map is implemented as an adapter, and therefore you pass a Collection as argument to the constructor for the Map, naturally brings with it the question of what should happen if that Collection is initially non-empty. What will happen currently is that eventually you will get a cast error, since whatever elements are in the collection will be cast to an Association. This is probably not as elegant as it could have been. Two solutions are possible. One would be to check for an empty collection in the constructor, and throw an exception if it is not empty. An alternative would have been to pass a class object, an instance of class Class, rather than the collection itself. We could then use the ability for a class to create an instance of itself. But this wouldn't work with all classes (would not work if the constructor for the collection required any arguments) and would require a discussion of class values.

This problem was pointed out by Ron Metoyer.

Errors in the Code

I have more control over the code than over the book, so I'll try to update these in real time as they come in. Here are things that have been spotted:

  • jds.util.CloseQuit was missing. (found by Fredrick Hagberg).

  • PostorderTreeTraversal from chapter 13 is correct in book, was missing three lines in the code. (found by (rm))
  • Acknowledgements

    Raj Babayan, Mathematics Department, California State University, Northridge.

    Dan Chrisman, Jr. Assistant Professor Department of Computer Science Hollins University, Roanoke, Virginia

    Björn Bringert, student at Chalmers University of Technology

    Jiangzhuo Chen, Masters student in CS, Northeastern University.

    Shaun Clark, S-Dog Consulting.

    Prof. Dr. Eberhard Bertsch, Ruhr-Universitat, Bochum.

    Adam Gretzinger, student in Department of Computer Science, Oregon state University

    Alex Kinneer, student in Department of Computer Science, Oregon State University

    Victor Krivonogoff, student in Department of Computer Science, Oregon State University

    Ray Lischner, Tempest Software, Corvallis Oregon

    Bob Martin, Department of Mathematics and Computer Science, Middlebury College

    Ron Metoyer, Assistant Professor, Department of Computer Science, Oregon State University.

    Brian Miller, Student at Oregon State University.

    Eric Mortensen, Assistant Professor, Department of Computer Science, Oregon State University.

    Dr. Michael Olan, Computer Scientist - Educator, Richard Stockton College of New Jersey

    Mian Azhar Sohail, MSC Programme, College of Computer Sciences, Pakistan Engineering Congress, Lahore, Pakistan.

    Hans Sondergaard, Senior Lecturer, The Engineering College of Horsens, Denmark.

    John P. Stoneback, Computer Science Program, Moravian College

    Randy Smith, Associate Professor, Department of Information and Computer Sciences, Covenant College.
    Bob Martin (bm) also found some errors in earlier versions of this errata sheet!