% CHANGES TO VOLUME 3 OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2011, 2012, ..., 2018, 2019 by Donald E. Knuth
% This file may be freely copied provided that no modifications are made.
% All other rights are reserved.
%
% Three levels of changes to the books are distinguished here:
%
% "\bugonpage" introduces the correction of an error;
% "\amendpage" introduces new material for future editions;
% "\improvepage" introduces ameliorations of lesser importance.
%
% (Changes introduced by \improvepage do not appear in the hardcopy listing.)
%
% Also, "\planforpage" introduces some of the author's half-baked intentions.
%
% NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE
% tex "\let\indexeject+ \input err3"
\newif\ifall % \alltrue means show the trivial items too
\relax % hook
\def\vertical{|}
\def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname}
\catcode`|=\active
\let|\inref \input \jobname.ref
\catcode`|=12
\input taocpmac % use the format for TAOCP, with modifications below
\def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change
\def\bugonpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin
{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\amendpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\iftrue\noindent}
\def\improvepage#1.#2 #3 (#4) {\ifall
\medbreak\ninepoint
\line{\kern-6pt{\sl Page #2\enspace #3\/}
\leaders\hrule\hfill\ \eightrm\date#4.}
\nobreak\smallskip\noindent}
\def\planforpage#1.#2 #3 (#4) {
\medbreak\defaultpointsize
\line{\kern-5pt{\bf Page #2}\enspace #3
\leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.}
\nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent}
\let\endchange=\fi
\def\nl{\par\noindent}
\def\nlh{\par\noindent\hangit}
\def\hangit{\hangindent2em}
\def\cutpar{{\parfillskip=0pt\par}}
\def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy"
#3
\ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or
Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
\ \ifnum #1<97 \hundred#1\else19#1\fi}
\def\hundred{20} % the "century" for dates before '97
\def\ex #1. [#2]{\ninepoint
\textindent{\bf#1.}[{\it#2\/}]\kern6pt}
\def\EX #1. [#2]{\ninepoint
\textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt}
\def\foottext#1{\medskip
\hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint
\smallskip\textindent{#1}}
\def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill
\titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}}
\def\refin#1 {\let|\inref \input #1.ref \let|\crossref}
\let\defaultpointsize=\tenpoint
%%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{INTRODUCTION}
\let\rhead=\lhead
\titlepage
\volheadline{THE ART OF COMPUTER PROGRAMMING}
\bigskip
\volheadline{ERRATA TO VOLUME 3 (after 2010)}
\bigskip
\noindent This document is a transcript of the notes that I have been making
in my personal copy of {\sl The Art of Computer Programming}, Volume~3 (second
edition, 27th printing) since it was first printed in 2011.
Previous errata are recorded in another file `{\tt all3-pre.ps}'.
\ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,''
and ``improvements''\dash---appear, indicated by four
\else Three levels of updates\dash---``errors,'' ``amendments,'' and
``plans''\dash---appear, indicated by three \fi
different typographic conventions:
\begingroup\def\hundred{17}
\bugonpage 0.666 line 1 (76.07.04)
Technical or typographical errors (aka bugs) are the most critical items, so
they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page
number. The date on which I first was told about the bug is shown; this is the
effective date on which I paid the finder's fee. The necessary
corrections are indicated in
a straightforward way. If,~for example, the book says
`$n$' where it should have said `$n+1$', the change is shown thus:
\smallskip
$n$ \becomes $n+1$
\endchange
\amendpage 0.666 line 2 (89.07.14)
Amendments to the text appear in the same format as bugs, but without
the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known
about or thought of when I wrote the original text, so I added them later.
The date is the date I drafted the new text.
\endchange
\def\hundred{19}
\planforpage 0.666 line 3 (17.11.20)
Plans for the future represent a third kind of item. In such notes I~sketched
my intentions about things that I wasn't ready to flesh out further when
I~wrote them down. You can identify these items because they're written in
slanted type, and preceded by a bunch of dots
`\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on
which I recorded the plan in my files.
\endchange
\improvepage 0.666 line 4 (38.01.10)
The fourth and final category\dash---indicated by page and line number in
smaller, slanted type\dash---consists of minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
You wouldn't even
be seeing these items if you hadn't specifically chosen to print the complete
errata list in all its gory details.
Are you sure you wanted to do that?
\endchange
\endgroup
\ifall\else\medskip\ninepoint
My personal file of updates also includes a fourth category of items, not
shown in this list. They are miscellaneous minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
If you really want to see all of the gory details,
you can download the full list from Internet webpage
$$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$
by selecting the ``long form'' of the errata.
\fi
\medskip
\tenpoint
My shelves at home are
bursting with preprints and reprints of significant research results that I
want to digest and summarize, where appropriate, in the ultimate edition of
Volume~3. I didn't do that in the second edition because I would surely have to do
it over again later: New results continue to pour forth at a great rate, and I
will have time to rewrite that volume only~once. Volumes 4 and~5 need to be
finished first. So I've put most of my effort so far into writing up
those parts of the total picture that seem to have converged to their
near-final form. It follows, somewhat paradoxically, that the updates in this
document are most current in the areas where there has been least activity.
On the other hand I do believe that the changes listed here bring Volume~3
completely up to date in two respects: (1)~All of the research problems in the
previous edition\dash---i.e., all exercises that were rated 46 and
above\dash---have received new ratings of 45 or less whenever I learned of a
solution; and in such cases, the answer now refers to that solution.
(2)~All of the historical information about pioneering developments has been
amended whenever new details have come to my attention.
\beginconstruction
The ultimate, glorious, 100\% perfect editions of Volumes 1--4A are works in progress.
Please let me know of any improvements that you think I ought to make.
Send your comments either by snail mail to D.~E. Knuth, Computer
Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045,
or by email to
{\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions
only, please\dash---all
other correspondence is returned unread to the sender, or discarded,
because I have no time to
read ordinary email.) Although I'm working full time on
Volume~4B these days, I~will try to reply to all such messages
within a year of receipt. Current news about {\sl The Art of Computer
Programming\/} is posted on
$$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$
and updated regularly.
\par\endconstruction
\rightline{\dash---Don Knuth, February 1998}
\bigskip
\bigskip
{\quoteformat
Writing a series like {\rm The Art of Computer Programming}
is similar to painting the Forth Rail Bridge.
No sooner is it finished than
the job must be started again.
\author MALCOLM CLARK (1992)
% A plain TeX primer, Oxford University Press, page 7
\bigskip\bigskip
The time when\/ {\rm The Guardian} ceases to make mistakes altogether
is not, at the moment, foreseeable.
\author IAN MAYES (1998)
% quoted in IHT, 17 Feb 98, p5
% he is Reader's Editor of the Manchester Guardian
\vfill\eject
}
\def\today{\number\day\space\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\year}
%%%%%%%%%%%%%%% CHANGES FOR VOLUME 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\lhead{CHANGES TO VOLUME 3: SORTING AND SEARCHING}
\let\rhead=\lhead
\titlepage
\volheadline{SORTING AND SEARCHING}
\bigskip
\rightline{Copyright \copyright\ 2011, 2012, 2013, 2014, 2015, 2016, 2017
Addison\with Wesley}
\rightline{Last updated \today}
\bigskip
\rightline{\sl Most of these corrections have already been made in
recent printings.}
\smallskip
\let\defaultpointsize=\tenpoint
\bugonpage 3.0 (on the back page of the dustcover, line 23) (12.09.10)
{\eightss Whatever your backgound, \becomes Whatever your background,}
\endchange
\improvepage 3.vii line 6 before the author's signature (15.09.23)
nobody noticed \becomes nobody else noticed
\endchange
\amendpage 3.x line 16 (11.06.16)
a {\it 45\/} rating \becomes
a {\it 40\/} rating
\endchange
\amendpage 3.x line 20 (13.01.30)
creativity.\ \becomes
creativity. All exercises with ratings of {\it46\/} or more are open problems
for future research, rated according to the number of
different attacks that they've resisted so far.
\endchange
\bugonpage 3.xii line 8 (12.04.04)
\ninepoint Internal sorting \becomes Internal Sorting
\endchange
\amendpage 3.34 in exercise 22 (12.04.13)
\ninepoint
line 6: $0^k$ \becomes $0^p$ (twice)\nl
line 6: $k\ge0$ \becomes $p\ge0$\vadjust{\smallskip}\nl
line $-3$: $\displaystyle \sum_{k\ge0}{k!^2(n_{\le t}-k)!\,(n_{>t}-k)!\over
n_1!\ldots n_m!}$ \becomes
$\displaystyle \sum_{p\ge0}{p!^2(n_{\le t}-p)!\,(n_{>t}-p)!\over
n_1!\ldots n_m!}$\nl
line $-1$: $p_{\le t}=p_{>t}=k$ \becomes
$p_{\le t}=p_{>t}=p$
\endchange
\improvepage 3.42 lines $-9$ and $-8$ (19.04.20)
Simon Newcomb's problem \dots~a multiset. \becomes
Thus Simon Newcomb's problem was to find the probability
distribution of runs in a random permutation of a certain multiset.
\endchange
\bugonpage 3.50 line 12 (19.04.21)
current values of $j$, $x_i$, \becomes
current values of $i$, $j$, $x_i$,
\endchange
\improvepage 3.86 line 12 (15.03.07)
$h_{t-2}$ sorting \becomes $h_{t-2}$-sorting
\endchange
\bugonpage 3.88 line 3 (15.03.07)
$0.15n^{3/2}\!@$ \becomes $0.16n^{3/2}\!@$
\endchange
\improvepage 3.96 steps L3 and L4 (15.03.10)
record $R$ \becomes record $R_j$ \quad(twice)
\endchange
\bugonpage 3.102 last line of exercise 6 (15.03.06)
\ninepoint for $N+1$ records \becomes for $N$ records
\endchange
\bugonpage 3.111 in Fig.~17 on the arrow $\rm M3\to M4$ (12.06.07)
\ninepoint $i\land p=r$ \becomes $i\band p=r$
\endchange
\amendpage 3.129 line $-5$ (11.07.16)
used before \becomes used at the end of Section 5.1.4
\endchange
\amendpage 3.133 the line following {\eq(48)} (11.11.05)
ignore $\delta(n)$ \becomes ignore the ``wobbles'' of $\delta(n)$
\endchange
\improvepage 3.136 in exercise 35 (15.04.22)
\ninepoint frequencies \becomes quantities
\endchange
\bugonpage 3.137 in exercise 49 (15.04.23)
\ninepoint \eq(47) \becomes \eq(50)
\endchange
\bugonpage 3.174 line {\it20\/} of the {\tt MIX} program (12.02.04)
\ninepoint To R3 if end of pass. \becomes To R3 if not end of pass.
\endchange
\improvepage 3.202 improvement to proof of Theorem K (15.05.16)
Line 3: large. We \becomes large. Let $d$ be 2, 3, or 4. We\nl
Line 6: on $d$, for $d\le4$. \becomes on $d$.\nl
Line 8: on $n$. \becomes on $n$. The upper bound follows from \eq(4) and \eq(8).
\endchange
\bugonpage 3.202 line $-16$ (11.05.16)
F. Hwang \becomes F. K. Hwang
\endchange
\bugonpage 3.205 line 1 of exercise 11 (11.05.16)
\ninepoint F. Hwang \becomes F. K. Hwang
\endchange
\improvepage 3.210 in {\eq(6)} (13.01.20)
$n\ge t$ \becomes $1\le t \le n$
\endchange
\amendpage 3.213 line 2 before {\eq(14)} (13.10.08)
Improved. \becomes Then Kirkpatrick discovered that $V_3(42)=50$; this may
well be the only other counterexample
[see {\sl Lecture Notes in Comp.\ Sci.\ \bf8066} (2013), 61--76].
Improved
\endchange
\improvepage 3.216 line 3 before the exercises (15.05.16)
$\Theta\bigl(\lg\bigl(n!/T(G)\bigr)+n-k\bigr)$ \becomes
$\Theta\bigl(\log\bigl(n!/T(G)\bigr)+n-k\bigr)$
\endchange
\amendpage 3.226 lines 5 and 6 after {\eq(11)} (16.08.12)
172]; the values of $\hat S(n)$ for $n>8$ are still \becomes
172]; M.~Codish, L.~Cruz-Filipe, M.~Frank, and P.~Schneider-Kamp
[{\sl Journal of Computer and System Sciences\/ \bf82}
(2016), 551--563]
have also verified this when $n\le10$.
The remaining values of $\hat S(n)$ are still
\endchange
\amendpage 3.229 line $-5$ (13.11.16)
For $n\le 10$ \dots (see exercise 4). \becomes
In fact all of the values given here are known to be exact (see the
answer to exercise~4).
\endchange
\amendpage 3.234 lines 6 and 7 before the exercises (14.11.30)
Andrew Yao \dots\ as $n\to\infty$; \becomes
Andrew Yao [{\sl SICOMP\/ \bf9} (1980), 566--582]
determined the asymptotic behavior of $\hat U_t(n)$ for fixed $t$, by
showing that $\hat U_3(n)=2n+\lg n+O(1)$ and $\hat U_t(n)=
n\bigl\lceil@\lg(t+1)\bigr\rceil +O\bigl((\log n)^{\lfloor\lg((t+1)/3)
\rfloor}\bigr)$ as $n\to \infty $;
\endchange
\improvepage 3.240 line 4 of exercise 37 (19.04.21)
\ninepoint performed alternatively \becomes performed in alternation
\endchange
\amendpage 3.241 exercise 44 (14.11.30)
\ninepoint some $n>8$ \becomes some $n>10$
\endchange
\amendpage 3.242 last line of exercise 52 (15.04.08)
\ninepoint co-NP-complete \becomes coNP-complete
\endchange
\improvepage 3.253 new sentence at end of the caption for Fig.~62 (13.01.20)
\ninepoint There are $P=12$ external nodes.
\endchange
\improvepage 3.253 lines 1 and 2 after the caption for Fig.~62 (19.04.20)
consists of replacing \dots, and changing \becomes
replaces \dots, and changes
\endchange
\improvepage 3.261 line $-2$ and page 262 line 1 (13.01.20)
$X$ \becomes $K$\qquad[6 times]
\endchange
\bugonpage 3.264 line 2 of exercise 17 (13.01.20)
$K_1\ge K_2\ge \cdots \ge K_N$ \becomes $K_1>K_2>\cdots>K_N$
\endchange
\improvepage 3.268 line 8 (15.06.15)
[insert a dash as the Contents of T3 in Phase 1]
\endchange
\amendpage 3.297 line 13 (16.06.07)
(see exercise 6). \becomes
(see exercise 6). Jost B\"urgi had~already discovered very similar ideas
before 1592;
see M.~Folkerts, D.~Launert, and A.~Thom, {\sl Historia
Mathematica\/ \bf43} (2016), 133--147.
\endchange
\improvepage 3.305 lines $-2$ and $-1$ (19.04.20)
Step number $i$ \dots, and changing \becomes
Then, at step number $i$ in the tree's growth, choose distinct tape names
$B$, $B_1$, $B_2$, \dots, $B_k$, and change
\endchange
\bugonpage 3.315 bottom line [but only in 17th--28th printings!] (11.03.27)
instead of as a \becomes instead of as
\endchange
\improvepage 3.330 line 6 after the caption to {Fig.\ 85} (15.08.19)
Figs.\ 70, 74, \becomes Figs.\ 70, 72, 74,
\endchange
\improvepage 3.339 line 12 (15.08.26)
numbers with the most significant fields at \becomes
numbers in a year-month-day format, so that the most significant fields are at
\endchange
\improvepage 3.344 line $-4$ (19.04.20)
consists of reading from tape $D$ and writing \becomes
reads from tape $D$, and it writes
\endchange
\amendpage 3.381 line $-10$ (16.12.29)
combining one or more \becomes combining two or more
\endchange
\amendpage 3.382 in footnote d to Table 5.5--1 (14.09.16)
\eightpoint
5.2.1--29. \becomes
5.2.1--29; $N^{7/6}$ is not rigorous.
\endchange
\bugonpage 3.392 line $-8$ (18.11.12)
sometime desirable \becomes sometimes desirable
\endchange
\amendpage 3.411 line {\it 07\/} of Program B (14.12.15)
\ninepoint $\rA\gets l+u$. \becomes
$\rA\gets l+u$. (Overflow cannot occur.)
\endchange
\bugonpage 3.422 line 25 (17.01.05)
$n$ is extremely large \becomes
$N$ is extremely large
\endchange
\bugonpage 3.423 line 2 of exercise 8 (12.03.27)
\ninepoint $\sum_{j=0}^{\lfloor\lg N\?\?\rfloor +2}$ \becomes
$\sum_{j=1}^{\lfloor\lg N\?\?\rfloor +2}$
\endchange
\bugonpage 3.426 line 6 of exercise 28 (12.10.30)
\ninepoint
$\bigl((x*x)*x\bigr)*\bigl((x*x)*x\bigr)$ \becomes
$\bigl(x*(x*x)\bigr)*\bigl(x*(x*x)\bigr)$
\endchange
\improvepage 3.432 line 11 (15.07.20)
$\.Q\equiv \.{LLINK(P)}$ or $\.{RLINK(P)}$ \becomes
$\.Q\equiv \.{LLINK(P)}$ or $\.Q\equiv\.{RLINK(P)}$
\endchange
\improvepage 3.443 line 6 (16.05.05)
$x\lg(1/x)$ is concave; \becomes
$x\lg(1/x)$ is concave, when $x>0$;
\endchange
\improvepage 3.464 line 16 (16.04.03)
$C\log N$ \becomes $C\lg N$
\endchange
\improvepage 3.489 line 21 (16.04.04)
$\ln2=69.3$ \becomes $\ln2$; that's about 69.3
\endchange
\improvepage 3.513 line $-14$ (12.07.12)
Section 2.3 \becomes Section II.3
\endchange
\amendpage 3.518 line 5 (17.08.30)
long ago by botanists \becomes long ago by
\endchange
\improvepage 3.534 line 4 (14.10.01)
or if \becomes or
\endchange
\amendpage 3.570 line $-1$ (17.12.28)
Superimposed coding \becomes Superimposed random coding
\endchange
\amendpage 3.571 line 8 (17.12.28)
32. \becomes 32; {\sl U.S. Patent 3521034\/} (1970).
\endchange
\amendpage 3.571 line 9 (17.12.28)
superimposed coding \becomes superimposed random coding
\endchange
\bugonpage 3.573 line $-16$ (16.04.21)
$286/8008\approx 3.5$ percent \becomes
$286/8008\approx 3.6$ percent
\endchange
\bugonpage 3.585 line 10 (19.02.17)
{\sl Information and Control\/ \bf63} \becomes
{\sl Information and Control\/ \bf64}
\endchange
\let\defaultpointsize=\ninepoint % get ready for answer pages
\amendpage 3.589 lines 10 and 11 of answer 19 (15.05.16)
suggested by Jiang Ling \becomes suggested by Ling Jiang
\endchange
\improvepage 3.593 lines 2--4 (19.03.21)
respective vectors \dots~as the difference \becomes\nl
respective vectors
$(1,1,0)$,
$(1,0,1)$,
$(0,-1,1)$,
$(0,1,1)$,
$(-1,0,1)$,
$(-1,1,0)$,
divided by $\sqrt2$,
stand for adjacent interchanges of the respective pairs
21, 31, 32, 41, 42, 43.
The sum of these vectors gives
$(0,2,4)/\sqrt2$ as the difference
\endchange
\bugonpage 3.595 line 2 of answer 23 (19.03.31)
$1+2k_2$ \becomes $1+2k_4$
\endchange
\improvepage 3.597 line 2 of answer 28 (15.10.5)
hence td \becomes hence we have total displacement td
\endchange
\amendpage 3.598 line 12 of answer 10 (12.04.13)
for some $k>1$ \becomes for some smallest $k>1$
\endchange
\improvepage 3.600 in answer 18 (15.10.10)
giving all elements \becomes giving each of the $n_j$ elements
\endchange
\amendpage 3.601 in answer 22 (12.04.13)
line 1: $0^k$ \becomes $0^p$\nl
line 1: for some $k$ \becomes for some $p$\nl
line 3: the number $k$ \becomes the number $p$\nl
line $-4$: $0^k$ \becomes $0^p$\nl
line $-3$: $k!\,(n_1+\cdots+n_t-k)!$ \becomes
$p!\,(n_1+\cdots+n_t-p)!$\nl
line $-3$: $\scriptstyle p_1+\cdots+p_t=k$ \becomes
$\scriptstyle p_1+\cdots+p_t=p$\nl
line $-2$: $k=0$ \becomes $p=0$
\endchange
\amendpage 3.610 line 1 of answer 23 (12.07.28)
{\sl Journal\/} \becomes
{\sl Comptes Rendus Acad.\ Sci.\ \bf88}
(Paris, 1879), 965--967; {\sl Journal\/}
\endchange
\amendpage 3.614 new sentenced appended to answer 40 (14.04.06)
See also Dan Romik, {\sl The Surprising Mathematics of
Longest Increasing Subsequences\/} (2014), Chapter~4.
\endchange
\improvepage 3.620 in answer 10 (13.04.29)
line 2 after the program: time savings \becomes time saved\nl
lines 5--6 after the program: not desirable \dots unless \becomes
usually
insignificant, since only $O(\log N)$ time is saved in that case
unless
\endchange
\bugonpage 3.621 replacement for line 7 of answer 16 (10.09.17)
\noindent$$a_{i+jh}=1+q(h-i)+(r-i)@\[i\le r]+j\qquad
\hbox{for $1\le i\le h$ and $j\ge0$}$$
\endchange
\bugonpage 3.629 line {\it23} of the program in answer 12 (12.06.06)
\.{J4N} \.{4B} \ \becomes \ \.{J4N} \.{8B}
\endchange
\improvepage 3.631 line 6 of answer 18 (16.03.11)
line 6: ``$\le$,'' \becomes ``$\le$'',
\endchange
\bugonpage 3.632 line 1 (16.04.20)
M. Regnier \becomes M.~R\'egnier
\endchange
\bugonpage 3.642 line 6 of answer 16 (16.03.18)
step 4 \becomes step I4
\endchange
\bugonpage 3.644 line 2 of answer 28 (15.04.24)
$21{2\over 3}N\log N$ \becomes $21{2\over 3}N\log_3N$
\endchange
\bugonpage 3.660 line 9 of answer 23 (11.02.26)
$x_{11}\gets 1$ \becomes $x_{11}\gets 0$
\endchange
\bugonpage 3.664 line 9 (16.03.31)
the first $t-1$ steps \becomes steps 1, 2, \dots, $t-1$
\endchange
Thus the first $t-1$ steps make at most $(t-1)(k-1)+1$ comparisons
\amendpage 3.666 last three lines of answer 4 (13.11.16)
Ian Parberry \dots 116. \becomes
Further values have been obtained by D. Bundala and J.~Z\'avodn\'y
via satisfiability encoding (see Section 7.2.2.2). The value of $\hat T(17)$
remains unknown.
\endchange
\improvepage 3.667 line 7 of answer 13 (19.04.21)
alternatively \becomes alternately
\endchange
\bugonpage 3.668 line 2 of answer 24 (14.11.30)
by exercise 21 \becomes by exercise 22(a)
\endchange
\amendpage 3.669 line $-3$ of answer 27 (11.12.18)
103--115. The fact \becomes 103--115; see also
B.~E. Tenner, {\sl Annals of Combinatorics\/ \bf11} (2007), 101--114.
The fact
\endchange
\amendpage 3.669 append to the end of answer 32 (15.12.16)
[{\sl Princeton Conference on Information Sciences and Systems\/ \bf6}
(1972), 387--391.]
\endchange
\improvepage 3.669 line $-3$ of answer 35 (16.04.02)
strike out \becomes remove
\endchange
\bugonpage 3.670 replacement for line 11 of answer 38 (19.01.10)
$$P=\vcenter{\offinterlineskip\halign{&\cell{#}\cr
1&2&3&4&5\cr
2&3&4&5\cr
3&4&5\cr
4&5\cr
5\cr}}\ ,\qquad
Q=\vcenter{\offinterlineskip\halign{&\cell{#}\cr
1&3&5&7&13\cr
2&6&8&15\cr
4&9&12\cr
10&11\cr
14\cr}}\ .$$
\endchange
\amendpage 3.677 line 2 of answer 11 (13.01.20)
sequence. \becomes
sequence; hence the probability is 1/2, given that $\.{LASTKEY}\ne\infty$.
\endchange
\bugonpage 3.681 replacement for first two lines of answer 7 (18.05.28)
\ans7. Let $\alpha_p=2x$ and $z=-1/2^{p+1}$. Then $x^{p+1}=x^p+z$; so
exercise 1.2.6--25 gives the convergent series
$\alpha_p=2\sum_{k\ge0}{1-kp\choose k}z^k\!/(1-kp)=2-2^{-p}-p@2^{-2p-1}
+O(p^22^{-3p})$.
\endchange
\bugonpage 3.687 last line of answer 7 (13.06.02)
polyphase's 176 \becomes polyphase's 180
\endchange
\bugonpage 3.723 line 3 of answer 10 (16.05.15)
$K$ is one less \becomes $k$ is one less
\endchange
\bugonpage 3.730 line 2 of step A7 (12.10.02)
\.{TABLE[$i$]} \becomes \.{TABLE[$j$]}
\endchange
\bugonpage 3.732 line 7 of answer 30 (16.04.16)
$q_{j-k-1}%% Unicode char "6797
\GC75:73:-2:60% G5011
<0007000000000000000000078000000e000070000007f800001f0000fc000007f800001f%
8001fe000007f000003fdfffff000007e00fffffdfffff000007e007ffff8ffffc000007%
e003c01f8100f8000007e000001f8700f8000007e038701f87c0f8001807e07e781f83e0%
f8000c07e07e3e1f83e0f8000e07e07c3f1f81f0f8000707e0fc3f1f81f0f8000787e0f8%
1f1f80f0f80003c7e1f01f1f80f0f80003c7e1f00f1f80f0f80003e7e3e00f1f80c0f800%
03e7e3c0073f8007f80001e7e7c000ff803ff80001e7e78001ff83fff80001e7ef000fdf%
9ffef80001e7ff003f9ffffcf80001e7fe0fff1fbff0f80001c7fc0ffc1f9fc0f80001c7%
f807f81f8f00fc000087f003e01f8400fc000007e07181df7000fc000007e0f803fff800%
f8000007e1fe03f87e00f8000007e3ff03f83f000000ffffffff87f81f8000007fffffff%
87f80f8070003ffc7c0007e00fc1f800007c7c000fc007c3fc00007c7c000f8007c7fc00%
003e7c001ffffffffe00003e7c001fffffffff00003e7c003fffffffff80003e7c003e00%
7e000000003e7c007e007e000000003e7c007e007e000000003e7c00fe007e038000007e%
7c00fe007e07c000007e7c01fe007e0fe000007c7c03be007e1ff000007c7c07bfffffff%
f800007c7c1f3ffffffffc00007c7c3e3ffffffffc00007c7c7c3e007e000000007c7cfe%
3e007e00000000787cee3e007e03800000f87c9e3e007e07c00000f87c3e3e007e07e000%
00f87c7c3e007e0ff00000f07cf03e007e1ff80000f07df03ffffffffc0000f07de03fff%
fffffc0001f07fe03e007e00000001e07fc03e007e00000003e07f803e007e00000003c0%
7f803e007e00000007c07f003e007e001c000783ff003e007e003e000f81fe003e007e00%
7f800f00fc003e007e00ffc01e0078003fffffffffe03c0038003fffffffffe038001000%
3fffffffffe0700000007e0000000000600000007e0000000000200000007e0000000000%
000000007e0000000000>%% Unicode char "8000
\Uni1.08:24:24:-1:20% Unicode char "71ca
<011c380318600718c00e350004630001c1f00700e000000026326366666666c66c4d04d019819830e60ec05804001806ffffff007c0000db000198c00718701c183fe0180e001800>%
), 520, 567, 578. % 33rd
Mahon, Maurice Hartland (= Magenta), xi. % 33rd
Mankin, Efrem Seymour, 698. % 33rd
Monge, Gaspard, inequality, \see Quadrangle inequality. % 36th
Neumann, John von (= Neumann J\'anos Lajos = Margittai Neumann J\'anos), 8, 159, 385. % 33rd
Odell, Margaret King, 394. % 32nd
Olson, Charles Arthur, 544. % 30th
Pareto, Vilfredo Federico Damaso (= Wilfried Fritz), 401. % 36th
Patents, vi, 225, 231, 244, 255, 312, 315--316, 369, 384--385, 394, 571, 675, 729. % 36th
Pittel, Boris Gershon ({\rus Pittelp1, Boris Gersonovich}), 713, 721, 728, 734. % 34th
Residue theorem, 131--133, 138, 603, 637. % 35th
Romik, Dan ({\heb\Hqq/\Hyy/\Hmm/\Hvv/\Hrr/ \Hfn/\Hdd/}), 614. % 32nd
Satisfiability, 242, 666. % 31st
Schneider-Kamp, Peter Jan (=~Jan~Peter), 226. % 32nd
Sch\"utzenberger, Marcel-Paul, 17, 21, 39, 55, 57--58, 66, 68, 70, 670. % 33rd
Selection of $t@$th largest, 136, 207--219, 472. % 36th
\sub networks for, 234, 238. % 36th
Steinhaus, W{\l}adys{\l}aw Hugo Dyonizy, 186, 209, 422, 518. % 34th
Submultisets, 744. % 36th
Thom, Andreas Berthold, 297. % 33rd
Uzgalis, Robert Charles, 482, 490. % 30th
Variance, different notions of, 709, 735, 742. %30th
von Neumann, John (= Neumann J\'anos Lajos = Margittai Neumann J\'anos), 8, 159, 385. % 33rd
Williams, Francis Aloysius, Jr\period, 521. % 33rd
Wobbles, 133, 636, 727. % 29th
Z\'avodn\'y, Jakub, 666. % 31st
Zeckendorf, \smash{\'E}douard, 681. % 34th
\vfill
\enddoublecolumns
\endchange
\bye
[The next printing will be the 37th.]
not mentioned above:
ARTICLES "TO APPEAR" THAT ARE STILL PENDING: