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"
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
.   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
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++


Errors in the first printing (fixed 11/18/97)