Data Structures and Abstractions with Java (1st ed)
Data Structures and Abstractions with Java
by Frank M. Carrano and Walter Savitch
Errata List for First Edition
Last updated on August 31, 2005.
The date after each error is the date it was posted on this list. Subsequent printings of the book will correct these errors.
If you find an error that is not on this list, please
e-mail a description of the error and the page number.
Inside front cover
Remove "inner" from the list of reserved words. (Nov. 26, 2002)
Chapter 1
Page 10, Segment 1.6 (Mar. 11, 2005)
In the class Name, String should not be bold.
Page 11 (May 11, 2004)
The questions should be numbered 4 through 7.
Page 21, Figure 1-7 (Mar. 11, 2005)
Add the data type double to the definition of PI:
public static final double PI = 3.14159;
Page 26, Exercise 6 (Sept. 3, 2003)
F can be negative. For example, for Sept. 1, 2003, F is -13. Modulo arithmetic produces non-negative results,
so W = -13 (modulo 7) is 1, or Monday. However, Java's % operator produces the remainder after division
instead of a true modulo. Thus, -13 % 7 is -6. To complete the computation, you must add 7 to a negative result:
-6 + 7 is 1.
Chapter 2
Page 50, Segment 2.34 (Mar. 11, 2005)
Replace the argument 2 in the two calls to setDegree with a string such as "B.A."
Page 50, Segment 2.35 (Mar. 11, 2005)
The argument 123456789 in the two calls to Student's constructor should be a string instead of an integer.
Enclose it in quotes: "123456789"
Page 51, Summary, first bullet (Apr. 27, 2004)
Replace the 2nd sentence with
The new class behaves as any other client of the existing classes.
Chapter 4
Page 90, Segment 4.15 (May 4, 2004)
The last two calls to the method add are missing a closing parenthesis. They should read, as follows:
nameList.add(new Name("Tina", "Drexel"));
nameList.add(new Name("Robert", "Jones"));
Chapter 5
Page 110, Segment 5.19 (Mar. 12, 2003)
The comments on the closing braces of the two constructors are interchanged.
The first constructor is the default constructor.
Chapter 7
Page 154, Segment 7.4, Line 5 (Nov. 26, 2002)
Insert the following sentence before "The following sequence of events ..."
"We now invoke nameList.reset() to initialize the iterator. "
Page 156, Segment 7.7, Line 5 (Nov. 26, 2002)
Insert
"and that we invoke nameList.reset()."
before
"Figure 7-2 illustrates ..."
Page 170, Exercise 10 (May 25, 2004)
Replace the first phrase with
Given a list of strings with an internal iterator,
Chapter 8
Page 177, Segment 8.6 (May 26, 2004)
Add the statement
import java.util.Iterator;
as the third import statement.
Page 180 (May 27, 2004)
In the class at the top of the page, the name of the constructor is wrong:
replace IteratorForLinkedList with IteratorForArrayList.
Page 195, top (May 27, 2004)
The method listIterator is in LinkedList as well as ArrayList.
Chapter 9
Page 201, first line (June 5, 2004)
7562 * 421 should be 7562 * 423
Page 209, Segment 9.21 (June 26, 2003)
Add "for a constant k" after the first identity
Page 210, Segment 9.22 (June 26, 2003)
Delete the last sentence.
Chapter 10
Page 253, Project 5 (Jan. 9, 2005)
Revise the third sentence, as follows:
Each of the other lights can be turned on or off only when the preceding light is on and all other lights before it are off.
Chapter 11
Page 259, (July 1, 2004)
The comments for the parameters first and last should be like those
on page 271.
Chapter 12
Page 284, Segment 12.10, Paragraph 3, Line 3 (July 1, 2004)
Change n log n to log n
Chapter 14
Page 326, Segment 14.9, Line 2 (July 1, 2004)
Change LList's to LinkedListBase's
Page 327, Line 1 (July 1, 2004)
Change LList's to LinkedListBase's
Chapter 15
Page 336, Note, Paragraph 2 (July 1, 2004)
Replace the second paragraph with:
String and StringBuffer are a pair of companion classes. String has a constructor that takes an instance of StringBuffer as an argument and produces a mutable string with the same value. StringBuffer has an analogous constructor that creates immutable strings from mutable ones. StringBuffer also has the methods substring and toString that return instances of String.
Page 340, Segment 15.13 (Nov. 26, 2002)
In the definition of the method clone(), make the following changes:
1. Insert "Name theCopy = null;" before "try"
2. Delete "Name" before "theCopy" in the try block
3. Move "return theCopy;" from the try block to immediately after the catch block
Page 348, Segment 15.21 (Nov. 26, 2002)
Replace the sentence that begins "Next, we declare the parameters . . . "
with
Next, we replace occurrences of Object within AList with Listable. We make the same change to ListInterface.
Page 349, Segment 15.22 (Nov. 26, 2002)
Insert the red words into the following sentence, which appears immediately after the Java code:
"We must also define the interface Listable, as we did in Segment 15.21, and replace occurrences
of Object within both the class LList and the interface ListInterface with Listable."
Page 353, Chapter Summary, next-to-last bullet (July 1, 2004)
Replace "and all the objects" with "but not the objects"
Chapter 16
Page 358, Segment 16.6 (July 21, 2004)
In the task comment for the method search, replace anEntry with desiredItem.
Page 373, Line 4 (Dec. 30. 2002)
Replace
index = ceiling((last - first) p)
with
index = first + ceiling((last - first) p)
Chapter 18
Page 395, Segments 18.3 and 18.4 (Aug. 11, 2004)
The discussion and analysis assume that duplicate search keys are allowed.
But this contradicts what we said earlier. To avoid duplicate search keys,
the add operation must search the array, making add an O(n) operation.
Page 396, last line (Aug. 11, 2004)
Replace "dictionary" with "array".
Pages 403 and 404, Segment 18.13 (Aug. 11, 2004)
The discussion and analysis assume that duplicate search keys are allowed.
But this contradicts what we said earlier. To avoid duplicate search keys,
the add operation must search the array, making add an O(n) operation.
Page 405, Segment 18.15 (Nov. 26, 2002)
Replace SortedDictionary with SortedLinkedDictionary
three times in the bottom third of the page
(once in the sentence before the code and
twice in the definition of the class).
Page 406, 12th line of code (Aug. 11, 2004)
Replace
result = currentNode.getKey()
with
result = currentNode.getValue()
Page 406, Segment 18.16 (Nov. 26, 2002)
Replace SortedDictionary with SortedLinkedDictionary twice in the second paragraph.
Page 408, First bullet at top of page (Aug. 11, 2004)
Replace O(1) with O(n) twice.
Chapter 19
Page 440, Segment 19.38 (Aug. 31, 2005)
In the algorithm probe, insert
index = next probe index
before the first close brace.
Page 442, Segment 19.38 (Nov. 26, 2002)
Insert
index = (index + 1) % hashTable.length; // linear probing
just before the first close brace on the page, aligned with the "if" in the first line.
Chapter 20
Page 464, Segment 20.18 (Nov. 26, 2002)
Insert an asterisk at the beginning of Line 7 of the definition of the class Postfix.
Chapter 22
Page 492, Segment 22.3 (Nov. 26, 2002)
"queueInterface" should be "QueueInterface" twice, at the beginning and end of the interface definition.
Page 495, Figure 22-4 (Oct. 18, 2004)
In the last line under Responsibilities, replace "amd" with "and"
Page 506, Segment 22.18 (Nov. 26, 2002)
We assume that Date is a Comparable class that represents a date.
The Java Class Library contains a class Date,
but it is not Comparable. To avoid confusion, it would be better to give our class a different name.
Chapter 23
Page 523, Top of page (Oct. 18, 2004)
In Question 3, replace "bottom of queue" with "back of queue"
Page 523, Segment 23.18 (Aug. 31, 2005)
In the second line of code, queueInterface should be QueueInterface.
Chapter 24
Page 544, Segment 24.8 (April 12, 2004)
In the last paragraph, replace the first sentence with
"When a binary tree of height h has all of it leaves at level h, and every nonleaf has exactly two children, the tree is said to be full."
Page 545, Note at top of page (April 12, 2004)
Replace the first sentence with
"All leaves of a full binary tree occur on its last level, and each of its nonleaves has exactly two children."
Page 551, Segment 24.19 (May 7, 2003)
In BinaryTreeInterface, insert "Task:" between /** and "Sets" two times
Page 556, Segment 24.25, Line 9 (Oct. 27, 2004)
"Is it in Europe?" should be bold.
Page 564, Summary (April 12, 2004)
Replace 5th bullet with
"In a full binary tree, the nodes at all levels before the last have two children each. Thus, a full binary tree of height h has as many nodes as possible among all binary trees of height h."
Chapter 25
Page 575, Segment 25.7 (Nov. 26, 2002)
Change the segment heading to
"Another approach, more problems."
Page 576, Segment 25.8 (Nov. 26, 2002)
Change the segment heading to
"The second solution."
Page 584, Segment 25.17 (Oct. 27, 2004)
Add the following clause at the end of the first line of code:
implements ExpressionTreeInterface
Chapter 26
Page 622, Segment 26.40 (Dec. 8, 2002)
In addition to the methods getkey, getValue, and setValue, the class Entry must also define the method equals.
Chapter 27
Page 635 (May 7, 2003)
In Figure 27-6a, delete the leaf that contains 30.
Page 639, Segment 27.17 (Nov. 9, 2004)
In the for statement, replace n/2 with n/2 - 1.
Page 641, Segment 27.18 (Nov. 9, 2004)
In the first for statement, replace n/2 with n/2 - 1.
You also need to change the two statements in reheap that assign values to largerChildIndex. In each case, this value should be 2 * first + 1 since the heap begins at index 0 instead of 1. (See Exercise 1.)
Page 642 (Nov. 26, 2002)
Add Project 3:
Use a binary search tree in the implementation of MaxHeapInterface.
Where in the tree will the largest entry occur?
How efficient is this implementation?
Chapter 28
Page 645, Segment 28.2, 3rd sentence (Nov. 19, 2004)
Change "from h to h + 1" to "by 1"
Page 668, Figure 28-35 (Nov. 19, 2004)
Exchange the letters p and g in each part of the figure.
Page 669, Figure 28-37 (Nov. 19, 2004)
Exchange the letters p and g in each part of the figure.
Chapter 30
Page 708, Segment 30.15 (Jan. 19, 2005)
In the constructor, change SortedDictionary to LinkedDictionary.
Appendix A
Page 724, Segment A.18, eight lines before the Note (March 12, 2003)
Change
"... operator - with any of the operators +, *, or /, ..."
with
"... operator - with any of the operators +, *, /, or %, ..."
Page 724, Segment A.18, seven lines before the Note (March 12, 2003)
Change
"The operator % is used only with integers, ..."
with
"The operator % is used typically with integers, ..."
Appendix C
Page 785, Line 10 (Jan. 31, 2005)
Replace openOutputFile with openFile:
openFile("data.txt", outStream);
Appendix E
Page 805 (May 27, 2004)
Replace the answer to Question 5 of Chapter 8 with
while (traverse.hasNext())
traverse.next();
while (traverse.hasPrevious())
System.out.println(traverse.previous());
Page 807 (June 9, 2004)
Replace the answer to Question 8a of Chapter 10 with
t(n) = 1 + t(n - 1) for n > 0, t(0) = 1.
Page 808 (Aug. 31, 2005)
Replace the answer to #3 with
No; insertInOrder links the node to be inserted into the sorted part of the chain so that the node no longer references the rest of the unsorted part. Since unsortedPart still references the inserted node, executing the line in question next would make unsortedPart either reference a node in the sorted part or be null.
Page 810, #5 at top of page (July 1, 2004)
Replace maxDigits with wordLength
Page 811, #3 (Aug. 31, 2005)
Insert
length++;
before the closing brace.
Page 813, Last line (July 21, 2004)
Replace dictionary.Brittany);
with
dictionary");
Page 814, 3rd line of code (July 21, 2004)
Replace dictionary.Brittany);
with
dictionary");
Page 814, Last line of code in answer to Question 5 (July 21, 2004)
Replace // end replace
with
// end changePhoneNumber
End of Errata List