ERRATA
An Introduction to the Analysis of Algorithms
R. Sedgewick and P. Flajolet
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