% CHANGES TO VOLUME 1 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 err1" \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 1 (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~1 (third edition, 27th printing), since it was first printed in 2022. Previous errata are recorded in another file `{\tt all1-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~1. I didn't do that in the third 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~1 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--4 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 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, January 2011} \bigskip \bigskip {\quoteformat What happened? The subject took the bit in its teeth and ran away with it, that's what happened. I know now how Sir James Frazer felt when, after setting out to dash off a brief monograph on a single obscure rite, he found himself in the embarrassing possession of the 12 volumes of ``The Golden Bough.'' \author WAVERLEY ROOT (1974) % International Herald Tribune, 22 May 1974, p8 \bigskip No matter how many times you proofread your book, after publication there will be roughly one typo per page. \author JOSEPH H. SILVERMAN (2017) % "A tale of two books", Bull AMS 54 (2017), 593 \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 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 1: FUNDAMENTAL ALGORITHMS} \let\rhead=\lhead \titlepage \volheadline{FUNDAMENTAL ALGORITHMS} \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 \amendpage 1.12 replacement for line $-14$ (23.03.29) $$p(0)=1,\quad p(1)=1,\quad p(2)=2,\quad p(3)=3,\quad p(4)=5,\quad p(5)=7.$$ \endchange \amendpage 1.13 add a sentence following line $-7$ (23.12.05) legitimate. \becomes legitimate. [Actually $P(0)$ does happen to be true, in this particular context; but we weren't asked to prove it. So we didn't.] \endchange \improvepage 1.16 line 18 (22.02.18) the key inductive assertions. Those assertions either \becomes the key assertions. Those assertions\dash---which are often called ``inductive assertions'' because we prove them by induction on the length of computation\dash---either \endchange \amendpage 1.17 lines 20 and 21 (23.11.17) The first European \dots\ 1575. \becomes Noteworthy early examples of inductive reasoning can be found in {\sl Sefer Maasei Hoshev\/} by Levi ben Gershon in France (1321), and in {\sl Arithmeticorum libri duo\/} by Francesco Maurolico in Italy (1557). \endchange \amendpage 1.21 line 2 after {\eq(1)} (24.02.07) end with infinitely many 9s. \becomes end with infinitely many 9s. (Instead of $999\ldots{}$, we can use $000\ldots$ and add 1 to the digit at the left.) \endchange \amendpage 1.22 top lines (24.02.07) \indent Throughout this section \dots\ It is easy to prove \becomes\nl \indent Throughout this section, let the letter $b$ stand for a positive real number. If $n$ is an integer, then $b^n$ and $0^n$ and $(-b)^n$ are defined by the familiar rules $$\displaylines{\hfill b^0=1,\qquad b^n=b^{n-1}b\quad\hbox{if}\quad n>0,\qquad b^n=b^{n+1}\!/b\quad\hbox{if}\quad n<0@;\hfill\eq(4)\cr\hfill {0@}^0=1,\qquad 0^n=0\quad\hbox{if $n>0$};\qquad (-b)^n=(-1)^nb^n. \hfill\eq(5)\cr} $$ It is easy to prove \endchange \amendpage 1.22 through 26 (24.02.07) [renumber equations formerly numbered \eq(5) through \eq(19) to be \eq(6) through \eq(20)] \endchange \amendpage 1.27 line 5 (22.03.01) following equivalent \becomes following essentially equivalent \endchange \amendpage 1.27 line 11 after {\eq(2)} (24.02.07) silly to interpret it as a sum on values of $n\ge j$; but \becomes silly to interpret it as a sum $a_j+a_j+a_j+\cdots$ over all indices~$n$ that satisfy $n\ge j$! But \endchange \amendpage 1.34 in exercise 8 (22.11.24) \ninepoint infinite series in which \becomes doubly infinite sequence $\langle a_{ij}\rangle$ of integers for which \endchange \amendpage 1.57 six lines after {\eq(13)} (22.08.11) since the terms in Eq.~\eq(13) are zero when $k<0$ or $k>r$. \becomes since we consider $r\choose k$ to be ``strongly zero'' when $k<0$ or $k>r=\lfloor r\rfloor$\dash---strong enough to cancel negative powers of~0. \endchange \bugonpage 1.60 line $-1$ (23.01.19) assuming that $k\ge0$ \becomes because $k\ge0$ \endchange \bugonpage 1.63 line $-10$ (22.08.11) $\displaystyle \sum_k$ \becomes $\displaystyle \sum_{k\ge0}$ \endchange \bugonpage 1.63 lines $-3$ and $-2$ (22.08.11) $\displaystyle \sum_n$ \becomes $\displaystyle \sum_{n\ge0}$ \endchange \bugonpage 1.70 append a new line to exercise 25 (22.08.09) \ninepoint\noindent where again the left-hand side is considered to be a polynomial in $r$.\nl [Also change `.' to `,' on the preceding line.] \endchange \amendpage 1.77 the line before {\eq(10)} (22.03.01) $S_1=x$ \becomes $S_0=0$ \endchange \amendpage 1.77 line $-7$ (22.03.01) {\sl If $x>0$, then\/} \becomes {\sl If $x>0$ and $n\ge0$, then} \endchange \bugonpage 1.79 line $-3$ (23.03.29) 285 \becomes 284 \endchange \bugonpage 1.80 second full paragraph, last line (23.03.29) 126 \becomes 124 \endchange \bugonpage 1.80 third full paragraph, line 4 (22.04.06) not greater than $F_k$, \becomes not greater than $F_k$, and $k>1$, \endchange \amendpage 1.83 replacement for {\eq(13)} (22.08.07) \noindent $$\phihat =1-\phi =-1/\phi={\textstyle\half }(1-\sqrt{5}\,).\eqno(13)$$ \endchange \bugonpage 1.85 in exercises 22 and 23 (22.04.06) \ninepoint number. \becomes number when $n\ge0$.\nl [And exercise 25 should also specify that $n\ge0$.] \endchange \improvepage 1.85 in exercise 29{(a)} (23.03.29) $0\le k\le n\le 6$ \becomes $0\le k,n\le 6$ \endchange \bugonpage 1.86 in exercise 31 (22.04.06) \ninepoint $\phi^{-2n-1}\!@$. \becomes $\phi^{-2n-1}\!@$, when $n\ge0$. \endchange \amendpage 1.88 line $-10$ (22.08.09) simplest example \becomes simplest nontrivial example \endchange \amendpage 1.92 replacement for {\eq(33)} (24.01.14) \noindent $$h_m=\sum_{1\le j_1\le \cdots \le j_m\le n}x_{j_1}\,\ldots\,x_{j_m};\qquad h_0=1. \eqno(33)$$ \endchange \bugonpage 1.93 replacement for {\eq(39)} (23.03.12) $$h_m={1\over m}(S_1h_{m-1}+S_2h_{m-2}+\cdots+S_mh_0),\qquad m\ge1.\eqno(39) $$ \endchange \bugonpage 1.93 line $-3$ (23.03.29) picture writing \becomes picture-writing \endchange \amendpage 1.94 replacement for second line of exercise 10 (24.01.14) \ninepoint\noindent $$e_m=\sum_{1\le j_1<\cdots 0$, \dots\ step. (After this operation, \becomes\nl While $\.{PARENT[$@j$]}>0$, set $j\gets \.{PARENT[$@j$]}$. Then, while $\.{PARENT[$k$]}>0$, set $k\gets \.{PARENT[$k$]}$. (After these loops, \endchange \amendpage 1.371 line 1 of exercise 11 (23.11.17) \ninepoint delete `(R.\ C.\ Prim, \dots 1389--1401.)' \endchange \improvepage 1.371 line $-4$ of exercise 11 (23.07.07) minimal cost tree \becomes minimum cost tree \endchange \bugonpage 1.376 line 2 of exercise 1 (23.07.07) \ninepoint simple oriented path \becomes simple oriented path or cycle \endchange \amendpage 1.388 line 4 after {\eq(7)} (23.01.15) $n-s_j\le s_j$ \becomes $n-s_j\le s_j=\max(s_1,s_2,\ldots,s_k)$ \endchange \bugonpage 1.406 line $-6$ (23.07.07) (1919), 7 \becomes (1919), 7:3--7:33 \endchange \bugonpage 1.408 line 2 of exercise 2 (23.07.07) $r$-sided polygon \becomes $r$-sided convex polygon \endchange \bugonpage 1.421 line $-16$ (23.07.07) 338--343 \becomes 338--346 \endchange \bugonpage 1.433 line 14 (23.07.07) (Syracuse, N.Y.: 1962) \becomes (Syracuse, N.Y.:\ 1962), 74--75 \endchange \bugonpage 1.457 line 7 (23.03.29) Reading, Mass. \becomes Cambridge, Mass. \endchange \bugonpage 1.458 line 7 (23.07.07) 61--70 \becomes 61--79 \endchange \bugonpage 1.461 line 24 (23.07.07) 578--588 \becomes 578--589 \endchange \amendpage 1.462 line 9 (23.07.07) Press, 1969) \becomes Press, 1969), 1--75 \endchange \bugonpage 1.462 line 12 (23.07.07) 567--643 \becomes 547--643 \endchange \amendpage 1.465 date of the Sherlock Holmes quote (03.07.07) {\eightss (1888) \becomes (1914)} \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \amendpage 1.466 new answer for Notes on the Exercises (23.11.24) \ans2. They help you to lodge ideas in your brain. \endchange \amendpage 1.469 and 470 (24.02.07) [renumber equations formerly numbered \eq(5) through \eq(19) to be \eq(6) through \eq(20)] \endchange \amendpage 1.471 append a new paragraph to answer 1 (22.03.01) \em Note: We might also say that $a_2+\cdots+a_0=\sum_{j=2}^0a_j$, and that $\sum_{j=p}^q a_j+\sum_{j=q+1}^r a_j=\sum_{j=p}^r a_j$, using the left half of~\eq(1). On the other hand, we should {\it not\/} replace $\cdots$ using the right half of~\eq(1)! The sum $\sum_{2\le j\le 0}a_j$ is~0, by~\eq(2). \endchange \amendpage 1.472 new copy for end of answer 30 (22.07.01) exercise~46.) \becomes exercise~46. Cauchy's sums were extended to integrals by V.~Bouniakowsky [{\sl M\'em.\ Acad.\ St.-P\'etersbourg\/ \rm(7) \bf1} (1859), No.~9, 4] % page 4 of 18 and H.~A. Schwarz [{\sl Acta Societatis Scientiarum Fennic\ae\/ \bf15} (1885), 315--362].) \endchange \amendpage 1.473 last line of answer 35 (24.02.07) $\sup\bigl(\sup$ \becomes $\max\bigl(\sup$ \endchange \bugonpage 1.481 line $-2$ of answer 20 (23.01.19) less than \becomes at most \endchange \bugonpage 1.485 line 3 of answer 22 (23.01.19) $(-1)^{k-1}$ \becomes $(-1)^k$ \endchange \amendpage 1.486 replacement for answer 30 (23.03.29) \ans30. Apply \eq(6) and \eq(19) to get $$\sum_{k\ge 0}\Bigl({n+k\atop n-m-k}\Bigr) \Bigl({-k-1\atop k}\Bigr){1\over k+1}.$$ Now we can apply Eq.~\eq(26) with $(r,s,t,n)=(-1,2n-m,1,n-m)$, obtaining $$\Bigl({n-1\atop n-m}\Bigr).$$ This result is the same as our previous formula, when $n$ is positive; but when $n=0$ the answer we have obtained is correct while ${n-1\choose m-1}$ is not. Our derivation has a further bonus, since the answer $\smash{n-1\choose n-m}$ is valid for $n\ge 0$ and {\it all\/} integers $m$. \endchange \bugonpage 1.486 line 2 of answer 31 (23.03.29) 38--57 \becomes 37--57 \endchange \bugonpage 1.489 line 1 of answer 58 (23.03.29) {\sl Arithmetik\/} \becomes {\sl Arithmetik\/ \bf2} \endchange \bugonpage 1.490 line 8 of answer 62 (23.03.29) 285--289 \becomes 284--289 \endchange \bugonpage 1.492 replacement for answer 9 (22.03.01) \ans9. $(n=0?\ 0{:}\ {-1}/n)$. \endchange \amendpage 1.493 new answer for end of section 1.2.7 (22.03.01) \ans25. $H_n^{(0,v)}=\sum_{k=1}^n k^{1-v}=H_n^{(v-1)}$ and $H_n^{(u,0)}=\sum_{k=1}^n H_k^{(u)}$; so the identity generalizes~\eq(8). [See L.~Euler, {\sl Novi Comment.\ Acad.\ Sci.\ Pet.\ \bf 20} (1775), 140--186, \S2.] \endchange \amendpage 1.494 new answer for exercise 31 (23.03.29) \ans31. Use exercise 11. \endchange \bugonpage 1.495 line 1 of answer 37 (23.11.15) {\bf 1} (December \becomes {\bf 1},\thinspace4 (December \endchange \bugonpage 1.495 replacement for last line of answer 37 (23.03.29) \noindent by A. J. Schwenk [{\sl Fibonacci Quarterly\/ \bf 8} (1970), 225--234, 241]. \endchange \bugonpage 1.497 line 5 of answer 11 (23.03.29) {\sl Invention Nouvelle en Alg\'ebre\/} \becomes {\sl Invention Nouvelle en l'Algebre\/} \endchange \amendpage 1.497 in answer 17 (23.03.29) [change $\scriptstyle k$ to $\scriptstyle k\ge0$ in the last two sums] \endchange \bugonpage 1.498 replacement for reference at end of answer 21 (23.03.29) [See K.~Knopp, {\sl Theory and Application of Infinite Series}, 2nd ed.\ (Glasgow: Blackie, 1951), Section 66.] \endchange \bugonpage 1.500 replacement for line 3 of answer 10 {(because $B_1=\half$)} (23.03.29) $$H_M-\sum_{m=1}^M \Bigl(1-{m\over M}\Bigr)^{\!n}m\_= H_n+\sum_{k=1}^n \left(\Bigl({n\atop k}\Bigr)-1\right) B_kM^{-k}k\_ -{n-1\over M}.$$ \endchange \amendpage 1.502 replacement for line 5 of answer 21 (23.04.25) \noindent $p\ge\half$. Still further work yields the upper bound $\exp\big({-}\sum_{k\ge1}2^{2k-1}\epsilon^{2k}\!/(2k^2-k)\bigr) \le\exp(-2\epsilon^2n)$, valid for all~$p$.) \endchange \amendpage 1.502 append new sentence to answer 22{(b)} (23.05.22) The slightly more complicated bound $e\losup{-\delta^2\!/(2+\delta)}$ can be used for all $\delta\ge0$, because $2\delta/(2+\delta)\le\ln(1+\delta)$. \endchange \bugonpage 1.502 line 2 of answer 22{(c)} (23.03.29) it is 1/2 \becomes it is $<1/2$ \endchange \improvepage 1.503 line 1 of answer 3 (23.03.29) $(m)!$ \becomes $m!$ \endchange \bugonpage 1.504 line 6 of answer 7 (23.03.29) 122--158 \becomes 122--138 \endchange \bugonpage 1.520 line $-3$ of answer 19 (23.03.29) {\sl Philomathique\/} \becomes {\sl philomatique\/} \endchange \bugonpage 1.523 in answer 13 (23.03.29) $X[i]=-j$ if and only if $i$ goes \becomes $X[i]=-j$ if and only if no number $>m$ goes to $i$ under~$\pi$, but $i$ goes \endchange \amendpage 1.524 append a sentence to answer 21 (23.04.10) (See also answer 1.2.5--21.) \endchange \bugonpage 1.525 last line of answer 23 (22.11.10) 373 \becomes 343 \endchange \amendpage 1.527 new answer (23.03.24) \ans38. (a) Obviously $\pi=\tau^-\pi\tau$ $\iff$ $\tau\pi=\pi\tau$. (b) $\pi^\tau$ takes $b_{ij}\mapsto a_{ij}\mapsto a_{i(j+1)}\mapsto b_{i(j+1)}$, if we regard $i(l_i{+}1)$ as $i1$. (c)~One of the $6\cdot3\cdot2$ solutions is $\tau=(1\,8)(2\,7)(3\,6)(4\,5)$. Others are $\tau=(2\,3)(7\,8)$; $\tau=(1\,6\,2\,8\,3\,7)$. (d)~None. (e)~True. (f)~True. [See E.~Netto, {\sl The Theory of Substitutions and its Applications to Algebra\/} (1892), \S46.] \endchange \amendpage 1.536 line 3 of answer 4 (23.07.07) divide a polygon \becomes divide a convex polygon \endchange \amendpage 1.537 line $-4$ (23.07.07) $\displaystyle \sum_{n,m}$ \becomes $\displaystyle \sum_{m,n\ge0}$ \endchange \amendpage 1.538 lines 3 and 4 of answer 5 (23.07.07) is impossible, since \dots yet \becomes is impossible: It means that $p_i$ must go off before $p_j$ is put on, and then $p_k$, yet \endchange \amendpage 1.562 bottom line (22.09.13) Charles's \becomes Charles III's \endchange \bugonpage 1.565 line 4 of answer 13 (23.07.07) go on to~T6 \becomes go on to~T6$'$ \endchange \bugonpage 1.576 beginning of answer 14,\thinspace15 (22.11.01) Hussain Zedan \becomes Hussein Zedan \endchange \amendpage 1.579 new paragraph at end of answer 11 (23.11.17) \em References: V$\?$. $\!$Jarn{\'\i}k, $\?${\sl Acta Societatis Scientiarum Naturalium Moravic{\ae}\/ \bf6} (1930), 57--61; R.\ C.\ Prim, {\sl Bell System Technical Journal\/ \bf 36} (1957), 1389--1401. \endchange \amendpage 1.586 in lines 3 and 4 of answer 4 (23.07.07) $n\times n$ solution(s) \becomes $n\times n$ tiling(s) \endchange \amendpage 1.587 replacing the the last lines of answer 5 (23.01.31) In 1974, \dots\ Chapters 1--2]. \becomes \indent After many decades of improvements, an optimum solution has finally been found: E.~Jeandel and M.~Rao [{\sl Advances in Combinatorics\/} (2021) 1:1--1:39] constructed a set of eleven tetrad types, using only four colors, that tiles the plane only nontoroidally. They also proved that no solution with fewer types or fewer colors is possible. \endchange \bugonpage 1.598 line $-6$ of answer 3 (22.11.10) {\sl Discrete Math.\ \bf64} \becomes {\sl Discrete Math.\ \bf62} \endchange \bugonpage 1.600 line $-9$ (23.07.07) (1974) \becomes (1973) \endchange \bugonpage 1.605 in answer 6 (23.11.18) B3 \becomes B3$'$, B6 \becomes B6$'$, B2 \becomes B2$'$ \endchange \bugonpage 1.606 in answer 12 (23.07.07) B2 \becomes B2$''$, B3 \becomes B3$''$, B4 \becomes B4$''$, B5 \becomes B5$''$ \endchange \bugonpage 1.616 last line of answer 40 (23.07.07) 96--97 \becomes 96--99 \endchange \bugonpage 1.629 page numbers for Algorithms {2.3.5H and 2.3.5Z} (23.07.07) 605 \becomes 604 \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 1.630 and following (22.02.01) Miscellaneous changes to the existing index of Volume~1 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 Bouniakowsky, Viktor Iakowlewitch ({\rus Bunyakovski1i0, Viktorp2 Yakovlevichp2}), 472. % 51st Charles III, King of England, 310, 562. % 51st Commutative law, 165, 185. % 52nd Conjugate of a permutation, 185, 526. % 52nd Demuth, Howard B\period\ (= Bud), 120. % 52nd Furch, Robert Otto, 121. % 52nd Gardner, Martin, 19, 80. % 52nd Gersonides, \see Levi ben Gershom. % 52nd Gr\"unbaum, Branko, 384. % 52nd Hald, Anders Hjorth, 103. % 52nd Jarn{\'\i}k, Vojt\v ech, 579. % 52nd Jeandel, Emmanuel Christian Francis, 587. % 52nd Levi ben Gershom ({\heb\Hfn/\Hvv/\Hsh/\Hrr/\Hgg/ \Hfn/\Hbb/ \Hyy/\Hvv/\Hll/} = {\heb\Hgg/\Hgm/\Hbb/\Hll/\Hrr/}), 17. % 52nd Maurolico (= Mauro Lyco, born Marul{\`\i}), Francesco, 17. % 52nd Netto, Otto Erwin Johannes Eugen, 527. % 52nd Onodera, Rikio (\JC48:48:0:40% J3014 <000003000000000003c00000000003e00000000003e00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000007003c0c000007c03c0e000003f03c07000003f03c03c00% 003e03c01e00003e03c00f00003e03c00780003e03c003c0003e03c001e0007e03c001f0% 007c03c000f8007c03c000fc00f803c0007e00f803c0007f01f003c0007f03e003c0007f% 03e003c0007f07c003c0007f0fc003c0007f1f8003c0003f1e0003c0003f3c0003c0001e% f00003c00000c00003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000007c000000000ffc0000000001f80000000000f800000000007000000% >%% Unicode char "5c0f \JC48:48:0:40% J4478 <3000180000183c003c00003c3ffffefffffe3ffffe7ffffe3c3c3c0001fc3c3c3c0001f8% 3c3c3c0003f03c3c3c0003e03c3c3c0007803c3c3c1c07003c3c3c070c003c3c3c07c000% 3ffffc03e0003ffffc01f0003c3c3c01f0003c3c3c00f0003c3c3c00e00c3c3c3c00001e% 3c3c3fffffff3c3c3dffffff3c3c3c00f83f3c3c3c00f83e3ffffc00f87c3ffffc00f878% 3c3c3c00f8f0183c1800f8e0003c0000f9c0003c0000f980003c0000fb00003c1800fa00% 003c3c00f8003ffffe00f8001ffffe00f800003c0000f800003c0000f800003c0000f800% 003c0000f800003c0000f800003c0000f800003c3fc0f800007ffc00f800fffff000f800% ffff0000f8007ff80001f8007fe0003ff8007c000007f80020000001f00000000000e000% >%% Unicode char "91ce \JC48:48:0:40% J2791 <000003000000000003c00000000003e00000000003e00000000003c00000000003c00000% 000003c00300000003c0078003ffffffffc001ffffffffc0000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c0000c000003c0001e% ffffffffffff7fffffffffff00000000000000000000c00000000000f00000000000f800% 00000000f83000000000f0783ffffffffffc1ffffffffffc00000000f00000000000f000% 00000000f000003c0000f000000f8000f0000007e000f0000003f000f0000001f800f000% 0000fc00f0000000fe00f00000007e00f00000007e00f00000003e00f00000003c00f000% 00000000f00000000001f0000000003ff0000000000ff00000000007e00000000003c000% >%% Unicode char "5bfa \JC44:48:-2:40% J4647 <00001c00000000001f00000000001f80000000001f80000000001f00000000001f000000% 00001f00000000001f00000000001f00000000001f00000000001f0001c000001f0003e0% 3ffffffffff01ffffffffff000003e0003e000003e0003e000003e0003e000003e0003e0% 00003e0003e000003e0003e000003e0003e000003e0003e000003c0003e000007c0003e0% 00007c0007c000007c0007c000007c0007c00000f80007c00000f80007c00000f80007c0% 0000f00007c00001f00007800001f0000f800003e0000f800003c0000f800007c0000f80% 000780000f80000f00001f80000f00001f00001e00001f00003c00003f00007800003f00% 00f00000fe0003e000fffe000780003ffe000f00000ffc003c000007f800f0000003e000% >%% Unicode char "529b \JC44:48:-2:40% J3543 <0c00000007000e0000000f800fffffffffc00fffffffffc00f000f000f000f000f000f00% 0f000f000f000f000f000f000f000f000f000f000f000f000fffffffff000fffffffff00% 0f000f000f000f000f000f000f000f000f000f000f000f000f000f000f000f000f000f00% 0fffffffff000fffffffff000f0000000f0006000000060000007c00000000007e000000% 00003f00000000003e00000000003c0001c000003c0003e0fffffffffff07ffffffffff0% 00003c0003c000003c0003c000003c0003c000003c0003c000003c0003c00000780003c0% 0000f00003c00001e00003c00003c00003c00007800003c0000f000003c0001e000007c0% 003c00000f8000f800001f0003e00007fe000f800003fc00fe000001f800f0000000f000% >%% Unicode char "7537 ), 582. % 52nd Prim, Robert Clay, 579. % 52nd Rao, Micha\"el, 587. % 52nd Real part of complex number, 21, 94. % 52nd Schwarz, Karl Hermann Amandus, inequality, 36, 472. % 51st Shephard, Geoffrey Colin, 384. % 52nd Slesvig-Holsteen-S{\o}nderborg-Gl\"ucksborg, Christian af, \see Christian~IX. % 52nd Strongly zero, 57. % 51st Zedan, Hussein Saleh Mahmoud\indexbreak ({\arab\An/\Aa/\Afd/\Aiy/\Az/ \Ad/\Afw/\Amm/\Amhh/\Aim/ \Afhh/\Ail/\Afa/\Aiss/ \Afn/\Amy/\Ams/\Aihh/}), 576. % 51st Zorn, Max August, lemma, 547. % 52nd Zuse, Konrad Ernst Otto, 457. % 52nd \vfill \enddoublecolumns \endchange \bye [The next printing will be the 53rd.] Not mentioned above: page iv, http: -> https: the change to page 17 affects pages 15 and 16 page 41, the period in Theorem F should be bold the change to page 60 affects page 61 page 64, better spacing in (37) page 66, better spacing in the first $n\brack k$ and $n\brace k$ page 71, better spacing in exercise 32 page 71, these -> those in exercise 36 page 72, better spacing in exercise 39 page 74, better spacing in exercise 64 page 81, the period in Theorem A should be bold the change to page 241 affects page 242 page 271, reformat B=0 and B=-1 on line -9 page 280, first sentence of 2.2.5, italicize "two"; tune up the following copy too page 341, \.{TREE(0)} \becomes \.{TREE($0$)}, etc. page 344, \.{TREE(0)} \becomes \.{TREE($0$)}, etc. page 347, several pairs of brackets in exercise 18 should be in \tt page 360, tiny repositioning of the label X_{10} in exercise 11 page 373, punctuation after part a) of the definition (line 5 should end with ;) page 382, fix style of Theorem K page 386, \ldots not \cdots in (2) page 419, not \tt parens on line -2 page 426, bold period in Operation 1., etc page 459, line -4, (1961) page 491, better spacing in answer 64 the change to page 527 affects page 526 page 535, bad spacing in line 1 of step D1 page 541, ${\rm I}_2$ in answer 6 page 547, space after '' in line -6 of answer 14 page 562, line 16: "Examples (b), (c):" page 565, line -1 of answer 11, Probability and Computing page 580, reformatted references in answer 12 page 582, better spacing in line -2 of answer 17 page 593, removed spurious parens in lines -10 and -9 ARTICLES "TO APPEAR" THAT ARE STILL PENDING: