|
《算法导论》 是计算机经典之书。号称如果学习计算机的人没有读过，堪称一大遗憾。这本书影响了无数的读者。但是——在MIT Preess,这本书的第二版已经是印刷10次了，其中纠正了许多读者反馈的错误(包括50多个严重错误，100多个微小错误)。而在我们国家的高等教育出版社，始终既往不咎！
来自：MIT出版社http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php
下面是影印版第2版的勘误：
Severity levels
A minor typographical error that should not affect your understanding (52 errors in first printing).
A minor technical or expository error (129 errors in first printing).
A more significant technical or expository error (41 errors in first printing).
A serious error in the exposition of an algorithm, or an error that requires significant change to the text (11 errors in first printing).
Page 14, bottom line. Change ``Medinas'' to ``Meidanis''. Reported by Marcel K. de Carli Silva. Posted 6 December 2001. Severity level: 1 Corrected in the third printing.
Page 20, line 13. Change ``x and y point to (``are'') the same object'' to ``x and y point to the same object''. Reported by Jinoh Kim. Posted 25 March 2002. Severity level: 2 Corrected in the third printing.
Page 26, lines 17-18. Change ``so tj = j/2. If we work out the resulting average-case running time, it turns out to be a quadratic function of the input size'' to ``so tj is about j/2. The resulting average-case running time turns out to be a quadratic function of the input size''. Reported by Carlos Brizuela. Posted 26 October 2002. Severity level: 2 Corrected in the fourth printing.
Page 44, line 26. Change ``the function f(n) is on or below g(n)'' to ``the function f(n) is on or below cg(n)''. Reported by San Skulrattanakulchai. Posted 26 September 2001. Severity level: 2 Corrected in the second printing.
Page 44, line 31. Change ``any quadratic function is in O(n2)'' to ``any such quadratic function is in O(n2)''. Reported by San Skulrattanakulchai. Posted 26 September 2001. Severity level: 2 Corrected in the second printing.
Page 44. Change the last sentence before the footnote to read ``What may be more surprising is that when a > 0, any linear function an+b is in O(n2), which is easily verified by taking c = a+|b| and n0 = max(1, -b/a).'' That is, add the condition that a > 0 and change the value of n0 to max(1, -b/a). Reported by Gerardo Quiñones and Linfeng Zhang. Posted 14 March 2005. Severity level: 2 Corrected in the seventh printing.
Page 50, Exercise 3.1-8. Change ``for all n ≥ n0 and m ≥ m0'' to ``for all n ≥ n0 or m ≥ m0''. Reported by Charles Leiserson. Posted 1 July 2003. Severity level: 2 Corrected in the fifth printing.
Page 51, inequality (3.7). There is an extra left parenthesis in the expression on the right-hand side. The right-hand side should read ''(a - (b - 1)) / b''. Reported by Georgios Fainekos. Posted 22 July 2002. Severity level: 2 Corrected in the fourth printing.
Page 83, line 7. Change ``≤'' to ``<''. Reported by Luke Hodgkinson. Posted 19 August 2003. Severity level: 2 Corrected in the fifth printing.
Page 85, Problem 4-2. Change the second paragraph of the problem to read, ``Show that if the only way to access information in array A is by this single-bit operation, we can still determine the missing integer in O(n) time. Any entire integer outside of A is still accessible in a single operation.'' Reported by Balbir Singh. Posted 29 November 2006. Severity level: 3 Corrected in the eighth printing.
Page 89, line 2. Change ``For the ``only if'' part'' to ``For the ``if'' part''. Reported by Hui Zheng. Posted 12 November 2001. Severity level: 3 Corrected in the third printing.
Page 90, line 2. The restriction on bi should read ``all bi are greater than 1''. Reported by Peter Hoyer. Posted 10 September 2001. Severity level: 2 Corrected in the second printing.
Page 90, line 7. The summation should run from 1 to k (not from 1 to p). Reported by Peter Hoyer. Posted 7 September 2001. Severity level: 2 Corrected in the second printing.
Page 94, last sentence before the exercises. There is an extraneous ``a'' after the end of the sentence. Reported by Tom O'Connell. Posted 4 August 2001. Severity level: 1 Corrected in the second printing.
Pages 95-96. The variables Y and Yi, whose codomain is {H, T}, violate the definition of a random variable on page 1106, which requires the codomain to be the real numbers. The best correction removes these variables altogether, recognizing that H and T are events that can serve as arguments for the I{} notation. Make the following changes:
Page 95, lines 7-10. Change ``Our sample space is S = {H, T}, and we define a random variable Y which takes on the values H and T, each with probability 1/2. We can then define an indicator random variable XH, associated with the coin coming up heads, which we can express as the event Y = H.'' to ``Our sample space is S = {H, T}, with Pr{H} = Pr{T} = 1/2. We can then define an indicator random variable XH, associated with the coin coming up heads, which is the event H.''
Page 95, lines 13-14. Change the definition of XH to read ``XH = I{H} = 1 if H occurs, 0 if T occurs.'' (HTML does not permit us to format the ``cases'' notation.)
Page 95, lines 17-18. Change the first two lines of the math display that calculates E[XH] to read
E[XH]
=
E[I{H}]
=
1 · Pr{H} + 0 · Pr{T}
Page 96, lines 8-9. Change ``comes up heads. Letting Yi be the random variable denoting the outcome of the ith flip, we have that Xi = I{Yi = H}.'' to ``comes up heads: Xi = I{the ith flip results in the event H}.''
Reported by Stanley Selkow. Posted 7 January 2003. Severity level: 3 Corrected in the fourth printing.
Page 98, line 12. Change ``The expected interview cost'' to ``The expected hiring cost''. Reported by Kiyoung Yang. Posted 20 September 2001. Severity level: 2 Corrected in the second printing.
Page 99, Exercise 5.2-5. Change ``Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n.'' to ``Suppose that the elements of A form a uniform random permutation of <1, 2, ..., n>.'' Reported by Tom Cormen. Posted 5 April 2002. Severity level: 3 Corrected in the third printing.
Page 103, line 9. Change ``(See Appendix B.)'' to ``(See Appendix C.)'' Reported by Tom O'Connell. Posted 15 October 2001. Severity level: 2 Corrected in the third printing.
Page 103, line 10 from the bottom. Change ``We assume that just before the (i - 1)st iteration'' to ``We assume that just before the ith iteration''. Reported by Tom Cormen. Posted 26 June 2002. Severity level: 2 Corrected in the fourth printing.
Page 104, line 2 of PERMUTE-WITHOUT-IDENTITY. Change ``1 to n'' to ``1 to n-1''. Reported by John Buck. Posted 20 February 2002. Severity level: 4 Corrected in the third printing.
Page 114. The last sentence before Subsection 5.4.4 should read ``From these rough estimates alone, we can conclude that the expected length of the longest streak is Θ(lg n).'' (Add the word ``expected.'') Reported by Tom O'Connell. Posted 10 September 2001. Severity level: 2 Corrected in the second printing.
Page 116, lines 1-5. Change ``whereas Bi depends only on whether the value in position i is greater than all the values 1 through i-1. The ordering of positions 1 through i-1 does not affect whether i is greater than all of them, and the value of i does not affect the ordering of positions 1 through i-1.'' to ``whereas Bi depends only on whether the value in position i is greater than the values in all other positions. The ordering of the values in positions 1 through i-1 does not affect whether the value in position i is greater than all of them, and the value in position i does not affect the ordering of the values in positions 1 through i-1.'' Reported by Tom O'Connell. Posted 12 October 2001. Severity level: 3 Corrected in the third printing.
Page 118, Problem 5-2. Change the start of the first sentence from ``Thus problem'' to ``This problem''. Reported by Fredrik Manne. Posted 12 September 2001. Severity level: 1 Corrected in the second printing.
Page 125, line 15. Change ``{1, 2, ..., k}'' to ``{0, 1, ..., k}''. On line 19, change ``and each digit is in the set {1, 2, ..., k}'' to ``and each digit can take on up to k possible values''. Reported by Dave DeBarr. Posted 2 March 2005. Severity level: 2 Corrected in the seventh printing.
Page 129, line 19. Change ``presents five basic procedures'' to ``presents some basic procedures''. Reported by Nancy Uehara. Posted 13 September 2001. Severity level: 1 Corrected in the second printing.
Page 133, last line. Change ``so we can express the total cost of BUILD-MAX-HEAP as'' to ``so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by''. Reported by Artem Matsak. Posted 26 August 2002. Severity level: 2 Corrected in the fourth printing.
Page 144, line 15 of the Chapter notes. Change ``O((lg lg n)2) time'' to ``O(lg lg n) time''. Reported by Anna Veszprémi. Posted 22 July 2003. Severity level: 2 Corrected in the fifth printing.
Page 144, line 27. Change ``Melhorn'' to ``Mehlhorn''. Reported by Anna Veszprémi. Posted 30 April 2003. Severity level: 1 Corrected in the fifth printing.
The PARTITION procedure puts all elements equal to the pivot into the same partition. Therefore, if many elements equal the pivot, the partitions are unbalanced, and the average-case analyses of quicksort and selection in expected linear time are incorrect. There are several changes in order to explicitly state the assumption that elements are distinct:
Page 145, line 15. Change ``and in O(n lg n) time on average.'' to ``and, assuming distinct elements, in O(n lg n) time on average.''
Page 156, line 10. Change ``and then using this understanding to derive an O(n lg n) bound on the expected running time.'' to ``and then using this understanding to derive an O(n lg n) bound on the expected running time (assuming that the values of the elements are distinct).''
Page 157, line 4 from the bottom. Change ``In general, once a pivot x is chosen'' to ``In general, because we assume that element values are distinct, once a pivot x is chosen''.
Page 158, last line. Change ``is O(n lg n).'' to ``is O(n lg n) when element values are distinct.''
Page 183, line 3 from the bottom. Change ``that achieves an O(n) bound on the running time in the average case.'' to ``that achieves an O(n) bound on the running time in the average case, assuming distinct elements.''
Page 185, line 4 from the bottom. Change ``the expected time of RANDOMIZED-SELECT is Θ(n).'' to ``the expected time of RANDOMIZED-SELECT is Θ(n), assuming that the elements are distinct.''
Page 187, line 4. Change ``and so we have'' to ``and so, assuming that the elements are distinct, we have''.
Page 192, Exercise 9.3-3. Change the exercise to read ``Show how quicksort can be made to run in O(n lg n) time in the worst case, assuming that all elements are distinct.''
Page 268, Exercise 12.4-5. Change ``a sequence of n input numbers'' to ``a sequence of n distinct input numbers''.
Reported by Jouni Järvinen. Posted 26 February 2003. Severity level: 4 Corrected in the fourth printing.
Page 147, Figure 7.1 caption. In part (f), change ``The values 3 and 8 are swapped'' to ``The values 3 and 7 are swapped''. Reported by Nafees Ud Din Ahmad. Posted 8 January 2002. Severity level: 2 Corrected in the third printing.
Page 148, Exercise 7.1-1. Because the array A has its maximum element in the rightmost position, it does not serve as a very interesting example for the PARTITION procedure. Switch the positions of the values 11 and 21 in the array so that A = 〈 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 〉. [Note: In some browsers, the angle brackets around this sequence appear as 〈 〉.] Reported by Ronald Tungol. Posted 7 July 2003. Severity level: 2 Corrected in the fifth printing.
Page 148, Exercise 7.1-2. Change ``so that q = (p+r) / 2'' to ``so that q = floor((p+r) / 2)''. (HTML does not permit us to print the appropriate floor symbol.) Reported by Antal Iványi. Posted 14 May 2003. Severity level: 2 Corrected in the fifth printing.
Page 152, last line. Change ``of the average case'' to ``of the average case of a randomized version of quicksort''. Reported by Joel Seiferas. Posted 2 December 2001. Severity level: 2 Corrected in the third printing.
Page 157, line 20. Add the sentence ``Our analysis assumes that each pivot is chosen randomly and independently.'' Page 158, line 8. Change ``Because the set Zij has j-i+1 elements,'' to ``Because the set Zij has j-i+1 elements, and because pivots are chosen randomly and independently,''. Reported by Charles Leiserson. Posted 15 September 2001. Severity level: 3 Corrected in the second printing.
Page 159, last line. Change ``T. Hoare'' to ``C. A. R. Hoare''. Reported by Charles Leiserson. Posted 2 October 2001. Severity level: 1 Corrected in the third printing.
Page 160, Problem 7-1(a). Change ``after each iteration of the for loop in lines 4-11'' to ``after each iteration of the while loop in lines 4-11''. Reported by Ronald Tungol. Posted 7 July 2003. Severity level: 1 Corrected in the fifth printing.
Page 160, Problem 7-1. Change the sentence immediately preceding part (b) to read, ``Assuming that the subarray A[p .. r] contains at least two elements, prove the following:'' Reported by Luke Hodgkinson. Posted 17 October 2005. Severity level: 2 Corrected in the seventh printing.
Page 161, Problem 7-2. In part (c), change ``Show that equation (7.5) simplifies to'' to ``Show that equation (7.5) can be rewritten as'', and change the summation to start at q=2. In part (d), change the summation to start at k=2, and in the hint change ``one for k = 1, 2, ...'' to ``one for k = 2, 3, ...''. In part (e), change the hint to read ``Show, by substitution, that E[T(n)] ≤ an lg n for sufficiently large n and for some positive constant a.'' Reported by Charles Leiserson. Posted 26 September 2001. Severity level: 3 Corrected in the second printing.
Page 172, Lemma 8.3. Append to the statement of the lemma ``if the stable sort it uses takes Θ(n+k) time''. Reported by Richard Beigel. Posted 7 April 2003. Severity level: 2 Corrected in the fifth printing.
Page 174, first line of Section 8.4. Change ''Bucket sort runs in linear time'' to ''Bucket sort runs in linear expected time''. Reported by Brendan McKay. Posted 23 July 2002. Severity level: 2 Corrected in the fourth printing.
Page 174, Section 8.4. In the fifth line of the first paragraph, change ``uniformly over the interval [0,1)'' to ``uniformly and independently over the interval [0,1)''. In the third line of the second paragraph, change ``uniformly distributed over [0,1)'' to ``uniformly and independently distributed over [0,1)''. Reported by Charles Leiserson. Posted 17 October 2005. Severity level: 2 Corrected in the seventh printing.
Page 187, line 19. Remove the outermost parentheses of the expression, so that the O(n) term is not in the summation. Reported by Randy Goldman. Posted 3 November 2001. Severity level: 3 Corrected in the third printing.
Page 188, line 6. Change ``Assume that T(n) ≤ cn'' to ``Assume that E[T(n)] ≤ cn''. Reported by Zubair Adamjee. Posted 12 August 2003. Severity level: 2 Corrected in the fifth printing.
Page 189, line 4. Change ``we have T(n) = O(n)'' to ``we have E[T(n)] = O(n)''. Reported by Tom Cormen. Posted 21 May 2002. Severity level: 2 Corrected in the fourth printing.
Page 190, last line of main text. Change ``greater than1 the median-of-medians x.'' to ``greater than or equal to the median-of-medians x.1''. Change the footnote to read ``Because of our assumption that the numbers are distinct, all medians except x are either greater than or less than x.'' Reported by Tom Cormen. Posted 1 June 2002. Severity level: 2 Corrected in the fourth printing.
Page 191. Lines 13-14, change ''that any input of 140 or fewer elements'' to ''that any input of fewer than 140 elements''. Lines 16-17 (the bound on T(n)), change the first case to ''O(1) if n < 140'' and change the second case to hold ''if n ≥ 140''. Line 20, change ''and all n ≤ 140'' to ''and all n < 140''. Reported by Tom Cormen. Posted 6 June 2002. Severity level: 2 Corrected in the fourth printing.
Page 195, line 4 from the bottom. Change ``Schonhage'' to ``Schönhage''. Reported by Zsolt Lencse. Posted 16 June 2003. Severity level: 1 Corrected in the fifth printing.
Page 219. In seven places in the text of Problem 10-3, calls to the procedures COMPACT-LIST-SEARCH and COMPACT-LIST-SEARCH´ should have the parameter n inserted as the second parameter of the call. Reported by István Fekete. Posted 29 April 2003. Severity level: 2 Corrected in the fifth printing.
Page 223, Exercise 11.1-4. In the hint, change ``Use an additional stack, whose size is the number of keys'' to ``Use an additional array, treated somewhat like a stack whose size is the number of keys''. Reported by Jack Weinstein. Posted 4 June 2007. Severity level: 2 Corrected in the tenth printing.
Page 234, Corollary 11.4. Add the following sentence at the end of the proof: ``Since each operation takes Ω(1) time, the &Theta(n); bound follows.''. Reported by Antal Iványi. Posted 22 September 2003. Severity level: 2 Corrected in the fifth printing.
Page 234, line 29. Change ``hav p > m'' to ``have p > m''. Reported by Tom O'Connell. Posted 4 September 2001. Severity level: 1 Corrected in the second printing.
Page 235, line 4 from the bottom. Change ``(by inequality (3.7))'' to ``(by inequality (3.6))''. Reported by H. Jun Lee. Posted 10 April 2002. Severity level: 2 Corrected in the third printing.
Page 244, Exercise 11.4-1. Change ``with the primary hash function'' to ``with the auxiliary hash function''. Reported by Scot Anderson. Posted 11 October 2001. Severity level: 2 Corrected in the third printing.
Page 246, Figure 11.6. For consistency with the scheme that the first-level hash table has size m = n, the set K in the figure should have 9 keys, rather than 7. Add the keys 52 and 72 to the set K so that K = {10, 22, 37, 40, 52, 60, 70, 72, 75}. In the figure, change m2 to 9, make secondary hash table S2 have 9 slots, and put 60 into slot 3, 72 into slot 4, and 75 into slot 7 of S2. All other slots of S2 are empty. In line 5 of the caption, change ``Since h2(75) = 1, key 75 is stored in slot 1'' to ``Since h2(75) = 7, key 75 is stored in slot 7''. In the figure, change m7 to 16, make secondary hash table S7 have 16 slots, and put 40 into slot 7, 52 into slot 8, 22 into slot 9, and 37 into slot 14 of S7. All other slots of S7 are empty. Reported by Tom Cormen. Posted 16 January 2004. Severity level: 2 Corrected in the fifth printing.
Page 249, last line in the statement of Corollary 11.12. Change ``exceeds 4n'' to ``equals or exceeds 4n''. Reported by Tom Cormen. Posted 16 January 2004. Severity level: 2 Corrected in the fifth printing.
Page 250, Problem 11-1. In part (b), change ``at most 1/n2'' to ``O(1/n2)''. In the paragraph between parts (b) and (c), change ``Pr{Xi > 2 lg n} ≤ 1/n2'' to ``Pr{Xi > 2 lg n} = O(1/n2)''. In part (c), change ``Pr{X > 2 lg n} ≤ 1/n'' to ``Pr{X > 2 lg n} = O(1/n)''. Reported by Stephan Stiller. Posted 20 November 2006. Severity level: 3 Corrected in the eighth printing.
Page 251. In Problem 11-3, change step 3 to ``Set j ← j + 1. If j = m, the table is full, so terminate the search. Otherwise, set i ← (i + j) mod m, and return to step 2.'' [Note: In some browsers, the left arrow symbol that we use for ``gets'' appears as ←.] Reported by Gabriel Nivasch. Posted 31 August 2005. Severity level: 3 Corrected in the seventh printing.
Page 251, Problem 11-4. The problem has been rewritten. You can get the new text in either PostScript or PDF. Reported by Charles Leiserson. Posted 5 November 2001. Severity level: 4 Corrected in the third printing.
Page 265, lines 21-22. Change ``we let Rn denote the random variable that holds this key's rank within the set of n keys.'' to ``we let Rn denote the random variable that holds this key's rank within the set of n keys; that is, Rn holds the position that this key would occupy if the set of keys were sorted.''. Reported by Johan Gade. Posted 31 May 2004. Severity level: 2 Corrected in the fifth printing.
Page 267, lines 3-5. We also need to verify that E[Y0] ≤ (1/4) (3 choose 3). Change the sentence to read ``For the base cases, we verify that the bounds0 = Y0 = E[Y0] ≤ (1/4) (3 choose 3) = 1/4 and 1 = Y1 = E[Y1] ≤ (1/4) (1+3 choose 3) = 1hold.'' (HTML does not permit us to format fractions or the ``choose'' notation properly.) Reported by Sára Nagy. Posted 12 May 2003. Severity level: 2 Corrected in the fifth printing.
Page 267, line 7 (second line of the math display bounding E[Yn]). Change the equal sign to less-than-or-equal. Reported by Tom Cormen. Posted 11 April 2002. Severity level: 2 Corrected in the third printing.
Page 278, procedure LEFT-ROTATE. Replace line 3 by the two linesif left[y] ≠ nil[T] then p[left[y]] ← x[Note: In some browsers, the left arrow symbol that we use for ``gets'' appears as ←.] Reported by Timothy Haritun. Posted 22 October 2001. Severity level: 4 Corrected in the third printing.
Page 285, caption for Figure 13.5. Change ``Case 1 of the procedure RB-INSERT'' to ``Case 1 of the procedure RB-INSERT-FIXUP''. Reported by Lee May. Posted 9 February 2006. Severity level: 2 Corrected in the seventh printing.
Page 289, line 4. Remove the phrase, ``In the latter case,''. Reported by Lee May. Posted 9 February 2006. Severity level: 2 Corrected in the seventh printing.
Page 296, Problem 13-3(d). The statement of part (d) asks for something that is not true. Change part (d) to read ``Show that AVL-INSERT, run on an n-node AVL tree, takes O(lg n) time and performs O(1) rotations.''. Reported by Vassos Hadzilacos. Posted 10 October 2002. Severity level: 3 Corrected in the fourth printing.
Page 301, line 8. Change ``Sleator and Tarjan [281]'' to ``Sleator and Tarjan [282]''. Reported by Steve Witham. Posted 3 March 2005. Severity level: 1 Corrected in the seventh printing.
Page 307, Exercise 14.1-1. Change ``OS-SELECT(T, 10)'' to ``OS-SELECT(root[T], 10)''. Reported by Jouni Järvinen. Posted 24 March 2003. Severity level: 2 Corrected in the fourth printing.
Page 314, line 10 from the bottom. Remove the sentence ``(Note that no interval in the right subtree overlaps i--we shall see why later.)'' Reported by Jørgen Villadsen. Posted 6 May 2002. Severity level: 3 Corrected in the fourth printing.
Page 317, Exercise 14.3-7. Change ``x- and y-axis'' to ``x- and y-axes'' and change ``a set of rectangles so represented'' to ``a set of n rectangles so represented''. Reported by Charles Leiserson. Posted 3 March 2005. Severity level: 1 Corrected in the seventh printing.
Page 329, line 3 of FASTEST-WAY. The keyword ``to'' should be in boldface. Reported by Curt Tilmes. Posted 15 September 2005. Severity level: 1 Corrected in the seventh printing.
Page 329, lines 15-18 of FASTEST-WAY. Change the equals signs to left arrows. Reported by Nándor Érsek. Posted 22 September 2003. Severity level: 1 Corrected in the fifth printing.
Page 330. Change the parameters of PRINT-STATIONS from ``(l, n)'' to ``(l, l*, n)''. Reported by Antal Iványi. Posted 12 July 2004. Severity level: 2 Corrected in the fifth printing.
Page 340, line 12 from the bottom. Change ``1 ≤ k ≤ j'' to ``1 ≤ k < j''. Reported by Domenico Maria De Giorgio. Posted 22 August 2003. Severity level: 2 Corrected in the fifth printing.
Page 343, line 14 from the bottom. Change ``then we cannot solve it all'' to ``we cannot solve it at all''. Reported by Luke Hodgkinson. Posted 2 September 2003. Severity level: 1 Corrected in the fifth printing.
Page 347, line 4. Change ``through Si,j'' to ``through S1,j''. Reported by Luke Hodgkinson. Posted 2 September 2003. Severity level: 2 Corrected in the fifth printing.
Page 361, line 14. Change ``for 1 ≤ i ≤ n'' to ``for 1 ≤ i ≤ n+1''. Reported by Stefan Schumann. Posted 4 August 2003. Severity level: 2 Corrected in the fifth printing.
Page 372, line 10. Change ``represent to entire problem'' to ``represent the entire problem''. Reported by John Buck. Posted 25 March 2002. Severity level: 1 Corrected in the third printing.
Page 373, line 2. Change ``producing a another solution'' to ``producing another solution''. Reported by Erica Schultz. Posted 10 April 2002. Severity level: 1 Corrected in the third printing.
Page 373, line 10. Change ``we can build an maximum'' to ``we can build a maximum''. Reported by Jim Nastos. Posted 12 August 2001. Severity level: 1 Corrected in the second printing.
Page 373, equation (16.3). The max needs to be over all k such that i < k < j and also ak is in Sij. Reported by Bob Roos. Posted 16 November 2001. Severity level: 3 Corrected in the third printing.
Page 374, line 8 from the bottom. Change ``there are j-i-1 choices'' to ``there are up to j-i-1 choices''. Reported by Luke Hodgkinson. Posted 9 September 2003. Severity level: 2 Corrected in the fifth printing.
Pages 375-378. As written, the procedure RECURSIVE-ACTIVITY-SELECTOR is flawed, in that it works only when j = n+1. It so happens that in the initial call and all recursive calls, j does equal n+1, but for general values of j, the statement on page 375, lines 4-5 from the bottom, ``It returns a maximum-size subset of mutually compatible activities in Sij'' does not hold. The best remedy is to rewrite the procedure so that the fourth parameter is always n, and have it return a maximum-size subset of mutually compatible activities in Si,n+1. Pages 375-378 have been rewritten to accommodate this change. You can get the updated pages in either PostScript or PDF. Note: these updated pages were changed on 12 February 2002. Reported by Paulo Feofiloff and Augusto Fernandes Vellozo. Posted 16 November 2001. Severity level: 4 Corrected in the third printing.
Page 384, Exercise 16.2-2. Change ``where n is number of items'' to ``where n is the number of items''. Reported by Eric Robinson. Posted 29 October 2004. Severity level: 1 Corrected in the seventh printing.
Page 384, Exercise 16.2-6. Remove the sentence ``Assume that you have a solution to Problem 9-2.'' Reported by Joel Seiferas. Posted 5 December 2001. Severity level: 2 Corrected in the third printing.
Page 393. In the definition of a matroid, change the first condition to ``S is a finite set.'' (Remove the word ``nonempty.'') Reported by Gene Luks. Posted 30 January 2003. Severity level: 2 Corrected in the fourth printing.
Page 393, Theorem 16.5. In the theorem statement, change ``undirected graph'' to ``acyclic, undirected graph''. Reported by Martin Schweitzer. Posted 18 May 2006. Severity level: 2 Corrected in the seventh printing.
Page 400, line 4. Change ``so it also still early'' to ``so it also is still early''. Reported by Jim Nastos. Posted 12 August 2001. Severity level: 1 Corrected in the second printing.
Page 403, Problem 16-3(b). At the end of this problem part, change ``is matroid'' to ``is a matroid''. Reported by Curt Tilmes. Posted 13 October 2005. Severity level: 1 Corrected in the seventh printing.
Page 403, Problem 16-3. In part (e), change ``for a directed graph G = (V, E)'' to ``for a directed graph G = (V, E) with no self-loops''. Page 531, Exercise 22.1-7. Change ``of a directed graph G = (V, E)'' to ``of a directed graph G = (V, E) with no self-loops''. Reported by Holger Mauch. Posted 30 November 2005. Severity level: 2 Corrected in the seventh printing.
Pages 408-409. Replace ``floor(lg n)'' by ``k-1''. (HTML does not permit us to print the appropriate floor symbol.) Specifically, on page 408, line 2 from the bottom, change ``for i = 0, 1, ..., floor(lg n)'' to ``for i = 0, 1, ..., k-1''; on page 408, last line, change ``For i > floor(lg n)'' to ``For i ≥ k''; and in page 409, line 2 of the text, change the upper bound of the first summation from ``floor(lg n)'' to ``k-1''. Reported by Tom Cormen. Posted 23 April 2002. Severity level: 3 Corrected in the fourth printing.
Page 416, Exercise 17.3-7. S should be a dynamic set. In the first sentence, change ``for a set S'' to ``for a dynamic set S''. Change the description of the INSERT operation to ``INSERT(S, x) inserts x into S.'' Reported by Ralf Juengling. Posted 28 May 2003. Severity level: 2 Corrected in the fifth printing.
Page 416, Exercise 17.3-7. The exercise should clarify that duplicate values are allowed, and so S is a dynamic multiset rather than a dynamic set. It should also specify that there should also be a way to output the elements of S in O(|S|) time. Reported by Kevin Liu. Posted 21 December 2004. Severity level: 3 Corrected in the seventh printing.
Page 416, Exercise 17.3-7. In the specification for DELETE-LARGER-HALF(S), change ``ceiling(S/2)'' to ``ceiling(|S|/2)''. (HTML does not permit us to print the appropriate ceiling symbol.) Reported by Eric Rupert. Posted 3 October 2002. Severity level: 2 Corrected in the fourth printing.
Page 431. The footnote should be numbered ``1'' rather than ``2''. Reported by Nándor Érsek. Posted 8 September 2003. Severity level: 1 Corrected in the fifth printing.
Page 442, line 21. Change ``The number of disk pages accessed by B-TREE-SEARCH is therefore Θ(h) = Θ(logt n)'' to ``The number of disk pages accessed by B-TREE-SEARCH is therefore O(h) = O(logt n)''. Reported by Jouni Järvinen. Posted 10 April 2002. Severity level: 2 Corrected in the third printing.
Page 455, line 4 from the bottom of the main text. Change ``in worst-case time O(lg n) (or better) on a binary heap'' to ``in worst-case time O(lg n) on a binary heap''. Reported by Zoltán Csörnyei. Posted 12 May 2003. Severity level: 2 Corrected in the fifth printing.
Page 456, Figure 19.1. The entry with row label ``UNION'' and column label ``Binomial heap (worst case)'' should read ``Θ(lg n)'' rather than ``O(lg n)''. Page 473, Exercise 19.2-10. The worst-case running time of BINOMIAL-HEAP-UNION is Ω(lg n), so this procedure should be moved from the list in the second sentence of the exercise to the list in the first sentence. Reported by Greg Plaxton. Posted 2 November 2004. Severity level: 3 Corrected in the seventh printing.
Page 458, proof of part (3) of Lemma 19.1. The reason ``(by the inductive hypothesis)'' should appear on the second line of the display (not the first line), and the reason ``(by Exercise C.1-7)'' should appear on the third line of the display (not the second line). Reported by Beau Skinner. Posted 28 June 2004. Severity level: 2 Corrected in the fifth printing.
Page 468, line 3 of BINOMIAL-HEAP-EXTRACT-MIN. Change the line to read ``reverse the order of the linked list of x's children, setting the p field of each child to NIL, and set head[H´] to point to the head of the resulting list''. Reported by Jouni Järvinen. Posted 14 April 2003. Severity level: 4 Corrected in the fifth printing.
Page 477, line 12. Change ``a handle to corresponding'' to ``a handle to the corresponding''. Reported by Beau Skinner. Posted 28 June 2004. Severity level: 1 Corrected in the fifth printing.
Page 480, line 5. Change ``D(n) = lg n'' to ``D(n) = floor(lg n)''. (HTML does not permit us to print the appropriate floor symbol.) Reported by Johan Gade. Posted 31 May 2004. Severity level: 2 Corrected in the fifth printing.
Page 482, line 4 of FIB-HEAP-UNION. Change the condition ``min[H2] < min[H1]'' to ``key[min[H2]] < key[min[H1]]''. Reported by Doug Dunham. Posted 10 April 2002. Severity level: 4 Corrected in the third printing.
Pages 484-485, Figure 20.3. In parts (f), (g), and (h), node w should be the node with key 7. In part (k), node w should be the node with key 52. Reported by Jens Kristian Jensen. Posted 20 November 2002. Severity level: 2 Corrected in the fourth printing.
Page 490, line 30. Change ``performs a cascading-cut operation on y'' to ``attempts to perform a cascading-cut operation on y''. Reported by Johan Gade. Posted 31 May 2004. Severity level: 2 Corrected in the fifth printing.
Page 493, proof of Lemma 20.1. In the second sentence of the proof, change ``degree[x] = i-1'' to ``degree[x] ≥ i-1''. In the third sentence of the proof, change ``degree[yi] = i-1'' to ``degree[yi] ≥ i-1''. Reported by Tom Cormen. Posted 13 February 2004. Severity level: 2 Corrected in the fifth printing.
Page 495, proof of Lemma 20.3. The first paragraph of the proof does not make it clear that z may be in any Fibonacci heap. There is no need to give a value for s2, since it is not needed anywhere. The lower bound for size(x) should not be in terms of x's children, since we do not know that size(x) = sk. Change the first paragraph of the proof, up to the first math display, to ``Let sk denote the minimum possible size of any node of degree k in any Fibonacci heap. Trivially, s0 = 1 and s1 = 2. The number sk is at most size(x) and, because adding children to a node cannot decrease the node's size, the value of sk increases monotonically with k. Consider some node z, in any Fibonacci heap, such that degree[z] = k and size(z) = sk. Because sk ≤ size(x), we compute a lower bound on size(x) by computing a lower bound on sk. As in Lemma 20.1, let y1, y2, ..., yk denote the children of z in the order in which they were linked to z. To bound sk, we count one for z itself and one for the first child y1 (for which size(y1) ≥ 1), giving''. Also, in the second line of the display that follows, change ``='' to ``≥''. Reported by Tom Cormen. Posted 2 February 2004. Severity level: 3 Corrected in the fifth printing.
Page 513, line 4. In the definition of Φq, the summation should be of φq(x) rather than of φ(x). Reported by Richard Beigel. Posted 15 April 2003. Severity level: 2 Corrected in the fifth printing.
Page 513. The auxiliary function iter(x) is defined only when rank[x] ≥ 1. Change line 26 from ``The second auxiliary function is'' to ``The second auxiliary function applies when rank[x] ≥ 1:'' and change line 30 from ``We claim that'' to ``We claim that when rank[x] ≥ 1, we have''. Reported by Ed Reingold. Posted 4 October 2006. Severity level: 2 Corrected in the eighth printing.
Page 517, lines 6, 14, 15, and 19. There should be parentheses around the superscripts of A, since these superscripts indicate functional iteration. Reported by Peter Hoyer. Posted 10 September 2001. Severity level: 2 |
