% CHANGES TO VOLUME 3 OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2022,2023,2024 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 2021)}
\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, 45th printing) since it was first printed in 2022.
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 2022}
\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\ 2022, 2023, 2024
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
\improvepage 3.46 replacement for Fig.~4 (24.09.22)
\noindent$$\epsfbox{\figdir/levy.471}$$
\endchange
\bugonpage 3.93 in Table 5 for increments `4 2 1' (23.03.15)
$274.42u$ \becomes $274.41u$
\endchange
\bugonpage 3.95 lines $-5$ and $-4$ (23.03.12)
using the quantity $\lfloor2.25h_s\rfloor$ in place of
$3h_s$ in~\eq(12); \becomes\nl
using the formula $h_s=\smash{\bigl\lfloor{4\over5}
\bigl({9\over4}^{s+\?1}-\nobreak1\bigr)\bigr\rfloor}$;
\endchange
\amendpage 3.179 new quotation for middle of page (23.06.21)
{\quoteformat
% [Porro] methodus quia quis brevissamo tempore & ordine optimo
% indicca conficiat, huiusmodi est.
To do this most quickly and arranged optimally, use this method.
% Quaecunque in indicem referre libuerit,
Write down whatever is to appear in the index,
% omnia ut primum se obtulerint,
% nulla ordinis ratione habita in charta describantur,
as soon as it presents itself, without any regard for order,
% ab altera tantum facie, ut altera nuda relinquatur. ...
using one side of a sheet of paper, leaving the other side blank. .\thinspace.\thinspace.
% [Tandem] omnia descripta forfice dissecabis,
Cut everything into pieces with scissors, and divide the slips
% dissecta quo volueris ordine divides,
into the desired order, first into large parts,
% primum in maiores partes, deinde subdivides semel aut iterum,
% vel quotiescunque opus fuerit. ...
then subdividing once or twice, or as often as needed. .\thinspace.\thinspace.
% Ubi plurimae schedulae fuerint, saepius subdividere suaserim:
If there are many slips, I recommend subdividing more often:
% sic enim omnia facilius et minori confusione peragentur, ...
all will then be easier to sort, with less confusion.
\author CONRAD GESSNER, {\sl Pandect\ae\/} (1548)
% right column of folio 19v, near the beginning of volume one
% found at MDZ, M\"unchener DigitaliserungsZentrum
% www.digitale-sammlungen.de/en/view/bsb10145114?page=64,65
}
\endchange
\amendpage 3.192 line 16 (22.08.12)
{\sl Vychisl.\ Matem.\ i Matem.\ Fiziki\/ \bf 62} \becomes
{\sl Vychisl.\ Matem.\ i Matem.\ Fiziki\/ \bf 61}
\endchange
\amendpage 3.197 new exercise (23.12.20)
\ninepoint\ex 37. [\HM39] (R. P. Stanley, 1981.) Let $A(G)$ be the $n\times n$
matrix for the graph~$G$ that's defined after~\eq(33). Prove that
$A_{ik}^2\ge A_{i(k-1)}A_{i(k+1)}$, for $1\le i\le n$ and $10$.
\endchange
\improvepage 3.493 and page 494 in lines 05, 06, 08 of Program P (24.09.30)
\ninepoint \.Q \becomes \.X
\endchange
\bugonpage 3.518 line 12 (22.11.01)
461--471 \becomes 461--472
\endchange
\amendpage 3.534 line 2 (22.02.06)
the algorithm terminates. \becomes
set $N\gets N-1$ and terminate the algorithm.
\endchange
\let\defaultpointsize=\ninepoint % get ready for answer pages
\amendpage 3.584 new answer for Notes on the Exercises (23.11.24)
\ans2. They often extend the material that's in the main text.
\endchange
\improvepage 3.594 amplify line 10 of answer 16 (24.09.26)
\indent We get further insights from $q$-generalizations of factorials
and exponentials. Let
$$n!_q=\prod_{k=1}^n(1+q+\cdots+q^{k-1});\qquad\qquad
\exp_q(z)=\sum_{n=0}^\infty {z^n\over n!_q}.$$
\endchange
\improvepage 3.595 and top of page 596 (24.09.22)
[remove the paragraph `This exercise \dots\ \S7.]'
\endchange
\improvepage 3.610 first two lines of answer 22 (24.09.22)
Assume that \dots\ answer is \becomes
The number of ways is clearly zero if $m>N$ and $n_m>0$. Otherwise we can
assume that $m=N$, by adding $0@$s to the shape if necessary. Then the answer is
\endchange
\bugonpage 3.612 line $-5$ of answer 33 (22.11.10)
40--70 \becomes 49--70
\endchange
\amendpage 3.615 line $-2$ of answer 45 (22.11.10)
{\bf A114} (2007) \becomes
{\bf A114} (2007), 211--234
\endchange
\bugonpage 3.618 correction to the Algorithm D$'$ of 21 December 2019 (24.09.03)
Otherwise if $\.{COUNT[$K_r$]}=r$, set $\.{COUNT[$K_r$]}\gets r$ \becomes
Otherwise if $\.{COUNT[$K_r$]}=r$, set $\.{COUNT[$K_r$]}\gets r-1$
\endchange
\bugonpage 3.642 in answer 16 (22.05.22)
line 7: $A_n=\lfloor\lg n\rfloor/n+$ \becomes
$A_1=0$ and $A_n=\lfloor\lg n\rfloor/n+$\nl
line 9: $(2^{l+1}-2)$ \becomes $(2^{l+1}-l-2)$
\endchange
\improvepage 3.649 line $-10$ of answer 18 (24.09.22)
Since no element \becomes Since no key
\endchange
\improvepage 3.657 line 2 of answer 28 (23.11.11)
optimal \becomes optimum
\endchange
\bugonpage 3.657 replacement for lines 4 and following of answer 31 (23.11.12)
\noindent
sorted in 3 more comparison-exchange operations. On the other
hand the following tree, constructed by Filip Stappers in 2023,
achieves the desired bound (and perhaps also
the minimum {\it average\/} number of comparison-exchanges,
namely $840/120=7$):\par
\nobreak\smallskip\line{\enspace\epsfbox{\figdir/v3.6310}\hfil
\vbox{\hbox{\vtop{\kern0pt\epsfbox{\figdir/v3.6311}}\kern-6pt
\vtop{\kern0pt\epsfbox{\figdir/v3.6312}} \
\vtop{\kern0pt\epsfbox{\figdir/v3.6313}}}\kern0pt}\enspace}
\endchange
\amendpage 3.657 new answer (23.11.11)
\ans32. Filip Stappers has shown that $S_e(n)=S(n)$ for $n=6$ and $n=7$.
\endchange
\amendpage 3.658 new answer (23.12.20)
\ans37. [The rows of $A(G)$ are said to be ``log-concave.''
An algebraic proof appears in
{\sl J.~Combinatorial Theory\/ \bf A31} (1981), 56--65;
no purely combinatorial proof is known.]
% scc to Igor Pak, see SIDM 37(2023)1877, conjecture 9.4
\endchange
\bugonpage 3.659 in answer 12 (23.05.01)
line 2: $\beta:X_{n-k}$ \becomes $\beta:X_{n+1-k}$ \nl
line 4: $Y_r=X_{r-k}$ \becomes $Y_r=X_{r+k}$
\endchange
\bugonpage 3.660 new answer {(and remove this citation from answer 22)} (23.03.21)
\ans18. See \v{L}.~Koll\'ar, {\sl Computers and Artificial
Intelligence\/ \bf5} (1986), 335--344.
\endchange
\bugonpage 3.711 replacement for answer 29 (23.11.11)
\ans29. It is a degenerate tree (see exercise 5) with \.{THIS} at the
top, \.{THE} at the bottom, needing 22.907 comparisons for an
average successful search.
\par
Douglas A.\ Hamilton has proved that some degenerate tree is always worst.
There\-fore, by exercise 6.1--14,
we can find pessimal binary search trees in $O(n\log n)$ steps.\tighten
\endchange
\amendpage 3.713 line 8 of answer 44 (24.09.30)
The variable $j$ \becomes Optionally, also set $\.{WT(X$_j$)}\gets
\.{WT(LLINK(X$_j$))}+
\.{WT(RLINK(X$_j$))}$.
The variable~$j$
\endchange
\bugonpage 3.719 in answers 1 and 2 (23.05.01)
{\fiverm 223 \becomes 233} (in the root node)
\endchange
\expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi
\amendpage 3.759 and following (22.02.01)
Miscellaneous changes to the existing index of Volume~3 are collected here,
including corrections and amendments to the old entries as well as new entries
that are occasioned by the new material. Thus, the lines of the full index
that have changed serve also as an index to the present document. However,
when a correction or amendment has caused an old index entry to be deleted,
the deletion is usually not indicated.
\input exotic
\begindoublecolumns
\indexformat
\gdef\Uni1.08:{\bitmap24:1.08:}
\hangindent 2em
Analysis of algorithms, 3, 77--78, 80, 82, 85--95, 100--105, 108--109, 118--122, 140, 152--158, 161--162, 167--168, 174--177, 185--186, 255--256, 259--266, 274--279, 285--287, 294--299, 330--335, 339--343, 379, 382, 387--388, 397--408, 412--413, 424--425, 430--431, 454--458, 466--471, 479--480, 485--486, 490, 500--512, 524--525, 534--539, 543--544, 552--557, 565--566, 576, 619, 642--643, \also Complexity analysis. % 48th
Demuth, Howard B\period\ (= Bud), 109, 184, 246, 348, 353, 387, 388, 676. % 49th
Fubini, Guido, numbers, \see Weak orderings. % 49th
Gessner, Conrad, 179. % 48th
Han, Guo-Niu (\GC73:73:-3:61% G2611
<000000000000e0000000000078000000fc00000000007f000000ff00000000007f000000%
ff00000000007f000000ff00000000007e000000ff00000000007e000000fc0000000000%
7e000000fc00000000007e038000fc00380000007e07c000fc007e0000007e0fe000fc00%
ff007ffffffff7ffffffff803ffffffffbffffffff801f007e0001ffffffff8000007e00%
0000fc00000000007e000000fc00000000007e000000fc00000000007e000000fc000000%
00007e038000fc00000003c07e07c000fc00000003f07e0fe000fc00000001fffffff000%
fc00000001fffffff000fc00e00001ffffffe000fc01f00001f00007c000fc03f80001f0%
0007c3fffffffc0001f00007c1fffffffe0001f00007c080fc00000001f00007c000fc00%
000001f00007c000fc00000001f00007c000fc00000001f00007c000fc00000001ffffff%
c000fc00000001ffffffc000fc00000001f00007c000fc00000001f00007c000fc003c00%
01f00007c000fc007e0001f00007c000fc00fe0001f00007cfffffffff0001f00007c7ff%
ffffff8001f00007c7ffffffff8001f00007c200fc003f0001ffffffc000fc003e0001ff%
ffffc000fc003e0001ffffffc000fc003e0003f07e07c000fc003e0003f07e07c000fc00%
3e0003f07e07c000fc003e0003f07e000000fc003e0000007e000000fc003e0000007e00%
7000fc003e0000007e00f800fc003e0000007e01fc00fc007e00fffffffffe00fc007c00%
7fffffffff00fc00fc003fffffffff00fc00f8000c007e000000fcf9f80000007e000000%
fc1ff00000007e000000fc07f00000007e000000fc03e00000007e000000fc03c0000000%
7e000000fc03800000007e000000fc01000000007e000000fc00000000007e000000fc00%
000000007e000000fc00000000007e000000fc00000000007e000000fc00000000007e00%
0000fc00000000007e000000fc00000000007e000000fc000000000000000000fc000000%
000000000000fc000000>%% Unicode char "97e9
\GC63:70:-11:58% G2590
%% Unicode char "56fd
\GC71:72:-5:60% G3703
<000000007000000000000000007c00000000000000007f00000000000000007fc0000000%
000000007fc0000000000000007f000000000000e0007e000000000000fc007e00000000%
0001ff007e000000000001ff007e000000000001fe007e000000000001fe007e00000000%
0003fc007e000000000003fc007e000000000003fc007e000000000003f8007e00003800%
0007f8007e00007c000007f0007e0000fe000007e0007e0001fe000007ffffffffffff00%
000fffffffffffff80000fffffffffffff80000f00007e00000000001f00007e00000000%
001e00007e00000000003e00007e00000000003c00007e00000000007c00007e00000000%
007800007e0000000000f800007e0000000000f000007e0000000001e000007e00000000%
03e000007e0000000007c000007e00000000078000007e000000000f0000007e00000000%
1e0000007e000000001c0000007e000001c0180000007e000003e0180000007e000007f0%
000000007e00000ff8fffffffffffffffffc7ffffffffffffffffe3ffffffffffffffffe%
100000007e00000000000000007e00000000000000007e00000000000000007e00000000%
000000007e00000000000000007e00000000000000007e00000000000000007e00000000%
000000007e00000000000000007e00000000000000007e00000000000000007e00000000%
000000007e00000000000000007e00000000000000007e00000000000000007e00000000%
000000007e00000000000000007e00000000000000007e00000000000000007e00000000%
000000007e00000000000000007e00000000000000007e00000000000000007f00000000%
000000007f00000000000000007f00000000000000007e00000000000000007e00000000%
>%% Unicode char "725b
), 595, 599, 602. % 49th
Hannenhalli, Sridhar Subrahmanyam\indexbreak
({\kn\C206\\{-4}\C167\\{-2}\C132\\2\C87\\{-3}\C128\\3\C102\\{-1.5}\C130\ \C110\\{-3}\C128\\2\C133\\2\C98\\{-5}\C167\|4128|\C111\C165\\{-3}\C83\\{-2}\C166\\2\|4128|\|{9.5}130|\C100\ \\1\|4128|\C111\\1\|4137|\C88\\{-2}\C160\\{-2}\C132\\2\|4128|\C88\\2\|4128|\C111\\2\C202\\{-3}\raise1pt\hbox{\C171}\\{-2}}), 614. % 49th
Log-concave sequences, 658. % 49th
Permutation tableaux, 72. % 49th
Stanley, Richard Peter, 69, 197, 600, 605, 606, 670, 671. % 49th
Stappers, Filip Jan Jos, 657. % 48th
Zuse, Konrad Ernst Otto, 385. % 49th
\vfill
\enddoublecolumns
\endchange
\bye
[The next printing will be the 49th.]
Not mentioned above:
page iv, http: -> https:
page vii, in Swift quote, Particularly -> particularly; A Tale (not just Tale)
page 72, subscripts adjusted to please Oliver Runge
page 101 and 109, added MIX units (or u) to runtime stats
page 197, less space in binomial coefficients of (2), (3), (4)
page 247, networks -> net-works
page 334, in Example 9, vice-versa -> vice versa
page 446, "improvement on" -> "improvement to"
page 565, two lines before (3): $N$th node
page 605, better spacing of {n\brace n-k} answer 19 line 3
page 607, better spacing in answer 29 line 1
page 624, better spacing in "B !"
Denert leaves the index
page 782, adjusted the Berkeley quote to match original
ARTICLES "TO APPEAR" THAT ARE STILL PENDING:
Jannis Harder on optimum sorting networks arXiv2012.04400 (v3, 24Jul2022)