Errata

Back Cover

The following items from the list of website contents require a password: The Web Book, Lecture Transparencies.

The following items from the list of website contents are not available: Complete Text, LaTeX Source.

Page 26

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

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

Page 28

The first line of the second block of equations should read,

T(2^k)=18k+T(1)

Page 35

The second sentence of the last paragraph of Section 3.1.1 should read,

For example, c=2 and will do, ...

Page 35, Figure 3.1

The rightmost thin blue line should be labeled f(n)=n².

Page 42

The last sentence in the first paragraph of the Inductive Hypothesis should read,

Using L'Hôpital's rule we see that

Page 44

The second sentence should read,

``For example, consider f₁(n)=n²+1 and f₂(n)=n. ''

The fourth sentence should read,

``Clearly too, f₁(n)>=f₂(n) for all values of n>=0!''

Finally, the last sentence of the paragraph following Fallacy 3.5 should read,

``Clearly too, since f₁(n)>=f₂(n) for all values of n>=0, there does not exist any value n₀>=0 for which f₁(n₀)<=f₂(n₀).''

Page 46

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 78, Program 4.10

In line 3 of the program, next should be _next.

Page 85

Last sentence of Section 4.2.11 should read,

``Therefore, the running time of the InsertBefore member function is T<T::T(T&)>+O(n).''

Page 97

The first sentence of the third paragraph of Section 5.2.1 should read,

An abstract class is intended to be used as the base class from which other classes are derived.

Page 110

The first sentence of the last paragraph should read,

``The observant reader will have noticed in Program 5.11 that the Visit member function of the abstract Visitor class is a pure virtual function, whereas the IsDone function is not.''

Page 127, Figure 6.2

The label Pop->8 should be Pop()->8 and the final stack configuration should be

|   |
|___|
| 7 |
|___|
| 2 |
|___|

Page 142, Figure 6.4

The first Enqueue should be Enqueue(1).

Page 144

In the second-last paragraph on the page, the last two sentences should read,

``The second is to use another member variable, count, to keep track explicitly of the actual number of elements in the queue rather than to infer the number from the head and tail variables. The second approach has been adopted for implementation below.''

Page 195, Program 7.28

Line 12 of the program should read,

double Term::Coefficient () const

Page 213

The last sentence of the first full paragraph should read,

However, the more significant deficiency of this function is that it cannot deal with strings of arbitrary length.

Page 229

Lines 23-24 of Program 8.15 should read,

unsigned int probe = H (object);
if (array[probe].object == 0)
    return NullObject::Instance ();
for ( ; probe != Entry::null; probe = array [probe].next)

Page 260

The first sentence following the proof of Theorem 9.2 should read,

An interesting consequence of Theorem 9.1 and 9.2 is that the maximum number of external nodes in an N-ary tree of height h is given by

Page 284

Line 1 of Program 9.14 should read,

bool NaryTree::IsEmpty () const

Page 320

The second-last sentence of the second paragraph of Section 10.5.2 should read,

Assuming that the item is not already in the tree, the search is unsuccessful and terminates at an external, empty node.

Page 321, Figure 10.7

The extension lines in part (c) are misleading. Here is the revised figure:

Page 323, Figure 10.8

The height of the tree B_R in part (a) of the figure should be h-1. Also, the extension lines in parts (a), (b), and (c) are misleading. Here is the revised figure:

Page 331

The first sentence of the second paragraph should read,

Consider the execution of the Find function for a node T of a an M-way search tree.

Page 341, Figure 10.12

The keys 2 and 3 are reversed in the third and fourth trees from the top of the figure. Here is the revised figure:

Page 351

The first sentence of the second paragraph should read,

Program 11.1 gives the declaration of the PriorityQueue abstract class.

Page 509

The first sentence should read,

Consider an arbitrary sequence S={s₁,s₂,s₃,...,s_n} comprised of of n>=0 elements drawn from some universal set U.

Page 520

The third-last sentence of the paragraph before Section 15.4.2 should read,

Since only adjacent elements are swapped, bubble sort removes inversions one at a time.

Page 548

In equation (15.11) "count[i]" should read "count[j]".

Page 549, Figure 15.13

The element "98" in the top row of the figure should be "93". Here is the revised figure:

Page 581

The equation last equation on the page should read S'''={a,c,f,b,e,d,h,g,i}.

Page 605, Program 16.16

Line 20 of the program should read,

Vertex& v1 = edge.Mate (v0);

and line 24 should read,

if (!table [v1].known && table [v1].distance > d)

Page 611, Equation 16.3

The min should be max.