ERRATA IN "DESIGN AND ANALYSIS OF ALGORITHMS"
<pre>
p.22, Def 2.4, part 2
There's a missing c   term in the sum
                   k                 

p. 32, Def. 2.12
Warning:  an implementation of this definition will probably
have to consider the case when exactly one is empty.

p. 40, Def 2.33
Replace the raised dot between "a" and "U" by a lowered dot

p. 58, Theorem
Add "average case" before "time complexity"

p. 60, Figure 2.12
Add a right child to the left child of the root

p. 61, Def. 2.53, part 2
                  j                               j
Replace "keys (k )    by "a sorted sequence (k )    of keys"
                i i=1                         i i=1  

p. 61, Def. 2.43, part 2, sentence 2.
Restate as "If the root is not a leaf, it has at least 2
children and at most m children"

p. 70, definition of "empty" (near bottom of page)
Restate as "empty(H,k) is ~(k>0 and k &lt = size(H))

p. 71  Algorithm 2.59(b), line 11
Replace "empty(H,k)" by "empty(H,left(k))"

p. 71, Algorithm 2.59(b), line 18
p. 76, Algorithm 2.61, lines 4-7
function calls should be
   empty(H,k)
   Heapify(H,left(k))
   Heapify(H,right(k))
   MoveDown(H,k)

p. 84, discussion of "midsquare" and Figure 2.23
delete

p. 92, statement of theorem
Replace c by d in both occurrences (for consistency with the proof)

p. 95, paragraph 4, line 1
Replace by "Here, for example, t = 1 + t  + t  = 1 + 1 + 2 = 4, 
                                2       1    0
                               t = 1 + t + t ="
                                3       2   1
 
Replace &lt 2 4 8 16 &gt  by  &lt 2 4 8 16 ... &gt

p. 95, example near bottom of page
                                                k
Replace the upper limit "n" of the sequence of 2  terms by "n+1"

p. 103, bottom half of page
Replace indices k in sums by i 
  (or better yet, use k consistently, as in later pages)

p. 112, line 2
Replace "0 to np" by "1 to np"

p. 112, line 18
Replace S[i,j,k] by S[i,j]

p. 116, line below indented equations
Replace R(x,y,n) by R(x,y,n-1)

p. 118, Figure 2.34(e), row 2, column 1
Replace 1 by 6

p. 123, last line
insert "not" between "is" and "subject"
note nonstandardness of definition of prefix property

p. 134, line 8
replace v by i

p. 134, line 26
move to before line 24

p. 138, Exercise 25
add "if P and Q are finite sets" after "that"

p. 149, Exercise 125(b)
         n  
replace 2  by 2n

p. 150, Exercise 138
Replace by "Why can the base case be omitted in the
induction proof for the average case analysis of quicksort?"

p. 151, Exercise 153
should refer to the minimum cost spanning tree algorithm,
not the all-pairs shortest paths algorithm.

p. 151, Exercise 160
should refer to Figure 2.50, not Figure 2.49

p. 151, Exercise 164
should refer to Figure 2.40, not Figure 2.50


CHAPTER 3

p. 164, Copy algorithm, line 5
should read "offset:= start - low"

p. 170, Algorithm 3.5, line 2
replace "largest" by "smallest"

p. 171, Figure 3.4, last line
replace 5 by 6

p. 172, 3d indented line
replace right parenthesis by right bracket

p. 184, line 2 of Algorithm
no variable "curr" is used

p. 184, line 13 of Algorithm
an extra right parenthesis is needed at the end of the line


CHAPTER 4

p. 249, line 2
should read "number 14 with upper bound 53 and profit so far
of 40 ... "

p. 249, end of page
This argument assumes that lower bounds are computed at
generation rather than at expansion

p. 249, Figure 4.33, right child of root
upper bound should be 38, not 36.4.

p. 273, Algorithm 4.24, lines 10 and 13
the respective factors "a" and "b" should be deleted

p. 273, Algorithm 4.24, after line 17
copies of lines 7 and 8 should be inserted here

p. 274, last line of Section 4.16
replace "d" by "the inverse of 17 mod 40"

p. 275, indented equation, middle of page
this is called Horner's method (and should appear in index)

p. 280, Figure 4.46, first two levels
                                 3           2
the three polynomials should be x +x-2, not x +x+2

p. 288, (b)-(e)
the "s" transitions from node 5 should all go to node 2

p. 293??

p. 295??

p. 307, Exercise 47(a)
the reference should be to (d) of Figure 4.19, not to (c)


CHAPTER 5

p. 335, proof, paragraph 3, line 1
omit "s=t "
         n

p. 349 ??

p. 396, solution to Exercise 192
Replace the first paragraph with "In unsuccessful search, we
assume that each bucket is equally likely to be searched.  The
argument suggested by the previous exercise correctly gives that
U = k/b.  The number of key comparisons required to search for
 k
the kth key inserted is just U   , so S  is just one more than
                              k-1      n
the average of U  as k ranges from 0 through n-1.  This average
                k
is just 1+(1/n)Z, where Z is the sum of k/b as k ranges from 0 to n-1

p. 396, solution to Exercise 193, paragraph 2, sentence 1
Replace by "Here S  is the average value of U ; note that in
                  n                          n
this case since unsuccessful search requires an explicit key
comparison to determine that the bucket is not occupied, we don't
need to add 1 as we did in the previous exercise."

p. 399, Algorithm C.2, line 3
Replace i:=low-1 by i:=low 


GENERAL
p. 59, derivation in middle of page
Set more legibly

p. 396, solutions to Exercise 192-3
Set more legibly


INDEX
tries covered??
</pre>