Algorithms, 3rd edition, in C, by Robert Sedgewick
Chnages made for fourth printing (January, 1999)
. 1/19/98 sm 7 2 "associative" -> "transitive"
. 3/13/98 cvw 7 -2 "a such a" -> "such a"
. 2/03/98 cvw 9 -15 "asks" -> "ask"
. 4/04/98 jk 12 12 "algorithm an" -> "algorithm is an"
. 2/03/98 cvw 13 1.1 "M pairs of N objects" ->
. "N objects that involve M union operations"
. [change proof and text following accordingly]
. 6/04/98 vc 15 1.6 caption should refer to quick union, not find
. 4/04/98 jk 15 1.6 last entry in "4 8" line should be shaded
! 3/13/98 rc 16 1.3 "lg N" -> "2lg N" [also mention that we don't
count the root self-pointer in the proof]
. 6/04/98 cvw 16 -11 "sets" -> "sizes of the sets"
. 3/13/98 cvw 17 -8 "the the" -> "the"
. 4/17/98 jk 17 -5 "1.2" -> "1.3"
. 3/13/98 cvw 17 -1 "MN" -> "MN/2"
. 3/13/98 cvw 18 1.9 "making make" -> "making"
. 2/03/98 cvw 18 1.9 "4 8" -> "6 8"
. 2/03/98 cvw 19 1.4 don't need t; use "id[i] = id[id[i]]" etc.
. 3/13/98 cvw 21 1.14 "Program 1.4" -> "Program 1.3"
. 4/04/98 jk 23 2 "such those" -> "such as those"
. 2/03/98 cvw 23 -13 "grow" -> "grows"
. 4/05/98 jk 32 -18 "take" -> "takes"
. 1/13/98 jl 33 2.2 count too big to be an int
. 3/13/98 cvw 38 2.1 "covert" -> "convert"
. 3/13/98 cvw 39 2.1 several entries are incorrect
. 2/03/98 cvw 39 -15 "produced" -> "produce"
. 2/03/98 cvw 42 -15 Second 1 missing in Fibonacci sequence
. 2/03/98 cvw 42 -3 -N/e + \sqrt{2\pi} -> -N\lg e +\lg\sqrt{2\pi N}
. [also reflect change in Table 2.3]
. 12/04/97 mw 42 23 .61803 -> 1.61803
. 2/03/98 cvw 43 2.3 F_{10} = 55
. 3/13/98 cvw 44 2.9 change function to $\lfloor \lg N\rfloor + 1$
. 4/15/98 pw 46 3 "N H_N" -> "2 N H_N"
. 11/19/98 rs 46 -12 a_0 -> 2a_0
. 2/03/98 cvw 47 -13 "algorithms" -> "algorithm"
. 2/03/98 cvw 48 2.24 "O\alpha^N" -> "O(\alpha^N)"
. 2/03/98 cvw 50 -2 "1 bits" -> "bits"
. 4/05/98 jk 50 2.6 "the the" -> "the"
. 2/02/98 gt 51 18 "is is" -> "is"
. 2/03/98 cvw 56 2.2 "functionality of" -> "functionality as"
. 2/03/98 cvw 57 8 "an an" -> "an"
. 2/24/98 dcl 59 2.4 "take s" -> "takes"
. 2/03/98 cvw 60 4 "data," -> "data"
. 5/01/98 lf 62 7 "Moveover" -> "Moreover"
. 3/13/98 cvw 64 2.51 "that time" -> "that the time"
. 1/06/98 rs 64 -1 "the algorithms" -> "specific algorithms that
. solve the problems"
! 4/08/98 jk 72 3 "-32,767" -> "-32,768"
. 3/08/98 rs 72 5 "a a" -> "a"
. 4/05/98 jk 75 3.2 add "#include " (for sqrt)
. 4/05/98 jk 75 3.2 add "#include " (for printf)
x 4/05/98 jk 75 3.2 change printf to %lf
. 3/08/98 rs 75 3.2 "numType" -> "Number"
. 1/27/98 cvw 75 4 "\mu^2/N" -> "\mu^2"
. 3/15/98 cvw 77 7 "operations" -> "an operation"
x 4/05/98 jk 80 3.4 note float vs. double for sqrt return and args
. 12/03/97 cvw 84 3.5 "j < N/i" -> "i*j < N"
. 3/15/98 cvw 84 -5 easier to see that function is < NH_N
x 4/05/98 jk 85 3.6 atoi -> atol
. 4/05/98 jk 86 6 "programs" -> "program"
. 1/27/98 cvw 89 3.15 "if a[i]" -> "if (a[i])"
. 1/27/98 cvw 91 -6 "links are references" -> "links are pointers"
. 4/08/98 jk 97 12 "procedure" -> "function"
. 1/27/98 cvw 99 3.8 a and b are reversed
. 5/20/98 cvw 101 3.1 else clause for "head pointer, null tail"
should be in braces
. 1/27/98 cvw 101 3.1 "circular, never empty"
first insert: "head->next = head"
traversal loop: "t = head;
do { ... t = t->next; } while (t != head);"
. 1/27/98 cvw 105 3.10 "x->next-prev" -> "x->next->prev"
. 1/27/98 cvw 105 3.10 "x->->next" -> "x->next"
. 3/15/98 cvw 111 -9 "break" -> "printf("%d ", i)"
. 3/15/98 cvw 114 3.2 parenthesis missing on strncmp call
. 3/15/98 cvw 114 3.2 "b-a" -> "b-a-1" (pointer version of strlen)
, 3/15/98 cvw 114 3.2 "*a" -> "*(a-1)", "*b" -> "*(b-1)" (last line)
. 5/05/98 rs 114 3.2 "*a" -> "*(a-1) == 0" (next-to-last line)
. 4/12/98 jk 116 -3 "us use" -> "us to use"
. 4/05/98 jk 117 3.12 "then" -> "than"
. 3/15/98 rs 117 20 a[k][j] -> b[k][j]
. 3/15/98 cvw 118 -11 b[N*k+i] -> b[N*k+j]
. 1/27/98 cvw 118 3.17 "pointer to pointer to pointer" ->
"pointer to pointer"
. 4/05/98 jk 121 3.15 "the the" -> "the"
. 1/19/98 ml 127 9 "build" -> "to build"
. 4/14/98 jk 137 4.1 "by implementations" -> "implementations"
x 10/08/97 drh 137 4.2 "STACKempty()" -> "STACKempty(void)
[same change elsewhere, e. g., Prog. 1.3]
. 1/27/98 cvw 138 3 "in" -> "into"
. 3/02/98 rs 141 -14 "code." -> "code"
. 4/14/98 jk 142 7 "procedure" -> "function"
. 6/04/98 et 152 4.6 "int UFunion" -> "void UFunion"
[same change elsewhere, e.g., Prog. 4.8]
. 10/08/97 drh 152 4.8 "int find" -> "static int find" in line 11
[same change elsewhere, e.g., Prog. 12.5]
. 1/27/98 cvw 154 5 "in" -> "on"
. 3/17/98 cvw 160 -3 "minus signs" -> "asterisks"
. 3/17/98 cvw 160 -2 "pop" -> "get"
. 11/23/97 ml 164 4.11 U -> T on queue in second-to-last line
. 1/27/98 cvw 164 4 "as is a" -> "is a"
. 1/27/98 cvw 169 15 "k = 2" -> "k = 1"
. 1/27/98 cvw 169 4.12 "eighth" -> "eight"
1/19/98 ml 170 11 "the own" -> "their own"
! 6/04/98 rb 177 4.20 QUEUEget could set tail null on empty queue
. 1/27/98 cvw 178 4.69 "7+4i" -> "8+4i"
. 1/27/98 cvw 183 4.23 caption is wrong about creating new objects
. 1/27/98 cvw 184 4.79 needs a concluding "."
. 1/27/98 cvw 190 5.2 "program" -> "function" in 1st line of caption
. 1/27/98 cvw 196 5.4 X -> Y on second line
. 3/17/98 cvw 196 5.4 outdent last three lines one level
. 1/27/98 cvw 205 5.11 interchange "mark(3,1)" and "rule(2,4,1)"
. 1/27/98 cvw 205 -3 "invocations" -> "invocations are involved"
. 1/19/98 ml 206 16 "is is" -> "is"
. 5/05/98 lf 209 5.35 "4.13" -> "4.3"
. 1/27/98 cvw 211 10 reference to Fig 5.16 is misplaced
. 1/27/98 cvw 214 5.17 3's should be internal, with external 0's
. 1/27/98 cvw 214 -5 "Parts" -> "in Parts"
. 1/27/98 rs 214 5.18 several bugs in tree
. 1/27/98 cvw 214 5.18 delete last two sentences in caption
. 1/27/98 cvw 217 14 "5.1 and 5.2" -> "5.2 and 5.3"
. 1/27/98 cvw 222 -4 "have" -> "has"
. 1/27/98 cvw 229 5.69 "M-ary" -> "an M-ary"
. 1/27/98 cvw 229 5.70 "a M-ary" -> "an M-ary"
. 3/17/98 cvw 229 5.68 "N nodes" -> "N internal nodes"
. 1/27/98 cvw 230 17-20 swap parenthesized clauses
. 1/27/98 cvw 231 5.25 add "visit" for A, C, F, and G
. 1/27/98 cvw 233 -6 items -> item
. 5/09/98 rs 233 -8 description doesn't match code
! 4/16/98 jk 237 -9 "document," -> "document."
. 1/27/98 cvw 237 5.18 single quotes (not double) around the *
x 3/08/98 rs 238 5.19 NEW not worth the trouble; save for Chapter 12
x 3/08/98 rs 240 5.20 NEW not worth the trouble; save for Chapter 12
. 5/21/98 cvw 243 5.21 "the all the" -> "all the"
. 1/27/98 cvw 243 5.32 indent "check 4 on 3's list" one more level
. 1/27/98 cvw 245 -12 "on each" -> "on the nodes on each"
. 1/27/98 cvw 256 6.1 "Section 8." -> "Section 6." (two occurrences)
. 5/21/98 cvw 257 12 "function function" -> "function"
. 4/01/98 cvw 260 6.10 "than" -> "that"
. 1/27/98 cvw 262 -4 "each in its" -> "each into its"
. 2/06/98 kh 263 6.3 circle 2nd E, not 1st, on line -2
. 3/16/98 rs 262 6.3 change first for loop to
for (i = r; i > l; i--)
compexch(a[i], a[i-1]);
(use bubble-sort pass to maintain stability)
. 2/13/97 kg 274 -10 4^i -> 4^{i+1}
. 1/20/98 rs 274 -9 Property 6.9 -> Property 6.10
. 1/27/98 cvw 276 12 Section 8.7 -> Section 6.7
. 2/06/97 pn 276 -10 factor of N missing
. 1/20/98 rs 276 6.8 "never does more than" -> "does less than"
[similar fixes nearby]
. 1/20/98 rs 277 -16 Property 6.7 -> Property 6.8
[similar errors nearby]
. 2/16/97 jw 279 6.2 Property and Exercise references in Key are
incorrect
. 3/21/98 rs 283 10 "all.." -> "all."
. 3/28/98 rs 291 5 should read "...name; int num; "
. 2/04/98 gt 295 18 "with with" -> "with"
. 1/27/98 cvw 299 -16 needs " = a[i];" at the end
! 6/04/98 et 300 6.17 last line: "b[i]" -> "b[i-l]"
[same bug in 10.4; change 10.2 to match]
. 3/28/98 rs 306 7.2 "begin" -> "begins"
. 3/28/98 rs 307 -6 suggested fix doesn't work without combining
Programs 7.1 and 7.2
. 2/16/97 dn 307 -4 "i < j" -> "i > j"
. 4/02/98 cvw 307 -1 "into" -> "in"
. 1/27/98 cvw 316 7.12 "the in" -> "in the"
. 4/02/98 cvw 317 7.22 "comparisions" -> "comparisons"
. 1/27/98 cvw 319 7.22 "a random files" -> "random files of N elements"
. 4/02/98 cvw 321 7.4 Chapter 8 -> Chapter 6
. 5/11/98 rs 323 7.33 "changed to" -> "changed to omit the first
exchange and to"
. 1/27/98 dc 336 12 Chapter 8 -> Chapter 6
. 3/13/98 cvw 340 8.2 not stable (sentinel needed)
. 4/12/98 dcl 343 5 right-hand floor bracket is wrong
. 1/27/98 cvw 343 8.3 64, 32, 16 -> 32, 16, 8 (in caption)
. 1/27/98 cvw 344 12 adaptive -> nonadaptive; 8.1 -> 6.1
. 3/16/98 rs 345 8.4 hide maxN definition
. 1/27/98 cvw 348 8.5 "m < r-l" -> "m <= r-l"
. 1/27/98 cvw 349 8.5 leaf nodes should be square
. 1/27/98 cvw 356 8.7 caption incorrectly says code uses z
. 3/28/98 rs 363 -9 prematurely refers to heaps
. 5/21/98 cvw 365 9 "structure" -> "structure."
. 2/23/98 st 365 11 "the the" -> "the"
. 4/03/98 cvw 365 9.2 "R * * I * T * Y" -> "R * I T * Y *"
. 1/27/98 cvw 368 9.15 "key in" -> "keys in"
. 3/28/98 rs 369 9.2 "element in" -> "the element in"
. 1/27/98 cvw 369 -9 "provides" -> "provide"
. 4/03/98 cvw 370 5 "in the" -> "in"
. 1/27/98 cvw 371 -7 "key" -> "keys"
. 1/27/98 cvw 375 -7 "to" -> "into"
. 2/17/98 mk 378 9.9 I and P should be interchanged in the top tree
. 1/27/98 cvw 379 9.7 Use pointer (not macro) for pq
. 1/13/98 rs 386 9.9 Replace last sentence in commentary by:
"We specify the structure PQnode to be
a doubly-linked list node (with a key and
two links), and the structure pq to be the
list's head and tail links."
. 1/27/98 cvw 386 9.9 add "return t;" as last statement in PQinsert
. 1/27/98 cvw 387 9.10 fix PQdelete to refer to x, not t
. 1/27/98 cvw 387 9.10 remove reference to atail and bhead
. 1/20/98 st 388 8 "a where" -> "where a"
. 3/28/98 rs 388 -8 "Program 9.1" -> "program 9.8"
. 3/28/98 rs 390 9.11 "data.grade[i]" -> "data[i].grade" [same for j]
. 3/16/98 pf 391 9.12 Fix exch to modify pq
. 5/11/98 lf 395 -9 "represent represent" -> "represent"
. 1/27/98 cvw 395 9.13 PQlink t is unused
. 1/27/98 cvw 395 9.16 in the bottom tree, N needs a child G and
M needs a child A
. 1/20/98 rs 396 9.14 brace hits right side of box
. 2/19/98 rs 396 9.17 M-A -> T-I
. 1/27/98 cvw 398 9.14 should use "less", not ">"
. 1/27/98 cvw 398 9.14 j unused
. 4/03/98 cvw 402 9.59 "R * * I * T * Y" -> "R * I T * Y *"
. 10/27/98 jaw 407 -9 bth -> bth (from the right)
. 2/22/98 mk 410 10.2 9.1 -> 7.1
. 3/10/98 mk 410 10.2 example not sorted
. 1/27/98 cvw 410 10.1 caption refers to b, should be w
. 2/22/98 mk 419 10.9 delete second occurrence of "by"
. 5/11/98 rs 420 10.10 "Figure 10.8" -> "Figure 10.7"
. 4/03/98 cvw 424 10.12 "number empty" -> "number of empty"
. 11/07/97 dek 425 "Program 10.3 ... application" ->
"When we adapt Program 10.3 to this application,
we refer to it as {\it multikey quicksort}."
! 6/04/98 et 416 10.2 subtract l from both aux refs to match change
to Prog. 10.4
! 6/04/98 et 426 10.4 last line: "aux[i]" -> "aux[i-l]"
. 3/28/98 rs 428 10.16 "consisiting" -> "consisting"
. 3/03/98 bs 428 10.35 "first" -> "leading"
. 1/27/98 cvw 428 10.37 "or records" -> "of records"
. 1/27/98 cvw 432 13 "result" -> "result."
. 1/27/98 cvw 432 10.40 "of the of the" -> "of the"
. 1/27/98 cvw 440 9 "a a" -> "a"
. 1/27/98 cvw 440 -14 "a a" -> "a"
. 1/27/98 cvw 442 11.1 emphasize assumption that N is a power of 2
. 3/17/98 rs 443 11.2 use example with 16 elements
. 1/27/98 cvw 443 11.2 emphasize assumption that N is a power of 2
. 1/27/98 cvw 443 5 "bottom" -> "top"
. 1/27/98 cvw 443 11.14 "6.1" -> "8.2"
. 4/04/98 cvw 444 7 "Shuffing" -> "Shuffling"
. 3/23/98 mk 444 8-10 "single pass ... ." ->
"single pass of N/2 - 1 independent
compare exchange operatations: between
elements 2i-1 and 2i for i from 1 to N/2 - 1."
. 2/16/98 nz 447 4-5 1-2 -> 0-2 and 2-3 -> 1-3
. 3/17/98 rs 448 11.6 use example with 16 elements
. 1/27/98 cvw 448 11.3 emphasize assumption that N is a power of 2
. 1/27/98 cvw 455 -13 "of the cost" -> "the cost"
. 1/27/98 cvw 456 6 "on to" -> "onto"
. 3/23/98 mk 458 11.13 "4, 5, and 6" -> "0, 1, and 2"
. 3/23/98 mk 463 11.16 caption doesn't correspond to diagram
. 3/23/98 mk 463 6 description doesn't correspond to diagram
. 1/27/98 cvw 470 -4 "to if" -> "if"
. 2/09/98 rs 471 11.63 P -> M
. 1/27/98 cvw 488 17 "with huge" -> "with a huge"
. 1/21/98 ml 491 -1 "frequently frequently" -> "frequently"
. 1/27/98 cvw 495 9 exchange "red-black" and "randomized BST"
. 1/27/98 cvw 495 12.19 omit first "and"
. 5/09/98 cvw 496 12.26 "the your" -> "your"
. 1/27/98 cvw 500 16 "the the" -> "the"
. 5/11/98 lf 500 2 "10.3" -> "8.3"
. 11/16/98 kw 502 19 tree definition doesn't match Chapter 5
. 3/01/98 mk 503 12.7 semicolon missing after the N in STNode
. 1/14/98 rs 506 12.9 code uses NULL; commentary refers to z
. 1/27/98 cvw 507 12.7 "illustrate" -> "illustrated"
. 1/06/98 rs 507 12.47 change to refer to the top tree in Fig. 12.6.
. 1/16/98 jpl 513 12.10 (N < maxN) -> (N < maxN - 1)
. 1/27/98 cvw 514 -16 period missing
. 4/30/98 rs 509 12.8 search hit cost different from value in text
. 6/04/98 et 521 12.13 say that the recursive procedure
. returns the (k+1)st smallest element
. 4/15/98 pw 525 12.13 check h == z before accessing h->l->N
. 1/27/98 cvw 525 2 visit -> sort
. 1/27/98 cvw 525 -8 "count fields" -> "sum of the count fields"
. 4/14/98 pw 526 12.16 "STinsert" -> "insertT"
. 4/14/98 pw 530 3 linear for random BSTs, not worst case
. 1/27/98 cvw 532 8 "provide" -> "provides"
. 1/27/98 cvw 532 8 "an truly" -> "a truly"
. 5/13/98 rs 532 13.4 Wrong. Program uses (N lg N)/2 rotations for
degenerate tree.
. 1/25/98 jpl 534 13.2 bug in 2nd and 3rd trees (E to the right of F)
. 3/01/98 mk 536 13.3 "a->rec" -> "a->item"
. 11/16/98 rs 536 13.3 "STinsert" -> "insertR"
. 5/09/98 cvw 536 13.3 "This functions" -> "This function"
. 1/27/98 cvw 539 13.14 "mod" -> "%"
. 1/27/98 cvw 539 13.15 "mod" -> "%"
. 1/27/98 cvw 539 13.19 "mod" -> "%"
. 1/27/98 cvw 548 6 "is not be changed" -> "is not changed"
. 1/27/98 cvw 551 13.47 "following" -> "the following"
. 5/09/98 cvw 552 13.16 M needs a right link
. 5/09/98 cvw 555 -4 "same the" -> "the same"
. 5/11/98 lf 559 11 "develop symbol" -> "develop a symbol"
. 5/11/98 lf 561 13.72 "with standard" -> "and with standard"
+ 1/27/98 cvw 563 13.7 first statement of searchR should be
" if (t == z) return NULLitem; "
. 2/03/98 jpl 564 13.24 "j links" -> "j+1 links"
. 2/22/98 rr 564 13.8 last line: lgNmax -> lgNmax+1
. 2/19/98 rr 566 13.9 arg to STinsert should be "Item item"; v->item
. 2/03/98 jpl 566 13.25 7 -> 8
. 1/27/98 cvw 577 -15 "necessary" -> "necessarily"
6/04/98 et 580 1 mention concept of hash function as array of
random numbers
. 5/11/98 cvw 583 14.9 "than" -> "that"
. 1/27/98 cvw 586 -20 "that average" -> "that the average"
. 5/11/98 cvw 590 14.4 "a unoccupied" -> "an unoccupied"
. 5/11/98 lf 591 2 "12.5" -> "14.5"
. 4/30/98 rs 592 14.8 hash value for P should be 8
. 5/11/98 lf 594 -13 "with process" -> "with the process"
. 1/21/98 rs 595 -4 "has" -> "hash"
. 4/30/98 rs 596 -15 "need" -> "expect"
. 1/27/98 cvw 600 14.7 "N++ > M/2" -> "N++ >= M/2" (to match figure)
. 5/11/98 cvw 611 15.2 "new nodes" -> "new node"
. 5/11/98 cvw 612 15.3 last sentence incorrect; no I in 15.2
. 3/10/98 ho 612 15.3 node for key I is missing
. 3/10/98 st 612 -1 "based the" -> "based on the"
. 1/29/98 cvw 612 -16 "search" -> "search tree"
. 1/29/98 cvw 616 15.2 eliminate t to make last line in caption true
. 5/11/98 cvw 624 15.10 "1***1" -> "1***0"
. 1/29/98 cvw 624 15.10 "reference" -> "pointed to"
. 1/29/98 cvw 635 15.7 "keyType" -> "Key"; "itemType" -> "Item"
. 3/05/98 jb 635 15.7 delete "N++" in last line
. 1/29/98 cvw 639 15.8 remove item from node
. 1/29/98 cvw 656 -12 "informations" -> "information"
. 5/11/98 lf 660 -12 "proportional to be" -> "proportional to"
. 1/29/98 cvw 660 -15 "The" -> "the"
. 1/29/98 cvw 665 5 "of the method" -> "the method"
. 11/23/97 je 669 16.3 change for loop in line -3 of insertR to
for (i = (h->m)++; i > j; i--)
. 1/29/98 cvw 673 16 "is improves" -> "improves"
. 1/29/98 cvw 675 16.13 "tree on order" -> "tree of order"
. 1/29/98 cvw 678 -2 "out" -> "our"
. 1/29/98 cvw 680 6 "series on" -> "series of"
. 1/29/98 cvw 684 16.7 "h->m == M" -> "h->m == 0 || h->m == M"
delete if statement in while loop
6/09/98 ch 693 index First-class ADT "171" -> "166"
jb: J. Balducci
dc: D. Caldwell
vc: V. Chang
rc: R. Choy
dcl: D. Clark
je: J. Eggleston
kg: K. Gillett
ch: C. Heames
drh: D. Hanson
kh: K. Hirakawa
lf: L. Ferrier
pf: P. Fiddelaers
drh: D. Hanson
ah: A. Hopkins
mk: M. Kesden
dek: D. Knuth
jk: J. Kovacs
dl: D. Lennon
jl: J. Liao
jpl: J. Linderman
ml: M. Lindahl
mm: M. McKenna
dn: D. Nawi
pn: P. Nikolov
ho: H. Oki
rr: R. Roth
bs: B. Schreir
ars: A. Sedgewick
sm: R. Smaby
st: S. Tadlock
et: E. Tardos
gt: G. Tong
cvw: C. Van Wyk
jw: J. Werfel
mw: M. Winrock
jaw: J. Woldering
pw: P. Wong
nz: N. Zeilberger
.: change entered, will appear in next printing
x: no change, for some good reason
+: change in code, not tested yet
*: implies global change, may not be fixed soon
!: same error in Algs in C++