% CHANGES TO FASCICLE V4F4 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2006,2007,2008 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 err4f4" \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{\hss\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill\hss}} \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 4 FASCICLE 4} \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~4, Fascicle~4, since it was first printed in 2006. \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 Volumes 1--5 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~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, March 2006} \bigskip \bigskip {\quoteformat 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) \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 4 FASCICLE 4 %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{\kern-16ptCHANGES TO V4F4: GENERATING ALL TREES; HISTORY OF GENERATION} \def\rhead{CHANGES TO V4F4: GENERATING ALL TREES; HISTORY OF GENERATION\kern-16pt} \titlepage \volheadline{GENERATING TREES; HISTORY} % the fascicle title \bigskip \rightline{Copyright \copyright\ 2006, 2007, 2008, 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 4f4.v replacement for lines 1--18 (07.02.02) \noindent {\bf A note on notation.} Near the beginning of Chapter 7, some operations on graphs are defined for which many different notations are presently rampant. If $G$ is a graph on the vertices $U=\{u_1,\ldots,u_m\}$ and if $H$ is a graph on the vertices $V=\{v_1,\ldots,v_n\}$, larger graphs can be constructed in two ``additive'' and five ``multiplicative'' ways, as follows. \def\\{\smallskip\item{$\bullet$}} \\$G\dirsum H$ is the direct sum, aka juxtaposition, of $G$ and $H$: It has the $m+n$ vertices $U\cup V$ and the edges of $G$ and $H$. \\$G\join H$ is the join of $G$ and $H$: On the vertices $U\cup V$, its edges are those of $G$ and $H$, plus all $u_j\adj v_k$ for $1\le j\le m$ and $1\le k\le n$. \\$G\cprod H$ is the Cartesian product of $G$ and $H$: It has the $mn$ vertices $U\times V$; its edges are $(u,v)\adj(u',v)$ when $u\adj u'$ in~$G$, and $(u,v)\adj(u,v')$ when $v\adj v'$ in~$H$. \\$G\dprod H$ is the direct product, aka conjunction, of $G$ and~$H$: Again its vertices are $U\times V$, but its edges are $(u,v)\adj(u',v')$ if and only if $u\adj u'$ in~$G$ and $v\adj v'$ in~$H$. \\$G\sprod H$ is the strong product of $G$ and~$H$: As its symbol implies, it combines the edges of $G\cprod H$ and $G\dprod H$. \\$G\oprod H$ is the odd product of $G$ and $H$: On the vertices $U\times V$, its edges are $(u,v'\adj(u',v')$ if and only if $u\adj u'$ in~$G$ or $v\adj v'$ in~$H$, but not both. \\$G\lprod H$ is the lexicographic product, aka composition, of $G$ and $H$: Again on vertices $U\times V$, it has the edge $(u,v)\adj(u',v')$ if and only if we have either (i)~$u\adj u'$ in~$G$ or (ii)~$u=u'$ and $v\adj v'$ in~$H$. \endchange \amendpage 4f4.1 replacement for line 4 (07.06.13) {\sl 2006 and 2007\/} \becomes {\sl 2008} \endchange \bugonpage 4f4.12 line 8 (06.08.26) 508--515 \becomes 508--516 \endchange \bugonpage 4f4.15 {(and throughout the fascicle!)} (08.04.04) \ninepoint{\bf Fig.\ 36} \becomes {\bf Fig.\ 56} [and all figure numbers need to increased by 20] \endchange \amendpage 4f4.19 line $-9$ (06.10.18) Section 7.1 \becomes Section 7.1.3 \endchange \bugonpage 4f4.21 line $-2$ (06.07.25) Table 8 \becomes Table 4 \endchange \bugonpage 4f4.25 line 8 (07.12.08) (1999) \becomes (1997) \endchange \amendpage 4f4.31 notational changes in Table 5 (07.02.02) $P_4\times P_4$ \becomes $P_4\cprod P_4$, $P_5\times P_5$ \becomes $P_5\cprod P_5$, etc. \endchange \bugonpage 4f4.32 line 16 (06.04.24) 137--142 \becomes 137--140 \endchange \amendpage 4f4.45 notational changes in exercises 105 and 106 (07.02.02) \ninepoint $G'\times G''$ \becomes $G'\cprod G''$, $G'\cnj G''$ \becomes $G'\dprod G''$, $G'\scnj G''$ \becomes $G'\sprod G''$, etc. (These changes also affect the answers to exercises 105--108.) \endchange \amendpage 4f4.45 new parts to exercise 105 (07.04.05) \ninepoint \item{h)} $G=G'\?\oprod G''$ is the odd product of regular graphs $G'$ and $G''$. \item{i)} $G=G'\?\lprod G''$ is the lexicographic product of regular graphs $G'$ and $G''$. \smallskip\noindent[Also the rating changes from [{\it\HM37\/}] to [{\it\HM38\/}].] \endchange \amendpage 4f4.46 the rating of exercise 121 (06.05.29) \ninepoint [{\it M32\/}] \becomes [{\it M34\/}] \endchange \improvepage 4f4.50 line $-5$ (06.01.12) code-names \becomes code names \endchange \bugonpage 4f4.54 lines 21 and 23 (06.01.12) line 21 (in Eq.~\eq(10)): $3@1@2@4-4@3@2@1$ \becomes $3@1@2@4-4@3@1@2$\nl line 23: ${}-a_4b_3c_2d_1$ \becomes ${}-a_4b_3c_1d_2$ \endchange \improvepage 4f4.54 bottom line (06.01.12) {\eightssi Bh\=askara\/} \becomes {\eightss BH\=ASKARA} \endchange \improvepage 4f4.61 line 7 (06.03.19) radix-2 arithmetic \becomes radix-2 numbers \endchange \improvepage 4f4.71 line $-6$ (08.03.24) Erd\H{o}s \becomes Erd\"os \qquad[to agree with the English spelling in the paper cited] \endchange \bugonpage 4f4.74 new wording for exercise 15 (06.03.19) \ninepoint \ex 15. [15] If all $n$-combinations $x_1\ldots x_n$ of $\{1,\ldots,m\}$ with repetition are listed in lexicographic order, with $x_1\le\cdots\le x_n$, how many of them begin with the number~$j$? \endchange \bugonpage 4f4.74 in exercise 17 (06.01.12) \ninepoint algorithm of exercise 15 \becomes algorithm of exercise 16 \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \amendpage 4f4.80 line 5 (07.01.01) 488--497] \becomes 488--497; {\bf49} (2006), 351--357] \endchange \amendpage 4f4.87 line 2 of answer 40 (06.10.18) 7.1--\eq(00) \becomes 7.1.3--\eq(36) \endchange \amendpage 4f4.88 new sentence for the end of answer 45 (07.04.26) {\sl[See the addendum on page 105.]} \endchange \amendpage 4f4.100 line $-2$ (07.04.03) Kronecker product \becomes direct product \endchange \amendpage 4f4.101 in answer 105{(e)} (07.04.05) line 1: $d'$\becomes$d$ \quad(twice)\nl line 2: $e_{ij}$\becomes$a_{ij}$ \endchange \amendpage 4f4.101 new paragraphs for answer 105 (07.04.05) \indent(h) When $G'$ is regular, we can make $S^-A'S$ a diagonal matrix with entries $d'-\alpha'_j$, while simultaneously $S^-J_{n'}S$ is a diagonal matrix with entries $(n',0,\ldots,0)$, because $(1,\ldots,1)^T$ is an eigenvector of both $A'$ and $J_{n'}$. Thus, by the formula of answer 7--96(c), the aspects turn out to be $\{d+(d'-\alpha'_j-n'\[j=0])(d''-\alpha''_k) +(d'-\alpha'_j)(d''-\alpha''_k-n''\[k=0]\mid 0\le jn$. \algstep B4*. [Demote $r_j$.] Set $x\gets r_j$, $r_j\gets r_x$, $r_x\gets0$, $z\gets c_j$, $c_j\gets x$. If $z>0$, set $r_x\gets x$; otherwise set $l_j\gets x$. Return to B2*.\quad\slug \smallskip\noindent If the values of $r_1$ and $c_1$ are maintained in registers, this algorithm needs only $4C_n+C_{n-1}+4(C_{n-1}+C_{n-2}+\cdots+C_0)+3n-6 =(67/12+73/(24n)+O(n^{-2}))@C_n$ mems to generate all $C_n$ trees. [See W.~Skarbek, {\sl Fundamenta Informatic{\ae} \bf75} (2007), 505--536.] \endchange \amendpage 4f4.106 lines 1--4 of answer 4 (07.04.26) this glitch \dots~this flaw. \becomes similarly, one $\vcenter{\epsfbox{\figdir/donnolo-30721.eps}}$ on line 8 should be $\vcenter{\epsfbox{\figdir/donnolo-37021.eps}}@$. And the six cases with rightmost letters $\vcenter{\epsfbox{\figdir/donnolo-73.eps}}$ appear twice, in lines 3 and~4, while the cases with rightmost $\vcenter{\epsfbox{\figdir/donnolo-23.eps}}$ are missing. These glitches are probably typographical and/or scribal errors, not made by Donnolo himself. \endchange \amendpage 4f4.106 line 4 of answer 6 (07.07.03) 1975 \becomes 1963 \endchange \bugonpage 4f4.107 line 2 of answer 8 (06.01.12) $ a_1a_{n-1}\ldots a_na_3a_2$ \becomes $ a_1a_4\ldots a_na_3a_2$ \endchange \improvepage 4f4.107 replacement for the last line of answer 8 (06.01.12) $\pm a_1\ldots a_{n-1}$ of $\{1,\ldots,n-1\}$ yields $n$~others, $\pm a_1\ldots a_{n-1}a_n\mp a_1\ldots a_{n-2}a_na_{n-1} \pm\cdots{}$. \endchange \bugonpage 4f4.109 answer 22 (06.01.12) line 11: exercise 20(c) \becomes exercise 21(c)\nl line 14: exercise 18 \becomes exercise 19 \endchange \amendpage 4f4.110 line $-3$ of answer 26 (06.12.27) closed form. \becomes closed form, although it does satisfy the interesting functional relation $1+zB(z)=B(z/(1+z))$. \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 4f4.112 and following (06.03.19) Miscellaneous changes to the existing index of Volume~4 Fascicle~4 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:} \hangindent2em $C_n$ (cycle graph), 43, 98, 101. % 2nd Combinations, null, 61. % 2nd Combinations, of a multiset, 60, 74, 111. % 2nd Composition of graphs, v, 45. % 2nd Cycle graph ($C_n$), 43, 98, 101. % 2nd Direct product of matrices, 100. % 2nd Direct sum of graphs, v, 45. % 2nd Errors, 49, 52--54, 60, 64--65, 67, 73--75, 109, 111. % 2nd Feussner, Friedrich Wilhelm, 24. % 2nd Fibonacci, Leonardo, of Pisa (= Leonardo filio Bonacii Pisano), numbers, 50, 106. % 2nd Hariharan, Ramesh ({\tm\\205\\125\kern-.1em\\203\\161 \\213\\235\\213\\205\\150}), 99. % 2nd Ibn Mun`im, A\d{h}mad al-`Abdar\ii\indexbreak ({\arab\Afm/\Amai/\Amn/\Aim/ \Afn/\Aib/ \Ay/\Ar/\Afd/\Amb/\Amai/\Ail/\Aa/ \Afd/\Amm/\Aihh/\Aha/}), 61. % 2nd Japanese mathematics, 54, 65--67, 75. % 2nd Jesus of Nazareth, son of Joseph\indexbreak % John 1:45, cf also Mt 21:11, Mk 1:9, Ac 10:38 ({\heb\Htv/\Hrr/\Hts/\Hnn/ \Hfn/\Hbb/ \Hfp/\Hss/\Hvv/\Hyy/ \Hfn/\Hbb/ \Hai/\Hvv/\Hsh/\Hyy/}, % from Peshitta {\grk >Ihso=us \indexbreak u>i`os to=u >Iws`hf ap`o Nazar'ej}), 53. % 2nd Jewish mathematics, 52, 59, 108. % 2nd Lexicographic order, 4--5, 21, 23, 33, 39, 42, 49, 53, 55, 56, 61, 67, 68, 70, 71, 74, 108, 110, 111. % 2nd Lexicographic product of graphs, v, 45. % 2nd Meters, poetic, 49--52, 54, 62--65, 70, 74--75. % 2nd Metrical feet, 51, 63, 74--75. % 2nd Multicombinations: Combinations with repetition, 55--56, 61, 74. % 2nd Multiset combinations, 60, 74, 111. % 2nd Multiset permutations, 53, 62, 64, 69. % 2nd Notational conventions:\indexnoperiod % 2nd \sub $G\dirsum H$, $G\join H$, $G\cprod H$, $G\dprod H$, $G\sprod H$, $G\oprod H$, $G\lprod H$, v. % 2nd Odd product of graphs, v, 45. Permutations of a Latin verse, 62--65, 74--75. % 2nd Permutations of a multiset, 53, 62, 64, 69. % 2nd Permutations, restricted, 63--65, 74--75. % 2nd Poetry, meters for, 49--52, 54, 62--65, 70, 74--75. % 2nd Radix-2 number system, 49, 52, 61. % 2nd Ramesh, Hariharan ({\tm\\205\\125\kern-.1em\\203\\161 \\213\\235\\213\\205\\150}), 99. % 2nd Recursive algorithms, 68--69, 73, 75. % 2nd Reverse lexicographic order, 56, 67, 68, 111. % 2nd Scoins, Hubert Ian, 23, 73. % 2nd (there were two entries, one in wrong spot) Skarbek, W{\l}adys{\l}aw Kazimierz, 6, 105. % 2nd Symmetric polynomials, 68, 110. % 2nd Tetragrams, 49. % 2nd Vakhovsky, Evgenii Borisovich ({\rus Vakhovskii0, Evgenii0 Borisovich}), 101. % 2nd Variations, 61, 74. % 2nd \vfill \enddoublecolumns \endchange \bye ******** I'm not sure yet about the Figure renumbering constant! ********** ******** (needs to be fixed also in err4f2 and err4f3) ******************** [The next printing will be the 3rd.] not listed above: ARTICLES "TO APPEAR" THAT ARE STILL PENDING: