ERRATA

An Introduction to the Analysis of Algorithms

R. Sedgewick and P. Flajolet


This list is now maintained at the booksite for An Introduction to the Analysis of Algorithms.

July, 2006


B 01/21/96  pf    xi   line -2    add Helmut Prodinger
  02/20/97  sk     6   Pr. 1.1    line 10 b[m+1] -> b[m-l+2]
B 02/29/96  rs    32   line -8    1983 -> 1988
A 11/20/95  pf    36   line -1    Orzag -> Orszag
A 10/13/95  rs    51   Ex. 2.26   n>t  ->  n>=t
  03/05/96  pf    51   line -14   grow exponentially -> are all exponentials
A 11/20/95  pf    79   line -13   Orzag -> Orszag
B 01/21/96  hp    80   line 19    Peter Henrici -> P. Henrici
B 01/21/96  hp    87   Ex. 3.6    k\ge0 -> k\ge1 [I don't understand the ex.]
A 10/17/95  mj    93   line  4    A(z)-1  ->  A(z)
A 10/17/95  mj    93   line  7    a_0 = 0  ->  a_0 = 1
B 01/21/96  hp    98   line 3     (1-z^2) -> (1+z^2)
A 10/13/95  rs    99   Ex. 3.21   a_{n-t}  ->  (-1)^{k-1} a_{n-k}
B 01/21/96  hp    99   line -5    on the left -> on the right
B 01/21/96  hp   100   Ex. 3.22   n>2 ->  n\ge2
B 01/21/96  hp   100   Ex. 3.23   n>0 -> n\ge0
? 01/21/96  hp   105   line 13   e^z B(-z)=A(z)
B 01/21/96  hp   106   Ex. 3.39   y/(1-y) -> y/(y-1)
B 01/21/96  hp   107   line -8    1/(1-z)^3 -> 2/(1-z)^3
B 01/21/96  hp   109   Ex. 3.42   (n-2) -> (n-1)
B 01/21/96  hp   111   line -4    eliminate + - in C(z)
B 01/21/96  hp   112   line 14    28\% -> 14\%
B 01/21/96  hp   117   line 9     B_{Nk} -> |B_{Nk}| (cardinality)
? 01/21/96  hp   117   l. 13, 18  Very unclear what we sum on (k? b?)
A 10/13/95  rs   129   Ex. 3.67   G(z)  ->  C(z)
A 10/20/95  eb   139   line -15   give  ->  to give
? 10/13/95  rs   139   line -7    p  ->  t
A 10/20/95  eb   140   line 6     fifth term: u^2 -> u^1
  06/23/05  mw   142   line 7     Reference to Ex 4.58 should be 4.56
B 01/21/96  hp   145   line -12   already -> already in
  11/04/96  dw   145   line -3    B_2  ->  B_2/2
A 10/20/95  eb   145   line -4    B_2  ->  B_2/2 and  B_3  ->  B_3/6
B 01/21/96  hp   150   line -14   1988 -> 1989
  11/19/96  sk   169   line 12    e-\lambda -> e^{-\lambda}
B 01/21/96  hp   174   line -11   1/N+1/N^2 -> 1/N-1/N^2
B 01/21/96  hp   175   Ex. 4.40   \log -> \ln [for consistency]
A 10/16/95  rs   182   line -3    f(k)  ->  f(x)dx
A 11/20/95  pf   184   line 3     space after "4.2"
  11/12/96  sk   185   line -3    R_{2m} -> R_m
  11/12/96  sk   187   line -13   Ex. 4.57 O(N^3) -> O(1/N^3)
A 11/20/95  pf   203   line 1     Orzag -> Orszag
  06/23/05  mw   204   line -6    \exp(-k^2/(2N)) has missing last )
  11/18/96  sk   210   line 5     Ex. 4.73 add bound k\le N/2 to sum
A 11/20/95  pf   218   line 16    Orzag -> Orszag
B 02/29/96  rs   218   line -1    1988 -> 1989
B 01/21/96  hp   226   line 7   |t| -> |g|
B 01/21/96  hp   243   line 13	   N\ge0 -> N\ge1
B 01/21/96  hp   243   line -9	      z=1 -> u=1
B 01/21/96  hp   246   line 1   z=1 -> u=1
A 10/16/95  rs   253   line -5    C(z)  ->  C_T(z)
A 11/08/95  rs   257   line -1    G_h  ->  G^{[h]}  (two occurrences)
A 11/20/95  pf   258   line -5    G_h  ->  G^{[h]}
A 11/20/95  pf   258   line -5    add factor of z on rhs of eq. for G^{[h]}(z)
? 01/21/96  hp   270   Ex. 5.48   Figure 5.17 -> (?) Figure 5.13
  06/23/05  mw   276   line 12    Plamer -> Palmer
  06/23/05  mw   281   line -14   "is is" -> "it is"
B 02/29/96  rs   297   line -5    1983 -> 1988
  11/19/96  sk   319   line -9    add bound k\le N/2 to sum
B 01/21/96  hp   331   line 12    Striling -> Stirling
  02/17/97  sk   335   Prog. 6.2  infinity -> -infinity
  06/23/05  mw   336   Thm 6.7    displayed product should be \prod_{1\leq k \leq N} (1 - u^k)/(1 - u)
A 11/15/95  rs   346   line -1    zB(u,z) -> uB(u,z)
A 11/15/95  rs   351   line -5    left-to-right minima -> cycles
B 02/29/96  rs   360   line -13   1983 -> 1988
  06/23/05  hl   371   line -1    probabilities are off by factor c_k
B 02/29/96  rs   412   line -6    1983 -> 1988
A 12/04/95  ms   439   line 4     sqrt{N/M} -> sqrt{N/M-N/M^2}
A 12/04/95  ms   439   line -8    add u^kz^N in second sum
  04/05/99  sk   446   line 2     has -> hash
B 01/21/96  hp   474   line 4     1993 -> 1993, 233-358 [pages]
A 11/20/95  pf   477   index      "Algebraic function" out of order

eb: Ender Bilir
hl: Hao Lu
mj: Mariusz Jakubowski
hp: Helmut Prodinger
ms: Michele Soria
dw: Dan Wang
sk: Scott Karlin
mw: Mark Wilson

 ?: Couldn't verify; didn't change
 A: Fixed on January 17, 1996
 B: Fixed on February 29, 1996

------------
Things to fix in next edition/printing?

rs: Need exercises in Chapter 3 on symbolic method
pf: Need summary tables a la Volume2 for symbolic methods
rs: Corollary for nonhomogenous linear recurrences in Chapters 2, 3
rs: We never say that number of leaves determines all node types 
    (combinatorially) in any binary tree
rs: Add simpler form of second version of EMS like page 182 line -3
rs: Expand, demystify, simplify pp. 259-60
rs: Merge, fix/simplify exercises 6.49 and 6.50
rs: Emphasize use of symbolic method in 5-8. Play down "doing it the hard way"
rs: Quote results on generalized birthday, coupon collector?
hp: page 448: 6-lines on top is just Vandermonde => {M+1 choose N} (Ex. 3.34).
rs: Special thanks to Mark Wilson for tracking errata