引自:http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php
Severity levels
A minor typographical error that should not affect your understanding (46 errors in first printing).
A minor technical or expository error (117 errors in first printing).
A more significant technical or expository error (35 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
To be corrected in the sixth 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 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
To be corrected in the sixth 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 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 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 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 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
To be corrected in the sixth 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 bounds
0 = Y0 = E[Y0] ≤ (1/4) (3 choose 3) = 1/4 and 1 = Y1 = E[Y1] ≤ (1/4) (1+3 choose 3) = 1
hold.'' (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 lines
if 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 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
To be corrected in the sixth 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
To be corrected in the sixth 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
To be corrected in the sixth 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
To be corrected in the sixth 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 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.
--------------------------------------------------------------------------------
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
To be corrected in the sixth 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
To be corrected in the sixth 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 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
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 533, line 2 of main text. Change ``Lines 1-4 paint every vertex white'' to ``With the exception of the source vertex s, lines 1-4 paint every vertex white''. An additional stylistic change: in the next sentence, change ``Line 5 paints the source vertex s gray'' to ``Line 5 paints s gray''.
Reported by George Havas. Posted 3 September 2002.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 534, line 14. Change ``in lines 11-18'' to ``in line 18''.
Reported by Wilasiree Buranatham. Posted 8 April 2002.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 539, Exercise 22.2-6. In the last sentence, change ``If is it possible'' to ``If it is possible''.
Reported by Susan Wang. Posted 29 March 2002.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 548, Exercise 22.3-4, part (b). The inequalities should read ``d[v] ≤ d[u] < f[u] ≤ f[v]''. That is, the first and last inequalities should be non-strict.
Reported by David Fowler. Posted 23 July 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 559, Problem 22-3. Change ``connected'' to ``strongly connected''.
Reported by Greg Plaxton. Posted 3 November 2004.
Severity level: 2
To be corrected in the sixth printing.
--------------------------------------------------------------------------------
Page 563, line 12. Change ``and so the set A is returned in line 5'' to ``and so the set A returned in line 5''.
Reported by Stefan Schumann. Posted 1 December 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 566, Exercise 23.1-4. The exercise should require the graph to be connected.
Reported by Tom Cormen. Posted 22 August 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 566, Exercise 23.1-5. Change ``Let e be a maximum-weight edge on some cycle of G = (V, E).'' to Change ``Let e be a maximum-weight edge on some cycle of connected graph G = (V, E).''
Reported by San Skulrattanakulchai. Posted 11 September 2002.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 569, Figure 23.4 parts (l), (m), and (n). Edge (c, i) should be labeled with weight 2.
Reported by Melissa Crounse. Posted 2 June 2002.
Severity level: 1
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 573, line 2. Change ``The for loop of lines 8-11 update'' to ``The for loop of lines 8-11 updates''.
Reported by San Skulrattanakulchai. Posted 11 September 2002.
Severity level: 1
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 578, Problem 23-4. In part (a), change line 5 of MAYBE-MST-A to read ``then T ← T - {e}''. In part (b), change line 4 of MAYBE-MST-B to read ``then T ← T ∪ {e}''. [Note: In some browsers, the left arrow symbol that we use for ``gets'' appears as ←, and the symbol for set union appears as ∪.]
Reported by Fredrik Manne. Posted 3 May 2002.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 578, line 5 of MAYBE-MST-C. Change ``the maximum-weight edge'' to ``a maximum-weight edge''.
Reported by Peter Hoyer. Posted 9 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 589, line 3 from the bottom. Change ``relaxes all E edges'' to ``relaxes all |E| edges''.
Reported by San Skulrattanakulchai. Posted 23 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 591, Exercise 24.1-3. To the end of the last sentence of the exercise, add ``even if m is not known in advance.''.
Reported by David Wagner. Posted 22 December 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 604, bottom two lines. Change the inequalities to read
xk-1 - xk-2 ≤ w(vk-2, vk-1) ,
xk - xk-1 ≤ w(vk-1, vk) .
Page 605, line 4. Change ``subtracted out once'' to ``subtracted out once (remember that v1 = vk implies x1 = xk)''.
Reported by Sam Slee. Posted 15 May 2002.
Severity level: 3
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 618, Problem 24-6. In the second paragraph of the problem, add the condition that all edge weights are unique.
Reported by Tom Cormen. Posted 2 June 2003.
Severity level: 3
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 619, line 10. Change ``by Raman'' to ``by Raman [256]''.
Reported by Tibor Gregorics. Posted 22 July 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 641, Problem 25-1(b). Add the phrase ``no matter what algorithm is used'' to the end of the problem statement.
Reported by Adam Chlipala. Posted 25 March 2002.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 652, line 2 of the Figure 26.3 caption. Change ``cf(p) = c(v2, v3) = 4'' to ``cf(p) = cf(v2, v3) = 4''.
Reported by San Skulrattanakulchai. Posted 15 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 658, footnote 2. Delete the sentence ''In practice, however, irrational numbers cannot be stored on finite-precision computers.''.
Reported by Brendan McKay. Posted 26 July 2002.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 662. On line 12, change ``|V|/2-1 times'' to ``|V|/2 times''. Change the sentence starting on line 30 to read ``Thus, after the first time that (u,v) becomes critical, it can become critical at most (|V|-2)/2 = |V|/2-1 times more, for a total of at most |V|/2 times.''
Reported by Florian Schwingenschl?gl. Posted 8 June 2005.
Severity level: 2
To be corrected in the sixth printing.
--------------------------------------------------------------------------------
Page 665, 5th line from the bottom. Change ``along with V new edges'' to ``along with |V| new edges''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 666, 6th line from the bottom. Change ``an integer-valued flow in G′ '' to ``an integer-valued flow f in G′ ''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 667, lines 12 and 13. Remove ``defined in the statement of the lemma''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 668, line 5. Change ``is the value'' to ``equals the value'' in order to strengthen the notion that Corollary 26.12 is an ``if and only if'' statement.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 669, line 11 from the bottom. Change ``the entire residual network G = (V, E) to find'' to ``the entire residual network to find''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 669, lines 3 and 4 from the bottom. Remove the sentence ``That is, the total net flow at each vertex other than the source is nonnegative.'' Change the next sentence from ``We call the total net flow at a vertex u the excess flow into u, given by ...'' to ``We call this quantity the excess flow into vertex u, given by ...''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 3
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 672, line 10. Change ``Thus we can we increase'' to ``Thus we can increase''.
Reported by San Skulrattanakulchai. Posted 19 September 2001.
Severity level: 1
Corrected in the second printing.
--------------------------------------------------------------------------------
Pages 696-697, Problem 26-7. In line 3 of the HOPCROFT-KARP procedure, change ``maximum set'' to ``maximal set''. In line 7 on page 697, change ``maximum set'' to ``maximal set''. Change part (e) to read ``Prove that if a shortest augmenting path with respect to M has l edges, the size of the maximum matching is at most |M| + |V|/(l+1).'' In line 1 of part (g), change ``maximum set'' to ``maximal set''.
Reported by Greg Plaxton. Posted 29 April 2002.
Severity level: 4
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 711, Figure 27.5 caption. Change ``f(x) = f(ceiling(x/2))'' to ``f(x) = ceiling(x/2)''. (HTML does not permit us to print the appropriate ceiling symbol.)
Reported by Xiaozhou Steve Li. Posted 25 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 760, third line of proof of Lemma 28.10. Change ``xkT Axk ≤ 0'' to ``xkT Akxk ≤ 0''.
Reported by Ofer Springer. Posted 30 July 2004.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 762, equation (28.31). Change the text immediately preceding the equation from ``a function F(x) such that'' to ``a function F(x) such that the approximation errors'', change equation (28.31) to ``ηi = F(xi) - yi'', and change the text immediately following the equation from ''for i = 1, 2, ..., m, where the approximation errors ηi are small'' to ``are small for i = 1, 2, ..., m.''
Reported by Alan Ritter. Posted 7 March 2005.
Severity level: 3
To be corrected in the sixth printing.
--------------------------------------------------------------------------------
Page 772, lines 3-4 from the bottom. Change ``either linear equalities or linear equalities'' to ``either linear equalities or linear inequalities''.
Reported by Mike Domaratzki. Posted 19 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 779, last line. Change ``and thus the two solutions are equivalent'' to ``and thus the two linear programs are equivalent''.
Reported by San Skulrattanakulchai. Posted 18 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 781, equations (29.30) and (29.32). In the summations, change ``xi'' to ``xj''.
Reported by Selim Akl. Posted 19 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 785, Exercise 29.1-8. Change ``into standard from'' to ``into standard form''.
Reported by Trivikram Dash. Posted 29 November 2002.
Severity level: 1
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 786, line (29.44). Change ``minimize d[t]'' to ``maximize d[t]''.
Reported by Tom O'Connell. Posted 15 September 2001.
Severity level: 3
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 786, lines 15 and 16. Change ``a sink s and a source t'' to ``a source s and a sink t''.
Reported by San Skulrattanakulchai. Posted 11 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 787, line 11 from the bottom. After the sentence, ``Suppose that each edge (u, v) has, in addition to a capacity c(u, v), a real-valued cost a(u, v),'' add the sentence, ``For technical reasons, we require that if a(u, v) > 0, then a(v, u) = 0.''
Reported by Uri Zwick. Posted 22 May 2003.
Severity level: 3
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 788, line 26. Change ``As in the maximum-flow problem, we implicitly assume that c(u, v) = 0 for (u, v) ? E.'' to ``As in the maximum-flow problem, we implicitly assume that c(u, v) = 0 for (u, v) ? E, and we also require that c(u, v) > 0 implies c(v, u) = 0.''
Reported by Uri Zwick. Posted 22 May 2003.
Severity level: 3
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Pages 788, lines 1-2 from the bottom. Remove the sentence ``This constraint subsumes the capacity constraints for the individual commodities.'' Page 789. Add to the linear program for multicommodity flow the constraints ``fi(u, v) ≤ c(u, v) for each u, v ∈ V and for each i = 1, 2, ..., k''.
Reported by Reuven Cohen and Tsur Doron. Posted 10 March 2003.
Severity level: 3
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 789, last equation of the linear program. Change ``fi(s, v)'' to ``fi(si, v)''.
Reported by Xiaozhou Steve Li. Posted 31 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 795, lines 18 and 19 of PIVOT. Change the equals signs to left arrows.
Reported by Ronald Tungol. Posted 16 March 2004.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 796, line 3. In the constraint, change ``x?i'' to ``xi'' (remove the bar from xi), change ``x?j'' to ``xj'' (remove the bar from xj), and change ``j ∈ N'' to ``j ∈ N?'' (add a hat to N).
Reported by Csaba Fábián. Posted 15 August 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 796, line 6. Change ``for each i ∈ B? - e'' to ``for each i ∈ B? - {e}''.
Reported by Csaba Fábián. Posted 15 August 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 799, line 3. Change ``i ∈ B - l'' to ``i ∈ B - {l}''.
Reported by Csaba Fábián. Posted 15 August 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 800, line 4 from the bottom. Change ``Since we picked i as any index in i'' to ``Since we picked i as any index in I''.
Reported by Mike Domaratzki. Posted 22 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
On page 812, in INITIALIZE-SIMPLEX, the variable l needs to be reindexed to compensate for the slack form before l is used in the call to PIVOT in line 7. This correction requires several changes:
Change line 1 of INITIALIZE-SIMPLEX to read ``let k be the index of the minimum bi''.
Change the non-comment part of line 2 of INITIALIZE-SIMPLEX to read ``if bk ≥ 0''.
After line 5 of INITIALIZE-SIMPLEX, add the line ``l ← n+k''. [Note: In some browsers, the left arrow symbol that we use for ``gets'' appears as ←.]
Page 813, line 4. Change ``as in Lemma 29.11. Since the initial basic solution to L is not feasible'' to ``as in Lemma 29.11. In line 6, we also set l to the index of the most negative bi, but reindexed after having converted to slack form. Since the initial basic solution to L is not feasible''.
Page 813, line 7. Change ``with x0 entering and xl leaving, where the index l is chosen in line 1 to be the index of the most negative bi.'' to ``with x0 entering and xl leaving.''
Page 815, line 20. Change ``bl < 0'' to ``bk < 0''.
Page 815, line 22. Change ``bl ≤ bi'' to ``bk ≤ bi''.
Page 815, line 23. Change ``we perform one pivot operation in which the leaving variable xl is the left-hand side'' to ``we perform one pivot operation in which the leaving variable xl (recall that l = n+k) is the left-hand side''.
Because we add a new line of pseudocode after line 5 of INITIALIZE-SIMPLEX, line numbers 6-12 become line numbers 7-13. In pages 812-817, each reference to a line numbered 6-12 in INITIALIZE-SIMPLEX should be incremented.
Reported by Uri Zwick. Posted 22 May 2003.
Severity level: 4
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 813, line 9 from the bottom. Change ``If the optimal objective value of this auxiliary linear program is positive'' to ``If the optimal objective value of this auxiliary linear program is negative''.
Reported by Uri Zwick. Posted 22 May 2003.
Severity level: 3
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 814, line 12 from the bottom. In the objective function, change ``4/5'' to ``-4/5''.
Reported by Samir Khuller. Posted 11 November 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 814, line 10 from the bottom. In the equation for z, change it from ``z = 4/5 + 9x1/5 - x4/5'' to ``z = -4/5 + 9x1/5 - x4/5''. That is, the constant should be -4/5, not 4/5.
Reported by Rance Cleaveland. Posted 26 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 818, lines 6-7 from the bottom. Change ``be an optimal solution to a primal linear program'' to ``be a feasible solution to the primal linear program'' and change ``be the optimal solution to the dual linear program'' to ``be a feasible solution to the dual linear program''.
Reported by Tom O'Connell. Posted 8 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 818, bottom line. The summation should be over j rather than over i.
Reported by Tom O'Connell. Posted 3 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 819, Problem 29-3. In the last sentence of part (c), change ``Show that'' to ``Assuming that both the primal integer program and the dual integer program are feasible and bounded, show that''.
Reported by Greg Plaxton. Posted 29 April 2002.
Severity level: 3
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Pages 819-820, Problem 29-4 (Farkas's lemma). Change ``and b be an m-vector'' to ``and c be an n-vector''. Change ``bx > 0'' to ``cTx > 0''. Change ``yA = b'' to ``ATy = c''.
Reported by Greg Plaxton. Posted 29 April 2002.
Severity level: 4
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Pages 823-827. There are several passages related to degree-bounds that need to be changed. The problem is that one cannot precisely refer to the degree-bound of a polynomial, since for a degree-n polynomial, any integer greater than n is a degree-bound. Make the following changes:
Page 823, lines 1-6 from the bottom. Change these lines to ``Note that degree(C) = degree(A) + degree(B), implying that if A is a polynomial of degree-bound na and B is a polynomial of degree-bound nb, then C is a a polynomial of degree-bound na + nb - 1. Since a polynomial of degree-bound k is also a polynomial of degree-bound k+1, we will normally say that the product polynomial C is a polynomial of degree-bound na + nb.''
Page 825, lines 7-9 from the bottom. Change the last sentence before Theorem 30.1 to ``The following theorem shows that interpolation is well defined when the desired interpolating polynomial must have a degree-bound equal to the given number of point-value pairs.''
Page 827, lines 11-16. Change the three sentences beginning on line 11 to ``We must face the problem, however, that degree(C) = degree(A) + degree(B); if A and B are of degree-bound n, then C is of degree-bound 2n. A standard point-value representation for A and B consists of n point-value pairs for each polynomial. Multiplying these together gives us n point-value pairs, but we need 2n pairs to interpolate a unique polynomial C of degree-bound 2n.''
Reported by San Skulrattanakulchai. Posted 28 November 2001.
Severity level: 4
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 832, statement of Lemma 30.6. Change ``nonnegative'' to ``nonzero''.
Reported by Michiel Smid. Posted 14 February 2002.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 837, line 10. Change ``-(n-1) < j′-j < n-1'' to ``-(n-1) ≤ j′-j ≤ n-1''.
Reported by San Skulrattanakulchai. Posted 9 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 841, ITERATIVE-FFT procedure. Add a new line (line 14) to the end of the procedure, not nested in any loop, and reading ``return A''.
Reported by Sekar Sundarraj. Posted 29 March 2004.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 846, Problem 30-5. In the first sentence, change ``degree-bound n-1'' to ``degree-bound n''.
Reported by Ferenc Schipp. Posted 6 June 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 850, line 19. Change ``Θ(βlg2 3)'' to ``Θ(βlg 3)''.
Reported by Tom Cormen. Posted 15 February 2003.
Severity level: 1
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 851, line 1. Change ``of an integer a'' to ``of a nonzero integer a''.
Reported by San Skulrattanakulchai. Posted 11 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 852, line 23. Change ``If a and b are not both 0'' to ``If a and b are both nonzero''.
Reported by San Skulrattanakulchai. Posted 11 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 853, line 9. Change ``since a mod s < s'' to ``since 0 ≤ a mod s < s''.
Reported by San Skulrattanakulchai. Posted 11 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 855. Exercise 31.1-6 should read ``Prove that if a and b are any positive integers such that a | b ...'' That is, both a and b are required to be positive. (Note: we misspelled ``positive'' as ``postive'' in the second printing.)
Reported by San Skulrattanakulchai. Posted 8 September 2001.
Severity level: 3
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 863, line 4 from the bottom. Change ``This size'' to ``The size''.
Reported by Constance Sawyer. Posted 5 November 2001.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 886, line 13 from the bottom. Change ``one-way hash function'' to ``collision-resistant hash function''.
Reported by Ron Rivest. Posted 19 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 887, Exercise 31.7-2. Add the condition on d that 0 < d < φ(n).
Reported by Richard Beigel. Posted 6 March 2003.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 896, line 6. Change ``using an improved version of Theorem 31.39'' to ``using an improved version of Theorem 31.38''.
Reported by Kai Huang. Posted 21 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 905, line 7. Change ``seive'' to ``sieve''.
Reported by George Stephanides. Posted 16 April 2004.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 908, Figure 32.3, part (c). The shaded region of z should be the same width as the shaded regions of x and y.
Reported by San Skulrattanakulchai. Posted 27 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 916, line 4. The summation should run from i=0 to n-1, not to n.
Reported by San Skulrattanakulchai. Posted 27 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 927, line 21. Change ``π(i+1)[q] = π[π(i)[q]]'' to ``π(i)[q] = π[π(i-1)[q]]''.
Reported by San Skulrattanakulchai. Posted 27 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 966, lines 5-7 from the bottom. Change ``Finding the longest simple path between two vertices is NP-complete, however. In fact, it is NP-complete even if all edge weights are 1.'' to ``Finding a longest simple path between two vertices is difficult, however. Merely determining whether a graph contains a simple path with at least a given number of edges is NP-complete.'' (Also reported by Joel Seiferas.)
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 968, line 5. Change ``then every NP-complete problem'' to ``then every problem in NP''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 968, line 2 from the bottom. Change ``and we wish to find the feasible solution'' to ``and we wish to find a feasible solution''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 969, line 1. Change ``and we wish to find the path'' to ``and we wish to find a path''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 977, line 6. Change ``uses breadth-first search to compute the shortest path'' to ``uses breadth-first search to compute a shortest path''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 977, line 11. Change ``instances in which the shortest path'' to ``instances in which a shortest path''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 978, line 3 of Exercise 34.1-1. Change ``in the longest simple path'' to ``in a longest simple path''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 981, line 5. Change ``in the hamiltonian cycle'' to ``in some hamiltonian cycle''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 997, Theorem 34.9, first line of proof. Change ``Then we prove that CIRCUIT-SAT is NP-hard'' to ``Then we prove that SAT is NP-hard.''
Reported by He Jun. Posted 15 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1011, lines 16-17. Change ``we form a hamiltonian cycle in G by'' to ``we form a hamiltonian cycle in G′ by''.
Reported by Xin Li. Posted 9 December 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1013, line 13. Change ``(G′, c, 0)'' to ``<G′, c, 0>''.
Reported by San Skulrattanakulchai. Posted 12 November 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1021, line 1. Change ``polyomial-time'' to ``polynomial-time''.
Reported by San Skulrattanakulchai. Posted 16 November 2001.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1021, line 11. Change ``Papadimitiou'' to ``Papadimitriou''.
Reported by Geoffrey King. Posted 11 January 2002.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1024, line 17. Change ``approximatation'' to ``approximation''.
Reported by Johan Gade. Posted 13 May 2004.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1032, line 10. Change ``there is a gap of at least |V|'' to ``there is a gap of at least ρ|V|''.
Reported by Tom O'Connell. Posted 9 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1032, lines 21 and 24. Change ``we can produce a minimization problem Y'' to ``we can produce in polynomial time a minimization problem Y'', and change ``there is no ρ-approximation algorithm for problem Y'' to ``there is no polynomial-time ρ-approximation algorithm for problem Y''.
Reported by San Skulrattanakulchai. Posted 19 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1033, Exercise 35.2-3. Change the first sentence to ``Consider the following closest-point heuristic for building an approximate traveling-salesman tour whose cost function satisfies the triangle inequality.''
Reported by San Skulrattanakulchai. Posted 19 November 2001.
Severity level: 3
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1040, second line of the proof of Theorem 35.6. Change ``1, 2, ..., n'' to ``1, 2, ..., m''.
Reported by Johan Gade. Posted 13 May 2004.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1041. Equations (35.13) and (35.16) should apply to each edge (u, v) in E (not to each vertex v in V).
Reported by Tom O'Connell. Posted 7 September 2001.
Severity level: 2
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 1041. Change the first sentence after (35.14) to read ``In the special case in which all the weights w(v) are equal to 1, this formulation is the optimization version of the NP-hard vertex-cover problem.''.
Reported by Joel Seiferas. Posted 27 April 2004.
Severity level: 3
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1052, line 3. Change ``max1 ≤ j ≤ n Ck'' to ``max1 ≤ j ≤ n Cj''.
Reported by Kimo Johnson. Posted 8 March 2004.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1053, line 17. Add a period to the end of the sentence.
Reported by Anna Iványi. Posted 22 July 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1053, line 19. Change ``Christofedes'' to ``Christofides''.
Reported by San Skulrattanakulchai. Posted 21 September 2001.
Severity level: 1
Corrected in the second printing.
--------------------------------------------------------------------------------
Page 1058, line 6 from the bottom. Change ``is an nonnegative integer'' to ``is a nonnegative integer''.
Reported by Luke Hodgkinson. Posted 19 August 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1066, line 7 from the bottom. Change ``floor(lg n) pieces'' to ``floor(lg n) + 1 pieces''. (HTML does not permit us to print the appropriate floor symbol.) Also, Page 1066, line 2 from the bottom. Change ``≤'' to ``=''.
Reported by Pavel Fabian. Posted 26 September 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1076, line 4 from the bottom. Change ``there may several'' to ``there may be several''.
Reported by Constance Sawyer. Posted 5 November 2001.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1083, line 7 of the main text. Change ``That is, v is a neighbor of u if either'' to ``That is, v is a neighbor of u if u ≠ v and either''.
Reported by San Skulrattanakulchai. Posted 6 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1091, Exercise B.5-7. Change ``Show that every binary tree'' to ``Show that if L ≥ 2, then every binary tree''.
Reported by San Skulrattanakulchai. Posted 6 October 2001.
Severity level: 2
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1107, line 9. Remove the set braces from the subscript of the summation.
Reported by Charles Leiserson. Posted 22 August 2002.
Severity level: 2
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 1110, line 18. Change ``positive square root'' to ``nonnegative square root''.
Reported by Antal Iványi. Posted 12 May 2003.
Severity level: 2
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1117, Exercise C.4-8. In the inequality to be proven, change less-than-or-equal to greater-than-or-equal.
Reported by Guolong Lin. Posted 27 September 2002.
Severity level: 3
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 1128, reference [29]. Change ``Jeffery'' to ``Jeffrey''.
Reported by Antal Iványi. Posted 24 March 2003.
Severity level: 1
Corrected in the fourth printing.
--------------------------------------------------------------------------------
Page 1132, reference [96]. Change ``Szermerédi'' to ``Szemerédi''.
Reported by Antal Iványi. Posted 25 April 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1135, reference [171]. Change ``Birk?user'' to ``Birkh?user''.
Reported by Antal Iványi. Posted 29 October 2001.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1138, reference [222]. Change ``MIT Press'' to ``The MIT Press''.
Reported by Antal Iványi. Posted 4 August 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1138, reference [228]. Change ``Unveristy'' to ``University''.
Reported by Anna Iványi. Posted 24 July 2003.
Severity level: 1
Corrected in the fifth printing.
--------------------------------------------------------------------------------
Page 1140, reference [266]. The title should be in title case: ``Theory of Linear and Integer Programming''.
Reported by Antal Iványi. Posted 29 October 2001.
Severity level: 1
Corrected in the third printing.
--------------------------------------------------------------------------------
Page 1150. There should be a blank line between the index entries for ``butterfly operation'' and ``cache''.
Reported by Tom Cormen. Posted 13 May 2001.
Severity level: 1
Corrected in the second printing.
