Errata

Back Cover

In the list of website contents, it should be indicated that a password is required to access The Web Book.

Page 18

The sixth line on the page should read

Line 8 of Program 2.4 is only executed if a_i is the largest of the i+1 values a₀, a₁, ..., a_i.

Page 27

The program fragment following the first paragraph in Section 2.2.5 should read,

int result = 1;
for (int i = 0; i < n; ++i)
    result *= x;

Page 42

Just above the horizontal rule the equation for f(n) should read .

Page 47

The first sentence of Section 3.2.1 should read

Consider the function f(n)=5n²-64n+256, which is shown in Figure 3.2.

Page 47

The third sentence of the last paragraph in Section 3.2.1 should read

Figure 3.2 clearly shows that the function f(n)=n² is less than the function f(n)=5n²-64n+256 for all values of n>=0.

Page 48

The caption on Figure 3.2 should read

Showing that .

Page 51, Table 3.2

The detailed model formula for 6b should read

(2T_fetch+T_<)*(n+1)

and the detailed model formula for 6c should read

(2T_fetch+T_-+T_store)*n

Page 60, Figure 3.3

The labels on the two curves, "Program 3.3" and "Program 3.4", are reversed.

Page 62

The fourth line should read so we cannot conclude in general that we should use algorithm A rather than algorithm B to solve a particular instance of the problem.

Page 80, Program 4.12

Line 22 of the program should read

sum += array[i][k] * arg.array [k][j];

Page 103

The ninth line should read

Because the String class does not implement the Comparable interface and because the String class cannot be extended, we are forced to implement a wrapper class.

Page 129

The sentence below Figure 6.9 should read

Assuming that the exception that is raised when pop is called on an empty list does not occur, the running time for pop is O(1).

Page 134

The first line should read

the while loop is executed n times.

Page 137

The ninth line should read

Finally, Figure 6.5(d) shows if the queue is empty, the head position will actually be to the right of the tail position.

Page 148

The eighth line should read

Program 6.25 defines the getTail, enqueueTail, and dequeueTail methods of the DequeAsLinkedList class.

Page 160

The third line of the program fragment following the second paragraph should read

OrderedList list = OrderedListAsArray (1);

Page 163

The second sentence of the second paragraph should read

The findPosition uses the isNE method to locate a contained object that is equal to the search target.

Page 219

The fifth sentence of the third paragraph should read

The item there, "åtta", does not match either.

Page 259

The equation between the third and fourth paragraph on the page should read

a, /, b, +, c, -, d, *, e.

Page 269

The last sentence on the page should read

The running time for nextElement is O(d), where d is the degree of the tree node found at the top of the stack.

Page 353

Definition 11.3, part 2 should read

(a) T_i is a perfect N-ary tree of height h-1 for all i: 0 <=i<j;
(b) T_j is a complete N-ary tree of height h-1; and
(c) T_i is a perfect N-ary tree of height h-2 for all i: j<i<N.

Page 507

The derivation at the top of the page should read

.

Page 548

The first sentence of the first paragraph should read

The getPredecessors method returns an Enumeration that enumerates the elements of and the getSuccessors method returns an Enumeration that enumerates .

Page 594

Exercise 16.2 should read

Consider the undirected graph G_A shown in Figure 16.24.