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.
>

Chap	Page	line	Comment	Contributor
1	10	-2	n should be val, also on next page	(js)
1	11	2	printInt(out, n/10); // two parameters	(hs)
1	11	3	Missing right parenthesis	(hs)
2	24	-2	integer=>int	(bb)
2	27	20	insertAndExtract => getAndSet	(js)
2	33	7	can invoked => can be invoked	(vk)
2	37	-18	should extend Collection or Bag
2	37	-18	arguments could be Bag, not Set
2	39	7	description backwards, -1 if left is smaller, not larger	(ms)
2	47	-10	removeElement should not return anything	(js)
3	55	1	code doesn't work without default	(js)
3	56	-8	printInt should have two arguments	(hs)
3	59	4	assert greater than, not >=	(brm)
3	66	Ex 6	Should have first asked to prove time is O(2^n).
4	71	10-11	for all and exists reversed, correct on p. 92	(hs)
4	77	19	n2+n => n2-n	(em)
4	80	12	m[i,j] should be m[i][j]	(rb)
5	114	Ex 13	Chapter 9? What was I thinking???
6	119	-15	index should begin at 1, not 2	(ms)
6	121	-12	addElement(...) => addLast(...) (vectors don't have addElement)	(rs)
6	125	3	getLast throws ArrayIndexException, interface specifies NoSuchElementException	(rl)
6	127	Box	Visitor not in source? (see comments below)	(rm)
6	147	Ex 11	16 should be 26, so as to force two reallocations.
6	148	Ex 14	Problem is, this version of bubble sort IS stable
7	160	code	should use comparator instead of equals (see below)	(mo)
7	179	Ex 2	10,000 should be 1,000
8	193	1	Insert should return new link (correct in code library)	(rm)
8	202	code	Variables x and y should be private	(dc)
8	204	-6	class Asteroid is unnecessary	(dc)
8	206	6	extend => extends	(dc)
8	214	Ex 11	Assume all elements are unique (much harder otherwise)
8	214	PP 6.b	Can't clone the individual elements (see below)	(rm)
9	228	4	insert may be confusing (see below)	(eb)
9	230	code	use equals or compare (see below)	(mo)
10	258	Fig 5	que is incongruous name for a stack
11	290	Ex 6.h	addElement => addElementAt	(sdog)
12	315	2	constructor should be public	(sdog)
12	316	12	addList=>addLast	(sdog)
12	319	-8	for consistency, should assign getfirst to variable	(ag)
13	341	16	need cast: current = (BinaryNode) stk.getLast();
13	341	17	recursive call needs guard, if (current.rightChild) != null	(js)
14	348	16	result=>res	(mo)
14	349	3	add stk.removeLast()	(mo)
14	360	getFirst	root.getFirst returns a node, need to get value	(ak)
14	379	Ex 6	Exercise 6 is same as exercise 3
14	381	-10	root is deleted=>current node is deleted	(jc)
15	393	-8	need to add ``if (max != 0)'' before loop	(sdog)
15	404	-8	less than should be less-or-equal	(dc)
15	407	3	DefaultComparator is now in java.util.DefaultComparator
17	464		what to do with non-empty collections (see below)	(rm)
17	473	Ex 4.c	Good luck. Doesn't parse
18	481		Arguments to union/intersection could be any Bag
18	489	2	Can return immediately when sentinel is encountered
18	503	Ex 10	should ask first if subset is less than or less-than-equal
19	527	Ex 2	Question doesn't make sense since matrix is an interface not a class
19	527	Ex 4	Should give a hint (see below)
B	573	-1	Comparator is now java.util.Comparator
B	583	3	DefaultComparator is now java.util.DefaultComparator
20	555	Ex 7	Need to specify a starting vertex
	593		Entry 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

(rb)

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

(dc)

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

(bb)

Björn Bringert, student at Chalmers University of Technology

(jc)

Jiangzhuo Chen, Masters student in CS, Northeastern University.

(sdog)

Shaun Clark, S-Dog Consulting.

(eb)

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

(ag)

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

(ak)

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

(vk)

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

(rl)

Ray Lischner, Tempest Software, Corvallis Oregon

(bm)

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

(rm)

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

(brm)

Brian Miller, Student at Oregon State University.

(em)

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

(mo)

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

(ms)

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

(hs)

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

(js)

John P. Stoneback, Computer Science Program, Moravian College

(rs)

Randy Smith, Associate Professor, Department of Information and Computer Sciences, Covenant College.