% CHANGES TO VOLUME 1 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 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 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.13 add a sentence following line $-7$ (22.11.02) legitimate. \becomes legitimate. [Actually $P(0)$ does happen to 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.27 line 5 (22.03.01) following equivalent \becomes following essentially equivalent \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.80 third 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 \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 \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 \amendpage 1.144 line 15 or 16 (22.11.03) \ninepoint always greater than 100 \becomes always 0100 or more \endchange \bugonpage 1.148 line {\it 05\/} of Program P (22.08.28) \indent\.{EQU} \ \.{-1} \becomes \.{EQU} \ \.{99} % because of exercise 1.3.1--26 \endchange \amendpage 1.185 new exercise (23.03.24) \EX38. [M22] ({\it Conjugate permutations.}) When $\pi$ and $\tau$ are arbitrary permutations, the permutation $$\pi^\tau\;=\;\tau^-\pi\tau$$ is called ``the conjugate of $\pi$ by $\tau$.'' \item{a)} Prove that $\pi=\pi^\tau$ if and only if $\pi$ commutes with $\tau$. \item{b)} Suppose the cycle form of $\pi$ is $(a_{11}\ldots a_{1l_1})\ldots(a_{k1}\ldots a_{kl_k})$. Prove that the cycle form of $\pi^{\tau}$ is $(b_{11}\ldots b_{1l_1})\ldots(b_{k1}\ldots b_{kl_k})$, where $\tau$ takes $a_{ij}\mapsto b_{ij}$. \breathe\item{c)} Find all $\tau$ for which $\bigl((1\,2\,3)(4\,5)(6\,7\,8)\bigr){}^\tau=(8\,7\,6)(5\,4)(3\,2\,1)$. \item{d)} Find all $\tau$ for which $\bigl((1\,2\,3)(4\,5)(6\,7\,8)\bigr){}^\tau=(8\,7\,6\,5)(4\,3\,2\,1)$. \item{e)} True or false: Every permutation $\pi$ is congruent to its inverse, $\pi^-$. \item{f)} True or false: $(\pi\sigma)^\tau=\pi^\tau\sigma^\tau$ and $\pi^{(\sigma\tau)}=(\pi^\sigma)^\tau$, for all $\pi$, $\sigma$, and $\tau$. \endchange \bugonpage 1.276 line 1 of step A4 (22.12.01) $\.{LINK(Q1)}\gets \.Q\gets \.{LINK(Q)}$, \becomes $\.Q\gets \.{LINK(Q)}$, $\.{LINK(Q1)}\gets \.Q$, \endchange \amendpage 1.310 at the ``root'' of Fig.~{18(a)} (22.09.13) {\sixrm Charles} \becomes {\sixrm Charles III} \endchange \improvepage 1.349 line $-6$ (22.12.01) complete the most recent instance of an incomplete \.{RLINK}. \becomes set the \.{RLINK} field of the most recent node whose \.{RTAG} was blank. \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 \let\defaultpointsize=\ninepoint % get ready for answer pages \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 \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 \bugonpage 1.492 replacement for answer 9 (22.03.01) \ans9. $(n=0?\ 0{:}\ {-1}/n)$. \endchange \amendpage 1.493 new answer for 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 \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.562 bottom line (22.09.13) Charles's \becomes Charles III's \endchange \bugonpage 1.576 beginning of answer 14,\thinspace15 (22.11.01) Hussain Zedan \becomes Hussein Zedan \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 \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. % 53rd Conjugate of a permutation, 185, 526. % 53rd Gardner, Martin, 19, 80. % 52nd Gr\"unbaum, Branko, 384. % 52nd Jeandel, Emmanuel Christian Francis, 587. % 52nd Netto, Otto Erwin Johannes Eugen, 527. % 53rd Rao, Micha\"el, 587. % 52nd Schwarz, Karl Hermann Amandus, inequality, 36, 472. % 51st Shephard, Geoffrey Colin, 384. % 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 \vfill \enddoublecolumns \endchange \bye [The next printing will be the 53rd.] Not mentioned above: the change to page 60 affects page 61 page 129 under LDX: "This is" -> "This instruction is" page 129 under LD$i$: "This is" -> "These instructions are" page 134 under CMPX: "This is" -> "This instruction is" page 310, italicize "References" in the caption ARTICLES "TO APPEAR" THAT ARE STILL PENDING: