From algorithms@theory.lcs.mit.edu Fri Jan 29 14:17:54 1999
Date: Fri, 29 Jan 1999 07:57:02 -0500 (EST)
From: algorithms <algorithms@theory.lcs.mit.edu>
To: dellacci@tibur.dis.uniroma1.it
Subject: Re: new-bug-list

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?
Content-Length: 201

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
Content-Length: 239


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

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