Data Structures, Algorithms, & Applications in C++
Errata 1

1. Page 17, line -2. follwoing -> following Pages 18 & 19, program line 9. int -> T
2. Page 20, line -8. types such -> types such as
3. Page 21, line 21. can show -> can let
4. Page 25, Program 1.17, line -3. 0.005 -> 0.001
5. Page 38, line -12. /2a -> /(2a) and sqrt(-d) -> sqrt(-d)/(2a)
6. Page 59, line -1. Equation 2.3 -> Equation 1.3
7. Page 60, Program 2.6, line 5. n+1 -> n
8. Page 67, line -1. in the worst -> , and in the worst
9. Page 68, line 2. polgon -> polygon
10. Page 78, Example 2.23. The codes should declare the loop variable i outside of the loop. This increases the best-case, worst-case, and average step counts by 1.
11. Page 91, line -12. n(m+1)+2 = Theta(mn) >- 2n+2 = Theta(n)
12. Page 91, line -11. t_Add(m,n) = 2mn+2n+1 = Theta(mn) >- t_Add(rows,cols) = 2rows * cols + 2rows + 1 = Theta(rows * cols)
    t_Transpose(n) = (n-1)(4n+2)/2 = Theta(n^2) >- t_Transpose(rows) = rows^2 + rows + 1 = Theta(rows^2)
13. Page 95, Figure 2.22. Total steps for return i should be the same as the frequency.
14. Page 95, line -2. invariant >- following invariant
15. Page 102, line 5. 486 >- a 486
16. Page 102, line 4. data space >- statically allocated
17. Page 139, line -10. for -> while
18. Page 143, Exercise 29(a), line 5. two input -> input
19. Page 144, Exercise 35, line 2. Your -> You
20. Page 145, Exercise 42. Should be: Write a nonmember function to reverse a circular list with a head node. See Exercises 28 and 36.
21. Page 145, Exercises 44-46. Delete second sentence.
22. Page 145, Exercises 54 & 55. Delete line 2.
23. Page 145, Exercise 56. Delete lines 2 and 3.
24. Page 161, Exercise 69, line 3. SimSpace -> SimNode
25. Page 178, line -7. Remove the sentence The code for ...
26. Page 180, lines 11, 14 and 15. All occurrences of size[] should be node[].size
27. Page 184, Ex. 77, line 2. 3.48 -> 3.44
28. Page 208, line -18. To go the -> To go to the
29. Page 226, line 24. repsentation -> representation
30. Page 227, line 15. int [rows + 1]<\code> >- int [cols + 1]
31. Page 231, line -8. input >- result
32. Page 234, line -8. delete (column i) + loop >- loops
33. Page 238, line 12. desribed -> described
34. Page 265, line -2. do >- for
35. Page 281, Exercises 20-22. Programs 3.13 and 3.14 -gt& Program 3.13
36. Page 310, Example 6.2. The number of jobs is 4 (not 6) and the wait time on machine 2 is 3 (not 0).
37. Page 311, Figure 6.14(b). In the line for time 15, 16 should be 19. In the line for time 16, C C I 19 should be C 3 I L; and there should be a new line with time 17 whose entries are - - - I 3 I L 19 L
38. Page 329, line 8. DistintInsert -> DistinctInsert
39. Page 386, line 3. element, -> element.
40. Page 390, Exercises 9 through 12. Do Exercise 1 -> Do Exercise 8
41. Page 390, Exercises 13 and 14. structure -> class
42. Page 401, line -5. Replace the line
    if (D(j) + d(j)) > tolerance) place a booster at j;
    with the line
    if (D(j) + d(j)) > tolerance) place a booster at j and update D(i);
43. Page 404, Program 8.14.

    void PlaceBoosters(BinaryTreeNode<Booster> *x)
    {// Compute degradation at *x.  Place booster
     // here if degradation exceeds tolerance.
       BinaryTreeNode<Booster> *y = x->LeftChild;
       int degradation;
       x->data.D = 0;  // initialize degradation at x
       if (y) {// compute from left child
               degradation = y->data.D + y->data.d;
               if (degradation > tolerance)
                  {y->data.boost = true;
                   x->data.D = y->data.d;}
               else x->data.D = degradation;
              }
       y = x->RightChild;
       if (y) {// compute from right child
               degradation = y->data.D + y->data.d;
               if (degradation > tolerance)
                  {y->data.boost = true;
                   degradation = y->data.d;}
               if (x->data.D < degradation)
                  x->data.D = degradation;
              }
    }
    

44. Page 415, Exercise 35, line 2. tree different -> tree is different
45. Page 415, Exercise 37. PostPrint -> PostOutput
46. Page 421, line 10. Eqation -> Equation
47. Page 421, lines 2 and 10. 2.1 -> 3.1
48. Page 429, Program 9.4, line 9. restucture -> restructure
49. Page 429, Program 9.4, line 18. [ci] -> [c]
50. Page 430, Program 9.5, line 19. [c]? -> [c/2]?
51. Page 441, line -1. n > 1 > n > 0
52. Page 446, line 20. This line should be set in black.
53. Page 456, line 3. (x,y) -> (x,e)
54. Page 456, Exercise 20, line 2. to a -> the
55. Page 457, Exercise 21, line 2. correction -> correctness
56. Pages 466-468. The symbol s used in the text does not agree with the variable s used in Program 10.3. The variable in the program is 2^{symbol in text}.
57. Page 472, Exercise 3, line 2. necessary matches -> matches that are necessary.
58. Page 474, line -4. 8.5.2 -> 9.5.2
59. Page 488, line -11. 11.3 ->& 11.5
60. Page 490, ADT 11.1, line -2. Output -> output
61. Page 491, ADT 11.2, line -2. Output -> output
62. Page 491, last sentence. to make BSTree ... -> to either make BSTree a friend of BinaryTree or make root a protected member of BinaryTree.
63. Page 496, Section 11.1.7, line 4. . No other changes are needed. -> and by changing the line
    if (e < pp->data) pp->LeftChild = r;
    to the line
    if (e <= pp->data) pp->LeftChild = r;
    
64. Page 498, Exercise 2, line 1. DBSTree -> DBSTree
65. Page 499, Exercise 9, line 1. whle -> while
66. Page 499, Exercise 12, line 1. BinarySearchTree -> BSTree
67. Page 501, line 10. Exercise 11 -> Exercise 13
68. Page 507, line 11. D2 -> D1
69. Page 518, lines 6 through 9. Delete parenthetical remarks.
70. Page 538, Exercise 31, line 4. for B -> for a B
71. Page 539, Exercise 34 (d), line 1. 11.4.4 -> 11.3.4
72. Page 552, Exercise 39 (b), line 2. BestFit -> BestFitPack
73. Page 561, lines 9 and 10. Delete last sentence.
74. Page 561, Figure 12.4(b). cost=100 -> cost=110
75. Page 565, Exercise 5, line 3. h -> H
76. Page 565, Exercise 7. Delete parts (c) and (d).
77. Page 570, line -4. 2(n + m + 1) >- 2(n + 2m + 1)
78. page 570, line -2. n + 2 >- n + 1
79. Page 572, Exercise 15, (a) and (b), line 2. Theta -> O
80. Page 574, Exercise 22, line 2. 12.1 -> 12.13
81. Page 574, Exercise 23, line 2. 12.1(a) and (b) -> 12.13(b) and (c)
82. Pages 576, 593, 594, and 597. The arrow heads in Figures 12.15 and 12.18 are inconsistent with those in Figures 12.16 and 12.17. For consistency, change those in Figures 12.15 and 12.18 to be at the other end.
83. Page 580, line -14. unweighted- -> unweighted
84. Page 613, Exercise 48, lines 1 and 2. Network -> Undirected; network -> undirected graph; and delete (directed)
85. Page 613, Exercise 49, lines 6 and 7. Theta -> O
86. Page 614, Exercise 50, line 1. Theta -> O
87. Page 626, line -8. nondecreasing -> nonincreasing
88. Page 645. Add the line d[s] = 0; p[s] = s; after the first for loop.
89. Page 649, line 13. one edge -> one edge, e,
90. Page 653, Figure 13.14, line -5. E} -> E
91. Page 656, Exercise 13, line 2. nondecreasing -> nonincreasing
92. Page 657, Exercise 17, line 3. nondecreasing -> nonincreasing
93. Page 657, Exercise 20. Trace the working of Program 13.3 on the graph of Figure 13.6.
94. Page 658, Exercise 22(c). int C > int C[]
95. Page 665, Equation 14.5. C_2 -> C_4
96. Page 673, line -2. zero > 1
97. Page 682, line -2. are to -> to
98. Page 683, line 3. *a -> a[]
99. Page 691, square root formula. remove last right parenthesis.
100. Page 693, Example 14.8, line 4. b, c, h, and n -> b, c, h, i, and n
101. Page 699, Program 14.11, line -16. fabs(Y[m] -> fabs(X[m]
102. Page 701, Exercise 14, line 2. smaller -> larger
103. Page 702, Exercise 22. 14.8 -> 14.10
104. Page 709, Figure 14.19. 0:1 -> 2:1 and 0:2 -> 2:0
105. Page 710, Exercise 38(c), line 4. comparisons -> comparisons in the worst case
106. Page 717, Program 15.2, line 5. w[n] -> min(w[n]-1,c)
107. Page 717, Program 15.2, line 11. w[i] -> min(w[i]-1,c)
108. page 726, lines -2 and -3. kj -> k+1,j
109. Page 737, Example 15.18, line 1. 10.17 -> 11.32
110. Page 737, Example 15.18, line 6 and Example 15.19 line1. 10.17 -> 15.7
111. Page 738, Equation 15.6. i -> 1
112. Page 740, line 3. MN >- size
113. Page 743, line 3. r_j+1 -> r_j+1
114. Page 743, line -2. obsrvation -> observation
115. Page 745, lines 6 and 7. wmin -> wmax and min > max
116. Page 745, Equation 15.14. k -> s
117. Page 747, Exercise 12, lines 2 and 3. <i,j> -> (i,j)
118. Page 757, line 17. -> (i,j)
119. Page 769, line 7 and 8. 16.2 -> 16.2.1
120. Page 770 and 772. Replace the sentence that begins: The complexity ... with: The complexity of Knap::Knapsack is O(2 sup n) even though the bounding function has complexity O(n) and it is computed at O(2 sup n) right children. To see this note that if, in the computation of the bounding function, the while loop of Bound is entered q times, then this computation of the bounding function is followed by q left-child moves. So over the entire run of Knap::Knapsack, the while loop of Bound cannot be entered more times than the number of left-child moves that are made. This number is O(2 sup n). Therefore, the total time spent computing the bounding function is O(2 sup 2).
121. Page 774, line -14. 15.6 -> 15.2.5
122. Page 778, line 18 of code. a[i] >- a[j]
123. Page 785, Ex. 16(b), line 3. x[i] >- x[j]
124. Page 789, line 18. 6.11 -> 6.9
125. Page 802, line -13. First uprofit >- up
126. Page 805, lines 8 and 9. delete stuff about ch
127. Page 809, line -17 of code. is x[1:0] >- is x[0:0]
128. Page 812, line -11 of code. {return bestd;} >- {break;}

feedback form | permissions | international | locate your campus rep | request a review copy

digital solutions | publish with us | customer service | mhhe home

---

Copyright ©2001 The McGraw-Hill Companies.
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of the The McGraw-Hill Companies.