If you find further errors, please drop me a line by email.
I enjoy corresponding with readers!
--Michael Main
(main@colorado.edu)
Page 46, line 2: "When your write" is changed to "When you write".
Page 67, Figure 2.13: Add a return at the end: return sqrt(c_squared);
Page 73, by the arrow at the top of the page: Change "istream" to "ostream"
Page 84, bottom of column 1: Change the 90 degrees in the headings to "theta"
Page 88: The exercise does produce an approximate Gaussian distribution,
but the properties are all wrong! The formula should use the standard
deviation (not the variance). For a better approximation: generate 12 random
numbers in the range [0...1) and add the median to the value:
(std dev) * (r1 + r2 + r3 + r4 + r5 + r6 + r7 + r8 + r9 + r10 + r11 + r12 - 6)
Page 154, two lines above the box, should be: "Cumbersome syntax of *&"
Page 157, Sample Dialogue at the bottom of the Figure:
The correct prompt (7 lines from the end) is:
Please type 3 double numbers:
Page 179: The quotation is from P.J. Plauger (not P.L. Plauger).
Page 222, line 4: "list_locate" is changed to "list_search"
Page 229, list_clear prototype: first parameter is Node*& (rather than Node&)
Page 243, Figure 5.12:
The test in the if-statement should be: if (target_ptr == NULL)
Page 250:
The operator += implementation has a bug for the case when addend is empty.
Here's a corrected implementation:
void Bag::operator +=(const Bag& addend)
// Library facilities used: stdlib.h
{
Node *copy_head_ptr;
Node *copy_tail_ptr;
if (addend.many_nodes > 0)
{
list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
copy_tail_ptr->link = head_ptr;
head_ptr = copy_head_ptr;
many_nodes += addend.many_nodes;
}
}
Page 254, DNode definition:
The backlink and forelink should be pointers to DNode, as shown here:
struct DNode
{
typedef ______ Item;
Item data;
DNode *backlink;
DNode *forelink;
};
Page 272: There should be no semi-colon after the maximal implementation.
Page 297: The remove_current function is a member function, so it needs
Bag<Item>:: in front of the function name.
Page 342, Answer to Self-Test Exercise 6 is inaccurate. Here's a better answer:
A stack overflow can occur if the input expression has parentheses that are
nested too dieeply. For example, consider the input expression
(1 + (2 + (3 + (4 + 5)))). By the time the 5 is read and pushed onto the
stack, the 1, 2, 3 and 4 are already on the numbers stack. Thus, there is a
limit to how deeply we can nest this kind of subexpression without
overflowing the stack.
Page 342, Answer 12: Reference should be Figure 7.10 on page 334.
Page 356, Figure 8.5:
The third line in the if-statement of Step 2 should use this arithmetic
expression: (current_second - next)
(This replaces next - current_second).
Page 369: The second line of the figure says "Stack", but this is a Queue!
Page 384: Solution to #18 should have queues[priority].insert(entry);
Page 394: At the bottom of the page, the activation record is the THIRD call
to super_write_vertical (not the second).
Page 410, 5 lines from the bottom: Change "2.0" to "3.0".
Page 417, Solution number 3:
Each of these lines: cout << "Hip";
is changed to this: cout << "Hip" << endl;
Page 420, end of 2nd column:
The final asterisk is moved right to align with the end of the previous line.
Pages 450, 451, 486: leaf_ptr does not need to be a reference parameter.
Page 451, Problem 7: The limits for the example should be 1 and 3 (rather
than 1 and 4), and the final value of a[4] is upper-case 'E'.
Page 455, line 11: Change the line to: cout << node_ptr->data << endl;
Page 464, Exercise 11: Change "numbers" to "letters".
Page 466, Documentation for the print function should have the template prefix:
template <class Item, class SizeType>
void print(BinaryTreeNode<Item>* node_ptr, SizeType depth)
Pages 476-477, all four tree diagrams: Change the upper 54 to 53.
Page 516, Step 1 of pseudocode should have: data[i] >= target.
Page 519, line 7: Change "data_count" to "child_count".
Page 520: Change the 12 (in both trees) to 16. Otherwise they are not b-trees!
Page 543: The formula in the box needs an extra +1: H(n) = |_ log2 n_| + 1
Page 557, 2 lines from the bottom: Change "never_used" to "is_vacant".
Page 566, 3rd column of the figure: Change 1,72 to a decimal point 1.72
Page 568, Solution to Exercise 12: The line used++ should be total_records++;
Page 594: The formulas at the top of the page should have
FOUR n/4 arrays and EIGHT n/8 arrays.
Page 616: Answer 9 is missing a bracket: (k>0 && data[k] < data[parent(k)]).
Page 617, Exercise 4: Change sections 2b and 2c as given here:
2b. If the area before the pivot index has more than one element, then
we must sort this area. This area begins at data[i] and has
pivot_index elements, so push i and pivot_index onto the stack.
2c. If the area after the pivot index has more than one element, then
we must sort this area. This area begins at data[i+pivot_index+1]
and has n - pivot_index - 1 elements, so push i+pivot_index+1
and n - pivot_index - 1 onto the stack.
Page 617: The four function calls at the bottom of Project 5 need two more
parameters; for example: heapify_subtree(data, 4, 10);
Page 649: The right figure title is "Pond Simulation Dialogue".
Page 650, Problem 8: The new rate is 2 ounces per week (not per weed!).
Page 650, end of Exercise 11: Change the if statement to:
if (rand( )/double(RAND_MAX) < chance)
(also set the word "if" in italic).
Page 660, Solution 11:
Use italic for the two "if"s, and change "MAX_RAND" to "double(RAND_MAX)".
Page 697-698: The call to rec_dfs in the middle of 697 needs parameters:
rec_dfs(f, g, neighbors.current(), marked);
Also, both pages must change NeighborIterator to NeighborIterator<Item>.
Page 705, halfway down: distance[3] should be distance[2].
Page 714, fourth line of first column should be: edges = new (bool*)[n];
Page 727: The three calls to setf should have a comma after the first
argument (not a semi-colon).
Page 728: Change "cout.setprecision(12);" to "cout.precision(12);"
and, in the last paragraph of "Precison of Float and Double Numbers":
Change "setpoint" to "showpoint"
Page 738, first line of the Header File: Change "item.h" to "items.h"
Page 739, in the precondition after the third shaded box:
Change "0 <= i < n" to "0 <= i <= n".
Page 740, just before the indentation begins, insert a new line:
#include <stdlib.h> // Provides size_t from stdlib.h
Page 743, line 6: Change "SizeType(i+1)" to simply "i+1".
Page 731, the eat_white implementation near the top of the page:
The while loop should be: while (cin && isspace(cin.peek( )))