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 <U60896%UICVM.BITNET@mitvma.mit.edu>
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
       <<Show how to use an order-statistic tree to count ...>>

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 <jwang@cse.ucsc.edu>
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 <jwang@cse.ucsc.edu>
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 <Christian.Collberg@dna.lth.se>
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" <kamiya@SPUNKY.CS.NYU.EDU>
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: <klein@cs.brown.edu>
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 <samjain@accord.ece.cmu.edu>
Date: Wed, 20 Oct 93 00:57:12 -0400
Just a small typo:

Page 299, Paragraph 2, line 6:  "memoize" --> "memorize"
---------------------------------------------------------------

From: Samir Jain <samjain@accord.ece.cmu.edu>
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 <<key[i] < k>> in line 3 of the code should be replaced
by <<key[i] <= k>>

----------  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 <jaf@dworkin.wustl.edu>
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 <a_1, a_3, ..., a_{n-1}> with
the sequence on lines <a_{n+1}, a_{n+3}, ..., a_{2n-1}> (the odd elements).
The second merges <a_2, a_4, ..., a_n> with <a_{n+2}, a_{n+4}, ..., a_{2n}>
(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 <a_1, a_3, ..., a_{n-1}> with
the sequence on the lines <a_{n+2}, a_{n+4}, ..., a_{2n}> (the odd
elements of the top half with the even elements of the bottom half).
The second merges <a_2, a_4, ..., a_n> with <a_{n+1}, a_{n+3}, ...,
a_{2n-1}>
(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 <cthombor@ua.d.umn.edu>
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 <cthombor@ua.d.umn.edu>
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 <chang@cs.umbc.edu>
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 <felzer@tigger.cs.Colorado.EDU>
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 <gjt@unix.brighton.ac.uk>
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 <tompa@cs.washington.edu>
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 <tompa@cs.washington.edu>
Date: Thu, 14 Apr 1994 16:58:18 PDT

page 152, line 1 of problem 7-2:
Change ((nodes have d children)) to <<nodes (with one possible exception)
have
d children>>.
---------------------------------------------------------------

# 293

From: Rolf Karlsson <Rolf.Karlsson@dna.lth.se>
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: <gereb@allegro.cs.tufts.edu>
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: <cel@theory.lcs.mit.edu>
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 <shallit@graceland.uwaterloo.ca>
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 <shallit@graceland.uwaterloo.ca>
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 <norberto@u.washington.edu>
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 <yu@pollux.cs.uga.edu>
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 <rjw@ccs.neu.edu>
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: <max@gac.edu>
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      <<if more than one point has the same angle>>
                       ^^^

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 <dietzf@markov.informatik.uni-dortmund.de>
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 <D15QC@qcvaxa.acc.qc.edu>
Subject: Bug
To: algorithms <algorithms@theory.lcs.mit.edu>
Message-ID: <Pine.VMS3.89:b9 QCM.9502232318.A539047091-0100000@>
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 <gordon@cs.uwa.edu.au>
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 <shallit@graceland.uwaterloo.ca>
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 <shallit@math.uwaterloo.ca>
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 <orenf@CS.HUJI.AC.IL>
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" <htlau@bnr.ca>
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 <galecki@paul.rutgers.edu>
Date: Mon, 02 Oct 1995 21:56:38 -0400
---------------------------------------------------------------

From: Marek <galecki@paul.rutgers.edu>
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 <Florian.Zschocke@post.rwth-aachen.de>
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 <beigel-richard@CS.YALE.EDU>
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 <yihchun@u.washington.edu>
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 <ldp@cs.brown.edu>
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 <chahin@owlnet.rice.edu>
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 <thnguyen@sunrise.cse.fau.edu>
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 <diferdin@cs.unibo.it>
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 <borges@isc.tamu.edu>
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: <av0@cis.ufl.edu>
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: <av0@cis.ufl.edu>
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 <sc@cs.unc.edu>
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" <cel@theory.lcs.mit.edu>
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 <ien@mit.edu>

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 <thc@zayante.cs.dartmouth.edu>
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" <lucven@inopera.it>
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:
<<Theorem 23.16 and Theorem 23.13 imply that every vertex in C(r)
ends up in the same depth-search tree.>>

Regards,
--
Luca Venuti
  Keyserver for PGP Public Key: 0x3E71BEE9
  WWW: http://www.geocities.com/CapitolHill/2358/
---------------------------------------------------------------

From: "Luca Venuti" <lucven@inopera.it>
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
   <<The "while" loop is executed |V| times)).

Regards,
--
Luca Venuti
  Keyserver for PGP Public Key: 0x3E71BEE9
  WWW: http://www.geocities.com/CapitolHill/2358/
---------------------------------------------------------------

From: Michael Folkmann <gobus@diku.dk>
Date: Mon, 10 Feb 1997 17:25:45 +0100
---------------------------------------------------------------

From: Popescu Carmen <pc193@scs.ubbcluj.ro>
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" <scott@CS.Princeton.EDU>
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 <todd@cs.washington.edu>
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 <alex@acintl.ro>
Date: Thu, 10 Jul 1997 15:09:33 +0300
---------------------------------------------------------------

From: Betty J Salzberg <salzberg@ccs.neu.edu>
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 <jgarcia@cs.purdue.edu>
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: <ney@zealand.cs.dartmouth.edu>
Date: Tue, 12 Aug 97 14:35:33 -0400 (EDT)
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
From: Neal Young <ney@cs.dartmouth.edu>
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 <strumpen@flax.lcs.mit.edu>
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 <bytedr@iglou.com> 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 <tony@ludens.elte.hu>
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 <colinp@mindspring.com>
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" <nelson@teapot.llnl.gov>
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 <pcsaszar@eecs.uic.edu>
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
       <<Change>>

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 <bdpeytch@students.wisc.edu>
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 <<of the second
edition of...>>

Introduction to Algorithms
Second Edition, fourth printing
page 26
lines 18-19
Change ((f(n) is on or below g(n).)) to <<f(n) is on or below cg(n).>>
---------------------------------------------------------------

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 <alexbrn@cix.compulink.co.uk>; 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 <alexbrn@cix.compulink.co.uk>; 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 <thc@zayante.cs.dartmouth.edu>
To: alexbrn@cix.compulink.co.uk
In-reply-to: <memo.145575@cix.compulink.co.uk>
(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" <cel@supertech.lcs.mit.edu>
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 <strumpen@supertech.lcs.mit.edu>
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 <jysky@cs.tut.fi>
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 <thc@zayante.cs.dartmouth.edu>
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 <jysky@cs.tut.fi>
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 <thc@zayante.cs.dartmouth.edu>
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 <philmac@moonstone.idbsu.edu>
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 <amink@mit.edu>
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 <orlovm@bgumail.bgu.ac.il>
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, <v0,v1,v0,v1,v0>
is a cycle that does not contain simple cycle).

2. Ex. 5.5-3, p.96: Counter-example: V={v1,v2,v3}, E={<v0,v1>,<v1,v2>,
<v2,v3>}. 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 <rivest@theory.lcs.mit.edu>
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 <zachary@cs.utah.edu>
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 <rivest@theory.lcs.mit.edu>
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 <liuda@seas.ucla.edu>
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 <rivest@theory.lcs.mit.edu>
Date: Fri, 19 Nov 1999 13:10:45 -0500 (EST)

(Resend)

------- Start of forwarded message -------
From: Mark Hill <markhill@cs.wisc.edu>
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 <rivest@theory.lcs.mit.edu>
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" <cel@supertech.lcs.mit.edu>
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 <dim@supertech.lcs.mit.edu>
To: "Charles E. Leiserson" <cel@supertech.lcs.mit.edu>
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 <dliao@cs.iupui.edu>
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 <rivest@theory.lcs.mit.edu>
Date: Fri, 19 Nov 1999 13:11:20 -0500 (EST)

(Resend)

------- Start of forwarded message -------
From: "Yaakov Eisenberg" <yaakov.eisenberg@worldnet.att.net>
To: <algorithms@theory.lcs.mit.edu>
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 <rivest@theory.lcs.mit.edu>
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" <muhamadi@hotmail.com>
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 <rivest@theory.lcs.mit.edu>
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 <ptaillon@turing.scs.carleton.ca>
X-Sender: ptaillon@floyd
To: algorithms <algorithms@theory.lcs.mit.edu>
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 <rivest@theory.lcs.mit.edu>
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 <wolfe@gac.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:09:37 -0500
------- Start of forwarded message -------
From: Mark Hill <markhill@cs.wisc.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:09:50 -0500
------- Start of forwarded message -------
Reply-To: "Duoduo Liao" <dliao@cs.iupui.edu>
From: "Duoduo Liao" <dliao@cs.iupui.edu>
To: "algorithms@theory.lcs" <algorithms@theory.lcs.mit.edu>
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" <cel@supertech.lcs.mit.edu>
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 <p_0, p_1, ..., p_n>, where ..."

        I assume this should read

        "The input is a sequence p = <p_0, p_1, ..., p_n>, 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" <cel@supertech.lcs.mit.edu>
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 <rig@cs.luc.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:10:20 -0500
------- Start of forwarded message -------
From: =?ISO-8859-2?Q?Iv=E1nyi_antal?= <tony@ludens.elte.hu>
To: "'algorithms@theory.lcs.mit.edu'" <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" <cel@supertech.lcs.mit.edu>
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 <czeng@dodge.Stanford.EDU>
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" <cel@supertech.lcs.mit.edu>
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 <deacon@supertech.lcs.mit.edu>
To: cel@MIT.EDU
Subject: [moran@cs.technion.ac.il: classification of DFS edges]

- ------- Start of forwarded message -------
Reply-To: "Shlomo Moran" <moran@cs.technion.ac.il>
From: "Shlomo Moran" <moran@cs.technion.ac.il>
To: "Cormen T H" <thc@cs.dartmouth.edu>,
        "Leiserson sec (Ms. Leigh Deacon)" <deacon@supertech.lcs.mit.edu>,
        "Rivest, R L" <rivest@mit.edu>
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" <cel@supertech.lcs.mit.edu>
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" <sherman@cs.umbc.edu>
To: "Cormen, Leiserson, Rivest -- Charles Leiserson"
<leiserson@theory.lcs.mit.edu>,
        Tom Cormen <tom.cormen@dartmouth.edu>,
        Ronald Rivest <rivest@theory.lcs.mit.edu>
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" <cel@supertech.lcs.mit.edu>
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 <kasa@CS.UBBCluj.Ro>
Reply-To: Kasa Zoltan <kasa@CS.UBBCluj.Ro>
To: algorithms <algorithms@theory.lcs.mit.edu>
Subject: Bug
In-Reply-To: <Pine.LNX.3.96.990212080303.17998C-100000@Nessie.CS.UBBCluj.Ro>

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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:10:49 -0500
------- Start of forwarded message -------
From: Jerry Grossman <grossman@Oakland.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:10:54 -0500
------- Start of forwarded message -------
From: Jerry Grossman <grossman@Oakland.edu>
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" <cel@supertech.lcs.mit.edu>
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 <zachary@cs.utah.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:11:03 -0500
------- Start of forwarded message -------
From: "Yaakov Eisenberg" <yaakov.eisenberg@worldnet.att.net>
To: <algorithms@theory.lcs.mit.edu>
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" <cel@supertech.lcs.mit.edu>
Date: Sun, 21 Nov 1999 18:11:07 -0500
------- Start of forwarded message -------
X-Originating-IP: [63.23.64.47]
From: "Sultan Al-Muhammadi" <muhamadi@hotmail.com>
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" <cel@supertech.lcs.mit.edu>
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 <ptaillon@turing.scs.carleton.ca>
To: algorithms <algorithms@theory.lcs.mit.edu>
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" <cel@supertech.lcs.mit.edu>
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 <wolfe@gac.edu>
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" <cel@supertech.lcs.mit.edu>
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 <fhca@site.uottawa.ca>
Reply-To: fhca@site.uottawa.ca
To: algorithms <algorithms@theory.lcs.mit.edu>
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 <ptaillon@turing.scs.carleton.ca>
Date: Tue, 23 Nov 1999 15:16:19 -0500 (EST)

        Page 923, Line 7:      Should read "we", not "wee"

---------------------------------------------------------------

From: Ron Rivest <rivest@theory.lcs.mit.edu>
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 <jeffwong@uclink4.berkeley.edu>
To: <rivest@MIT.EDU>
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 <nikhil.kartha@usa.net>
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" <zjren@eng.uiowa.edu>
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 <gezahegnk@yahoo.com>
Date: Thu, 23 Mar 2000 00:24:47 -0800 (PST)

--- algorithms <algorithms@theory.lcs.mit.edu> 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: <your login @ your machine>
>               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 <veragg@ecn.purdue.edu>
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 <yhchin@cs.nthu.edu.tw>
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

<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Page 777, line 6.&nbsp; bound 2<i>n</i> - 1 should be changed to bound
2<i>n </i>- 2.
<p>Professor Y. H. Chin
<br>Institute of Computer Science
<br>National tsing-Hua University
<br>Hsinchu 30013, Taiwan</html>

--------------5F30C977D4358579D26676AC--

---------------------------------------------------------------