% CHANGES TO VOLUME 1 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2011, 2012, 2013 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 2010)} \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 2011. 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--4A are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4B these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, 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 \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\ 2011, 2012, 2013 Addison\with Wesley; all rights reserved} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \amendpage 1.xvi line 16 (11.06.16) a {\it 45\/} rating \becomes a {\it 40\/} rating \endchange \amendpage 1.xvi line 20 (13.01.30) creativity.\ \becomes creativity. All exercises with ratings of {\it46\/} or more are open problems for future research, rated according to the number of different attacks that they've resisted so far. \endchange \improvepage 1.6 lines 1--3 (13.03.13) $\{m,n\}$ \becomes $m$ and $n$ [twice]\nl $\{n,r\}$ \becomes $n$ and $r$ [twice] \endchange \improvepage 1.8 lines $-5$ and $-4$ (13.03.13) Such a computational method \dots\ it is also \becomes Every step of such a computational method is clearly effective, and experience shows that pattern-matching rules of this kind are also \endchange \improvepage 1.18 clarification in exercise 4 (13.02.10) \ninepoint $\phi^{n-2}$. \becomes $\phi^{n-2}$ for all positive integers $n$. \endchange \improvepage 1.19 clarification in exercise 5 line 1 (13.02.05) exact divisors \becomes positive integer divisors \endchange \improvepage 1.22 lines 1 and 3 after {\eq(8)} (13.01.20) $10^x$ \becomes $b^x$ \qquad[two places] \endchange \bugonpage 1.27 line 1 (11.07.22) \ninepoint $n>1$ \becomes $n>1$ and $n\ne e$. \endchange % actually I've also changed $n$ to $x$ in this exercise \amendpage 1.79 new exercise for Section 1.2.7 (13.02.11) \ninepoint \ex25. [M21] Let $H_n^{(u,v)}=\sum_{1\le j\le k\le n}1/(j^uk^v)$. What are $H_n^{(0,v)}$ and $H_n^{(u,0)}$? Prove the general identity $H_n^{(u,v)}+H_n^{(v,u)}=H_n^{(u)}H_n^{(v)}+H_n^{(u+v)}$. \endchange \amendpage 1.104 new sentence preceding the exercises (12.07.19) \noindent[S.~Bernstein had contributed key ideas in {\sl Uchenye zapiski Nauchno-\nl\quad Issledovatel'skikh kafedr Ukrainy\/ \bf1} (1924), 38--48.] \endchange \amendpage 1.111 line above Fig.~12 (12.07.08) {\sl Petropoli\-tan\ae\/} \becomes {\sl Imperialis Petropoli\-tan\ae\/} \endchange \amendpage 1.114 line 7 (13.02.26) is less than \becomes is less in absolute value than \endchange \improvepage 1.116 line 2 of exercise 8 (12.02.18) ${cn^2\choose n}\big/c^n{n^2\choose n}$ \becomes ${cn^2\choose n}\big/\bigl(c^n{n^2\choose n}\bigr)$ \endchange \amendpage 1.144 line 2 (11.11.29) \ninepoint to zero. \becomes to zero, and the overflow toggle is cleared. \endchange \amendpage 1.151 line $-11$ (11.11.29) {\sl set to zero\/} \becomes {\sl set to positive zero\/} \endchange \bugonpage 1.229 line 11 (11.02.06) {\sl Mechanization\/} \becomes {\sl Mechanisation} \endchange \amendpage 1.242 line 2 (12.04.28) top, front \becomes top, bottom, front \endchange \bugonpage 1.268 program line {\it 71\/} (12.06.30) \ninepoint \tt QLINK(F) \becomes QLINK[F] \endchange \improvepage 1.275 line 7 (12.09.06) list have \becomes list must have \endchange \amendpage 1.303 in the line before {\eq(13)} (11.08.29) transformation: \becomes transformation (see M.~H. Doolittle, {\sl Report of the Superintendent of the U.~S. Coast and Geodetic Survey\/} (1878), 115--120): \endchange \amendpage 1.331 rating of exercise 14 (12.08.15) \ninepoint {\it22\/} \becomes {\it20\/} \endchange \bugonpage 1.339 replacement for line 17 (11.03.14) $$D(y)=3\bigl( 1/(x+1)\bigr) -\bigl(-(a(2x))/(x^2)^2\bigr),\eqno(21)$$ \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \amendpage 1.467 new line at end of answer 8 (13.04.29) \noindent Each iteration either decreases $m$ or keeps $m$ unchanged and decreases~$n$. \endchange \amendpage 1.469 new lines at end of answer 8 (13.02.26) \noindent This construction can't make $d_k=9$ for all $k>l$, because that could happen only if $(n+d_1/10+\cdots+d_l/10^l+1/10^l)^m\le u$. \endchange \improvepage 1.470 in step E1 of answer 28 (11.10.28) If $1-\epsilon$ \dots $k\gets1$. \becomes Set $x\gets1-\epsilon-x$, $y\gets y_0$, and $k\gets1$, where $1-\epsilon$ is the largest possible value of~$x$, and $y_0$ is the nearest approximation to $b^{1-\epsilon}$. \endchange \amendpage 1.472 new copy for end of answer 31 (11.10.20) Consequently we have $\bigl(\sum_{j=1}^n u_j\bigr)\bigl(\sum_{j=1}^n v_j\bigr) \le n\sum_{j=1}^n u_jv_j$ when $u_1\le u_2\le\cdots\le u_n$ and $v_1\le v_2\le\cdots\le v_n$, a result known as {\it Chebyshev}'s monotonic inequality. [See {\sl Soobshch.\ mat.\ obshch.\ Khar'kovskom Univ.\ \bf4},\thinspace2 (1882), 93--98.] \endchange \amendpage 1.474 lines 3--5 of answer 43 (11.11.26) as in exercise 44 \dots\ $(x_i-1)\bigr)$. \becomes by setting $x=1$ in exercise~40 and obtaining ${\prod_{k\ne i}(x_k-1)/x_i\prod_{k\ne i}(x_k-x_i)}$. After multiplying numerator and denominator by $x_i-1$, we can sum on $i$ by applying exercise~33 with $r=0$ to the $n+2$ numbers $\{0,1,x_1,\ldots,x_n\}$. \endchange \amendpage 1.491 replacement for last line of answer 67 (12.02.18) ${n\choose k}\ge\bigl({(n-k+1)e\over k} \bigr){}^k{1\over ek}$, which is less memorable (but often sharper) than ${n\choose k}\ge\bigl({n\over k}\bigr){}^k$. \endchange \amendpage 1.493 new answer for section 1.2.7 (13.02.11) \ans25. $H_n^{(0,v)}=\sum_{k=1}^nH_n^{(v)}$ and $H_n^{(u,0)}=H_n^{(u-1)}$; so the identity generalizes~\eq(8). [See L.~Euler, {\sl Novi Comment.\ Acad.\ Sci.\ Pet.\ \bf 20} (1775), 140--186, \S2.] \endchange \bugonpage 1.503 last line of answer 3 (13.03.05) 1937 \becomes 1927 \endchange \improvepage 1.504 last line of answer 8 (12.02.18) ${cn^2\choose n}\big/c^n{n^2\choose n}$ \becomes ${cn^2\choose n}\big/\bigl(c^n{n^2\choose n}\bigr)$ \endchange \improvepage 1.514 replacement for line 5 of the program (13.04.30) \nobreak\vskip-12pt\ansmixthree 3H \ \ \ &ENT2&9*8-8,1&Start at row 9.\cr \endmix \endchange \bugonpage 1.514 replacement for lines 19 and 20 of the program (13.03.10) \nobreak\vskip-12pt\ansmixthree PHASE2&ENT3&9*8 \ \ \ &At this point $\rA =\min_jC(j)$\cr 3H&ENT2&0,3&Prepare to search a row.\cr \endmix \endchange \bugonpage 1.552 in answer 12 (12.06.30) line 1: $29p$ \becomes $27p$\nl line 3: $3\over4$ \becomes 78\% \endchange \let\defaultpointsize=\tenpoint % begin appendices \amendpage 1.624 through page 626 (12.04.07) [replace the notation $(R\Relbar\joinrel\joinrel\joinrel\Rightarrow x;\;y)$ by $(R{?}\ x{:}\ y)$ in eleven places] \endchange \amendpage 1.628 new entries for Appendix C (11.04.17) \ninepoint\noindent Program 1.2.10M, 145, 186.\nl Program 1.4.3.1M, 204--211, 530.\nl Program 2.1A, 236.\nl Program 2.1B, 535.\nl Program 2.3.1S, 325. \endchange \bugonpage 1.629 in Appendix C (11.04.17) \ninepoint\noindent Algorithm 2.4B$'$, 606. \becomes Algorithm 2.4B$'$, 605. Algorithm 2.4B$''$, 606.\nl Algorithm 2.5G, 613. \becomes Algorithm 2.5G, 613--614. \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 1.630 and following (11.01.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 Bernstein, Sergei Natanovich ({\rus Bernshtei0n, Sergei0 Natanovich}), 104. %30th Chebyshev (= Tschebyscheff), Pafnutii Lvovich ({\rus Chebyshebp2, Pafnut{\char12}i0 Lp1vovichp2} = {\rus Chebyshev, Pafnutii0 Lp1vovich}), inequalities, 98, 104, 472. % 31st Depth of node in a tree, \see Level. % 30th Doolittle, Myrick Hascall, 303. % 29th $e$ (base of natural logarithms), 23, 619--620, 626. % 30th Empty list, 244--245, 247, 258, 260--261, 273--275, 278, 280, 540, 546. % 30th Euler, Leonhard ({\rus Ei0lerp2, Leonardp2} = {\rus E1i0ler, Leonard}), 49, 50, 52, 57, 75, 76, 87, 111, 374, 407, 472, 493, 496, 536, 600. % 31st GO button of \MIX, 126, 139, 143--144, 211. % 29th Nonnegative coefficients, 396, 501. % 30th Overflow toggle of \MIX, 126, 131, 134, 142, 144, 208, 214, 228. % 29th Pattern matching, 8. % 31st Staver, Tor B{\o}hm, 582. % 28th \vfill \enddoublecolumns \endchange \bye [The next printing will be the 31st.] Not mentioned above: Page 8 line 5, Note -> Notice Page 31, Example 3, better wording Page 79, wording of exercise 23 shortened to save a line Page 234, subtle correction to (3) Page 276, correcting the "nicked" plus and minus signs in the illustration Page 439, "random" edges have changed in the figs (henceforth will be stable) Page 468 answer 12 shortened to accommodate new material on page 469 Page 495, line 1 of answer 37, don't abbreviate Quarterly Page 551, correcting the "nicked" plus and minus signs in answer 6 Page 492, answer 22 moved here, to make room for the new answer 25 on page 493 ARTICLES "TO APPEAR" THAT ARE STILL PENDING: