Errata for Edition 3.2 of
Data Structures and Algorithm Analysis
by Clifford A. Shaffer

A list of corrections to the printed version (Edition 3.2).

Java

P14, L8 of Section 1.3.3: "Each action such method" -> "Each such action method".

P24, end of first paragraph, last two paragraphs should read: Finally, the set {5, 3, 2} is indistinguishable from set P, because sets have no concept of order. Likewise, set {2, 3, 2, 5} is also indistinguishable from P, because sets have no concept of duplicate elements.

P51
Exercises 2.42 through 2.46: Add at the end the sentence "Explain how you got your answer."

P54
Line 6: "Therefor" -> "Therefore"

P58
In Table 3.2 on the first line, under the \(n \log n\) column the entry should read: \(4 \cdot 2^{4} = 2^{6}\)

P64
On the last line preceding Example 3.4, "executes in less than" should be "executes in less than or equal to".

P69
For Example 3.8, the definitions for f(n) and g(n) should be reversed.

P87
In exercise 3.12(g), line 3 should read:
A[j] = DSutil.random(n);

P103
Figure 4.6, Caption line 1: "one node head" -> "one node ahead".

P104
Line 6: cnt should be private

P128
Line 21: Method size -> Member maxSize
Line 22: Member -> Method
Line 23: position of the rear element. -> position of the current rear element, while front is the position of the current front element.
Last paragraph, line 2: Methods -> Members

P130
Line 5: size should be private

P138
Line 16: "for for" -> "for"

P140
Exercise 4.11, add at end of directions: State when the linked list needs less space than the array.

P150
In last line, replace "pointer" with "reference".

P151
In second line, replace "pointer" with "reference".
In function preorder2 there are two calls to function preorder that should be replaced by calls to preorder2.
In the middle of the page within the text there are two occurrances of the variable name root that should instead be rt.

P160
In the paragraph that begins "Great savings...", add after the first sentence the following: "Again assume the tree stores a reference to the data field." In the next sentence, replace "overhead" with "child pointers".
On the last line, change "only a data field" to "only a reference to a data field". Change "\(2Pn + D(n+1)\)" to be "\(\frac{n}{2}2P + \frac{n}{2}(P+D)\)"

P161
On the top line, change "about \(2P/(2P + D) = 2/3\)" to "\(3P/(3P + D) = 3/4\)"

P165
Line 5 should read:
private int nodecount; // Number of nodes in the BST

P172
In the last paragraph at the start of the third line the old version says \Theta(n \log n). This should be \Theta(\log n).

P189
In both Exercises 5.10 and 5.11, change "BST" to "binary tree".

P226: In code change "Sort" -> "inssort"
P228: In code change "Sort" -> "bubblesort"
P229: In code change "Sort" -> "selectsort"
P233: In code change "Sort" -> "shellsort"

P282
Line 7, change "the implementations for class BufferPool above does" -> "these implementations for the buffer pool ADT do"

P308
Second equation of Example 9.1 should read:

P379
Line 5: Mark should be private

P381
Line 5: Mark should be private

P385
Figure 11.9, rightmost panel in top row: caption should read "call DFS on B"

P389
Line 8 in comment, "v2's" -> "v's".

P394
In the middle of the page, there are 4 lines of code. In each place that currently has G->weight it should be G.weight

P420
Line 6 of "Other Memory Allocation Methods": "stack" -> "queue".

P509
4th line from the bottom: n^1.62 should be 1.62ⁿ

P510
Replace function fibrt as follows:

int fibrt(int n) {
  // Assume Values has at least n slots, and all
  // slots are initialized to 0
  if (n <= 2) return 1; // Base case
  if (Values[n] == 0)
    Values[n] = fibrt(n-1) + fibrt(n-2);
  return Values[n];
}

P511
Section 16.1.1, Paragraph 2, Line 7: "exactly with the first and third items." should be "exacty with the second and third items."

P533
Added Exercise 16.11.

C++

P14, L8 of Section 1.3.3: "Each action such method" -> "Each such action method".

P26, end of first paragraph, last two paragraphs should read: Finally, the set {5, 3, 2} is indistinguishable from set P, because sets have no concept of order. Likewise, set {2, 3, 2, 5} is also indistinguishable from P, because sets have no concept of duplicate elements.

P53
Exercises 2.42 through 2.46: Add at the end the sentence "Explain how you got your answer."

P56
Line 6: "Therefor" -> "Therefore"

P60
In Table 3.2 on the first line, under the \(n \log n\) column the entry should read: \(4 \cdot 2^{4} = 2^{6}\)

P66
On the last line preceding Example 3.4, "executes in less than" should be "executes in less than or equal to".

P70
For Example 3.8, the definitions for f(n) and g(n) should be reversed.

P88
In exercise 3.12(g), line 3 should read:
A[j] = Random(n);

P105
Figure 4.6, Caption line 1: "one node head" -> "one node ahead".

P123-151
After version 3.2.0.9, there is substantial page layout revision to remove a largely blank page in the original Edition 3.2 printing.

P132
Line 33: Method size -> Member maxSize
Line 34: Member -> Method
Line 35: position of the rear element. -> position of the current rear element, while front is the position of the current front element.

P134
First paragraph, line2: Methods -> Members

P134
Linked Queue clear method should be modified as follows:

  void clear() {                 // Clear queue
    while(front->next != NULL) { // Delete each link node
      rear = front;
      front = front->next;
      delete rear;
    }
    rear = front;
    size = 0;
  }

P144
First line of text: "for for" -> "for"

P146
Exercise 4.11, add at end of directions: State when the linked list needs less space than the array.

P157
In the first full paragraph there are three occurrances of the variable name rt that should instead be root.

P166
About 2/3 of the way down the page, change "A commonimplementation" to "A common implementation".
In the last paragraph, which begins "Great savings...", add after the first sentence the following: "Again assume the tree stores a pointer to the data field." In the next sentence, replace "overhead" with "child pointers".

P167
On the third line of the first full paragraph, change "only a data field" to "only a pointer to a data field".
Change "\(2Pn + D(n+1)\)" to be "\(\frac{n}{2}2P + \frac{n}{2}(P+D)\)"
Change "about \(2P/(2P + D) = 2/3\)" to "\(3P/(3P + D) = 3/4\)"

P182
In the first full paragraph at the start of the third line the old version says \(\Theta(n \log n)\). This should be \(\Theta(\log n)\).

P197
In both Exercises 5.10 and 5.11, change "BST" to "binary tree".

P290
Line 7, change "the implementations for class BufferPool above does" -> "these implementations for the buffer pool ADT do"

P318
Second equation of Example 9.1 should read:

P366
Change this line of code:

else if (rkey < it->lkey) { // Add center

to be

else if (rkey > it->lkey) { // Add center

P399
Line 8 in comment, "v2's" -> "v's".

P395
Figure 11.9, rightmost panel in top row: caption should read "call DFS on B"

Figures 11.17 (P401), 11.18 (P403), 11.21 (P405), and 11.22 (P406) have each had three lines added to initialize the values in the D array. This was done to make the algorithms a bit clearer. Note that these changes affect the page numbers for the rest of the book.

P428
Line 6 of "Other Memory Allocation Methods": "stack" -> "queue".

P517
4th line from the bottom: n^1.62 should be 1.62ⁿ

P518
Replace function fibrt as follows:

int fibrt(int n) {
  // Assume Values has at least n slots, and all
  // slots are initialized to 0
  if (n <= 2) return 1; // Base case
  if (Values[n] == 0)
    Values[n] = fibrt(n-1) + fibrt(n-2);
  return Values[n];
}

P519
Section 16.1.1, Paragraph 2, Line 7: "exactly with the first and third items." should be "exactly with the second and third items."

P541
Added Exercise 16.11.