### 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
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