Subject: Re: new-bug-list Date: Tue, 25 Jul 2000 07:03:41 -0400 (EDT) From: algorithms@theory.lcs.mit.edu (algorithms) To: jcampos@posta.unizar.es Subject: New-Bug-List Dear Reader: Your email addressed to "algorithms@theory.lcs.mit.edu" has been handled by an automatic server program that generated this response. This server provides several services for readers of INTRODUCTION TO ALGORITHMS by Cormen, Leiserson, and Rivest (MIT Press and McGraw-Hill, 1990). If this service is not what you expected, please email a message to "algorithms@theory.lcs.mit.edu" that contains the line "Subject: Help" in the header. The automatic server will respond with a full description of the service. If the server program seems to be broken somehow, send email to William Ang (ang@theory.lcs.mit.edu). In response to your "New-Bug-List" request, here is a list of bug reports that have been recently submitted by readers. The accuracy of these reports has not yet been verified by the authors. ---------------------------------------------------------------------- From: anderson@cs.washington.edu Date: Wed, 13 Jan 93 09:41:46 -0800 Page 73, Problem 4-4b. The boundary condition T(n)<= 2 is not sufficient for the recurrence T(n) = 3T(n/3 + 5) + n/2. --------------------------------------------------------------- From: thc@monroe.dartmouth.edu (Thomas Cormen) Date: Tue, 2 Feb 93 09:46:18 -0500 From: joel@cs.rochester.edu Minor corrections nearby: In the eighth-to-last line on page 141, ``smaller'' should be ``no larger''. Exercise 7.4-3 should refer to ``worst-case running time'' rather than just plain ``running time'', according to the guidelines on page 28. For example, the cases with all elements equal require time only O(n). Joel Seiferas joel@cs.rochester.edu Computer Science Department voice (716)275-7898 University of Rochester fax (716)461-2018 Rochester, New York 14627-0226 home (716)442-7396 --------------------------------------------------------------- From: sunshine@image.mit.edu (Lon Sunshine) Date: Wed, 3 Feb 93 13:50:34 EST page 82, line 11: "...equivalent to A." should read "...equivalent to a." Lon Sunshine --------------------------------------------------------------- From: Peter Csaszar Date: Thu, 04 Feb 93 10:34:53 CST A minor bug's gonna be reported, but it's a BUG anyway! Page 286, Exercise 15.1-7 Change ((Show how to use an order-statistic tree to to count ...)) to <> Peter Csaszar csaszar@bert.eecs.uic.edu University of Illinois at Chicago u60896@uicvm.cc.uic.edu College of Engineering Dept. of Electrical Engineering Computer Science --------------------------------------------------------------- From: joel@cs.rochester.edu Date: Thu, 4 Feb 93 13:54:09 -0500 Page 173, lines -5 to -3: This is true only if the path's test outcomes are consistent. Perhaps the fix is to prune inconsistent continuations from such trees. --------------------------------------------------------------- From: singer@trio.mit.edu (Andrew C Singer) Date: Thu, 11 Feb 93 14:59:29 EST Page 95 line -2 "... have degree k" should read "... have degree k+1" --------------------------------------------------------------- From: singer@trio.mit.edu (Andrew C Singer) Date: Thu, 11 Feb 93 15:04:54 EST Page 110 problem 6.2-10 This is the famed "Monty Hall" problem. You have to be very careful in the problem statement to explicitly state that the "Game Host" knows which curtain hides the prize, and that no matter which curtain you pick, the host will _ALWAYS_ show you an empty stage. --------------------------------------------------------------- From: marc@es.ele.tue.nl (Marc Heijligers) Date: Tue, 16 Feb 93 14:25:57 +0100 The errata 1.2 list contains a mistake on page 13: The errata considering the bug on page 487, lines -10 to -8, problem 23.4-1, refers to exercise 23.3-3. This should a reference to exercise 23.3-2. Marc --------------------------------------------------------------- From: yiannis@sun350j.ccs.northeastern.edu (Ioannis Tsiounis) Date: Tue, 2 Mar 93 12:45:20 EST Could I have the bugs, please ? --------------------------------------------------------------- From: yiannis@sun350j.ccs.northeastern.edu (Ioannis Tsiounis) Date: Tue, 2 Mar 93 12:51:14 EST The previous mail was a mistake, sorry. The bug is in page 143, Procedure Heapify(A,i). After step 2, and before step 3, the variable "largest" should be initialized to i. Yiannis --------------------------------------------------------------- From: Jian Wang Date: Wed, 3 Mar 1993 12:51:16 -0800 A bug in the hint of the problem 26.2-3, it says: pi(k,i,j)=l => d(k,i,j) >= d(k-1,i,l) + w(l,j). A counterexample can be found in Fig 26.4: pi(5,1,2)=3, d(5,1,2)=1, d(4,1,3)=-1,w(3,2)=4 apparently d(5,1,2) = 1 < d(4,1,3) + w(3,2) The right relation is: pi(k,i,j)=l => d(k,i,j) >= d(k,i,l) + w(l,j) and it can be proved by induction. Jian Wang --------------------------------------------------------------- From: Jian Wang Date: Sun, 14 Mar 1993 19:48:20 -0800 page 923, line -3 '... of a undirected graph ...' should be '... of an undirected graph ...' Jian Wang --------------------------------------------------------------- From: wellman@engin.umich.edu (Michael Wellman) Date: Wed, 17 Mar 93 22:48:15 -0500 Section 35.1, p. 890 states that line segments p1p2 and p3p4 must intersect if (1) p3 or p4 is collinear with p1p2 and (2) the segments pass the quick-rejection test. A counterexample is: p1: (0,0) p2: (5,5) p3: (2,4) p4: (6,6) where p1, p2, and p4 are collinear, quick rejection fails (p3p4 is clearly in the bounding box of p1p2), but the two segments do not intersect. One way to fix this is to specifically check, when the cross-product is zero, whether p4 (or p3) is on the segment p1p2. --Mike. Michael P. Wellman University of Michigan, Dept of EECS Artificial Intelligence Laboratory 1101 Beal Avenue Ann Arbor, MI 48109 tel: (313) 764-6894 fax: (313) 763-1260 --------------------------------------------------------------- From: yannis@Athena.MIT.EDU Date: Sat, 03 Apr 93 12:59:36 EST In page 541 under title "Constraint graphs", third line: "the nxm linear programming matrix A" should read "the mxn linear programming matrix A". Ioannis Ch. Paschalidis Laboratory for Information and Decision Systems MIT --------------------------------------------------------------- From: sloan@turing.eecs.uic.edu (Bob Sloan) Date: Tue, 6 Apr 93 16:14:56 CDT Page 651, problem 28-2. The description of Batcher's odd-even sort is incorrect. You merge the odds with odds and the evens with the evens, and then put comparators between positions 2i-1 and 2i. Example of network not working: 8 inputs, with each sorted half being three 0's and one 1. After merging odds together and evens together, we have 0's in all the odd positions, 0's in positions 2 and 4, and 1's in positions 6 and 8. The last set of comparators are between pairs (1,2) (3,4) (5,6) and (7,8), so no exchanges are made, leaving us with 00000101. Fixes: (A) Merge evens of the first half with odds from the second half, and in the interleaving to reassemble put this list first, interleaved with the merge of odds from the first half with evens from the second half. (B) Alternatively, put the final set of comparators between elements 2i and 2i+i, for i = 1,2,...,n-1. --------------------------------------------------------------- From: Christian S. Collberg Date: Thu, 22 Apr 93 13:47:38 +0200 Page 276, first line of caption: RB-DELETE should be RB-DELETE-FIXUP. Christian S. Collberg ----- Christian.Collberg@dna.lth.se Department of Computer Science, Lund University, BOX 118, S-221 00 LUND, Sweden --------------------------------------------------------------- From: wiener@haze.rap.ucar.EDU (Gerry Wiener) Date: Wed, 28 Apr 93 09:29:52 -0600 First Printing pg 530, 2nd paragraph from the bottom You mention that the modified Dijkstra algorithm is accomplished through using the call DECREASE-KEY(Q, v, d[u] + w(u,v)) (Exercise 7.5-4). This is misleading. A vertex v adjacent to u does not necessarily lie at Q[v] in the heap. One first has to locate v's position in the heap and then do DECREASE-KEY(Q, position(v), d[u] + w(u,v)). One can avoid searching for a vertex in the heap by making suitable modifications to the heap routines to keep track of a vertex's position. In particular, HEAPIFY(), HEAP-EXTRACT-MIN() and HEAP-DECREASE-KEY() need to be altered slightly. If you want further details or a c-code implementation let me know. Gerry Wiener Email:gerry@ncar.ucar.edu --------------------------------------------------------------- From: zwick@math.tau.ac.il Date: Mon, 3 May 93 17:26:17 GMT+3:00 Two minor problems with Problem 25-5 page 548. In item (c) it should be assumed that G contains no negative cycles otherwise \delta(s,v) and \delta(s,u) are not well defined. It is probably best to assume that \mu^*=0 as was done in the previous items. Item (d) should be changed to "Show that if \mu^*=0 then on every minimum mean-weight cycle there exists a vertex v such that ... ". This is becuase the minimum mean-weight cycle is not necessarily unique and it is a mistake to speak of THE minimum mean-weight cycle. Same correction required in the hint given. Uri ---------------------------------------------------------- | | Uri Zwick | | zwick@math.tau.ac.il | Dept. of Computer Science | | | Tel Aviv University | | PHONE: +972 3 6408829 | Tel Aviv 69978 | | FAX: +972 3 6409357 | ISRAEL | ---------------------------------------------------------- --------------------------------------------------------------- From: dietz@cs.rochester.edu Date: Thu, 6 May 93 16:48:41 -0400 Page 354, Problem 17-2, part b. A counterexample: the columns of the incidence matrix of a 3-cycle are linearly independent. Paul F. Dietz dietz@cs.rochester.edu --------------------------------------------------------------- From: "Fumiaki Kamiya" Date: Sat, 05 Jun 93 12:53:07 -0400 Page 48, first paragraph: Since the summation starts from k=1, each term is bounded above by $(1/3)(2/3)^{k-1}$ (and not $(1/3)(2/3)^k$). Thus, in lines 5 and 6, $(1/3)(2/3)^{k-1}$. Fumiaki Kamiya --------------------------------------------------------------- From: woun3887@mstr.hgc.edu (richard woundy) Date: Tue, 15 Jun 93 19:42:25 -0400 Page 37, Exercise 2.2-2. The assertion is not correct for T(n) asymptotically less than one (e.g. T(n) = 0.5). Obviously, if T(n) < 1, k it is true that T(n) = O(n ) for any constant k > 0, O(1) but it cannot be the case that T(n) = n . Otherwise, we could f(n) find some function f(n) = O(1) such that T(n) = n < 1. This wound require that f(n) < 0 for all n >= 1, which contradicts the definition of O-notation. --------------------------------------------------------------- From: alex@cs.UMD.EDU (Alex Blakemore) Date: Mon, 23 Aug 93 22:14:18 EDT In the middle of the last paragraph on page 223, the following sentence appears. "Deletion of an element x can be accomplished in O(1) time if the lists are doubly linked." That is true only if you already have a pointer to the element you wish to delete from the list. Perhaps you assume that the deletion operation takes a pointer to the element to be deleted as an argument, (as opposed to just the key). That does not seem like a natural definition of the deletion command. If so, you expect the pointer to each element that has been inserted in the hash table to be stored externally (in perhaps another hash table :-) if the deletion operation takes a key as an argument, (as do all hash table implementations that I have used) then deletion from a chained hash table has the same complexity as searching and insertion, irrespective of whether the list is doubly or singly linked. P.S. great book by the way -- Alex Blakemore alex@cs.umd.edu NeXT mail accepted -------------------------------------------------------------- "Without an engaged and motivated human being at the keyboard, the computer is just another dumb box." William Raspberry --------------------------------------------------------------- From: jack@sanjuan.UVic.CA (Jack Chan) Date: Thu, 23 Sep 93 20:23:23 PDT ----------------------------------------------- Page 874, right after the proof of Lemma 34.6 * E = { k < q-1 : k in pi [q-1] and P[k+1]=P[q] }. q-1 instead of * E = { k : k in pi [q-1] and P[k+1]=P[q] }. q-1 Jack T.H. Chan --------------------------------------------- Page 874, line before Corollary 34.7 "... and get a proper suffix of ..." instead of "... and get a suffix of ..." suggested by John Ellis ----------------------------------------------- --------------------------------------------------------------- From: rivest@theory.lcs.mit.edu (Ron Rivest) Date: Wed, 06 Oct 93 14:05:00 EDT You can find out about our electronic distribution by sending mail to algorithms@theory.lcs.mit.edu with the word "help" in the subject line. I think "bug-list" as the subject line gets you the latest bug list... Cheers, Ron ------------------------------------------------------------------------------ Return-Path: Date: Mon, 20 Sep 93 11:36:16 -0400 From: klein@cs.brown.edu (Philip Klein) To: rivest@theory.lcs.mit.edu Subject: bug list for CLR? Ron, Where can I get the most recent bug list for CLR? Also, a student discovered an exercise that is somewhat problematic, exercise 2.2-2. T(n) could be 1/n and hence O(n^k) without being n^{O(1)}. --------------------------------------------------------------- From: bradley@whopper.lcs.mit.edu (Bradley C. Kuszmaul) Date: Wed, 13 Oct 93 15:22:25 EDT "little-o index bugs" There should be index entries for "little-oh" (under "l") "little-omega" "big-Oh", (under "b") and "big-omega" Also, "o-notation" seems to be out of alphabetical order. Also, There is no index entry under "Omega" for $\Omega$-notation. -Bradley P.s. is this a bug or a suggestion? I could not quite decide based on the help message sent by the algorithms mailing daemon... -B --------------------------------------------------------------- From: Samir Jain Date: Wed, 20 Oct 93 00:57:12 -0400 Just a small typo: Page 299, Paragraph 2, line 6: "memoize" --> "memorize" --------------------------------------------------------------- From: Samir Jain Date: Wed, 20 Oct 93 02:08:56 -0400 Whoops, my fault. I see now that the book *is* indeed correct. >Date: Wed, 20 Oct 93 00:57:12 -0400 >Just a small typo: >Page 299, Paragraph 2, line 6: "memoize" --> "memorize" Sam --------------------------------------------------------------- From: kaun@northstar.dartmouth.edu (Sanjay Khanna) Date: Wed, 20 Oct 93 18:19:37 -0400 I found a bug in problem 11-3 on page 217 of the book "Introduction to Algorithms," and I was looking through the bug report to see if it was already there. The fix that has been proposed is incorrect. Please examine the fix proposed below as discussed: ---------- bug report in bugs2.ps from ftp site ---------- Page 217, Problem 11-3 [fix by John Gateley] The code for Compact-List-Search does not work properly when searching for the first element of the list. The test <> in line 3 of the code should be replaced by <> ---------- end of bug report from ftp site ---------- This does not fix the problem because in line 7 of the code, i is bumped to point to next[i]. I propose the following fix which also improves the running time of the algorithm. ----- proposed bug report for problem 11-3 page 217 ----- Page 217, Problem 11-3 The code for Compact-List-Search returns nil if the key to be found is the first element of the list. If the while loop is modified to end after line 7 of the code, then not only does it work properly, but it is also made more efficient because it would have to do less comparisons. That way when it came out of the while loop, it would check for equality and then return i, otherwise return nil. ----- end of proposed bug report for problem 11-3 ----- --------------------------------------------------------------- From: cchen@cse.ttit.edu.tw (Chienhua Chen) Date: Fri, 29 Oct 1993 10:21:26 +0800 (WST) Page 390, lines 3--4 after the procedure B-Tree-Split-Child The text should read << ... has 2t-1 keys but is reduced to t-1 keys by this operation. Node z "adopts" the t-1 largest keys of y, ...>> --------------------------------------------------------------- From: melkman@black.bgu.ac.il (melkman abraham) Date: Wed, 3 Nov 93 09:30:51-020 --------------------------------------------------------------- From: mike@psarc.com (Michael D. Sofka) Date: Wed, 24 Nov 93 14:22:09 -0500 On page 173 figure 9.1 the decision tree is incorrect. The values for <3,1,2> and <2,3,1> should be reversed since a_2 <= a_3 in the former value and a_2 > a_3 in the latter. -- Michael D. Sofka mike@psarc.com Publication Services, Inc. --------------------------------------------------------------- From: rose@yoda.eng.hou.compaq.com (Eric Rose) Date: Fri, 10 Dec 93 15:00:01 CST Bug: Page 923, line 7 "wee" instead of "we". --------------------------------------------------------------- From: Andy Fingerhut Date: Thu, 16 Dec 1993 16:22:37 -0600 I have a copy of the third printing of Cormen, Leiserson, and Rivest's Intro. to Algorithms. In Problem 28-2 on page 651, the definition of Batcher's odd-even merging network is incorrect. To see this, note that the 2n-input merge network for n=2 passes through the inputs 1 3 2 4 unchanged. The two sentences: "The first merges the sequences on lines with the sequence on lines (the odd elements). The second merges with (the even elements)." should be replaced with something like the following. Feel free to replace the comments in parentheses with anything you want. "The first merges the sequences on lines with the sequence on the lines (the odd elements of the top half with the even elements of the bottom half). The second merges with (the top evens with the bottom odds)." Also, a minor nitpick in the bug list for the second printing. The bug with the header "Page 190, Exercise 7.5-1" should be "Page 150, Exercise 7.5-1" Andy Fingerhut jaf@dworkin.wustl.edu Washington University, St. Louis MO --------------------------------------------------------------- # 261 From: Clark Thomborson Date: Wed, 5 Jan 1994 18:48:46 -0600 Some of my students had trouble following the proof on page 191. One problem is the unmotivated insertion of the constant 80; the other is the cavalier treatment of O(n). I suggest you add a parenthetic comment along the lines of "(We chose the value 80 after completing the first draft of our proof.)" As for the conceptual problem with the O(n), it might be worth mentioning that the "function described by the O(n) term" in the last step of the proof is not the same as the function described by the O(n) term in the runtime recurrence, unless perchance the O(n) in the runtime recurrence dominates the \Theta(1) term in its boundary condition. However, I think that my students were confused on much more fundamental grounds. They seemed satisfied when I gave a fuller explanation of the last step in the proof, along the following lines: The last step, $T(n) \leq 9cn/10 + 7c + O(n)$ implies $T(n) \leq cn$, is valid only if we establish that $cn - (9cn/10 + 7c + O(n)) \geq 0$. Introducing $an$ as an upper bound on the $O(n)$ term, then solving for $c$, we find that we must fix $c \geq a/(1/10 - 7/n)$. Note that the denominator of this lower bound for $c$ is zero at $n = 70$, and negative for $n < 70$. This is the reason we included all $n \leq 80$ in the base case of our induction: our induction hypothesis $T(n) \leq cn$ is indeed established for any $c \geq a/(1/10 - 7/80) = 80a$. (Overall, it's a great book. Thanks for writing it!) Clark --------------------------------------------------------------- # 262 From: cchen@cse.ttit.edu.tw (Chienhua Chen) Date: Fri, 7 Jan 1994 09:39:01 +0800 (WST) Page 529, line -9 Change (( x \in V )) to << x \in S >> --------------------------------------------------------------- # 263 From: Clark Thomborson Date: Tue, 1 Feb 1994 18:09:55 -0600 pages 4-5, Pseudocode conventions: Add a new item, along the following lines. (I've included LaTex formatting codes...) 9. Pascal programmers beware! Our {\bf and} and {\bf or} logical operators specify ``lazy'' or ``partial'' evaluation. For example, in the evaluation of the expression $a$ {\bf and} $b$, if the operand $a$ on the left-hand side of the {\bf and} operator evaluates to {\bf FALSE}, then the operand $b$ is never evaluated. These semantics allow us to write expressions of the form {\bf if} $x \neq$ {\bf NIL} {\bf and} $p[x]$ {\bf then} $...$ without fear of provoking the dreaded ``segmentation fault'' error message on a Unix system. Alternatively, rewrite line 3 of RB-Insert(T,x), on page 268 to use the Pascal semantics for {\bf and}. If you do this, I'd recommend making a scan of all the {\bf and}s and {\bf or}s in your codes, to make sure that no other segmentation faults are lurking. -------- Notes: In standard Pascal, all terms of a logical expression may be evaluated. Ref: Cooper&Clancy, 2nd ed, 1985, p. 191. I don't have a standards document handy, but Landis concurs in his {\it C for Pascal Programmers}, 1989, p. 31. I don't know how Fortran's {\bf AND} works. I vaguely recall running across a conditional and {\bf CAND} in some language or another, with ``lazy'' semantics. Most, if not all, Pascal compilers can be directed by command-line argument to use non-standard semantics for {\bf and} and {\bf or} similar (or perhaps identical) to the one you are apparently employing. For example, on a Sun, you can use {\tt pc -P}. Clark --------------------------------------------------------------- # 264 From: todd@hposl03.cup.hp.com (Todd Poynor) Date: Fri, 4 Feb 1994 14:28:40 -0800 Eighth printing, page 821, line 3 of Theorem 33.24: The phrase "this equation has exactly d distinct solutions, modulo n, given by" is misleading, as the solutions are specified "for i = 1,2,...,d-1", which presents d-1 solutions. The x0 solution could be explicitly added to the list. If you don't have a problem with defining something in terms of itself when its value is already given, change (( i = 1,2,...,d-1 )) to << i = 0,1,...,d-1 >> . -- Todd Poynor "I would have a watch that says 'Arrive Late' on it." -- Karen Finley --------------------------------------------------------------- # 265 From: cetto@ecn.purdue.edu (Juan Andrade-Cetto) Date: Tue, 8 Feb 94 01:13:17 -0500 page 4, eighth printing, 1992. line 7 from bottom to top. reads " ...and else have the the same interpretation... " must read " ...and else have the same interpretation... " Juan Andrade-Cetto --------------------------------------------------------------- # 266 From: cel@theory.lcs.mit.edu (Charles E. Leiserson) Date: Wed, 09 Feb 94 13:19:52 EST Page 468, Exercise 23.1-6. The term "sink" would more appropriately be called a "universal sink". --------------------------------------------------------------- # 267 From: Richard Chang Date: Wed, 16 Feb 1994 15:33:28 -0500 In the second edition of the book, page 126, Exercise 6.5-5, the hint says to show: p_i e^{\alpha q_i} + q_i e^{-\alpha p_i} \leq e^{- \alpha^2 /2} I think the negative sign on the right hand side is a typo. In particular, the inequality does not hold for \alpha = 1, p_i = q_i = 1/2. The probable correction is: p_i e^{\alpha q_i} + q_i e^{-\alpha p_i} \leq e^{\alpha^2 /2} which gives the desired theorem by substituting r/n for \alpha. Richard Chang (chang@cs.umbc.edu) --------------------------------------------------------------- # 268 From: cel@theory.lcs.mit.edu (Charles E. Leiserson) Date: Thu, 17 Feb 94 12:04:46 EST The "mod" function seems not to be defined, except somewhat implicitly in the Division theorem on page 803. It is used extensively before then. Perhaps it should be defined in Section 2.2 in terms of the floor function: $a \bmod b = a - b\cdot\floor{a/b}$. (Question: Is this a good definition if $a$ or $b$ is negative?) --------------------------------------------------------------- # 269 From: FELZER TORSTEN Date: Wed, 2 Mar 1994 23:21:30 -0700 (MST) In exercise 32.2-7 on page 791, $P(x)$ should be a polynomial of degree $\leq n$ (or of degree-bound $n+1$), and not of degree-bound $n$, since a polynomial of degree-bound $n$ has at most degree $n-1$, and a degree $n-1$ polynomial can have at most $n-1$ roots, but $P(x)$ has up to $n$ roots (if all the $z_i$ are different). If $P(x)$ has $n$ roots (not more and not less) then $P(x)$ has at least degree $n$, degree $n-1$ is not possible. Besides, you cannot uniquely determine the coefficients of "the" polynomial $P(x)$ that has zeroes only at $z_0,z_1,\dots,z_{n-1}$, you can only find the coefficients of "one" polynomial $P(x)$ among all those that satisfy this property, because in fact all $P_a(x)$ with $P_a(x)=a(x-z_0)(x-z_1)\cdot\dots\cdot (x-z_{n-1})$ for arbitrary $a\not= 0$ have zeroes only at $z_0,z_1,\dots,z_{n-1}$. The $a$ in $P(x)$ cannot be determined without additional information. Best wishes, TORSTEN FELZER --------------------------------------------------------------- # 270 From: rivest@theory.lcs.mit.edu (Ron Rivest) Date: Mon, 07 Mar 94 11:36:20 EST Exercise 9-4.4 (page 183) could be improved by removing any possibility of having an "atom" of weight on the smallest element. (This is not inconsistent with having a continuous distribution.) This was presumably what was actually intended here. Maybe emphasize that random variable is real-valued, and state explicitly that no element x has p(x)>0 (i.e. no atoms exist). [Bug reported to me by Igal Galperin]. Ron Rivest --------------------------------------------------------------- # 271 From: lambert@cse.unsw.edu.au (Tim Lambert) Date: Thu, 10 Mar 94 16:26:46 +1000 The divide and conquer algorithm for closest pair (pages 908-912) contains an error. The pseudocode given for splitting a sorted array Y into two sorted arrays Y_L and Y_R (page 911) puts both Y_L and Y_R in the same place (on top of Y). We need to create two local array variables to store Y_L and Y_R. This is a problem in a language like Pascal -- we must declare arrays of size n (the number of points in the original problem and not the divided problem) and total storage requirements will be O(n log n). Even in a langauge like C which allows us to malloc an array of the size of the divided problem, some analysis is required to show that space requirements do not blow up to O(n log n). Alternatively, we can reuse Y, be storing Y_L and Y_R in it. This leaves us with a problem -- we need Y for the combine step, and we just destroyed it in the divide step. Can we restore Y during the divide step? Sure. We just need the opposite of the splitting method on page 911, which is the opposite of the opposite of the MERGE procedure of merge sort. Oh. That's just the MERGE procedure. We can now simplify the algorithm by observing that we don't need to presort by y or pass Y sorted arrays to recursive calls. Each recursive call produces two things -- a closest pair for the given points, and a y sort of the given points. The whole thing can be done inside one array which starts off sorted by x and ends up sorted by y and has a very interesting structure in the intermediate stages. Tim --------------------------------------------------------------- From: p6ip051@cicrp.jussieu.fr (Xavier CAZIN) Date: Sun, 27 Mar 94 17:23:39 EST Page 4, line -7 : replace "the the" by "the" ; %% Fixed already Page 11, Exercise 1.2-4 : the first \cdots is unneeded ; %% Not a bug. Ellipsis is for missing parens Page 287, line -14 : replace "fields" by "field" ; # 272 Page 340, line -8 : replace "$\abs{n}-1$" by "$n-1$" ; # 273 Page 354, part (c) : remove one "an" in "...find an an acyclique..." ; # 274 part (e), 3rd line : remove one "and" ; # 275 part (e), 4th line : replace "edges of $G$" by "columns of $M$" ; # 276 Page 360, line 6 : replace "next-highest-order" by "next-lowest-order" ; %% Not a bug Page 362, line 5 : replace "stack" by "plate" ; %% Not a bug Page 439, line -9 : replace "shortest pairs" by "shortest paths" ; # 277 Page 490, line 14 : replace "theorem" by "lemma" ; # 278 Page 513, in revision 2.1 (in the files, not book), the paper of Gabow, Galil, Spencer, and Tarjan is mentioned to be an ehancement of that of Fredman and Tarjan. According to the bib file, however, the former was published in 86, and the latter in 87. ; # 279 Page 520, line 2 : the second phrase "$G=(V,E)$" should be removed. ; %% Fixed already Page 575, line 9 of the code : replace "to" by "\To" ; # 280 Page 601, line -4 : lemma 27.10 is referred to as "The following theorem" ; # 281 Page 603, line 3 : ditto ; # 282 Page 680, line 17 : replace "the clock period $d$" by "the clock period" ; %% Not a bug Page 692, line -5 : replace "next[i]" by "\id{next}[i]" ; # 283 Page 704, line 7 : replace "the the" by "the" ; # 284 Page 727, line 7 : replace "to a parent." by "to its parent." ; # 285 Page 760, line 6 : replace "the the" by "the" ; # 286 Page 807, Proof : insert "as" between "left" and "Exercise" ; # 287 Page 826, line -2 : insert "of" between "each" and "the equations" ; # 288 Page 948, line -1 : delete "of" between "set" and "$V'$" ; # 289 Page 968, Exercise 37.1-1 : replace "Given" by "Give". # 290 ============================================================================ --------------------------------------------------------------- %% Not a bug From: blob@syl.dl.nec.com (David Blob) Date: Mon, 28 Mar 94 00:50:19 CST Hello, I beleive there is a bug in the Problem 15-2 on page 296. In part B you ask for a Solution for non-constant m which runs in O(n log n) time. In the solution discussed by Knuth, the solution builds a Inversion table, b, with the rule : b[i+1] = (b[i] + m - 1) mod (n - i). I am assuming the solution you intend for the student to provide is similar, and frankly do not see how it could be done without using mod in any case. At any rate, my point is that the cost of doing a mod is M(B), the time taken to multipy two B bit numbers together. Later in the book you point out that M(B) is O(B log B log log B), but generally dismiss it as being (B^2). In either case, B here would be log(max{m,n}), so I point out that the best possible running time for the algorithm is O(n M(max{m,n})). Perhaps this could be fixed by adding the property that to the problem: "m and n are both within the bounds of hardware arithmetic operations". This would avoid the need to explain the concept of M(n), which does not appear until far later in the book. If I have made a mistake, please let me know. Thank you. - David Blob NEC Systems Labratories BTW, I really appreciate your book. --------------------------------------------------------------- %% Already fixed From: petermc@theory.lcs.mit.edu (Peter McCorquodale) Date: Wed, 30 Mar 94 12:38:06 EST Page 347, line -6: Change "an an" to "an". Peter McCorquodale, petermc@theory --------------------------------------------------------------- %% Not a bug From: tracey Date: Mon, 4 Apr 1994 20:12:26 +0100 (BST) >From : George Tracey Crawley College West Sussex England JANET Address gjt@uk.ac.bton.unix Subject : Chapter > 13 Section > 2 Title > Querying a binary search tree Firstly, thank you for a text I wish I had the time to read. I am only able to sample on occasions and find - ignoring the timing analysis - much that is interesting. I would be grateful for a list of known errors and apologise if my submission is already there. The TREE_SUCCESSOR function suffers from three flaws. 1. Binary search trees have no facility for climbing up and therefore the parent of a node is unobtainable. 2. Considering the paragraph 'On the other hand, if ........ and x has a successor' This presumably requires knowledge of a successor, which is not taken account of. 3. The definition of successor where it exists implies a degree of bactracking. This would be amended by the following Define a path as the set of nodes visited from the root to the key. If the key is in the tree and it is not the maximum then its successor is its own right pointer - if it exists - or its ancestor whose right pointer is not on its path. It follows from the above that the tree maxima should be obtained and the tree searched to establish the entry. The search mechanism could create a path list which would enable the tree to be climbed if needs be. --------------------------------------------------------------- # 291 From: Martin Tompa Date: Thu, 14 Apr 1994 16:55:49 PDT page 969, line 5: c(A) must be defined for a multiset A of edges rather than a subset of edges, in order for c(W) on page 970, equation (37.5) to be well-defined. --------------------------------------------------------------- # 292 From: Martin Tompa Date: Thu, 14 Apr 1994 16:58:18 PDT page 152, line 1 of problem 7-2: Change ((nodes have d children)) to <>. --------------------------------------------------------------- # 293 From: Rolf Karlsson Date: Wed, 11 May 94 15:26 MET DST Page 651, line -2: "a_{2i-1} and a_{2i} for i=1,2,...,n" should read "a_{2i} and a_{2i+1} for i=1,2,...,n-1" --------------------------------------------------------------- From: gereb@allegro.cs.tufts.edu (Mihaly Gereb) Date: Wed, 11 May 1994 14:31:24 +0500 ----- Begin Included Message ----- >From algorithms@theory.lcs.mit.edu Wed May 11 14:24 EDT 1994 Date: Wed, 11 May 94 14:25:42 EDT From: algorithms@theory.lcs.mit.edu (algorithms) To: gereb@allegro.cs.tufts.edu Subject: Too many arguments in Subject line You have specified more than one options in your "Subject line". The mail-server "algorithms@theory.lcs.mit.edu" cannot decide on what to do with your mail. Therefore, your original mail has been returned without further processing. Please make sure you have specified only one option in "Subject line". For more information, please send e-mail to algorithms@theory.lcs.mit.edu with a single word "help" in your subject line. -----------------returned email------------------ # 294 >From gereb@allegro.cs.tufts.edu Wed May 11 19:22:10 1994 Return-Path: Received: from Allegro.CS.Tufts.EDU by theory.lcs.mit.edu (5.65c/TOC-1.2S) id AA22681; Wed, 11 May 94 14:25:39 EDT Received: from gereb.tufts.edu by allegro.cs.tufts.edu (5.0/SMI-SVR4) id AA25537; Wed, 11 May 1994 14:24:36 +0500 Received: by gereb.tufts.edu (5.0/SMI-SVR4) id AA03181; Wed, 11 May 1994 14:22:10 +0500 Date: Wed, 11 May 1994 14:22:10 +0500 From: gereb@allegro.cs.tufts.edu (Mihaly Gereb) Message-Id: <9405111822.AA03181@gereb.tufts.edu> To: algorithms@theory.lcs.mit.edu Subject: error report Exercise 33.8-1 should exclude besides primes, and prime powers, 2*(prime powers) as well. since for those numbers (e.g. 6, 10, 14, 18,) 1 does not have non-trivial square root either. every other nmber is OK. Greetings Mihaly Gereb ----- End Included Message ----- --------------------------------------------------------------- # 295 From: ponzio@theory.lcs.mit.edu (Stephen J. Ponzio) Date: Tue, 14 Jun 94 12:10:55 EDT This is a correction of Stirling's approximation, Eqn. (2.12) on p. 35. Actually, I think the bugs document already includes this correction. I'm forwarding this so you will have the reference. Stephen ---------------------------------------------------------------------------- Return-Path: From: cel@theory.lcs.mit.edu (Charles E. Leiserson) Date: Thu, 09 Jun 94 22:10:18 EDT To: ponzio@theory.lcs.mit.edu Cc: ftl, koods, ponzio, brian In-Reply-To: Stephen J. Ponzio's message of Thu, 09 Jun 94 16:24:45 EDT <199406092024.AA01236@jacksnipe.lcs.mit.edu> Subject: Stirling's approx. > From: ponzio@theory.lcs.mit.edu (Stephen J. Ponzio) > Date: Thu, 09 Jun 94 16:24:45 EDT > > I just noticed that in "Random Graphs", Bollobas quotes it as > > n! = (n/e)^n \sqrt{2pin} e^{a_n} > > where > 1/(12n+1) < a_n < 1/(12n). > > This is a better upper bound than what we gave > (with (n/e)^{n+1/12n}) and it even looks like what we gave > isn't right for (n/e) < e. > > (And what's in CLR?) > > Bollobas references Robbins(AMM 62,1955). > > Steve > Steve, CLR has the bug you mention for small n. Please submit it to "algorithms@theory", and you'll receive an acknowledgment. Please mention these references. Cheers, Charles --------------------------------------------------------------- # 296 From: Jeffrey Shallit Date: Mon, 11 Jul 94 09:59:03 -0400 The construction reducing VERTEX-COVER to SUBSET SUM in Cormen, Leiserson, and Rivest, is, strictly speaking, incorrect. The problem is that it is possible for two different x_i to have the same value; since the problem deals with sets, rather than lists, this creates a problem. (I note that the issue of ensuring distinct x_i is not even raised in the reduction.) For example, consider the graph G consisting of two vertices and one edge. Then x_0 = (1 1) base 4, or 5; x_1 = (1 1) base 4, or 5, and y_0 = (0 1) base 4, or 1. Hence the constructed subset is {1, 5, 5} = {1, 5}. If we are asking, "does this graph have a vertex cover of size 2?", then the target in the transformed problem is (2 2) base 4, or 10. But there is no way to choose a subset of {1, 5} that sums to 10. This can be repaired in a variety of ways; one way is to include another set of bits that 'codes' the index of each of the x_i, and adjusting the target t accordingly. (That's a pain, though). You could also redefine the problem to work with multisets instead of sets. Jeff Shallit --------------------------------------------------------------- # 297 From: Jeffrey Shallit Date: Mon, 11 Jul 94 10:25:06 -0400 Here is another bug: on page 955, in the description of the edges in the middle of the page, you speak of adding edges (x'_m, x''_{m+1}). But the illustration on page 957 clearly shows edges (x''_m, x'_{m+1}) instead. Jeff --------------------------------------------------------------- # 298 From: thc@zayante.dartmouth.edu (Thomas Cormen) Date: Wed, 3 Aug 1994 11:12:59 -0400 Pages 418-419, Problem 20-2. This problem is actually not suited for mergeable heaps. Line 8 says "assume without loss of generality that u in V_i and v in V_j". But we need to KNOW which are sets V_i and V_j so that we can perform the Union operations required by lines 11 and 12. V_i isn't a problem, since it's the set we chose arbitrarily in line 6. But we cannot determine which set is V_j because the mergeable-heap operations do not include an operation analogous to Find-Set. Given a node, we have no way to determine which heap it's in. --------------------------------------------------------------- From: Norberto Arrieta Date: Sun, 11 Sep 94 13:59:08 -0700 --------------------------------------------------------------- # 299 From: greg@math.wayne.edu (Gregory Bachelis) Date: Fri, 30 Sep 94 11:28:26 EDT This is to report a possible bug, since I don't know the intent of the authors. On page 39, problem 2-4(c), was it the intention of the authors that the answer be "yes". As it now stands, the answer is "no", with the functions f(n) = 2 + 1/n , g(n) = 1 + 1/n providing a counterexample. If lg g(n) is assumed to be bounded away from zero, then the answer is "yes". greg bachelis --------------------------------------------------------------- # 300 From: HUAIYUAN YU Date: Fri, 30 Sep 1994 15:39:56 -0400 (EDT) > > > Dear Sirs, > > I'm a psychology graduate student taking an algorithms course in > University of Georgia. Our textbook is written by you guys, the > textbook is great in general. But I still feel uncomfortable at > one spot. > > One of the assignments is exercise 7.4-3, it doesn't seem to be one > that I can find a solution. > > One possibility concerning this exercise is that what is meant is > asking a proof of a more general case -- bounding of comparision sort, > which would be discussed in more detail in Chapter 9. This would > not be too tricky. However, this is not literally expressed in the > exercise, because if that is what was meant, then the situation that > would be taken care of are only worst cases. > > The other possibility is that what is meant can be taken literally > from the exercises -- lower bound of best cases. If that > would be the case, then the solution that I spent quite a few hours > to get would be rather tricky as far as exercises instead of problems > are concerned. Moreover, the solution I found only works for a heap > with distinct elements. This could be demonstrated this way: > > A heap of the same elements will only take lower bound n to be taken > care of. It is the same situation when only first several elements > are distinct, most of the other elements down in the heap > are the same. There may be other variations too. > > Thanks for attention. > > Looking forward to your reply. > > Sincerelly, > > Huaiyuan Yu > > --------------------------------------------------------------- # 301 From: Ronald J Williams Date: Wed, 5 Oct 1994 10:52:12 -0400 The material on recursion trees (pp. 59-61) contains an oversight by failing to take into account the leaves of the final tree, each of which contributes an additional $\Theta(1)$ to the computation of $T(n)$. For the $T(n)=2T(n/2)+n^2$ example, the overall contribution to the sum from these leaves is $\Theta(n)$, so the final result, that $T(n)=\Theta(n^2)$, is unchanged. However, in the next example, $T(n)=T(n/3)+T(2n/3)+n$, the crude upper bound for the contribution from the leaves based on the complete binary tree of height $\log_{3/2}n$ is $n^{\log_{3/2}2}$, which is asymptotically strictly larger than $n\lg n$. Thus to conclude $T(n)=O(n\lg n)$ must require a more careful bounding of the number of leaves in this tree. (However, a corresponding argument considering the complete tree of height $\log_3 n$ shows that the contribution from the leaves has as a lower bound $n^{log_3 2} = o(n\lg n)$, so no such subtleties are required to show that $T(n) = \Omega(n\lg n)$, as required in problem 4.2-2.) This may also be an issue in obtaining asymptotically tight bounds in problem 4.2-5. -- Ron Williams --------------------------------------------------------------------------- Ronald J. Williams | email: rjw@ccs.neu.edu College of Computer Science, 161 CN | Phone: (617) 373-8683 Northeastern University | Fax: (617) 373-5121 Boston, MA 02115, USA | --------------------------------------------------------------------------- --------------------------------------------------------------- # 302 From: Date: Wed, 19 Oct 94 09:37:43 -0500 Exercise 17.3-4, page 344 lines 16-18 of the second printing, asks for a proof that in an optimal (prefix) code, if the characters are ordered so that their frequencies are nonincreasing, then their codeword lengths are nondecreasing. Yet this seems not to be true in general. Consider a three character alphabet with equal frequencies. The codeword lengths will be 1, 2, and 2. Any of the six orderings is such that thee frequencies are nonincreasing, but only two of the six orderings are such that the codeword lengths are nondecreasing. My student Jon Kroger pointed this out to me. Suggested corrections: option 1: replace "nonincreasing" on line 17 with "strictly decreasing" option 2: rewrite entire exercise as "Prove that if an alphabet is ordered such that the characters' frequencies are nondecreasing, there exists an optimal code for that alphabet for which the characters' codeword lengths are nondecreasing." The first option tightens the hypothesis such that a "for all optimal codes" result holds, while the second drops back to a "for some optimal code" result. I'm not sure which you intended. -Max Hailperin Assistant Professor of Computer Science Gustavus Adolphus College St. Peter, MN 56082 --------------------------------------------------------------- # 303 From: fresko@cs.purdue.edu (Nedim Fresko) Date: Sat, 10 Dec 1994 20:09:13 -0500 This one is a minor typo in the text: On page 902, in line 2 of GRAHAM-SCAN, inside the parantheses: Change ((if more than point has the same angle)) To <> ^^^ Thank you for your excellent book, and for supplying this service through e-mail to the widest community of readers possible. -- Nedim Fresko | e-mail: fresko@cs.purdue.edu Department of Computer Science | WWW: http://www.cs.purdue.edu Purdue University | Phone: (317) 495-6811 --------------------------------------------------------------- # 304 From: fresko@cs.purdue.edu (Nedim Fresko) Date: Sat, 10 Dec 1994 20:59:01 -0500 Page 912, line 3 of exercise 35.4-3: The Lm distance between p1 and p2 should be given as (abs(x1 - x2)^m + abs(y1 - y2)^m) ^ (1/m) instead of without the absolute values, as stated in the exercise. -- Nedim Fresko | e-mail: fresko@cs.purdue.edu Department of Computer Science | WWW: http://www.cs.purdue.edu/people/fresko Purdue University | Phone: (317) 495-6811 --------------------------------------------------------------- # 305 From: spiess@ips.cs.tu-bs.de Date: Wed, 14 Dec 1994 15:28:01 +0100 Hi! In your excellent book on ALGORITHMS (fifth printing 1991) you define Carmichael numbers on page 839 to be all numbers that satisfy equation (33.42) for all natural numbers a. That is: a^(n-1) = 1 (mod n) By this definition your examples of Carmichael numbers 561, 1105, 1729 are not true Carmichael numbers. Counter examples: 3^560 mod 561 = 375 5^1104 mod 1105 = 885 7^1728 mod 1729 = 742 If you define Carmichael numbers to satisfy a^n = a (mod n) for all a then the above examples are oK. Alternatively you may write ... that satisfy equation (33.42) for all a ... with gcd(a,n)=1. Best regards Juergen Spiess - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Address: Institut fuer Programmiersprachen Technische Universitaet Braunschweig Germany --------------------------------------------------------------- From: Martin Dietzfelbinger Date: Tue, 7 Feb 1995 13:19:50 +0100 (MET) From: ------------------------------------------------------------------------------- Martin Dietzfelbinger | Fachbereich Informatik | Office: Campus Sued, GB IV, Room 323 Lehrstuhl II | Phone: +49/231/755-4737 Universitaet Dortmund | +49/231/755-2777 (Secret.) D-44221 Dortmund | Fax: +49/231/755-2047 Germany | email: dietzfelbinger@ls2.informatik.uni-dortmund.de ------------------------------------------------------------------------------- %%%%%%%%%%%%%%%%%%%%%%%% LaTeX document follows %%%%%%%%%%%%%%%%%%%%%%%% \documentstyle[12pt]{article} \parindent=0pt \begin{document} Some corrections, and some remarks on corrections as reflected in ``ERRATA 1.2'' of August 3, 1993. \begin{description} %% # 306 \item{{\bf p.~121, l.~11\,ff.}\quad} Theorem~6.2 has an easy and intuitive proof, if one uses Boole's inequality (Exercise 6.2-1): For $S \subseteq \{0,\ldots,n\}$, let $A_S$ be the event that the $i$-th trial is a success. Clearly: \begin{eqnarray*} \mbox{\rm Pr}\{X \ge k\} &=& \mbox{\rm Pr} \{\begin{array}[t]{l} \exists\; S \subseteq \{1,\ldots,n\}\colon\; \mbox{$\vert S\vert = k$ and}\\ \forall\; i\in S\colon\; \mbox{$i$-th trial is a success} \} \end{array}\\ &=& \mbox{\rm Pr} \Biggl\{ \bigcup_{\textstyle{{S \subseteq \{1,\ldots,n\}}\atop{\vert S\vert=k}}} A_S \Biggr\}\\ &\le& \sum_{\textstyle{{S \subseteq \{1,\ldots,n\}}\atop{\vert S\vert=k}}} \mbox{\rm Pr}\{A_S\}\\ &=& {n \choose k} \cdot p^k.\\ \end{eqnarray*} %% Fixed in printings 2 and up \item{{\bf Page 124, line -1, and Page 125, line 1}\quad} Regarding the correction of T.~Cormen for this place in the text: the reference to the location in the book seems to be wrong. I couldn't find anything that looks like the formulas given at the bottom of p.~124 and the top of p.~125. %% # 307 \item{{\bf Pages 443--446, Section 22.2}\quad} Concerning the correction by Scot Drysdale for this place in the text and the reference to ``{\tt last[x]}'' in line~4 of Exercise~22.2-1 on p.~446 \begin{quote} ``The linked-list representation of disjoint sets requires that each list also includes a pointer to its last element. Otherwise, the APPEND operation does not take $O(1)$ time''. \end{quote} The need for a pointer to the last element (which would increase the space requirements by a factor 4/3) can be avoided altogether, by the following simple modification to the implementation of the UNION operation (p.~445, l.~10): Do not append the smaller list onto the larger, but rather insert the smaller list immediately after the first element (the representative) of the longer list, before all other entries in the longer list. For this, one only needs a pointer to the last element of the {\it shorter\/} list, which can easily be obtained as a byproduct of the traversal of the shorter list, which has to be done anyway for updating the pointers to the representative. If the longer list contains only one element, this is true for the shorter list, too; in this case the two lists are simply concatenated. %% Fixed in printings 2 and up \item{{\bf p.~786, l.~10}\quad} (last line before caption ``{\bf The DFT}''): \begin{quote} replace $((w^k_n = 1 ))$ by $\langle\langle \omega^k_n = 1 \rangle\rangle$ \end{quote} \end{description} \end{document} --------------------------------------------------------------- From: d15qc@qcvaxa.acc.qc.edu Date: Thu, 23 Feb 1995 23:42:58 EDT Date: Thu, 23 Feb 1995 23:42:49 +0200 (IST) From: HUANG DUEN-HUANG Subject: Bug To: algorithms Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII --------------------------------------------------------------- # 308 From: Karen.Seidel@comlab.ox.ac.uk Date: Mon, 27 Feb 95 17:31:43 GMT p. 134, Exercise 6-4 (Probabilistic Counting), part a: "Show that the expected value represented by the counter after n INCREMENT operations is exactly n." This is true only if n_i = i for all i, but not in general. Also, the question attributes probabilistic counting to "R. Morris" but no reference is given. Could you please send it to me? Regards Karen Seidel --------------------------------------------------------------- From: erba@maya.dei.unipd.it (Claudio Erbisti 321125/IL) Date: Tue, 21 Mar 95 19:21:08 +0100 --------------------------------------------------------------- %% Same as # 302 From: Gordon Royle Date: Wed, 3 May 1995 10:10:39 +0800 (WST) Page 344, Exercise 17.3-4 is incorrect. Counterexample -------------- Here is a list of three characters with frequencies A - 1 B - 1 C - 1 The optimal Huffman code is A - 1 B - 00 C - 01 Here is an order of the characters with non-increasing frequencies: B A C Here is the order of their codeword lengths 2 1 2 This sequence is NOT non-decreasing. Suggested correction -------------------- Show that if characters x and y have f(x) < f(y) then the codeword for x cannot be shorter than the codeword for y. Yours Gordon Royle Dept of Computer Science University of Western Australia --------------------------------------------------------------- From: Jeffrey Shallit Date: Fri, 12 May 1995 14:18:34 -0400 There definitely seems to be a bug in the correctness proof of Huffman's algorithm in section 17.3. In particular, it appears to me that Lemma 17.3 is not useful; what is needed is the *converse* of Lemma 17.3. Here is *my* statement of what I believe to be the correct Lemma, together with the proof of Theorem 17.4: ---------------------------------------------------------------------- .. [discussion paralleling yours in Lemma 17.2 deleted] Lemma 2. (CLR, Lemma 17.3) Let T be a full binary tree representing a prefix code over the alphabet A. Let x and y be the two characters that occur with lowest frequency in A. Let z be a new character with frequency f(z) = f(x) + f(y). If the tree T' = T - {x, y} is optimal for A' = A - {x,y} U {z}, then T is optimal for A. Proof. By Lemma 1, we can assume that x and y are sibling leaves in T, so that d_T (x) = d_T (y) = d_T' (z) + 1. Now we show B(T) - B(T') = f(x) + f(y): B(T) - B(T') = f(x) d_T (x) + f(y) d_T (y) - f(z) d_T' (z) = (f(x) + f(y)) (d_T' (z) + 1) - (f(x) + f(y)) d_T' (z) = f(x) + f(y), which is what we wanted. Now assume, contrary to what we want to prove, that T is not optimal for A. Then there is an optimal tree V for the alphabet A, and B(V) < B(T). Again by Lemma 1, we can assume that x and y are sibling leaves in V. Now modify V so that x and y are removed, and their parent z is labeled with the sum of f(x) and f(y). Call the new tree V'. Then we have, just as above, B(V) - B(V') = f(x) + f(y). Now B(V) < B(T) implies B(V) -f(x)-f(y) < B(T) -f(x)-f(y), and so B(V') < B(T'). But then T' is not optimal for A', a contradiction. Now we can prove that the algorithm Huffman produces an optimal code. The proof is by induction on the number of letters in the alphabet. If the alphabet contains 1 letter, then Huffman is clearly correct. Now assume that Huffman works correctly on all alphabets of < n letters; we prove it works for an alphabet of n letters. In the first step, Huffman identifies the letters of lowest frequency, x and y, joins them to form a new letter z such that f(z) = f(x) + f(y), and continues working on A' = A - {x,y} U {z}. This new alphabet A' has one fewer letter, and so by induction Huffman produces an optimal tree for A'. But then, by Lemma 2, by expanding the node z to have x and y as children, we get an optimal tree for A. Jeffrey Shallit, Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1 Canada shallit@graceland.uwaterloo.ca URL = http://math.uwaterloo.ca/~shallit/ --------------------------------------------------------------- # 309 From: Jeffrey Shallit Date: Fri, 12 May 1995 15:54:17 -0400 Sorry, ignore my last message about Huffman codes. I think your argument can be made to work (and there was also an error -- fixable -- in what I wrote), but you really need a few more details in your proof of Theorem 17.4. Jeff Shallit, Univ. of Waterloo --------------------------------------------------------------- %% Not a bug...procedure does not try to work in place. From: Oren Farber Date: Sun, 14 May 1995 14:37:22 +0300 Greetings, in page 795: I think the procedure to reverse bits should be slightly extended: n <- length(n) for k <- 0 to n-1 if k < rev(k) **THIS LINE IS MISSING** do A[rev(k)] = A[k] otherwise the entries are exchanged and then exchanged back. oren farber, Hebrew Univ. Jerusalem. --------------------------------------------------------------- # 310 From: "hang (h.t.) lau" Date: Tue, 6 Jun 1995 10:36:00 -0400 First printing of the text. Page: 960 Location of the bug: The last sentence in the proof of Theorem 36.15 Original sentence: We conclude that h is a hamiltonian cycle in graph G. Correct sentence shoud be: We conclude that h' is a hamiltonian cycle in graph G. H. T. Lau Bell-Northern Research Quebec, Canada email: htlau@bnr.ca June 6, 1995 --------------------------------------------------------------- From: Marek Date: Mon, 02 Oct 1995 21:56:38 -0400 --------------------------------------------------------------- From: Marek Date: Mon, 02 Oct 1995 22:20:32 -0400 p.169, exercise 8-2 e should assume that all the elements are distinct p + r - q should be p + r - 1 - q p.183, problem 9-1 there is a correction already to this, but I have some corrections on top of the current correction all elements should be distinct all trees should be binary (you must be more general here than just to have decision trees, as suggested in the current correction, because part e, as explained below, needs any binary tree, maybe with parents with precisely one child) in the hint to part c, i should be replace with i subscript 0, for example finally, in part e, it is insufficient to prove the equality for T subscript A part e should say: Observe that (...) for any subtree of T subscript A with n! leaves, and conclude that ... ("observe" should be used and not prove, because the thing is wholly obvious from part d) p.193 row 14 from the bottom, the word "methods" should be replaced by "algorithm" --------------------------------------------------------------- From: gac@cs.duke.edu (Geoff Alex Cohen) Date: Sun, 8 Oct 1995 17:22:10 -0400 (EDT) Page 382. You define a "page" as a fixed-size unit of information on a disk. A better term (and one that is more in line with systems literature) is "block", reserving "page" to refer to a unit of virtual memory (and "frame" to a unit of physical memory). --------------------------------------------------------------- From: Florian Zschocke Date: Fri, 13 Oct 1995 21:13:34 +0000 On page 173 figure 9.1 is wrong. In the decision tree two leaves are swapped. Counting the leaves from left to right, leaves three (i.e. <3,1,2>) and five (i.e. <2,3,1>) should be exchanged. --------------------------------------------------------------- From: Richard Beigel Date: Wed, 29 Nov 1995 12:44:44 -0500 In Exercise 5-3.c, a tree consisting of a root and n-1 children is a counterexample. I think "any n-vertex tree" should be "any n-vertex binary tree". --------------------------------------------------------------- From: muskat@bimacs.cs.biu.ac.il (Prof. J. B. Muskat) Date: Mon, 18 Dec 1995 15:54:23 +0200 To the authors of "Introduction to Algorithms": I believe that on page 228, line 18 (second paragraph, last sentence) the restriction "two adjacent" is unnecessary. The value obtained in this case is the sum of the representations of the characters in the string, modulo m, as 2^(kp) = 1(mod 2^p - 1). Any permutation of the characters in the string will not change the sum. This is a generalization of the well-known "casting out nines" rule. Sincerely, Joseph B. Muskat --------------------------------------------------------------- From: Yih-Chun Hu Date: Tue, 9 Jan 1996 17:23:59 -0800 (PST) Page 37, Exercise 2.2-2. The assertion is not correct for n=0 and n=1. Suppose it were correct. Then any function T(n) in O(n^k) would have some corresponding g(n) in O(1) such that g(n) T(n) = n . However, were this so, then either T(1) is undefined or T(1) = 1, and either T(0) is undefined or T(0) = 0. 2 T(n) = n + 1 clearly contradicts both the above since T(0) = 1 and T(1) = 2. +---- Yih-Chun Hu (finger:yihchun@cs.washington.edu) ----------------------+ | http://www.cs.washington.edu/homes/yihchun yihchun@cs.washington.edu | | http://weber.u.washington.edu/~yihchun yihchun@u.washington.edu | +--------------------------------------------------------------------------+ --------------------------------------------------------------- From: Leonid Peshkin Date: Fri, 19 Jan 1996 17:08:50 -0500 (EST) 1. page 467 line 17 "We define the the ..." 2. page 42 looks like in a second case you ment a "ceiling" sign but put a "floor" in a 3rd line from the bottom. -Leonid Peshkin --------------------------------------------------------------- From: Jesus Chahin Date: Mon, 22 Jan 1996 00:55:35 -0600 (CST) I just bought the 14th Printing (1994) of the book and it's missing pages 13-44!!! What the hell!? I'm taking the book back for a refund tomorrow, that's just rediculous! --------------------------------------------------------------- From: Tung Hoang Nguyen Date: Mon, 5 Feb 1996 09:29:21 -0500 (EST) Dear authors, On chapter 7.3, exercise 7.3-3, I think the formula is not correct for the last level of the tree. Counterexample: h=2, n=7. So that the formula (7.2) is not correct neither, because it counts until the last level. I think we can do much more simple : at level h ==> at most 2^h nodes (7.2) becomes: Sum from 0 to floor(lg n) of ( 2^h x O(h) ) = = O( Sum from 0 to floor(lg n) of 2^h ) = O( 2^( floor(lg n) +1 ) -1 ) ------------------------ >= n = O(n) I wish my remark might be useful. Please let me know if I made error in reasoning. Thanks. Tung H. Nguyen --------------------------------------------------------------- From: Antonio Di_Ferdinando Date: Thu, 8 Feb 1996 13:43:01 +0100 (MET) -------------------------------------------------------------------------------- | Antonio Di Ferdinando: | |-------------------------| V. Irnerio n.12 | V. Vittoria n.185 40126 Bologna (x) 64011 Alba Adriatica(TE) Tel.051-25075 | Tel.0861-712107 |----------------------------------| | e-mail:diferdin@cs.unibo.it | | | | http://www.cs.unibo.it/~diferdin | ------------------------------------------------------------------------------- non lasciate che le luci artificiali disegnino di voi strane ombre... ...sapevate cantare prima che vi regalassero un bancomat, sapevate ballare. Spegnete tutte le TV di questo paese, sono guaste... ... se veramente cercate qualcosa guardate nelle vostre mani, e' li che si trova la vera definizione di magia. (Paolo Rossi) ----------------------------------------------------------------------------- --------------------------------------------------------------- From: Leonardo Jose Borges Date: Sun, 18 Feb 1996 18:48:00 -0600 (CST) pag 278, problem 14-2. Change "key[x1] <= key[x] <= key[x2]" to "key[x1] < key[x] < key[x2]" Since the result is supposed to be a set, we must maintain the rule "A set cannot contain the same object more than once,..." (pag 78, line 12). Actually, this rule is used to solve part (c). Thanks, Leonardo J. Borges Texas A&M Univ. grad. student --------------------------------------------------------------- From: Date: Wed, 1 May 1996 22:06:58 -0400 Page 969, line -5: ... a near-optimal tour of an undirected graph G should be replaced with ... a near-optimal tour of a complete undirected graph G with non-negative cost c. --------------------------------------------------------------- From: Date: Wed, 1 May 1996 23:53:59 -0400 page 960, line 11: E'={(i,j): i,j is_in V} should be changed to E'={(i,j): i,j is_in V and i != j} -anek --------------------------------------------------------------- From: therese@tsssun4.tomsawyer.com (Therese Biedl) Date: Fri, 10 May 1996 09:45:23 -0700 Page 274, RB-Delete-Fixup, line 9. It is possible that w is nil[T]. In this case, the children of w are undefined. In my opinion, the following fix works: If w is nil[T], we can push the double black load to the parent of x, and iterate. So add the following lines: if w = nil[T] x <- p[x]; else [...] Therese Biedl Tom Sawyer Software / RUTCOR, Rutgers University --------------------------------------------------------------- From: dcoles@cs.bu.edu (Drue Coles) Date: Sat, 13 Jul 1996 15:33:02 -0400 Page 813, problem 33.2-8: in line 2, the last argument to the first invocation of gcd should be a-subscript-n, not n. Same page/problem: in the last line, "max" should not have a subscript. Drue Coles --------------------------------------------------------------- From: Siddhartha Chatterjee Date: Tue, 22 Oct 1996 14:18:01 -0400 Page 911, code at the end of page: Line 5 should be "Y_L[length[Y_L]] <- Y[i]" and line 7 should be "Y_R[length[Y_R]] <- Y[i]". -- Dr. Siddhartha Chatterjee, Asst. Professor http://www.cs.unc.edu/~sc/ Department of Computer Science sc@cs.unc.edu The University of North Carolina (919) 962-1766 Chapel Hill, NC 27599-3175 (919) 962-1799 fax --------------------------------------------------------------- From: goia@leonardo.polito.it (Alessandro Goia) Date: Fri, 25 Oct 1996 13:20:14 +0100 --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Mon, 28 Oct 96 10:33:05 EST ------- Start of forwarded message ------- To: cel@theory.lcs.mit.edu Subject: typo in CLR Date: Sun, 27 Oct 1996 14:07:54 EST From: Ien Cheng Typo in CLR, page 276. The first line of the caption says RB-Delete. It should say RB-Delete-Fixup. Ien ------- End of forwarded message ------- --------------------------------------------------------------- From: Thomas Cormen Date: Mon, 16 Dec 1996 16:46:39 -0500 (EST) This is from Phil MacKenzie about Exercise 23.1-10: Phil, the solution we had in mind was O(VE) time. You run DFS once from each vertex, and the graph is singly connected iff all edges are tree or back. I don't know if there's a better solution. OK, that's the best time we got also. By the way, Amit brought up the point that if you have two overlapping back edges on the same path, then the graph is not singly-connected. Think of the path A->B->C->D with back edges C->A and D->B. Then there are 2 paths from C to B: C->A->B and C->D->B Or are we confused on what singly-connected means? --THC -Phil --------------------------------------------------------------- From: "Luca Venuti" Date: Thu, 30 Jan 1997 10:51:15 +0100 Hi! Here's a little carelessness I've found in your excellent book. Page 493, Proof of Theorem 23.17, line beginning with "<=:" For more clearness the phrase should be read as follows: <> Regards, -- Luca Venuti Keyserver for PGP Public Key: 0x3E71BEE9 WWW: http://www.geocities.com/CapitolHill/2358/ --------------------------------------------------------------- From: "Luca Venuti" Date: Sat, 1 Feb 1997 02:06:34 +0100 Dear sirs, Here's a little bug that confused me at first glance, when I read the book. I think it should be correct as follows: Page 509, line -17 The text ((The loop is executed |V| times)) should be changed to < Date: Mon, 10 Feb 1997 17:25:45 +0100 --------------------------------------------------------------- From: Popescu Carmen Date: Mon, 10 Mar 1997 17:44:11 +0200 (EET) --------------------------------------------------------------- From: palumb@cli.di.unipi.it Date: Mon, 31 Mar 1997 12:09:05 +0100 --------------------------------------------------------------- From: "Scott C. Karlin" Date: Thu, 3 Apr 1997 12:07:03 -0500 (EST) Bug Report for CLR sent to algorithms@theory.lcs.mit.edu Page 511 Problem 24-1 This is not in the Errata 1.2 dated July 28, 1994 which I found at http://theory.lcs.mit.edu/~rivest/CLR.html It is possible for a graph not to have a second-best MST under the conditions specified in the problem. For example, a graph with three vertices and three edges (a triangle) all of equal weight has three different MSTs but no second-best MST. The problem is that Chapter 24 states that there can be many minimum spanning trees for a particular graph. If "second-best" MST means a spanning tree which has weight strictly greater than the weight of all the MSTs (with equal, minimum, weight), the problem needs to be restated: I suggest that the first sentence of part a be changed from "Let $T$ be a minimum spanning tree of $G$." to "Let $T$ be a minimum spanning tree of $G$ which has a second-best minimum spanning tree." to Part c can also be modified so that the algorithm reports that there is, in fact, no second-best MST. I also suggest that in part b, parentheses be added to the set expression to be a little more clear: Change $T-\{(u,v)\}\cup\{(x,y)\}$ to $\bigl[T-\{(u,v)\}\bigr]\cup\{(x,y)\}$ -Scott -------------------------------------------------------------------------- Scott C. Karlin Princeton University Graduate Student Department of Computer Science Voice: (609) 258-5386 35 Olden Street Email: scott@cs.princeton.edu Princeton, NJ 08544-2087 WWW: http://www.cs.princeton.edu/~scott -------------------------------------------------------------------------- --------------------------------------------------------------- From: palumb@cli.di.unipi.it Date: Mon, 07 Apr 1997 07:28:14 +0200 --------------------------------------------------------------- From: Todd D Millstein Date: Mon, 30 Jun 1997 09:59:41 -0700 (PDT) I believe there is a bug in problem 20.2-10 on p.417. It asks you to prove that BINOMIAL-HEAP-UNION is omega infinity (lg n) but not omega (lg n), but it seems that it actually is omega (lg n). For the union, n = n1 + n2, where n1 and n2 are the sizes of the two heaps being unioned. Given any n, it can be broken into an n1 and n2 such that the union will take time proportional to (lg n). For example, let n1 = 2^(floor(lg (n+1))) - 1 and n2 = n - n1. Todd Millstein University of Washington --------------------------------------------------------------- From: master Date: Thu, 10 Jul 1997 15:09:33 +0300 --------------------------------------------------------------- From: Betty J Salzberg Date: Wed, 6 Aug 1997 16:26:23 -0400 (EDT) In section 10.3, p. 190, the picture and the analysis do not match the algorithm. In step 3 of the algorithm, Select is called recursively to find the median of medians. This recursion will not produce a picture like that in Figure 10.1. For example, suppose there are 26 elements. (Five squared plus one) Suppose the one element in a set by itself is the biggest. Then we take the 5 medians and take the median of them. Then we have two numbers in the last step: The largest number and the median of the medians of the other 25 elements. This last group has only two elements and we take the biggest which gives as a partitioning pivot the largest element in the set. This reasoning works with 5^N + 1 elements and any integer N >= 1. The picture and the analysis don't hold once you get past the first recursion step. Suppose you have 125 elements. In the first recursion step, you find 5 new medians of 5 old medians (not one median of 25 medians). How many elements are larger than each of the 5 new medians? 2 + 3 +3 = 8. Now take the median of the new medians in the next recursion. There are 8 + 9 + 9 larger than the ultimate "median" or 26 of the 125 elements. This is not >= 3n/10 - 6. Betty Salzberg -- Betty Salzberg salzberg@ccs.neu.edu College of Computer Science 617-373-2229 Northeastern University FAX 617-373-5121 Boston, Ma. 02115 --------------------------------------------------------------- From: Jose Omar Garcia-Fernandez Date: Fri, 29 Aug 1997 16:02:06 -0500 (EST) --------------------------------------------------------------- From: rivest@theory.lcs.mit.edu (Ron Rivest) Date: Sun, 07 Sep 97 14:37:24 EDT Dear Neal -- Thanks for your bug report (below). I think that your observations are good ones, and that the presentation of this material could be improved. Thanks! Ron ============================================================================== Return-Path: Date: Tue, 12 Aug 97 14:35:33 -0400 (EDT) Mime-Version: 1.0 Content-Transfer-Encoding: 7bit From: Neal Young To: rivest@lcs.mit.edu Cc: thc@zealand.cs.dartmouth.edu Subject: CLR textbook bug? Prof. Rivest, I think there might be a bug in CLR chapter 17 (greedy algorithms). Tom Cormen suggested that you wrote this chapter so that I might direct my question to you... In the proof of Theorem 17.1, around page 332, the last paragraph, you want to prove that (paraphrasing) (i) "After the greedy choice is made, the problem reduces to solving the remaining subproblem optimally." I think the subsequent argument is flawed? The justification given is that (ii) "If A is an optimal solution to the original problem, then A-{1} is an optimal solution to the subproblem..." This is true, and is what the remainder of the paragraph proves. But I don't think (ii) implies (i), rather is needed instead of (ii) is the converse: (iii) "If B is any optimal solution to the subproblem, then B union {1} is an optimal solution to the original problem." The reason is that it could be the case (a-priori) that an optimal solution to the remaining subproblem, when combined with the greedy choice, does not give an optimal solution to the overall problem. So (ii) holds but not (i). For (an admittedly strained) example, consider the problem of vertex coloring a given bipartite graph with two colors so as to minimize the number of pairs of adjacent vertices that are colored the same (of course the answer will always be zero). For any greedy first choice (e.g. color a vertex "red") it is the case that some optimal solution is consistent with that choice. Also, it is the case that the remaining subproblem (delete the vertex and color the remaining vertices) will have to be solved optimally. Thus (ii) holds. But it is not the case that (i) holds, in particular, there are optimal solutions to the subproblem, that, when combined with the particular first choice, do not yield an optimal solution to the original problem. Consequently, a greedy algorithm will not work unless it restricts solutions to the remaining problem. This issue arises again in the discussion of "optimal substructure" on page 334 and also in the use of Lemma 17.3 in the proof of Theorem 17.4. Lemma 17.9 (matroids) seems ok to me, since you prove both (ii) and (iii). Neal --------------------------------------------------------------- From: Volker Strumpen Date: Tue, 23 Sep 97 15:59:18 EDT I just found a bug in the RB-INSERT function on p. 268 of your book. In case you don't know it already, here is the fix: Change line 6: if color[y] = RED into: if y != NIL and color[y] = RED Alternatively, the bug goes away with NIL sentinels. The bug arises for the following tree: B / \ R nil <-- y / \ x --> R nil / \ nil nil The color of y is taken on line 6, and y is nil. --------------------------------------------------------------- From: Geno Date: Thu, 02 Oct 1997 12:13:54 -0400 > I am currently reading Cormen's Intro. to Algorithms book, 15th > printing 1995, and I think I have found an error in section 10.3 on page 191. A proof is being given that the selection algorithm of page 190 is O(N). I believe that in step 3. "Use Select recursively to find the median x of the n/5 rounded up medians found in step 2, requires time which is the sum T(n/5) + T(N/125) + T(N/625) ... terminating when the denomator 5 to the ith power is >= N, instead of just T(n/5). The proof will still work, since the sum of the series is still less that N/4, which is still small enough to make the induction argument go through that follows. The reason I think that this sum is necessary is that this grand median must be found before the partition step 4 can be done. Check this out, and e-respond if you get a chance. Thanks. Dr.Gene Smith Bellarmine College > 2001 Newburg Rd. > Louisville, KY 40205 --------------------------------------------------------------- From: Antal Ivanyi Date: Fri, 17 Oct 1997 19:53:20 -0700 On page 739, in line 7 Change Section 26.1. To Section 16.1. ------------------------------------------------------------- A. M. Ivanyi, Eotvos Uversity of Budapest --------------------------------------------------------------- From: Colin Date: Fri, 14 Nov 1997 21:52:27 -0500 I have the 1991, 3rd printing of Algorithms... On p. 478 (the discussion of Depth-First Search), there's no mention of what order to initially visit each vertex in (line 5 of the DFS(G) algorithm pseudo-code: "for each vertex u mem V[G]"). I think the text implies it doesn't matter, but I believe it does, to get correct discovery times'. For example, in the picture on p. 479, what if node v is started with rather than node u? It's discovery time would be lower than u's, and mess up all the nice theorems depending on it... Please let me know if I'm overlooking something. Regards, Colin Prepscius --------------------------------------------------------------- From: "Nelson L. Max" Date: Wed, 3 Dec 1997 15:16:19 -0800 page 527, Dijkstra(G,w,s) pseudocode I think lines 4 and 5 should be replaced by while Q != 0 and d[u<-ExtractMin(Q)] < infinity -- email: max2@llnl.gov Nelson Max, Mail Stop L-307 http://www.llnl.gov/graphics Lawrence Livermore National Laboratory phone (510) 422-4074 7000 East Avenue fax (510) 423-4139 Livermore, CA 94550, USA --------------------------------------------------------------- From: Peter Csaszar Date: Tue, 9 Dec 1997 14:53:10 -0600 (CST) This bug is actually in the bug list, Errata 1.2: ERRATA 1.2, Page 11, Bug 5 Change ((Chnage)) to <> Peter Csaszar pcsaszar@eecs.uic.edu University of Illinois at Chicago peterc@ai.uic.edu College of Engineering Dept. of Electrical Engineering Computer Science --------------------------------------------------------------- From: Boytcho Peytchev Date: Tue, 30 Dec 1997 05:07:22 -0600 Erata 1.2 (July 28, 1994) Page 1 line 7 reads ((of the first edition of...)) correct to <> Introduction to Algorithms Second Edition, fourth printing page 26 lines 18-19 Change ((f(n) is on or below g(n).)) to <> --------------------------------------------------------------- From: alexbrn@cix.compulink.co.uk (Alexander Brown) Date: Tue, 10 Feb 98 21:59 GMT0 ---- Forwarded Message ---- >From thc@zayante.cs.dartmouth.edu Tue Feb 10 21:52:38 1998 Received: from mail-relay.compulink.co.uk (le0-1.mail-relay.cix.co.uk [194.153.0.61]) by tom.compulink.co.uk (8.8.8/8.8.6) with ESMTP id VAA24358 for ; Tue, 10 Feb 1998 21:52:38 GMT Received: from zayante.cs.dartmouth.edu (zayante.cs.dartmouth.edu [129.170.194.25]) by mail-relay.compulink.co.uk (8.8.7/8.8.7) with ESMTP id VAA23953 for ; Tue, 10 Feb 1998 21:52:23 GMT X-Envelope-From: thc@zayante.cs.dartmouth.edu Received: by zayante.cs.dartmouth.edu (8.8.3/4.2) id QAA03291; Tue, 10 Feb 1998 16:50:45 -0500 (EST) Date: Tue, 10 Feb 1998 16:50:45 -0500 (EST) Message-Id: <199802102150.QAA03291@zayante.cs.dartmouth.edu> From: Thomas Cormen To: alexbrn@cix.compulink.co.uk In-reply-to: (alexbrn@cix.compulink.co.uk) Subject: Re: _Introduction to Algorithms_ : error? Reply-to: thc@cs.dartmouth.edu Alternate-reply-to: BBQ@dartmouth.edu Apparently-To: alexbrn@cix.compulink.co.uk >Apologies is this is picky (or wrong) ... > >I've just coded-up a B-Tree based on the pseudo-code in _Introduction to >Algorithms_ (17th printing) and was confused by the text on page 390 (2 >lines after the B-Tree-Split-Child routine) where it states "y [...] is >the node being split. Node y originally has 2t - 1 children but is >reduced to t - 1 children by this operation". > >Shouldn't "children" be "keys" here? > >- Alex. Alex, I believe that you are correct. Please email a bug report to algorithms@theory.lcs.mit.edu with Subject: Bug so that it is officially logged. Thanks! --THC ------------------------------------------------------------------------ Thomas H. Cormen Voice: (603) 646-2417 Assistant Professor Fax: (603) 646-1672 Dept. of Computer Science Email: thc@cs.dartmouth.edu Dartmouth College URL: http://www.cs.dartmouth.edu/~thc/ 6211 Sudikoff Laboratory Hanover, NH 03755-3510 ------------------------------------------------------------------------ --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 1 Mar 1998 21:27:23 -0500 ------- Start of forwarded message ------- Date: Sun, 1 Mar 1998 13:48:02 -0500 From: Volker Strumpen To: cel Subject: inconsistency in CLR Charles, I just bumped into a minor inconsistency in your book. p. 140: "The heap ... as a complete binary tree ..., as shown in Figure 7.1." p. 95: "A complete k-ary tree is a k-ary tree in which all leaves have the same depth ..." In Figure 7.1, not all leaves have the same depth! Volker ------- End of forwarded message ------- --------------------------------------------------------------- From: Knuutila Juha Date: Tue, 31 Mar 1998 21:45:38 +0300 (EET DST) Hi, Page 895, I think ANY-SEGMENTS-INTERSECT(S) fails to find that there are intersecting lines. If we have situation like this: \ \ \ \ ---- \ ---- / / / / / Lines are for example (2,0)-(7,3) (2,6)-(7,3) (1,2)-(4,2) (1,3)-(4,3) -jk ---- Juha Knuutila, jysky@cs.tut.fi --------------------------------------------------------------- From: Thomas Cormen Date: Thu, 2 Apr 1998 09:31:42 -0500 (EST) X-Authentication-Warning: kaarne.cs.tut.fi: jysky owned process doing -bs Date: Thu, 2 Apr 1998 08:52:50 +0300 (EET DST) From: Knuutila Juha To: thc@cs.dartmouth.edu Subject: Wrong bug announcement In-Reply-To: <199803152036.PAA05127@zayante.cs.dartmouth.edu> Content-Type: TEXT/PLAIN; charset=US-ASCII I'm sorry, I send an announcement to Bug-list of (Introduction to Algoritms) that ANY-SEGMENTS-INTERSECT(S) doesn't work. I war wrong, it works. Could you please remove the announcement from the list. -jk --- Juha Knuutila, jysky@cs.tut.fi --------------------------------------------------------------- From: Thomas Cormen Date: Wed, 6 May 1998 16:47:09 -0400 (EDT) ------- Start of forwarded message ------- Sender: philmac@moonstone.idbsu.edu Date: Wed, 06 May 1998 13:49:08 -0600 From: Phil MacKenzie X-Mailer: Mozilla 4.05 [en] (X11; I; Linux 2.0.30 i686) MIME-Version: 1.0 To: thc@cs.dartmouth.edu Subject: possible bugs in CLR Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Tom, I've used CLR both for undergraduate and graduate algorithms - it's great! I just have a few "bug" reports. I think the following 3 are unreported "bugs" or at least wording problems. I'll send them to the official bug report list unless you find that I've made an error. - -Phil - ----------------- p.39 problem 2-4e Depends on exact definition of "asymptotically positive" which is never stated [Phil MacKenzie] p.344 problem 17.3-8 Bad wording - expected length might be about 8n-2 if you include all 2^{8n}-1 possible encodings of length < 8n (plus one of length 8n) Expected length* = (1/2^{8n})[8n + sum_{i=0}^{8n-1} i2^{i}] *This assumes the "file size" is given to you outside the actual file. [Phil MacKenzie] p.110 problem 6.2-5 Can solve in O(1) expected number of flips, but still need O(log b) bit operations to perform tests for success. [David Hargrove] ------- End of forwarded message ------- --------------------------------------------------------------- From: Alexander Hartemink Date: Fri, 8 May 1998 12:08:55 -0400 (EDT) hi, great book! i think i solved an exercise more efficiently than the solution provided in the text: exercise 6.2-5. the exercise suggests that the solution's expected number of coin flips will be polynomial in lg b. i think i have a solution where the expected number of coin flips is always 2. here's the idea: write the ratio a/b as a real number in binary. for example, if a/b = 1/3 then .01010101... or if a/b = 2/7 then .010010010... now flip the coin and using 1 for heads and 0 for tails, generate a random binary bit string between 0 and 1 by adding 1's and 0's after a decimal point. claim: you can determine if the bit string so generated will be less than a/b or more than a/b as soon as a single bit differs from the binary representation of a/b. with this in hand, it is easy to see that the expected number of necessary coin tosses is 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ... = 2. --------------------------------------------------------------- From: Michael Orlov Date: Mon, 8 Jun 1998 14:27:35 +0300 (IDT) 1. Ex. 5.4-3, p.90: For a cycle C to contain simple cycle, C should contain at least 3 distinct vertices. (For example, is a cycle that does not contain simple cycle). 2. Ex. 5.5-3, p.96: Counter-example: V={v1,v2,v3}, E={,, }. The condition should probably be restated as << unique simple path from v0 to each v $belongs-to$ V-{v0} >> 3. Ex. 5.5-4,5.5-5, p.96: (( binary tree )) should be << non-empty binary tree >>, since binary tree could be empty according to definition in 5.5.3 4. Ex. 12.2-1, p.225: It is not clear from the text whether (x,y) is ordered or unordered pair; it should probably be changed to {x,y}. 5. Ex. 12.2-6, p.226: The problem conditions are not well-defined: If the authors meant _any_ hash function, then the answer is $Omega$(n), $Big-Oh$(n*m); but if the worst-case is for the "best" hash function possible (whatever that would mean), then the answer is $Theta$(n). Probably the reuirement for the hash function to be uniform should be added. Michael Orlov BGU, Israel --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:09:28 -0500 (EST) (Resend, and test) ------- Start of forwarded message ------- Date: Mon, 3 May 1999 13:40:14 -0600 (MDT) From: Joseph L Zachary To: algorithms@theory.lcs.mit.edu Subject: Bug On page 834, in item 1 of the list that describes how to create public and secret RSA keys, change "large prime" to "large distinct prime". - Joe Zachary ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:10:23 -0500 (EST) (Resend) ------- Start of forwarded message ------- Date: Sun, 30 May 1999 18:15:31 -0700 (PDT) From: David T Liu To: algorithms@theory.lcs.mit.edu Subject: Bug Content-Type: TEXT/PLAIN; charset=US-ASCII Page 479, Line -2 Second line from the bottom: "...the total cost of executing lines 2-5 of DFS-Visit is theta(E)..." This is picky, but I believe that 2-5 should be 3-6, since we are discussing the contents of the loop and the loop spans from 3-6. ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:10:45 -0500 (EST) (Resend) ------- Start of forwarded message ------- From: Mark Hill Subject: Bug To: algorithms@theory.lcs.mit.edu Date: Tue, 27 Jul 1999 11:38:12 -0500 (CDT) Cc: markhill@cs.wisc.edu (Mark D. Hill) Content-Type: text/plain; charset=US-ASCII Possible Problem with Proof of Theorem 12.2 - ------------------------------------------- Theorem 12.2 (p. 225) states: In a hash table in which collisions are resolved by chaining, a successful search takes time THETA(1+alpha), on the average, under the assumption of simple uniform hashing. The proof seems rely on the fact that the i-th element is inserted on a list with (i-1)/m members on average. This seems true for insertion and valid for searches when the hash function puts exactly the same number of elements in the each bucket. Under "uniform" hashing, however, some buckets will have more elements than other buckets. If each element is searched for equally often, then longer lists will be searched more often than shorter lists. Example 1: bucket 1: 1 2 3 bucket 2: 4 5 6 bucket 3: 7 8 9 Average search = (1+2+3 + 1+2+3 + 1+2+3)/9 = 18/9 = 2 Example 3: bucket 1: 1 bucket 2: 2 3 4 bucket 3: 5 6 7 8 9 Average search = (1 + 1+2+3 + 1+2+3+4+5)/9 = 22/9 = 2.44 > 2 Thus, it would seem to me that analysis of successful searching would need to take into account both the mean and variance of the number of elements hashed to each bucket. Am I in error? You guys are much better than this than I am. - --Mark - ---------------------------------------------------------------------- Mark D. Hill Office 6373 CSS Professor & Romnes Fellow Phone 608-262-2196 Computer Sciences Department Asstnt 608-265-3402 University of Wisconsin-Madison FAX 608-262-9777 1210 West Dayton Street E-mail markhill@cs.wisc.edu Madison, WI 53706-1685 USA http://www.cs.wisc.edu/~markhill - ---------------------------------------------------------------------- ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:11:06 -0500 (EST) (Resend) ------- Start of forwarded message ------- Date: Sat, 4 Sep 1999 22:46:01 -0400 From: "Charles E. Leiserson" To: algorithms@theory.lcs.mit.edu Subject: bug Reply-to: dliao@cs.iupui.edu, dim@supertech.lcs.mit.edu - ------- Start of forwarded message ------- Date: Sat, 4 Sep 1999 14:42:53 -0400 (EDT) From: Dimitris Mitsouras To: "Charles E. Leiserson" cc: "6.046 Staff" <6046-staff@theory.lcs.mit.edu> Subject: bug (fwd) - - ---------- Forwarded message ---------- Date: Thu, 3 Sep 1998 12:18:11 +0800 From: Duoduo Liao To: dim@supertech.lcs.mit.edu Subject: bug Dear Professor, I am a graduate student in Purdue University School of Science. Now we are using the book of Introduction to Algorithms (The MIT Press) as our textbooks. I have just found one bug in your errata file (clrbugs.pdf) on your website. This bug is on Page 2 of this file, and also on the line 13 of page 35 of our textbook. That modified formula is not correct. It should be 2**(a(lgn))(** means POWER). Only if so, it can be equal to n**a. In addition, there are basic and correct logarithm formulas on the line -7 and -9 of page 34 as your reference. Therefore, I think the error in our textbook is only misprint, but the content in the errata is concept error. I am looking forward to your reply. Sinerely, Duoduo Liao - ------- End of forwarded message ------- ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:11:20 -0500 (EST) (Resend) ------- Start of forwarded message ------- From: "Yaakov Eisenberg" To: Subject: bug Date: Wed, 22 Sep 1999 05:39:29 -0400 Content-Type: text/plain; charset="iso-8859-1" X-Priority: 3 X-MSMail-Priority: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 page 502 The proof of Corollary 24.2 is given as: The cut (C, V - C) respects A, and (u,v) is therefore a light edge for this cut. I don't understand the "therefore." I would have written the proof thus: The cut (C, V - C) respects A, and (u,v) is a light edge for this cut. Therefore, (u,v) is safe for A. Is this a bug in the proof, or in my understanding ? ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:11:36 -0500 (EST) (Resend) ------- Start of forwarded message ------- X-Originating-IP: [63.23.64.47] From: "Sultan Al-Muhammadi" To: algorithms@theory.lcs.mit.edu Cc: jdym@pollux.usc.edu Subject: Bug Date: Fri, 24 Sep 1999 02:52:28 GMT Content-Type: text/plain; format=flowed Dear LCS, Here is a bug in the CLR text. Problem 8-2(e), page 169, line 7, I think the expression p + r - q should be p + (r-1) - q I tried a small example, but it doesn't work with p + r - q. But I think it works with p + (r-1) - q. Because the Lomuto-Partition never returns r. When i = r, it returns r-1 instead. So the prob of q is: P[q = r] = 0 p[q = r-1] = 2/n (when x is the max or 2nd max) p[p <= q <= r-2] = 1/n (for other values of x) where n = number of elements = r-p+1. For the Partition algorithm, the prob of the returned value q' is: p[q' = r] = 0 p[q' = p] = 2/n (when x is the min or the 2nd min) p[p+1 <= p <= r-1] = 1/n (for other values of x) So we have to map p to r-1. All other valuse in the range [p, r-] have the same prob. The only possible mapping is: F(i) = p + (r-1) - i ==> F(p) = p + (r-1) - p = r-1 So, if q' = F(q) = p + (r-1) - q, then both q and q' will have the same prob. Therefore, I suggest the above change. Please let me know if I am right or wrong. Thank you very much. - - Sultan Al-Muhammadi Univ of Southern California, Los Angeles. Tel# (213)386-2099 ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:11:50 -0500 (EST) (Resend) ------- Start of forwarded message ------- Date: Tue, 19 Oct 1999 12:01:35 -0400 (EDT) From: Peter Taillon X-Sender: ptaillon@floyd To: algorithms Subject: Bug In-Reply-To: <199910191556.LAA03371@theory.lcs.mit.edu> Content-Type: TEXT/PLAIN; charset=US-ASCII Page 756, Line 19: Should read "LUP-Solve", not "LU-Solve" ------- End of forwarded message ------- --------------------------------------------------------------- From: Ron Rivest Date: Fri, 19 Nov 1999 13:12:06 -0500 (EST) (Resend) ------- Start of forwarded message ------- Date: Wed, 3 Nov 1999 11:12:31 -0600 X-Authentication-Warning: playgo.mcs.gac.edu: wolfe set sender to wolfe@playgo.mcs.gac.edu using -f From: David Wolfe To: algorithms@theory.lcs.mit.edu Subject: Bug Reply-to: wolfe@gustavus.edu On page 399 of CLR (problem 19-2 part b): "the join should run in O(|h'-h''|) time" should read "the join should run in O(1 + |h'-h''|) time" (Constant time still has to be spent if h'=h''.) David ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:09:37 -0500 ------- Start of forwarded message ------- From: Mark Hill Subject: Bug To: algorithms@theory.lcs.mit.edu Date: Tue, 27 Jul 1999 11:38:12 -0500 (CDT) Cc: markhill@cs.wisc.edu (Mark D. Hill) Possible Problem with Proof of Theorem 12.2 - ------------------------------------------- Theorem 12.2 (p. 225) states: In a hash table in which collisions are resolved by chaining, a successful search takes time THETA(1+alpha), on the average, under the assumption of simple uniform hashing. The proof seems rely on the fact that the i-th element is inserted on a list with (i-1)/m members on average. This seems true for insertion and valid for searches when the hash function puts exactly the same number of elements in the each bucket. Under "uniform" hashing, however, some buckets will have more elements than other buckets. If each element is searched for equally often, then longer lists will be searched more often than shorter lists. Example 1: bucket 1: 1 2 3 bucket 2: 4 5 6 bucket 3: 7 8 9 Average search = (1+2+3 + 1+2+3 + 1+2+3)/9 = 18/9 = 2 Example 3: bucket 1: 1 bucket 2: 2 3 4 bucket 3: 5 6 7 8 9 Average search = (1 + 1+2+3 + 1+2+3+4+5)/9 = 22/9 = 2.44 > 2 Thus, it would seem to me that analysis of successful searching would need to take into account both the mean and variance of the number of elements hashed to each bucket. Am I in error? You guys are much better than this than I am. - --Mark - ---------------------------------------------------------------------- Mark D. Hill Office 6373 CSS Professor & Romnes Fellow Phone 608-262-2196 Computer Sciences Department Asstnt 608-265-3402 University of Wisconsin-Madison FAX 608-262-9777 1210 West Dayton Street E-mail markhill@cs.wisc.edu Madison, WI 53706-1685 USA http://www.cs.wisc.edu/~markhill - ---------------------------------------------------------------------- ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:09:50 -0500 ------- Start of forwarded message ------- Reply-To: "Duoduo Liao" From: "Duoduo Liao" To: "algorithms@theory.lcs" Subject: bug Date: Thu, 3 Sep 1998 12:18:21 +0800 X-Priority: 3 X-MSMail-Priority: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 X-MIME-Autoconverted: from base64 to 8bit by theory.lcs.mit.edu id NAA10647 Dear Professor, I am a graduate student in Purdue University School of Science. Now we are using the book of Introduction to Algorithms (The MIT Press) as our textbooks. I have just found one bug in your errata file (clrbugs.pdf) on your website. This bug is on Page 2 of this file, and also on the line 13 of page 35 of our textbook. That modified formula is not correct. It should be 2**(a(lgn))(** means POWER). Only if so, it can be equal to n**a. In addition, there are basic and correct logarithm formulas on the line -7 and -9 of page 34 as your reference. Therefore, I think the error in our textbook is only misprint, but the content in the errata is concept error. I am looking forward to your reply. Sinerely, Duoduo Liao ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:09:58 -0500 ------- Start of forwarded message ------- From: kpt@idt.mdh.se Date: Tue, 28 Jul 1998 00:02:26 +0200 (MET DST) To: algorithms@theory.lcs.mit.edu Subject: Bug Page 306, line +9 "The input is a sequence , where ..." I assume this should read "The input is a sequence p = , where ..." ? Page 6 in bug2.ps "Page 190, Exercise 7.5-1" should read "Page 150, Exercise 7.5-1" ________________________________________ Kjell Post, FD WWW: http://www.idt.mdh.se/kpt Phone: +46 21 101687 Telefax: +46 21 101460 ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:15 -0500 ------- Start of forwarded message ------- Date: Tue, 24 Nov 1998 09:46:50 -0600 (CST) From: Ronald Greenberg To: algorithms@theory.lcs.mit.edu Subject: Bug p. 277 Exercise 14.4-6 The problem will be much more interesting if the stipulation is added that the initial red-black tree has a black root. This is the apparent presumption when the problem is solved in the instructor's manual. Ron ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:20 -0500 ------- Start of forwarded message ------- From: =?ISO-8859-2?Q?Iv=E1nyi_antal?= To: "'algorithms@theory.lcs.mit.edu'" Subject: bug Date: Thu, 7 Jan 1999 14:50:59 +0100 Page 762, line -13: change LU-SOLVE to LUP-SOLVE (Benjamin BUDAI, student, Eo"tvo"s Lora'nd University of Budapest) ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:26 -0500 ------- Start of forwarded message ------- Date: Fri, 29 Jan 1999 12:08:14 -0800 (PST) From: Steve Chaohuang Zeng Sender: czeng@roar.stanford.edu To: algorithms@theory.lcs.mit.edu Subject: Bug In the topic: Polynomial and the FFT In this section, you defined DFT as Yk = SUM(A_j * W^kj), j= 0,1,2,...n. This definition is correct. However, you define the coefficient W^kj as W^kj = exp(2*PI*i/n). This is inconsistent with some classical books, such as "Discrete-time Signal Processing" by A. Oppenheim and R. Schafer, where W^kj = exp(-2*PI*i/n). Consequently, the DFT result by the alorithm in your book is inconsistent with the result from MATLAB. Hope this helps. Steve - -- Steve Zeng Gates 234, Center for Reliable Computing Dept. of Electrical Engineering Stanford, CA 94305 phone: +(650)-725-0487 http://www-leland.stanford.edu/~czeng ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:32 -0500 ------- Start of forwarded message ------- Date: Mon, 1 Feb 1999 11:44:06 -0500 (EST) From: Leigh Deacon To: cel@MIT.EDU Subject: [moran@cs.technion.ac.il: classification of DFS edges] - ------- Start of forwarded message ------- Reply-To: "Shlomo Moran" From: "Shlomo Moran" To: "Cormen T H" , "Leiserson sec (Ms. Leigh Deacon)" , "Rivest, R L" Subject: classification of DFS edges Date: Wed, 27 Jan 1999 12:51:19 +0200 X-Priority: 3 X-MSMail-Priority: Normal X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.22 Dear authors The classification of edges in a graph scanned by DFS, as written in p. 482 of your book, seems to imply that in an undirected graph, every non-tree edge is both a back edge and a forward edge. I think that usually, non-tree edges are considered only as back edge (see also Theorem 23.9 in p. 483 of your book) Best - - --Shlomo Shlomo Moran Head, Dept. of Computer Science, Technion, Haifa 32,000 Israel email: moran@cs.technion.ac.il phone: (972) 4 829 4261/2 fax: (972) 4 829 4353 - ------- End of forwarded message ------- ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:38 -0500 ------- Start of forwarded message ------- X-Authentication-Warning: everest.cs.umbc.edu: sherman owned process doing -bs Date: Fri, 25 Dec 1998 07:29:58 -0500 (EST) From: "Dr. Alan Sherman" To: "Cormen, Leiserson, Rivest -- Charles Leiserson" , Tom Cormen , Ronald Rivest Subject: hashing suggestion for CLR algs book How's the revision of CLR coming along? In the hashing chapter, I suggest that you add a section on perfect minimal hash functions. See Cormack, Horspool, Kaiserwerth (computer journal, vol 28, no 1, 1985, pp. 54-58). Best wishes, Alan T. Sherman sherman@umbc.edu - --------------------------------------------------------------------------- Dr. Alan T. Sherman Associate Professor, Computer Science Faculty Advisor Tele: (410) 455-2666 UMBC Chess Club Fax: (410) 455-3969 Club tele: (410) 455-8499 www.csee.umbc.edu/~sherman www.umbc.edu/chess Office: Room ECS 225j chess-external@lists.umbc.edu Department of Computer Science and Electrical Engineering University of Maryland, Baltimore County 1000 Hilltop Circle Baltimore, MD 21250 USA Directions: Take Exit 47B off I95 and follow signs to UMBC. During business hours, park in visitor's lot; at other times park in Lot 16 or 9. - --------------------------------------------------------------------------- ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:43 -0500 ------- Start of forwarded message ------- Date: Fri, 12 Feb 1999 20:12:45 +0200 (EET) From: Kasa Zoltan Reply-To: Kasa Zoltan To: algorithms Subject: Bug In-Reply-To: On page 638 in exercise 28.1-5 is superfluous to say "the number of ... is at least $\Omega (n\lg n)$" instead of "the number of ... is $\Omega (n\lg n)$" because $\Omega (n)$ informally means "at least n". On the same page in exercise 28.1-2 intead of "n-input n-output comparison network" you can write "n-input comparison network" only, because by definition an n-input comparison network has n outputs. Zoltan Kasa - ----,---,------------------------------------------------------------------- Zoltan KASA * E-mail: kasa@null.net, kasa@cs.ubbcluj.ro * * WWW : http://www.cs.ubbcluj.ro/~kasa/ * - ---------------------------------------------------------------------------- ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:49 -0500 ------- Start of forwarded message ------- From: Jerry Grossman Subject: Bug To: algorithms@theory.lcs.mit.edu Date: Tue, 9 Mar 1999 13:03:10 -0500 (EST) Cc: grossman@saturn.acs.oakland.edu (Jerry Grossman) Dear authors, Exercise 23.1-6 on page 468 asks for a O(V) algorithm for computing whether a digraph has a sink (vertex with outdegree 0 and indegree V-1) "even" if an adjacency matrix representation is used. I can find such an algorithm IF an adjacency matrix representation is used, but I don't see how one can find it if an adjacency matrix representation is NOT used. Therefore the word "even" seems inappropriate here and should be deleted. Am I missing something? best regards, jerry - -- Jerrold W. Grossman, Professor VOICE: (248) 370-3443 Department of Mathematics and Statistics FAX: (248) 370-4184 Oakland University FLESH: 346 SEB Rochester, MI 48309-4485 E-MAIL: grossman@oakland.edu WEB: http://www.oakland.edu/~grossman/ ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:54 -0500 ------- Start of forwarded message ------- From: Jerry Grossman Subject: Bug To: algorithms@theory.lcs.mit.edu Date: Mon, 22 Mar 1999 16:02:46 -0500 (EST) Cc: grossman@saturn.acs.oakland.edu (Jerry Grossman) Here's a minor typo to fix, which I didn't see in the errata list. page 923, line -3: "a undirected" should be "an undirected". best regards, jerry - -- Jerrold W. Grossman, Professor VOICE: (248) 370-3443 Department of Mathematics and Statistics FAX: (248) 370-4184 Oakland University FLESH: 346 SEB Rochester, MI 48309-4485 E-MAIL: grossman@oakland.edu WEB: http://www.oakland.edu/~grossman/ ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:10:58 -0500 ------- Start of forwarded message ------- Date: Mon, 3 May 1999 13:40:14 -0600 (MDT) From: Joseph L Zachary To: algorithms@theory.lcs.mit.edu Subject: Bug On page 834, in item 1 of the list that describes how to create public and secret RSA keys, change "large prime" to "large distinct prime". - Joe Zachary ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:11:03 -0500 ------- Start of forwarded message ------- From: "Yaakov Eisenberg" To: Subject: bug Date: Wed, 22 Sep 1999 05:39:29 -0400 X-Priority: 3 X-MSMail-Priority: Normal X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300 page 502 The proof of Corollary 24.2 is given as: The cut (C, V - C) respects A, and (u,v) is therefore a light edge for this cut. I don't understand the "therefore." I would have written the proof thus: The cut (C, V - C) respects A, and (u,v) is a light edge for this cut. Therefore, (u,v) is safe for A. Is this a bug in the proof, or in my understanding ? ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:11:07 -0500 ------- Start of forwarded message ------- X-Originating-IP: [63.23.64.47] From: "Sultan Al-Muhammadi" To: algorithms@theory.lcs.mit.edu Cc: jdym@pollux.usc.edu Subject: Bug Date: Fri, 24 Sep 1999 02:52:28 GMT Dear LCS, Here is a bug in the CLR text. Problem 8-2(e), page 169, line 7, I think the expression p + r - q should be p + (r-1) - q I tried a small example, but it doesn't work with p + r - q. But I think it works with p + (r-1) - q. Because the Lomuto-Partition never returns r. When i = r, it returns r-1 instead. So the prob of q is: P[q = r] = 0 p[q = r-1] = 2/n (when x is the max or 2nd max) p[p <= q <= r-2] = 1/n (for other values of x) where n = number of elements = r-p+1. For the Partition algorithm, the prob of the returned value q' is: p[q' = r] = 0 p[q' = p] = 2/n (when x is the min or the 2nd min) p[p+1 <= p <= r-1] = 1/n (for other values of x) So we have to map p to r-1. All other valuse in the range [p, r-] have the same prob. The only possible mapping is: F(i) = p + (r-1) - i ==> F(p) = p + (r-1) - p = r-1 So, if q' = F(q) = p + (r-1) - q, then both q and q' will have the same prob. Therefore, I suggest the above change. Please let me know if I am right or wrong. Thank you very much. - - Sultan Al-Muhammadi Univ of Southern California, Los Angeles. Tel# (213)386-2099 ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:11:11 -0500 ------- Start of forwarded message ------- Date: Tue, 19 Oct 1999 12:01:35 -0400 (EDT) From: Peter Taillon To: algorithms Subject: Bug In-Reply-To: <199910191556.LAA03371@theory.lcs.mit.edu> Page 756, Line 19: Should read "LUP-Solve", not "LU-Solve" ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:11:16 -0500 ------- Start of forwarded message ------- Date: Wed, 3 Nov 1999 11:12:31 -0600 X-Authentication-Warning: playgo.mcs.gac.edu: wolfe set sender to wolfe@playgo.mcs.gac.edu using -f From: David Wolfe To: algorithms@theory.lcs.mit.edu Subject: Bug Reply-to: wolfe@gustavus.edu On page 399 of CLR (problem 19-2 part b): "the join should run in O(|h'-h''|) time" should read "the join should run in O(1 + |h'-h''|) time" (Constant time still has to be spent if h'=h''.) David ------- End of forwarded message ------- --------------------------------------------------------------- From: "Charles E. Leiserson" Date: Sun, 21 Nov 1999 18:11:20 -0500 ------- Start of forwarded message ------- Date: Mon, 8 Nov 1999 16:56:46 -0500 (EST) From: Felipe Contreras Reply-To: fhca@site.uottawa.ca To: algorithms Subject: Bug In-Reply-To: <199911031730.MAA02183@theory.lcs.mit.edu> I haven't seen this one reported (is subtle anyway), from third print at least. Pag. 252, Line -2 (caption of Figure 13.4) Says: which has at most one child Should say: which has no left child - -- Felipe Contreras "Exactly, Watson. Pathetic and futile. But is not all life pathetic and futile? Is not his story a microcosm of the whole? We reach. We grasp. And what is left in our hands at the end? A shadow. Or worse than a shadow -- misery." RETI ------- End of forwarded message ------- --------------------------------------------------------------- From: Peter Taillon Date: Tue, 23 Nov 1999 15:16:19 -0500 (EST) Page 923, Line 7: Should read "we", not "wee" --------------------------------------------------------------- From: Ron Rivest Date: Tue, 30 Nov 1999 16:22:09 -0500 (EST) Hi Jeff Wong -- You are right; it should say "since for k > 2" rather than "since for k >= 2" in the third line of the paragraph following the statement of Theorem 33.11 on page 811. I don't think that anything else needs to be changed, though. Thanks for pointing this out! Cheers, Ron Rivest ------- Start of forwarded message ------- Subject: CLR typo Date: Tue, 30 Nov 1999 09:40:50 -0800 From: Jeff Wong To: Content-Type: text/plain; charset="US-ASCII" I believe I have found a typo in CLR: On page 811, in the paragraph following the body of Theorem 33.11, on the third line, CLR makes the claim that for k >= 2, F(k+1) mod F(k) = F(k-1) I think they meant to say "for k > 2" because for k = 2, F(3) mod F(2) = F(1) According to their definition of the Fibonacci sequence on pg 36, the Fibonacci numbers are: F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 Then for the statement "F(k+1) mod F(k) = F(k-1)", when k = 2, they are essentially saying, 2 mod 1 = 1 Am I seeing things? I think 2 (mod 1) should be 0. Jeff Wong jeffwong@ieee.org http://www.ocf.berkeley.edu/~jeffwong ================================================================== Never offend people with style when you can offend them with substance. -- Sam Brown ------- End of forwarded message ------- --------------------------------------------------------------- From: nikhil kartha Date: 9 Dec 99 08:34:08 MST This is a multi-part message in MIME format. ------NetAddressPart-00--=_iPIi7680S0a68e8cc13 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable TREE_SUCCESSOR algorithm in pg249 of CLR. Lines from 3 to 7 should be enclosed within an "ELSE" construct. ____________________________________________________________________ Get free email and a permanent address at http://www.netaddress.com/?N=3D= 1 ------NetAddressPart-00--=_iPIi7680S0a68e8cc13 Content-Type: text/plain; name="ALGOpg249.txt" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="ALGOpg249.txt" Tree-Successor(x) {algorithm on Pg 249 of INTRODUCTION TO ALGORITHM } Tree-Successor(x) 1 if right[x] <> NIL 2 then return Tree-Minimum(right[x]) 3 ELSE y <- p[x] {the book does'nt have ELSE } 4 While y <> NIL AND x = right[y] 5 Do x <- y 6 y <- p[y] 7 return y ------NetAddressPart-00--=_iPIi7680S0a68e8cc13-- --------------------------------------------------------------- From: "Zijian Ren" Date: Sat, 26 Feb 2000 17:45:13 -0600 Hi I am a graduate student studing "Intro. to Algorithms". In Page 488 question 23.4-5 to get the complexity O(V+E) of topological sort. But I think it should be O(V*V). the algorithm: while(not all vertices is labeled) { find a vertex in-degree 0 //could it spend time? in worst case it is O(V) label it remove all out edges of this vertex } So overall is O(V) * O(V) For example: 2<---3<---4......<---n and 1 has edge to 2,...n.(1,2),(1.3)....(1,n) (Sorry I can't make a graph) The vertices V=n and E about 2n. If vertices store in (1, 2, 3....n) First time to find : 1 Second to find n T= n-1 find n-1: T=n-2 ..... find 2: T=1 the overall time is O(n*n). How about your opinion? Best Regards, Zijian Ren --------------------------------------------------------------- From: Gezahegn Mekuria Date: Thu, 23 Mar 2000 00:24:47 -0800 (PST) --- algorithms wrote: > > Dear Reader: > > Your e-mail addressed to > "algorithms@theory.lcs.mit.edu" has been > handled by an automatic server program that > generated this response. > This server provides several services for readers of > INTRODUCTION TO > ALGORITHMS by Cormen, Leiserson, and Rivest (MIT > Press and > McGraw-Hill, 1990). For textbook orders in North > America, contact > your local representative of the McGraw-Hill Book > Company. For all > other orders, contact The MIT Press. > > There are several distinct services that you can > obtain from this > server, each identified by a unique keyword. To > obtain a service, > email a message to "algorithms@theory.lcs.mit.edu" > that contains the > appropriate keyword (and only that keyword) in the > "Subject:" line. > Only one service can be obtained per message. > > Here are the services available, with the > appropriate "Subject:" lines > shown: > > ============================================================================ > Subject: Help > > The server sends you this helpful message in > response. If the > server program seems to be broken somehow, send > email to > (admin@theory.lcs.mit.edu). > ---------------------------------------------------------------------------- > Subject: Bug-List > > Use this service to obtain a PostScript file of > errata for the > second and later printings of the text. A text > version of this > errata sheet is not available. A hard copy can be > obtained from > the publisher. You can also fetch this file by > anonymous ftp > using the following protocol: > % ftp theory.lcs.mit.edu > Name: anonymous > Password: > ftp> cd /pub/algorithms > ftp> get bug2.ps > ftp> quit > > --------------------------------------------------------------------------- > Subject: Old-Bug-List > > Use this service to obtain a PostScript file of > errata for the > first printing of the text. A text version of this > errata sheet > is not available. A hard copy can be obtained from > the publisher. > You can also fetch this file by anonymous ftp using > the protocol > in "Bug-List" above, but substituting "get bug1.ps" > for "get bug2.ps". > > --------------------------------------------------------------------------- > Subject: New-Bug-List > > Use this service to obtain a text file of recently > reported bugs > in the textbook that have not yet been included in > the official > errata list. > > ---------------------------------------------------------------------------- > Subject: Bug > > Use this service to report a bug in the text. The > body of your > message should give the page and line number of the > bug, and if > possible, indicate the necessary correction to be > made. > > Please check the "Bug-List" and "New-Bug-List" > before submitting > a bug report so you don't submit a duplicate bug > report. > > Please don't submit a bug report unless you are > sure that there is > a bug in the text; this service is not for raising > questions. > ---------------------------------------------------------------------------- > Subject: Manual-Bug-List > > Use this service to obtain a list of known > bugs in the > instructor's manual. > ---------------------------------------------------------------------------- > Subject: Manual-Bug > > Use this service to report a bug in the > instructor's manual. > The body of your message should give the > page and line number of > the bug, and if possible, indicate the > necessary correction to > be made. > > Please check the "Manual-Bug-List" before > submitting a bug > report so you don't submit a duplicate > report. > > Please don't submit a bug report unless you > are sure that there is > a bug in the instructor's manual; this > service is not for raising > questions. > ---------------------------------------------------------------------------- > Subject: Suggestion-List > > Use this service to obtain a list of the > suggestions that have been > made to improve the book on its next edition. > ---------------------------------------------------------------------------- > Subject: Suggestion > > Use this service to suggest improvements to the > next edition > of the book. Constructive comments and criticisms > are gratefully > appreciated. > ============================================================================ > > We regret that we cannot personally respond to all > queries and suggestions. > > Sincerely, > Thomas H. Cormen > Charles E. Leiserson > Ronald L. Rivest > > > __________________________________________________ Do You Yahoo!? Talk to your friends online with Yahoo! Messenger. http://im.yahoo.com --------------------------------------------------------------- From: German Guillermo Vera Date: Thu, 13 Apr 2000 18:07:08 -0500 (EST) Regarding Data Structures for Disjoint sets: In section 22.4 it is shown that the inverse of Ackerman's function alpha(m,n) is upper bounded by lg*(n). However, at the end of the second paragraph of page 505, line 27 (section 24.2) says: "Since alpha(E,V)=O(lg(E))..." It should say: ".. alpha(E,V)=O(lg*(V))..." Best regards, German Vera Graduate Student Purdue University --------------------------------------------------------------- From: yhchin Date: Wed, 14 Jun 2000 13:40:02 -0700 --------------5F30C977D4358579D26676AC Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Page 777, line 6. bound 2n - 1 should be changed to bound 2n - 2. Professor Y. H. Chin Institute of Computer Science National tsing-Hua University Hsinchu 30013, Taiwan --------------5F30C977D4358579D26676AC Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Page 777, line 6.  bound 2n - 1 should be changed to bound 2n - 2.

Professor Y. H. Chin
Institute of Computer Science
National tsing-Hua University
Hsinchu 30013, Taiwan --------------5F30C977D4358579D26676AC-- ---------------------------------------------------------------