% CHANGES TO VOLUME 4A OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2022, 2023 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 err4a" \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 4A (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~4A (20th printing), since it was first printed in 2022. Previous errata are recorded in another file `{\tt all4a-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 \beginconstruction The ultimate, glorious, future editions of {\sl The Art of Computer Programming\/} 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 1B, Stanford University, Stanford CA~94305-9015, 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~4 these days, I~will try to reply to all such messages within a year of receipt. Current news is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, January 2011} \bigskip \bigskip {\quoteformat If there happen to bee any iarre or dissonance, % % people say "ther" but it's really just a lightly printed letter e blame not the Printer, who (I doe assure thee) through his great paines and diligence, doth heere deliuer to thee a perfect and true Coppie. If .\thinspace.\thinspace.\ there bee any fault by mee committed, I desire the skilfull, eyther with courtesie to let the same bee concealed, or in friendly sort to bee thereof admonished: and at the next Impression he shall find error reformed: remembring alwaies, that it is more easie to finde a fault then to amend it. \author WILLIAM BYRD, % {\sl Psalmes, Sonets, \& songs of sadnes and pietie\/} (1588) \bigskip\bigskip He did a lot of editing. That's how he liked to work. Sometimes he even made alterations between printings. \author P. D. JAMES, {\sl The Lighthouse\/} (2005) % page 148 (within Chapter 7) \bigskip\bigskip \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 4A %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 4A: COMBINATORIAL ALGORITHMS, PART 1} \let\rhead=\lhead \titlepage \volheadline{COMBINATORIAL ALGORITHMS, PART 1} \bigskip \rightline{Copyright \copyright\ 2022, 2023 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 \def\bland{@\land@} % \land as wide as \xor \def\blor{@\lor@} \def\nbool#1{\mathbin{\mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}} \def\nimp{\?\nbool\supset\?} \improvepage 4a.v lines $-6$ and $-5$ (22.06.15) because, in fact, \dots~by 1. \becomes because the size of a combinatorial problem can increase more than 100,000-fold when a parameter~$n$ increases by just~1. \endchange \amendpage 4a.ix new paragraph to follow line 4 (23.10.09) Many of the computer programs that I wrote while preparing this material are listed Internet on the following webpage: $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/programs.html}$$ In particular, you can download {\mc BDD14} and {\mc BDD15}, which are the experimental toolkits that I played with when studying BDDs and ZDDs, respectively, in Section~7.1.4. Another example is a program called {\mc SIMPATH}, for exercise 7.1.4--225.\tighten \endchange \bugonpage 4a.60 line 2 (22.02.28) $l\gets l+k$ \becomes $\.{START($c$)}\gets l$, $l\gets l+k$ \endchange \amendpage 4a.60 new steps C3 and C5 (23.05.30) \algindentset{C1}% \algstep C3. [Done with loop?] If $c=\Lambda$, return to C2. Otherwise set $c'\gets\.{PREV($c$)}$, $q\gets\.{CONCLUSION($c$)}$, and go to C6 if $\.{TRUTH($q$)}=1$. Otherwise set $l\gets\.{START($c$)}$ and $k\gets\.{COUNT($c$)}-1$. \algstep C5. [Deduce \.{CONCLUSION($c$)}.] Set $\.{TRUTH($q$)}\gets1$, $S_s\gets q$, $s\gets s+1$. \endchange \amendpage 4a.112 new copy to follow line 3 (23.07.15) \noindent [An even better upper bound, replacing $3\lg n$ by $\lg n+\lg\lg n$, has been proved by S.~A. Lozhkin, {\sl Moscow University Mathematics Bulletin\/ \bf77} (2022), 144--153.]\tighten \endchange \bugonpage 4a.142 line 6 (22.05.24) 64 substrings \becomes 64 truncated shifts \endchange \amendpage 4a.299 line 1 (22.05.24) the sequence \becomes the digits change by $\pm1$ and the sequence \endchange \bugonpage 4a.334 line 21 (22.11.20) [{\sl Inf.\ Proc.\ Letters\/ \bf17} (1983), 231--234] \becomes [{\sl Inf.\ Proc.\ Letters\/ \bf17} (1983), 231--233] \endchange \improvepage 4a.363 first line of step R4 (22.05.24) $c_j=c_{j-1}+1$ \becomes $c_{j-1}=c_j-1$ \endchange \improvepage 4a.379 second line of exercise 1 (23.10.08) \ninepoint $\infty\cdot n-t$ \becomes $\infty\cdot(n{-}t)$ \endchange \amendpage 4a.389 in exercise 110 (22.05.24) \ninepoint line 4: where one card \dots\ choice of $k$: \becomes where a player holds $\{c_1,c_2,c_3,c_4\}$ and card $c_5$ is called the {\it starter}. The score is the sum of points computed as follows, for each subset~$S$ of~$C$:\nl lines 11 and 12: If $s=4$ \dots\ same suit as \becomes If $S=\{c_1,c_2,c_3,c_4\}$ and all cards of $S$ have the same suit, score $4+[c_5$~has the same suit as\nl line 13: $c_k$ \becomes $c_5$ \quad(twice)\nl line $-2$: combinations and starter choices \becomes combinations \endchange \bugonpage 4a.425 line 14 (22.11.20) {\sl Duke Math.\ J. \bf25} (1957), 29--43 \becomes {\sl Duke Math.\ J. \bf25} (1958), 29--43 \endchange \amendpage 4a.428 insert new algorithm in the middle of the page (23.05.05) line 3 before \eq(53): A nice way \becomes An interesting way\nl line 5 after \eq(53): $1/\varpi_n$. \becomes $1/\varpi_n$. We can generate $M$ by using 3.4.1--\eq(3); it tends to be approximately $n/\xi=e^{@\xi}$ (see exercise 67).\nl\smallskip\noindent now replace the following paragraph by new copy:\nl\indent There's also an all-integer method, based on Peirce's triangle: \algbegin Algorithm P (Uniformly random set partitions). Given $N\ge1$, this algorithm generates the blocks of a random partition of $\{1,\ldots,N\}$, using ideas explained in exercise~26. Three auxiliary stacks, $S$, $T$, and $B$, hold auxiliary data. \algstep P1. [Initialize.] Set $n\gets N$, $k\gets1$, $S\gets\{1,\ldots,N\}$, and $T\gets B\gets\emptyset$. \algstep P2. [Begin a block.] %(At this point $k=1$ and $\vert S\vert=n$.) Pop $x\Leftarrow S$ and push $B\Leftarrow x$. (See 2.2.1--\eq(2) and 2.2.1--\eq(1).)\tighten \algstep P3. [Done with block?] If $n=k$, output $B$ as a block of the partition, and set $n\gets n-1$, $k\gets1$, $S\gets T$, $T\gets B\gets\emptyset$; terminate if $n=0$, else go to~P2.\tighten \algstep P4. [Add to block?] Pop $x\Leftarrow S$ and let $U$ be a random integer, $0\le U<\varpi_{nk}$. If $U<\varpi_{(n-1)k}$, push $B\Leftarrow x$ and set $n\gets n-1$; otherwise push $T\Leftarrow x$ and set $k\gets k+1$. Return to P3.\quad\slug \endchange \amendpage 4a.462 new paragraph before the Spanning trees subsection (22.11.01) E. F. Harding [{\sl Advances in Appl.\ Prob.\ \bf3} (1971), 44--77] has shown how to generate the $k$th oriented {\it binary\/} tree with $n$ vertices (see exercise 2.3.4.4--6). \endchange \amendpage 4a.464 line 2 of Algorithm S becomes two lines (22.12.15) trees. \becomes trees in a revolving-door Gray code order. \endchange \bugonpage 4a.507 line $-5$ (23.04.13) {\sl Zahlen durch\/} \becomes {\sl Zahlen, durch\/} \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \amendpage 4a.514 replacement for the first answer 3 (22.07.26) \ans3. See H. Poincar\'e, {\sl Rendiconti del Circolo Matematico di Palermo\/ \bf18} (1904), 45--110; R.~H. Bing, {\sl Annals of Math.\ \rm(2) \bf68} (1958), 17--37; G.~Perelman, \arXiv:math/0211159 [math.DG] (2002), 39~pages; 0303109 and 0307245 [math.{\mc DG}] (2003), $22{+}7$~pages.\tighten \endchange \amendpage 4a.516 last line of answer 9 (22.12.09) 132 rows \becomes 132 options \endchange \bugonpage 4a.521 in answer 47 (22.11.10) {\sl Geometrie der Gewebe\/} (1937) \becomes {\sl Geometrie der Gewebe\/} (1938) \endchange \bugonpage 4a.522 in answer 54 (22.11.10) Darryl~Francis, Philip Cohen, and A.~Ross Eckler in {\sl Word Ways\/ \bf19} (1976), 241; {\bf20} (1977), 8. \becomes Darryl~Francis and Philip Cohen in {\sl Word Ways\/ \bf9} (1976), 241; {\bf10} (1977), 46--47. \endchange \amendpage 4a.672 line 3 of answer {241(d)} (23.06.01) Once again, \becomes See (C6) and~(C7). Once again, \endchange \bugonpage 4a.679 in answer 10 (22.11.10) {\sl De Viribus Quantititatis\/} \becomes {\sl De Viribus Quantitatis\/} \endchange \amendpage 4a.707 append a new sentence at end of answer 27 (23.03.05) F.~Stappers has found $\.{WRITE}+\.{WRITE}+\.{WRITE}+\.{WRITE}+\.{WRITE}+\.{WRITE}=\.{BOOKS}$; $\.{NOTES}+\.{SOUND}+\.{TONES}=\.{MUSIC}$. \endchange \amendpage 4a.717 new paragraph before answer {89(e)} (22.09.17) [But when applied to \eq(48), this procedure actually {\it increases\/} the value of $M$ in~(b).]\par \endchange \improvepage 4a.724 lines 1 and 2 of answer 1 (23.10.08) by listing the distinct elements first \becomes first listing its distinct elements (in increasing order) \endchange \bugonpage 4a.735 line 1 of answer {55(b)} (22.05.24) $t>0$ \becomes $0 wildcard ARTICLES "TO APPEAR" THAT ARE STILL PENDING: