% CHANGES TO VOLUME 4A OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2022, 2023, 2024, 2025 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, 2024, 2025 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 \improvepage 4a.x line $-3$ (23.11.24) For example, $\nu@10=2$, $\lambda@10=3$, $\rho@10=1$. \becomes\nl For example, $\nu@18=2$, $\lambda@18=4$, $\rho@18=1$. \endchange \amendpage 4a.xiv line 4 of Boswell's quote (24.04.27) {\eightssi shown \becomes shewn} \endchange \improvepage 4a.31 line 14 (24.11.28) pixel density \becomes level of gray \endchange \amendpage 4a.33 line 4 (24.02.10) incident with~$e$. The hypergraph \becomes incident with~$e$. (We~assume that $V\?\cap E=\emptyset$.) The hypergraph \endchange \amendpage 4a.34 line 2 before {\eq(61)} (24.11.28) all $w\notin W$ \becomes all $w\in V\setminus W$ \endchange \amendpage 4a.42 line 1 of exercise 80 (24.11.28) \ninepoint graph must \becomes graph on two or more vertices must \endchange \bugonpage 4a.48 line 8 (23.11.15) {\eightssi Looking Glass \becomes Looking-Glass} \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 \improvepage 4a.98 line 8 (24.06.15) its complexity \becomes its cost \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 \amendpage 4a.113 replacement for {\eq(43)} and preceding lines (25.02.21) a chain of 22 steps does emerge; and David Stevenson \dots [end of display] \becomes\nl a chain of 22 steps does emerge. And Oliver~{Runge} has shown that only 19 steps are actually needed(!), if we do a ``{hungry search}'' that uses footprints more cleverly [$\,$\.{https://orunge.org/boolean-chains/}$\,$]: $$\advance\abovedisplayskip2pt\openup-.9\jot\eqalign{ x_5&=\bar x_3\bland x_4,\cr x_6&=x_3\xor x_4,\cr x_7&=x_2\xor x_3,\cr x_8&=x_5\blor x_7,\cr x_9&=x_1\xor x_2,\cr \bar f=x_{10}&=x_8\bland\bar x_9,\cr \strut x_{11}&=x_6\xor x_{10},\cr }\qquad\eqalign{ x_{12}&=x_1\blor x_{11},\cr g=x_{13}&=x_7\blor x_{12},\cr x_{14}&=x_7\bland\bar x_{11},\cr x_{15}&=x_2\xor x_{14},\cr \bar c=x_{16}&=\bar x_9\bland x_{15},\cr \bar b=x_{17}&=x_{12}\bland x_{15},\cr \strut\cr }\qquad\eqalign{ x_{18}&=x_{11}\xor x_{16},\cr \bar a=x_{19}&=x_8\bland\bar x_{18},\cr x_{20}&=x_4\xor x_{14},\cr \bar e=x_{21}&=\bar x_{16}\bland x_{20},\cr x_{22}&=x_{19}\xor x_{20},\ \cr \bar d=x_{23}&=x_8\xor x_{22}.\cr \strut\cr }\eqno(43)$$ \endchange \improvepage 4a.115 line 6 after {\eq(46)} (25.02.18) telephone dial \becomes telephone keypad \endchange \amendpage 4a.125 new rating for exercise 11 (25.03.22) \ninepoint [{\it 22\/}] \becomes [{\it 23\/}] \endchange \amendpage 4a.133 replacement for the Colman quote (24.04.27) {\quoteformat\vskip-8pt \noindent % enable \everypar \setbox0=\hbox{{\rm Lady C.}\hskip8.2em Pshaw, that's such a hack.}% \noindent\copy0 % (she's referring to Fielding's "Tom Jones") \vskip2pt\noindent % \hbox to\wd0{{\rm Sir Sim.}\hfil A hack, Lady Caroline, that} the knowing one's have warranted sound. \par} \endchange \bugonpage 4a.142 line 6 (22.05.24) 64 substrings \becomes 64 truncated shifts \endchange \amendpage 4a.186 in exercise 23 (24.06.14) \ninepoint line 2: right parenthesis \becomes left parenthesis\nl line 3: $(001101)_2$, the number 13. \becomes $(110010)_2$, the number 50.\nl line 8: assuming that $\nu x\le32$. \becomes assuming that $m<32$. \endchange \amendpage 4a.274 new rating for exercise 206 (24.09.26) \ninepoint [{\it M46\/}] \becomes [{\it M40\/}] \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 \amendpage 4a.484 replacement for last two lines of exercise 122 (24.01.08) \ninepoint \centerline{$\def\<#1>{\hbox{$\langle\,$#1$\,\rangle$}} \\to\\mid .\\mid \.\$} \medskip\noindent For example, $100=((.1\times.2+3)/.4)/.5+6+78.9$, amazingly enough. \endchange \amendpage 4a.499 line $-4$ (25.01.05) ``Lotus Delight of Calculation'' \becomes ``Mathematics Illuminated'' \endchange \amendpage 4a.505 line 15 (24.02.26) Stirling subset numbers \becomes Stirling partition numbers \endchange \amendpage 4a.505 new intro to the subsection on integer partitions (24.04.12) \noindent {\bf Integer partitions.}\enspace Partitions of integers \dots\ Bishop Wibold \becomes\nl \noindent {\bf Integer partitions.}\enspace Partitions of integers can be found in Chapter 12, Part~4 of the {\sl Bhagavat{\=\i} S\=utra}, an encyclopedic work in the canon of Jainism that was completed before \AD.~500. Every partition of every number up to 10 is explicitly mentioned, in words (not symbols), except that $2+2+5$ and $1+2+2+5$ were omitted. [See D.~Jadhav, {\sl Mathematics in Ancient Jaina Literature\/} (World Scientific, 2023), 87--105.] The earliest known European references came much later. We saw above that Bishop Wibold \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.516 last line of answer 13 (24.02.13) (2) {\bf 50} \becomes {\bf 50} \endchange \amendpage 4a.519 end of answer 23 (24.11.28) [See S. W. Golomb \dots \ code.]\becomes (The literature of {coding theory} often denotes a code $C(b,n,r)$ of distance~$d$ by the symbol $(n+r,b^n,d)_b$. Thus, a $b$-ary orthogonal array of depth~$m$ is essentially an $(m,b^2,m-1)_b$ code.)\par [See R.~W. {Hamming}, {\sl The Bell System Technical Journal\/ \bf29} (1950), 147--160; S.~W. {Golomb} and E.~C. {Posner}, {\sl IEEE Transactions\/ \bf IT-10} (1964), 196--208.] \endchange \amendpage 4a.519 replacement for answer 26 (25.02.13) \ans26. ``$@$\.{local} \.{press} \.{print} \.{scoop}: \.{daily}, \.{young} \.{sharp} \.{geeks} \.{check} \.{dodgy} \.{input}, \.{track} \.{stray} \.{flaws}, \.{bring} \.{quick} \.{fixes}, \.{about} \.{fifty} \.{years} \.{after} \.{grand} \.{elder} \.{minds} \.{first} \.{wrote} \.{crisp} \.{codes} \.{using} \.{bytes} \.{every} \.{night}$@$.'' [Filip {Stappers}, 2025.]\tighten \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.522 beginning of answer {59(c)} (24.11.28) Yes. \becomes Yes, up to isomorphism. \endchange \amendpage 4a.562 replacement for the first part of answer 11 (25.03.22) \ans11. The only subtle point is that $j$ should {\it decrease\/} in step~U3; then we'll never have $\phi(g)\band\phi(h)\ne0$ when $j=0$, so all cases of cost~$r-1$ will be discovered before we begin to look at list~$r-1$. Some normal functions $x_{n+1}$, \dots, $x_m$ may also be given (cost~0).\tighten \par\algindentset{\hskip\parindent U1} \algstep U1. [Initialize.] Set $U(0)\gets\phi(0)\gets0$ and $U(f)\gets\infty$ for $1\le f<2^{2^n-1}$. Then set $U(x_k)\gets\phi(x_k)\gets0$ and put $x_k$ into list~0, for $1\le k\le m$. Let there be $t$ distinct functions of the form $f=x_j\circ x_k$, where $1\le j2^{2m}$. [See C. Neri, \arXiv:1602.06426 [cs.DS] (2016), 9~pages.]\par (c) \.{SUBU} \.{t,x,1;} \ \.{ANDN} \.{u,x,t;} \ \.{SADD} \.{k,t,x;} \ \.{ADDU} \.{v,x,u;} \ \.{SUBU} \.{t,x,1;} \ \.{ANDN} \.{u,x,t;} \ \.{SADD} \.{k,t,x;} \ \.{ADDU} \.{v,x,u;} \ \.{SADD} \.{k,x,v;} \ \.{SUB} \.{ k,xxxiii,k;} \ \.{SRU} \.{ t,mu0bar,k;} \ \.{SRU} \.{ t,t,k;} \ \.{ADDU} \.{y,v,t}. (Here \.{xxxiii} is the constant 33.) \endchange \amendpage 4a.650 line 9 of answer 160 (24.01.01) the most symmetric solution \becomes one of the most symmetric \endchange \bugonpage 4a.651 replacement for $(A0)$ on line 2 (24.01.01) $$\vcenter{\epsfbox{\figdir/ch7a.1400}}$$ \endchange \bugonpage 4a.659 lines 5 and 14 of answer 198 (23.11.04) answer 200 \becomes answer 201 \endchange \amendpage 4a.662 new answer (25.01.29) \ans206. Although all five routines seem to be reasonably fast in practice, they can be exponentially slow in the worst case. For example, the meet and join operations can simulate the hidden weighted bit function. [See K.~Nakamura, M.~Nishino, and S.~Denzumi, %\arXiv:2403.05074 [cs.DX] (2024), 19~pages.] {\sl LIPIcs\/ \bf322} (2024), 52:1--52:17.] \endchange \amendpage 4a.670 line $-12$ of answer 237 (24.09.26) are unknown \becomes are exponential \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%% Unicode char "4f1d \JC48:48:0:40% J2927 <000e03e00000000f80f80000000f807c0000001f803e0000001f003f0000001f001f0000% 003e001f0000003e000e0000007c00000000007c0000000000f80000003000f800000078% 01f3fffffffc01e1fffffffc03e0000f000003c0000f000007c0000f000007f0000f0000% 0ff0000f00000fe0000f00001fe0000f00003de0000f000071e0000f0000c1e0000f0000% 01e0000f00c001e0000f01e001e0fffffff001e07ffffff001e0000f000001e0000f0000% 01e0000f000001e0000f000001e0000f000001e0000f000001e0000f000001e0000f0000% 01e0000f000001e0000f000001e0000f000001e0000f000001e0000f000001e0000f0000% 01e0000f000c01e0000f001e01efffffffff01e7ffffffff01e00000000000c000000000% >%% Unicode char "4f4f \JC46:48:0:40% J2894 <01800000003001e00000007801fffffffffc01fffffffffc01e00000007801e001800078% 01e001e0007801e001f0007801e001f0007801e001e0007801e001e0607801e001e0f078% 01e1fffff87801e0fffff87801e001e0007801e001e0007801e001e0007801e001e00078% 01e001e0187801e001e03c7801e7fffffe7801e3fffffe7801e00000007801e000000078% 01e00000007801e00000007801e06003007801e07807807801e07fffc07801e07fffc078% 01e07807807801e07807807801e07807807801e07807807801e07807807801e078078078% 01e07807807803e07807807803c07fff807803c07fff807807c078078078078030030078% 0f80000000780f00000000f81e0000000ff83c00000003f87000000001f0c000000000e0% >%% Unicode char 5468 \JC48:46:0:38% J4231 <0000000000c00000000001e00ffffffffff007fffffffff0000003c00000000003c00000% 00c003c0040000f003c00700007803c007c0007c03c007c0003e03c007c0003e03c00780% 001f03c00f80001f03c00f80000f03c01f00000f03c01e00000f03c03e00000603c03c00% 000003c07800000003c0f000000003c3c00c000003c3001effffffffffff7fffffffffff% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000001800000>%% Unicode char "5e73 ), 662. % 24th Dijoin, \see $@$Directed join of digraphs. % 25th Downloadable programs, \see Internet. % 23rd Empty graph ($\overline{K_n}$), 26, 27, 41--43, 46, 530, 806. % 23rd Euler, Leonhard ({\rus Ei0lerp2, Leonardp2} = {\rus E1i0ler, Leonard}), 3--7, 36, 395--396, 404, 408, 409, 507, 516, 655, 759. % 23rd Feller, Vilibald (= Vilim = Willy = William) Sre\'cko, 797. % 25th Flood fill algorithm, \see Reachability problem. % 23rd Fraenkel, Aviezri Siegmund\indexbreak ({\heb\Hll/\Hqq/\Hnn/\Hrr/\Hpp/ \Hdd/\Hnn/\Hvv/\Hmm/\Hgg/\Hyy/\Hss/ \Hyy/\Hrr/\Hzz/\Hai/\Hyy/\Hbb/\Haa/}), 721, 727. % 24th {\sl IEEE Transactions}, citations from, ix--x. % 23rd Harding, Edward Frank, 464. % 22nd Hidden weighted bit function ($h_n$), 235--238, 240, 262, 266--267, 269, 646, 662. % 24th Hungry search, 113, 571. % 25th Indian mathematics, 15, 487--489, 491--492, 499--500, 505, 507, 512. % 24th Jadhav, Dipak ({\dn Edpk jADv}), 505. % 24th Jainism, 505. % 24th Kumar, Panganamala Vijay \indexbreak({\tl \|1128|\C97\\1\C9\|1128|\C73\\1\|2128|\C90\\1\|1129|\C90\\5\|2128|\|7129|\C101\\7\C105\ \C227\\2\C78\\2\|2148|\C102\ \C184\\7\|2128|\|7129|\C101\\7\|1148|\C103\\2}), 681. % 24th {\sl LIPIcs\/}: {\sl Leibniz International Proceedings in Informatics\/} (2008--). % 25th % Leighton, Robert Eric, leaves the index % 25th Lozhkin, Sergey Andreevich ({\rus Lozhkin, Sergei0 Andreebich}), 112. % 23rd Menon, Vairelil Vishwanath ({\mly\\74\\74\\65\\75\\63\\64\\6F\\B2 \\65\\6F\\66\\7C\\5C\\6E\\59 \\75\\61\\75\\5C\\6E\\B0}), 525. % 22nd Nakamura, Kengo (\JC41:48:-4:40% J3570 <00003000000000003c00000000003e00000000003e00000000003c00000000003c000000% 00003c00000000003c00000000003c00000000003c000000c0003c000600f0003c000f00% ffffffffff80ffffffffff80f0003c000f00f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00ffffffffff00ffffffffff00% f0003c000f00f0003c000f00f0003c00060060003c00000000003c00000000003c000000% 00003c00000000003c00000000003c00000000003c00000000003c00000000003c000000% 00003c00000000003c00000000003c00000000003c00000000003c000000000018000000% >%% Unicode char "4e2d \JC48:48:0:40% J3428 <007000001c00007c00001f00003e00001f80003e00000f80003c00000f00003c00000f00% 003c00000f00003c00000f00003c00000f00003c00000f00003c30000f0c003c78000f1e% fffffcffffff7ffffc7fffff003c00000f00003c00000f00003c00000f00003c00000f00% 007f00000f00007fc0000f0000fcf0c00f0000fcf8e00f0000fc7c780f0001fc3c7c0f00% 01fc3c3e0f0003fc183e0f0003bc001f0f0007bc001f0f00073c000f0f000f3c000e0f00% 1e3c00000f003c3c00000f00f03c00000f00c03c00000f00003c00000f00003c00000f00% 003c00000f00003c00000f00003c00000f00003c00000f00003c00000f00003c00000f00% 003c00000f00003c00000f00003c0001ff00003c0000ff00003c00007e00001800003c00% >%% Unicode char "6751 \JC48:48:0:40% J2382 <00c00001800000f80001e00001f80001f00001f00001f00001f03001e18001f07801e3c0% 03effcffffe003e7fc7fffe003e07801e3c007c0f001e3c007c0f001e3cc0781e001e3de% 0781efffffff0f83c7ffffff0f03c001e3c00f078001e3c01f878001e3c01f8f0001e3c0% 3f0f18ffffc03f1e3c7fffc06f1ffe01e3c06f3ffe01e180cf3c3c01e0008f183c01e0c0% 0f003c01e1e00f003cfffff00f003c7ffff00f003c01e0000f003c01e0000f003c01e000% 0f003c01e0180f003c01e03c0f103ffffffe0f183dfffffe0f0c3c01e0000f063c01e000% 0f073801e0000f03f801e0000f01f801e0000f00fc00c0000f007f0000000f00ffe00000% 0f00efffffff0f01c3fffffe0f0180fffffe0f03801ffffc0f0700000000060c00000000% >%% Unicode char "5065 \JC48:48:0:40% J2467 <0000000000c00000000001e00ffffffffff007fffffffff000000f00000000000f000000% 00000f00000000000f00000000001e00000000001e00600000001e00f00003fffffff800% 01fffffff80000003c00f00000003c00f00000003c00f00000007800f00000007800f000% 00007800f00000007800f0000000f000f00c0000f000f01effffffffffff7fffffffffff% 00000000000000000000000000000000000000000000000000c00000060000f000000f00% 00ffffffff8000ffffffff8000f000000f0000f000000f0000f000000f0000f000000f00% 00f000000f0000f000000f0000f000000f0000f000000f0000f000000f0000f000000f00% 00f000000f0000f000000f0000ffffffff0000ffffffff0000f000000f00006000000600% >%% Unicode char "543e ), 662. % 24th Neri Moreira, Cassio, 587. % 24th Nishino, Masaaki (\JC48:46:0:38% J3230 <00000000000c00000000001effffffffffff7fffffffffff0000f03c00000000f03c0000% 0000f03c00000000f03c00000000f03c00000000f03c00000000f03c00000000f03c0000% 0c00f03c00300e00f03c00780ffffffffffc0ffffffffffc0f00f03c00f00f00f03c00f0% 0f00f03c00f00f00f03c00f00f00f03c00f00f00f03c00f00f00f03c00f00f00f03c00f0% 0f01e03c00f00f01e03e00f00f01c03ffff00f03c03ffef00f07801ffcf00f07800ff8f0% 0f0f000000f00f3e000000f00ff8000000f00fe0000000f00f00000000f00f00000000f0% 0f00000000f00f00000000f00f00000000f00f00000000f00ffffffffff00ffffffffff0% 0f00000000f00f00000000f00f00000000f0060000000060>%% Unicode char "898f \JC48:48:0:40% J4478 <3000180000183c003c00003c3ffffefffffe3ffffe7ffffe3c3c3c0001fc3c3c3c0001f8% 3c3c3c0003f03c3c3c0003e03c3c3c0007803c3c3c1c07003c3c3c070c003c3c3c07c000% 3ffffc03e0003ffffc01f0003c3c3c01f0003c3c3c00f0003c3c3c00e00c3c3c3c00001e% 3c3c3fffffff3c3c3dffffff3c3c3c00f83f3c3c3c00f83e3ffffc00f87c3ffffc00f878% 3c3c3c00f8f0183c1800f8e0003c0000f9c0003c0000f980003c0000fb00003c1800fa00% 003c3c00f8003ffffe00f8001ffffe00f800003c0000f800003c0000f800003c0000f800% 003c0000f800003c0000f800003c0000f800003c3fc0f800007ffc00f800fffff000f800% ffff0000f8007ff80001f8007fe0003ff8007c000007f80020000001f00000000000e000% >%% Unicode char "91ce \JC48:44:0:38% J3221 <0000000000300000000000783ffffffffffc1ffffffffffc000000f00000000000f00000% 000000f00000000000f00000000000f00000000000f00000000000f00000000000f00000% 000000f00000000000f00000003000f00000003c00f00000003e00f00000003e00f00000% 003c00f00300003c00f00780003c00ffffc0003c00ffffc0003c00f00000003c00f00000% 003c00f00000003c00f00000003c00f00000003c00f00000003c00f00000003c00f00000% 003c00f00000003c00f00000003c00f00000003c00f00000003c00f00000003c00f00000% 003c00f00000003c00f00000003c00f00000003c00f00000003c00f0000c003c00f0001e% ffffffffffff7fffffffffff>%% Unicode char "6b63 \JC48:48:0:40% J4143 <00c00300004000f003c0007000f803e0007c00f803e000fc00f003c000f800f003c000f0% 00f003c001f000f003c001e000f203c303e000f703c783c0ffffbfffc7807fff9fffcf00% 00f003c00e1800f003c01c1e00f003c0381f00f003c0e03f01f807e0003e01fe07f8007c% 01ff07fc007c01f787de007803f7cfdf00f803f7cfdf00f003f3cfcf01e007f3dfcf03c0% 07f19fc6038007f01fc007000ff03fc00e100ff03fc01c1c0ef03bc0301f1ef07bc0e01f% 1cf073c0001e38f0e3c0003e38f0e3c0003c70f1c3c0003c60f183c0007cc0f303c00078% 00f003c000f800f003c000f000f003c001f000f003c001e000f003c003c000f003c00780% 00f003c00f0000f003c01e0000f003c03c0000f003c0700000f003c0e000006001838000% >%% Unicode char "5f6c ), 662. % 24th No-three-in-line problem, 277, 831. % 25th Oriented binary trees, 464, 570. % 22nd Peirce, Charles Santiago Sanders, triangle, 418, 428, 434--436, 438, 769, 771, 779. % 23rd Postal codes, 15, 40, 210, 276. % 22nd Rao, Calyampudi Radhakrishna\indexbreak ({\tl\|1128|\C71\\1\|0105|\\6\C174\C9\|097|\|0128|\\2\C212\\1\|3131|\C83\ \|2103|\C129\\1\|089|\C129\\1\|171|\|2128|\\2\C137\\1\|2128|\|0109|\C163\ \|2103|\C129\|0107|\|1128|\\2\C210}), 518. % 24th Recurrence relations, 140, 142, 143, 169, 183, 187, 199, 211, 224, 228, 246, 266, 270, 303, 380, 396, 404, 409, 537--538, 557, 566, 567, 623, 641, 643, 651, 654, 669, 673, 681, 683, 693, 697--699, 703, 728--730, 778, 789--791, 796, 798, 809, 814. % 23rd Revolving-door Gray codes, 362, 383, 405, 463--465, 467, 468, 481, 804. % 23rd $S_m$ (a symmetric Boolean function), 77, 99, 126, 262, 272, 274, 626, 636, 642. % 24th Runge, Oliver, 113, 571--572. % 25th \.{SADD} (sideways addition), 141, 160, 586--587, 589, 590, 620. % 24th Set partitions, ordered, \see Weak orderings. % 24th {\mc SIMPATH}, ix, 254, 275. % 23rd Stappers, Filip Jan Jos, 519, 649, 707. % 25th Stevenson, David Ian, 564, 572, 574. % 25th Stirling, James, 504. \sub partition numbers, 439, 504--505, 777, 824. % 24th \sub partition numbers, asymptotic value, 424--426. % 24th \sub partition numbers, generalized, 436, 765. % 24th Tables of numerical quantities, Boolean function counts, 79. % 23rd Ternary encodings, 160--163, 195. % 23rd USA graph, \see Contiguous United States of America. % 23rd ZDD: A zero-suppressed BDD, ix, 204, 249. % 23rd Zuse, Konrad Ernst Otto, 570. % 24th \vfill \enddoublecolumns \endchange \bye [The next printing will be the 25th.] not listed above: Page 73, proof of Theorem F, line 2: Ph. D. -> Ph.D. the change to page 499 also affects page 500 Page 597 line 4: C-57 not C57 Page 608, line -3 of answer 159, better spacing in the conditional expr Ternary Boolean functions leaves the index Ternary operations is merged with Ternary Boolean operations (in index) ARTICLES "TO APPEAR" THAT ARE STILL PENDING: