% CHANGES TO VOLUME 4A OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2011 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} \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 since it was first printed in 2011. \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 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 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 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 The time when\/ {\rm The Guardian} ceases to make mistakes altogether is not, at the moment, foreseeable. \author IAN MAYES (1998) % quoted in IHT, 17 Feb 98, p5 % he is Reader's Editor of the Manchester Guardian \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\ 2011, 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 \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\?} \amendpage 4a.viii line 11 (11.05.26) Section 7.2 \becomes Section 7.2.2 \endchange \amendpage 4a.xii line 16 (11.06.16) a {\it 45\/} rating \becomes a {\it 40\/} rating \endchange \amendpage 4a.1 line 18 (11.04.23) {\eightss (1927)} \becomes {\eightss (1926)} \endchange \bugonpage 4a.9 line 19 (11.04.23) ``Can toy problems be useful?'' \becomes ``Are toy problems useful?'' \endchange \bugonpage 4a.10 line 16 (11.04.23) {\eightssi good society} \becomes {\eightssi good Society} \endchange \bugonpage 4a.10 line $-12$ (11.01.31) (see page ii) \becomes (see page iv) \endchange \improvepage 4a.12 line 18 (11.08.03) \font\logosl=logosl9 in the author's books about \TeX\ and \MF\ \becomes\nl in {\sl The \TeX book\/} and {\sl The {\logosl METAFONT\kern.1em}book} \endchange \improvepage 4a.15 lines $-19$ and $-18$ (11.07.20) spanning path \becomes spanning path $P_n$\nl spanning cycle \becomes spanning cycle $C_n$ \endchange \bugonpage 4a.16 line 26 (11.04.23) the odds \becomes changing two different letters, the odds \endchange \bugonpage 4a.16 line 29 (11.04.23) 2056, 1198, 224 \becomes 2056, 1186, 224 \endchange \bugonpage 4a.16 line before {\eq(22)} (11.05.15) out be \becomes out to be \endchange \amendpage 4a.19 line 5 in the right column of Fig{.} 3 (11.04.23) {\sevenrm Hector MacQueen} \becomes {\sevenrm Hector Willard MacQueen} \endchange \bugonpage 4a.19 line 15 in the right column of Fig{.} 3 (11.04.23) {\sevenrm Cyrus Bettman Hardman} \becomes {\sevenrm Cyrus Bethman Hardman} \endchange \improvepage 4a.23 line $-11$ (11.09.13) cross references \becomes cross-references \endchange \bugonpage 4a.24 line 9 (11.04.23) {\it plane\_lisa\/}$(360,250,15,0,360,0,250,0,0,2295000)$ \becomes\nl {\it plane\_lisa\/}$(360,250,15,0,360,0,250,0,22950000)$ \endchange \bugonpage 4a.25 line 28 (11.04.23) $\.{3,1,4,2}\adj\.{3,0,4,3}@$ \becomes $\.{3.1.4.2}\adj\.{3.0.4.3}@$ \endchange \improvepage 4a.26 line 11 (11.04.23) two edges are adjacent in $L(G)$ \becomes two edges of $G$ are adjacent in $L(G)$ \endchange \bugonpage 4a.31 lines 13 and 14 (11.04.23) {\it plane\_lisa\/}$(360,250,15,0,360,0,250,0,0,2295000)$ \becomes\nl {\it plane\_lisa\/}$(360,250,15,0,360,0,250,0,22950000)$ \endchange \bugonpage 4a.35 lines 15--17 (11.08.06) In Section 7.5.1 we'll \dots~study \becomes In Sections 7.5.1 and~7.5.5 we'll see that a minimum vertex cover can be discovered quickly in any bipartite graph, or in any hypergraph that is the dual of a graph; we'll also study \endchange \amendpage 4a.44 line 2 of exercise 114 (11.05.23) \ninepoint bipartite graph \becomes bipartite multigraph \endchange \bugonpage 4a.46 replacement for last line of exercise 142 (11.05.23) \ninepoint\noindent of order~4 that are considered in exercise~90. \em Hint: Observe that $(n-3)\#(K_3{:}G)= 4\#(K_4{:}G)+2\#(K_{1,1,2}{:}G)+\#(\overline{K_{1,3}}{:}G) +\#(\overline{K_1{\dirsum}K_{1,2}}{:}G)$. \endchange \bugonpage 4a.49 entire page (11.01.01) [In the first printing this page was shifted about 1\thinspace cm to the left] \endchange \amendpage 4a.56 lines 4 and 5 after {\eq(31)} (11.07.13) especially in Section 7.9 \becomes for instance in Section 7.2.2.2 \endchange \improvepage 4a.68 line $-2$ (11.06.18) Setting $x=y$ \becomes Setting $y=x$ \endchange \bugonpage 4a.70 line 1 of step I4 (11.07.11) $\.{MARK($u$)}\ne s$ \becomes $\.{MARK($u$)}\ne s$ or $\.{RANK($u$)}\ne 1$ \endchange \bugonpage 4a.74 line 7 (11.06.10) $u_k\le u_{k+d}$ \becomes $u_k\to u_{k+d}$ \endchange \bugonpage 4a.74 lines 4 and 5 after {\eq(74)} (11.06.10) inequalities \becomes relations \qquad(twice) \endchange \bugonpage 4a.81 line 4 of exercise 26 (11.06.14) \ninepoint Exhibit \becomes Efficiently exhibit \endchange \amendpage 4a.89 reordering of exercise 67 in the top several lines (11.07.08) \ninepoint The original part (b) [`If $n>0$, let $t^*$ \dots'] becomes part (a); and the original part (a) [`Prove that, \dots'] becomes part (b). \endchange \bugonpage 4a.93 replacement for part {(d)} of exercise 110 (11.07.20) \ninepoint \item{d)} Suppose $f$ is a pure majority function, namely a threshold function of the form \eq(86) with $a=b=0$. Then $s_1\ge s_2\ge \cdots\ge s_n$ implies that $w_1\ge w_2\ge\cdots\ge w_n$. \endchange \improvepage 4a.96 line 6 (11.08.20) \ninepoint all vectors $z$. \becomes all $n$-bit vectors $z$. \endchange \improvepage 4a.103 just before the displayed special chains (11.08.08) cannot obviously be shortened: \becomes cannot be shortened in an obvious way: \endchange \amendpage 4a.114 replacement for {\eq(45)} and the line above it (11.05.05) \noindent only 11\dash---a chain with fewer than 1.6 operations per output(!): $$\openup-.9\jot\eqalign{ x_5&=x_1\blor x_2,\cr x_6&=x_3\xor x_5,\cr x_7&=\bar x_2\bland x_6,\cr \strut x_8&=x_4\blor x_7,\cr }\qquad\eqalign{ \bar d=\phantom{_9}x_9&=x_6\xor x_8,\cr \bar f=x_{10}&=\bar x_5\bland x_8,\cr \bar b=x_{11}&=x_2\bland\bar x_9,\cr \strut\bar a=x_{12}&=\bar x_3\bland x_9,\cr }\qquad\eqalign{ \bar c=x_{13}&=\bar x_4\bland x_{10},\cr \bar e=x_{14}&=x_4\blor x_9,\cr g=x_{15}&=x_6\blor x_{11}.\cr \strut\cr }\eqno(45)$$ This amazing chain, found by Corey Plover in 2011, chooses $x_7$ non-greedily. \endchange \amendpage 4a.125 replacement for exercise 4 (11.11.19) \ninepoint \ex4. [M28] Prove that the minimum depth and formula length of a Boolean function satisfy $\lg L(f)1$, where $\alpha=1/\?\lg\chi\approx2.465965$ is related to the ``plastic constant''~$\chi$ of Eq.~7.1.4--\eq(90). \em Hint: If $f$ contains a subformula~$g$, we have $f=g{?}\ f_1{:}\ f_0$ for suitable $f_1$ and~$f_0$. \endchange \amendpage 4a.126 replacement for exercise 15 (11.12.01) \ninepoint \ex15. [28] Find short-as-possible ways to evaluate the following Boolean functions using minimum memory: (a)~$S_1(x_1,x_2,x_3)$; (b)~$S_2(x_1,x_2,x_3,x_4)$; (c)~$S_1(x_1,x_2,x_3,x_4)$; (d)~the function in \eq(18). \endchange \amendpage 4a.128 rating of exercise 42 (11.09.07) \ninepoint {\it25\/} \becomes {\it30\/} \endchange \amendpage 4a.129 line 3 of exercise 58 (11.11.01) Russian \becomes USSR All-Union \endchange \amendpage 4a.131 rating of exercise 76 (11.10.16) \ninepoint{\it M25\/} \becomes {\it M26} \endchange \bugonpage 4a.131 line 8 of exercise 76 (11.10.16) \ninepoint$O(n/@\!\log n)^2$ \becomes $O(n^2)$ \endchange \improvepage 4a.131 line 10 of exercise 76 (11.10.16) \ninepoint length $2^m$. \becomes length $2^m$, and the one-bit quantity $(\[l\le i]\xor\[i\le j])$ is {\mc AND}$@$ed with each component of $x\xor y$. \endchange \amendpage 4a.132 rating of exercise 80 (11.10.24) \ninepoint {\it M27\/} \becomes {\it M29} \endchange \amendpage 4a.133 line $-2$ of exercise 86 (11.12.01) \ninepoint $r^2q\ge2^{r-1}$. \becomes $r^2q\ge2^{r+1}$. \em Hint: Now use the first formula. \endchange \amendpage 4a.133 rating of exercise 87 (11.11.30) \ninepoint {\it M20\/} \becomes {\it M22\/} \endchange \improvepage 4a.134 line 20 (11.11.17) {\it technique\/} is a trick \becomes {\it technique\/} is a mature trick \endchange \bugonpage 4a.157 replacement for the display in the proof of Theorem R (11.08.04) $$\{2^k,\,2^{k+2^d},\,2^{k+2\cdot2^d},\,\ldots,\,2^{k+(d-1)2^d}\}\;\cap V_{d@0r}\;=\;\emptyset.$$ \endchange \improvepage 4a.171 the line before {Fig.~15} (11.01.25) sides: \becomes sides (Fig.~15(b)): \endchange \bugonpage 4a.173 line 1 after {Fig.~16} (11.04.15) at least two \becomes one, two, or three \endchange \bugonpage 4a.194 line 3 of exercise 127 (11.02.24) \ninepoint boardword \becomes broadword \endchange \improvepage 4a.207 line $-6$ (11.02.12) is best possible \becomes is the best possible \endchange \improvepage 4a.267 last line of exercise 131 (11.10.19) \ninepoint Prove, however, that \becomes Prove that \endchange \bugonpage 4a.278 line 3 of exercise 253 (11.10.04) \ninepoint {\mc PI}$(f_2)\setminus A$ \becomes {\mc PI}$(f_1)\setminus A$ \endchange \improvepage 4a.286 line 8 (11.03.29) successively \becomes starting with $00\ldots0$ and successively \endchange \improvepage 4a.288 four lines before {\eq(20)} (11.07.27) The {\sl Walsh transform\/} \becomes The {\it Walsh transform\/} \endchange \amendpage 4a.313 rating of exercise 43 (11.11.08) \ninepoint {\it47\/} \becomes {\it41\/} \endchange \improvepage 4a.326 line $-15$ (11.08.27) saying that $j\alpha$ is ``the image \becomes saying that ``$j\alpha$ is the image \endchange \bugonpage 4a.359 line 18 (11.03.24) $tt>1$. \becomes $n\ge t>1$. An auxiliary variable $c_{t+1}$ is used. \endchange \improvepage 4a.363 last line of Algorithm R (11.04.01) if $j\le t$.\quad\slug\qquad \becomes if $j\le t$. Otherwise the algorithm terminates.\quad\slug \endchange \amendpage 4a.399 line 11 (11.04.19) $O(n^{1/2})$ steps. \becomes $O(n^{1/2})$ steps. [See {\sl Handbook of Combinatorics\/ \bf2} (MIT Press, 1995), 1068--1069.] \endchange \bugonpage 4a.475 line 1 of exercise 31 (11.06.29) \ninepoint height $n-1$ \becomes height $n$ \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \amendpage 4a.514 line 2 of the first answer 2 (11.09.13) its answer. \becomes its answer, assuming that he or she is suitably sagacious. \endchange \improvepage 4a.517 line $-3$ (11.05.23) $L$ is a latin square \becomes $L$ with entries in $\{1,2,\ldots,n\}$ is a latin square \endchange \bugonpage 4a.522 line 2 of answer 63 (11.05.23) $1\le k0$, set $m\gets c_t$, create the arc $m\dadj n$, and set''; \endchange \amendpage 4a.528 line 4 of answer 110 (11.05.23) $d=2k$ \becomes $d=2k>0$ \endchange \amendpage 4a.529 line 5 of answer 114 (11.05.23) bipartite graph \becomes bipartite multigraph \endchange \bugonpage 4a.529 line 4 of answer 122 (11.05.29) other three colors \becomes other three vertices \endchange \bugonpage 4a.530 last line of answer 126 (11.05.23) 1978 \becomes 1979 \endchange \bugonpage 4a.531 in answer 135 (11.05.23) line 1: $\omega=e^{2\pi i/6}$ \becomes $\omega=e^{2\pi i/12}$\nl line 5: $TD^mT^-$ \becomes $TD^{2m}T^-$ \endchange \improvepage 4a.533 line 1 of answer 142 (11.05.24) the previous answer \becomes answer 140 \endchange \bugonpage 4a.540 lines 2 and 3 (11.06.19) the generalized consensus if and only if this subcube is contained in $c_1\cup\cdots\cup c_m$. \becomes\nl the only subcube that could possibly be a generalized consensus. \endchange \amendpage 4a.540 added remark for end of answer 33 (11.06.20) (See, for example, Eq.~1.2.6--\eq(24).) \endchange \amendpage 4a.546 replacement for answer {67(a)} (11.07.08) \ans67. (a) A black Y in $t$ forces a black Y in $t^*$, because adjacent black stones $a\adj b\adj c$ in~$t$ yield two adjacent black stones in~$t^*$. Similarly, a black~Y in $t^*$ forces a black~Y in $t$.\tighten \endchange \amendpage 4a.548 lines 16--18 of answer 77 (11.07.10) Since $d(w,v)$ \dots\ has rank~1. \becomes The vertex $x=\langle svw\rangle$ has rank~1 by~(c). If $x=v$, then $u$ has rank~2 unless $w$ has rank~0. \endchange \bugonpage 4a.552 line 1 of answer 102 (11.07.17) \eq(1) and~\eq(2) \becomes \eq(11) and~\eq(12) \endchange \improvepage 4a.554 line 2 of answer 111 (11.07.22) set \becomes choose \endchange \bugonpage 4a.559 line 2 of answer 127 (11.07.31) $x_j$. \becomes $x_j$ or $\bar x_j$. \endchange \improvepage 4a.560 in lines 1 and 2 of answer 132{(b)} (11.08.08) Given $y=y_1\ldots y_n$ \becomes Given $y_0$, $y_1$, \dots, $y_n$\nl $1+h(y_1,y_3,\ldots,y_{n-1})$ \becomes $1+y_0+h(y_1,y_3,\ldots,y_{n-1})$\nl $x\cdot y\mod 2$ \becomes $(y_0+x\cdot y)\mod 2$ \endchange \amendpage 4a.561 replacement for lines 3--10 of answer 4 (11.11.19) The hint follows when we let $f_t$ be the formula of size $L(f)-L(g)-1$ that arises when $g$ is replaced by~$t$. For $1\le k1$. [See P.~M. Spira, {\sl Hawaii Int.\ Conf.\ Syst.\ Sci.\ \bf4} (1971), 525--527; R.~Brent, D.~Kuck, and K.~Maruyama, {\sl IEEE\/ \bf C-22} (1973), 532--534. In {\sl JACM\/ \bf23} (1976), 534--543, D.~E. Muller and F.~P. Preparata proved that $D(f)\le\beta\lg L(f)+O(1)$, where $\beta=1/\?\lg z\approx 2.0807$, % 2.0806735551368511736 $z^4=2z+1$. Is $\beta$ optimum?] \endchange \amendpage 4a.562 replacement for lines 2--8 of answer 15 (11.12.01) \vtop{\vskip-\baselineskip$$\openup-1\jot \eqalign{ {\rm(a)}\enspace x_1&\gets x_1\xor x_2,\cr x_1&\gets x_1\xor x_3,\cr x_2&\gets x_2\land x_3,\cr x_1&\gets x_1\land\bar x_2.\cr &\phantom{x_3\land\bar x_1}\cr &\phantom{x_3\land\bar x_1}\cr &\phantom{x_3\land\bar x_1}\cr }\quad\eqalign{ {\rm(b)}\enspace x_1&\gets x_1\xor x_2,\cr x_3&\gets x_3\xor x_4,\cr x_1&\gets x_1\xor x_3,\cr x_2&\gets x_2\xor x_4,\cr x_3&\gets x_3\lor x_2,\cr x_3&\gets x_3\land\bar x_1.\cr &\phantom{x_3\land\bar x_1}\cr }\quad\eqalign{ {\rm(c)}\enspace x_1&\gets x_1\xor x_2,\cr x_2&\gets x_2\land\bar x_1,\cr x_3&\gets x_3\xor x_4,\cr x_4&\gets x_4\land x_1,\cr x_2&\gets\bar x_2\land x_3,\cr x_2&\gets x_2\xor x_1,\cr x_2&\gets x_2\land\bar x_4.\cr }\quad\eqalign{ {\rm(d)}\enspace x_1&\gets x_1\xor x_2,\cr x_2&\gets x_2\xor x_3,\cr x_2&\gets x_2\lor x_1,\cr x_1&\gets x_1\xor x_4,\cr x_1&\gets x_1\land x_3,\cr x_2&\gets x_2\land\bar x_1,\cr x_2&\gets x_2\xor x_4.\cr }\quad$$} \endchange \amendpage 4a.564 last line of answer 20 (11.01.21) is the complement of~\eq(20) \becomes is equivalent to~\eq(20) \endchange \amendpage 4a.564 replacement for lines 3--6 of answer 21 (11.01.21) \noindent hardest function \eq(20) is still unknown, but David Stevenson has shown that $V(f)\le17$: $$\openup-2pt\eqalign{ g&=\hbox{\mc AND}\bigl( \hbox{\mc NAND}(w,x),\hbox{\mc NAND}(\bar w,\bar x)\bigr);\cr f&=\hbox{\mc OR}\bigl(\hbox{\mc AND}\bigl(\hbox{\mc NOT}(g), \hbox{\mc NAND}(w,\bar z),\hbox{\mc NAND}(y,z)\bigr),\cr &\qquad \hbox{\mc AND}\bigl(\hbox{\mc NOT}(\hbox{\mc NOT}(g)), \hbox{\mc NAND}(y,\bar z),\hbox{\mc NAND}(\bar y,z)\bigr)\bigr).\cr }$$ \endchange \bugonpage 4a.568 line 7 of answer 42 (11.09.07) $l=2$ \becomes $l=3$ \endchange \amendpage 4a.572 replacement for answer 57 (11.05.19) \ans57. The truth tables for $x_5$ through $x_{15}$, in hexadecimal notation, are respectively \.{0fff}, \.{3ccc}, \.{30c0}, \.{75d5}, \.{4919}, \.{7000}, \.{0606}, \.{4808}, \.{2000}, \.{5d5d}, \.{3ece}. So we get $$\def\\#1{\vcenter{\def\epsfsize##1##2{.5##1}\epsfbox{\figdir/v4a.125#1}}} 1010\mapsto\\0\,,\quad 1011\mapsto\\7\,,\quad 1100\mapsto\\4\,,\quad 1101\mapsto\\5\,,\quad 1110\mapsto\\6\,,\quad 1111\mapsto\\7\,.$$ [Corey Plover, believing that it might be better to have a solution in which nondigits never masquerade as digits, has discovered a 12-step chain (with non-greedy $x_7$) $$\openup-.9\jot\eqalign{ x_5&=x_1\xor x_2,\cr x_6&=x_3\bland\bar x_4,\cr x_7&=x_1\xor x_6,\cr x_8&=x_4\blor x_7,\cr }\qquad\eqalign{ x_9&=x_2\xor x_3,\cr g=x_{10}&=x_7\blor x_9,\cr \bar d=x_{11}&=x_8\xor x_{10},\cr \bar a=x_{12}&=\bar x_3\bland x_{11},\cr }\qquad\eqalign{ \bar b=x_{13}&=x_2\bland\bar x_{11},\cr \bar c=x_{14}&=x_7\bland x_9,\cr \bar e=x_{15}&=x_4\blor x_{12},\cr \bar f=x_{16}&=\bar x_5\bland x_8,\cr }$$ for which $a$, \dots, $g$ have the truth tables \.{b7ff}, \.{f9f0}, \.{dfe3}, \.{b6df}, \.{a2aa}, \.{8ff2}, \.{3efd}, and $$\def\\#1{\vcenter{\def\epsfsize##1##2{.5##1}\epsfbox{\figdir/v4a.127#1}}} 1010\mapsto\\0\,,\quad 1011\mapsto\\1\,,\quad 1100\mapsto\\2\,,\quad 1101\mapsto\\3\,,\quad 1110\mapsto\\4\,,\quad 1111\mapsto\\5\,.$$ \def\\#1{\vbox{\def\epsfsize##1##2{.25##1}\epsfbox{\figdir/v4a.125#1}}}% \def\|#1{\vbox{\def\epsfsize##1##2{.25##1}\epsfbox{\figdir/v4a.127#1}}}% He has also shown that all 11-step solutions to \eq(44) map the nondigits into either $(\\0,\\7,\\4,\\5,\\6,\\7)$, $(\\0,\\7,\\6,\\1,\|9,\|5)$, $(\\0,\\7,\\6,\\1,\|0,\|5)$, $(\\2,\\3,\\6,\\7,\\6,\\7)$, $(\|6,\\1,\\6,\\7,\\4,\\5)$, or $(\|6,\|8,\\6,\\7,\\4,\\5)$.] \endchange \bugonpage 4a.573 line 1 of answer 62 (11.09.13) $t(n,r)$ \becomes $c(n,r)$ \endchange \bugonpage 4a.574 line 2 of answer 67 (11.04.24) {\mc ANDN} \becomes {\mc BUTNOT} \endchange \bugonpage 4a.574 line 3 of answer 69 (11.10.09) $\alpha_{110}$ \becomes $\alpha_{011}$ \endchange \bugonpage 4a.576 line 4 of answer 76 (11.10.16) $O(n/\!@\log n)$ \becomes $O(n)$ \endchange \bugonpage 4a.576 bottom line (11.10.19) $x_1=x_1\circ x_2$ \becomes $x_{n+1}=x_1\circ x_2$ \endchange \bugonpage 4a.577 replacement for the first 10 lines (11.10.19) \indent\em Case~4.1:\enspace $k>n$. Then $k>n+1$. If $u_k=1$, set $x_1\gets t_{@l}$ and remove steps $n+1$,~$k$, $l$,~$U_{@l}$. Otherwise set $x_2\gets t_{n+1}$; this forces $x_k=\bar t_{@l}$, and we can remove $n+1$,~$k$, $l$,~$U_k$.\par \em Case 4.2:\enspace $x_{@l}=x_1\circ x_m$. Then we must have $m=2$; for if $m>2$ we could set $x_2\gets t_{n+1}$, $x_m\gets t_{@l}$, and make $x_{n+r}$ independent of~$x_1$. Hence we may assume that $x_{n+1}=x_1\land x_2$, $x_{n+2}=x_1\?\?\lor x_2$. Setting $x_1\gets0$ allows us to remove $U_1$ and $U_{n+1}$; setting $x_1\gets1$ allows us to remove $U_1$ and $U_{n+2}$. Thus we're done unless $u_{n+1}=u_{n+2}=1$.\tighten\par If $x_p=\bar x_{n+1}$, set $x_1\gets0$ and remove $n+1$, $n+2$, $p$, $U_p$; if $x_q=\bar x_{n+2}$, set $x_1\gets1$ and remove $n+1$, $n+2$, $q$, $U_q$. Otherwise $x_p=x_{n+1}\circ x_u$ and $x_q=x_{n+2}\circ x_v$, where $x_u$ and~$x_v$ do not depend on $x_1$ or~$x_2$. But that's impossible; it would allow us to set $x_3$, \dots,~$x_n$ to make $x_u=t_p$, then $x_2\gets1$ to make $x_{n+r}$ independent of~$x_1$. \endchange \bugonpage 4a.578 line 5 of case 3 in answer 80 (11.10.24) $u_{j'}=1$ \becomes $u_{j'}\ne1$ \endchange \bugonpage 4a.578 lines $-3$ and $-2$ of answer 80 (11.10.24) optimum for $k=\lceil n/2\rceil$ \dots~$k\ge n/2$. \becomes optimum when $n=4$ except for $S_1$, $S_3$, $S_{\ge2}$, and $S_{\ge3}$, and optimum when $n=5$ except for $S_1$, $S_4$, $S_{\ge2}$, and $S_{\ge4}$. All known results are consistent with the conjecture that $C(S_k)=C(S_{\ge k})$ for $k>n/2$. \endchange \bugonpage 4a.580 in answer 86 (11.11.01) line 3 of (e): one of the functions $\epsilon_i=\hat x_i\xor(\hat x_{j(i)}\land x_{k(i)})$. \becomes the union of the terms $\epsilon_i=\hat x_i\xor (\hat x_{j(i)}\land\hat x_{k(i)})$ for the $p$ {\mc AND} steps.\nl line 4 of (f): in one of the terms $T=\delta_i=\hat x_i\xor(\hat x_{j(i)}\lor x_{k(i)})$ \becomes within the terms $T=\delta_i=\hat x_i\xor(\hat x_{j(i)}\lor\hat x_{k(i)})$\nl {\it also replace line 8 of (f) through line 3 of (g) by the following:}\nl monochromatic. We will prove that each term $T$ includes at most $2^{n-2-r}r^2$ such~$B$, hence $2^{n-2-r}r^2q\ge2^{n-1}$.\tighten\par We can compute $G^*=G_t$ from any given graph~$G$ by the following (inefficient) algorithm: Set $G_0\gets G$, $t\gets0$. If $G_t$ has an $r$-family~$S$ with $\vert\Delta(S)\vert<2$, set $t\gets t+1$, $G_t\gets\infty$, and stop. Otherwise, if $\Delta(S)=\{u,v\}$ and $u\nadj v$, set $t\gets t+1$, $G_t\gets(G_{t-1}$ plus the edge $u\adj v$) and repeat. Otherwise stop.\par There are $2^{n-1-r}$ bipartite minterms~$B$ with monochromatic $\{u_j,v_j\}$ for $1\le j\le r$ when $\vert\Delta(S)\vert<2$. And when $\Delta(S)=\{u,v\}$ there are $2^{n-2-r}$ with monochromatic $\{u_j,v_j\}$ and bichromatic~$\{u,v\}$. Hence $$% again displayed to help paging (although it also helped comprehension!) T=\lceil G^*\rceil\setminus\lceil G\rceil= \bigl(\lceil G_t\rceil\setminus\lceil G_{t-1}\rceil\bigr)\lor\cdots\lor \bigl(\lceil G_1\rceil\setminus\nobreak\lceil G_0\rceil\bigr)$$ contains $2^{n-2-r}(t+\[G^*=\infty])$ minterms~$B$. And the algorithm stops with $t\le(r-1)^2$.\par % I had (r-1)^2+2, but the original graph G_0 must have r edges already. (g) Exercise 84 tells us that $q<{p\choose2}+(p+1){n\choose2}$. Thus we have \vadjust{\vskip2pt}% either $2(r-1)^3p\ge{n\choose3}-(r-1)^2(n-2)$ or ${p\choose 2}+ (p+1){n\choose2}>2^{r+1}\!/r^2$. Both lower bounds for $p$ are $$\ge{1\over6}\Bigl({n\over6\lg n}\Bigr)^{\!3}\Bigl(1+O\Bigl( {\log\log n\over\log n}\Bigr)\Bigr)\qquad\hbox{when}\qquad r=\Big\lceil\lg\Bigl({n^6\over746496(\lg n)^4}\Bigr)\Big\rceil.$$ \endchange \amendpage 4a.583 lines $-7$ thru $-3$ of answer 10 (11.01.23) $1\le j\le7$ \becomes $0\le j\le7$ \qquad and also include the constant $\.q_0=\.{8040201008040201}$ \endchange \bugonpage 4a.584 line 2 of answer 13 (11.11.28) $a\ne b$ \becomes $x\oplus y=x'\oplus y'$ and $a\ne b$ \endchange \bugonpage 4a.602 line 1 of answer 124 (11.08.04) $\{1,2,\ldots,2^{n-1}\}$ \becomes $\{2^0,2^1,\ldots,2^{n-1}\}$ \endchange \amendpage 4a.620 improvement to answer 218 (11.08.04) line 4: for $1%% Unicode "4e38 \JC41:47:-4:39% J2719 <00003000000000003c00000000003e00000000003e00000000003c00000000003c000000% 00003c00000000003c00000000003c00000000003c000000c0003c000000f0003c000c00% f8003c000f00f8003c000f80f0003c000f80f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00% f0003c000f00f0003c000f00f0003c000f00f0003c000f00f0003c000f00ffffffffff00% ffffffffff00f00000000f00f00000000f00f00000000f00600000000600>%% Unicode "5c71 \JC48:48:0:40% J3222 <0e00000c00000f80000f000007c0000f800003e0000f800001f0000f003001f0000f0078% 00f0fffffffc00607ffffffc0000000f00000000000f00000000000f00c00000000f01e0% c0003ffffff0f0001ffffff07c00000f00003e00000f00001f04000f000c0f04000f001e% 0f0fffffffff060dffffffff000c0000000000180000000000180c00018000380f0003c0% 00380fffffe000780fffffe000700f0003c000f00f0003c000e00f0003c001e00f0003c0% 03e00fffffc003c00fffffc007c00f0003c0cf800f0003c07f000f0003c07f000f0003c0% 3f000fffffc03f000fffffc01f800f0003c01f800f0003c01f800f0003c01fc00f0003c0% 0fc00f0003c00fe00f0007c00fe00f007fc00fe00f001fc007e00f000f8003c006000700% >%% Unicode "6e05 ), 561. % 3rd Minimal vertex covers, 34--35, 259, 537. % 3rd Mod 4 parity, 126. % 3rd Modular arithmetic, 207, 260, 515. % 3rd Muller, David Eugene, 143, 561, 567. % 3rd Mux (multiplex) operation, 96, 125, 566, 568, 569, \also If-then-else function. % 3rd Orthogonal latin squares, 3--8, 36--38, 516. % 3rd \"Osterg{\aa}rd, Patric Ralf Johan, 673, 686. % 3rd Padovan, Richard, numbers, 537, 561, 641. % 3rd Perrin, Fran\c{c}ois Olivier Raoul, numbers, 537, 561, 623, 641. % 3rd Plastic constant ($\chi$), 125, 236, 623, 641. % 3rd Plover, Corey Michael, 114, 572. % 3rd Polynomials modulo a prime, 260. % 3rd Preparata, Franco Paolo, 561, 567. % 3rd Products of digraphs and multigraphs, 42, 526. % 3rd Products of graphs, 27--28, 42--44, 483, 526. % 3rd Pure majority functions, 76, 93, 550. % 3rd Regular graphs, 14, 24--26, 33, 40--44, 483. % 3rd Reliability polynomials, 80, 81, 84, 93, 206, 211--212, 260, 261, 267, 388, 535. % 2nd Set systems, \see $@$Families of sets. % 3rd Shrikhande, Sharadchandra Shankar ({\dn frd\char99\char6\lower0.1em\hbox{\char125}\kern-0.6emd \hbox{f\kern-0.6em\raise0.4em\hbox{\char21}}kr \char128FK\kern-0.6em\raise0.4em\hbox{\char21}X\kern-0.8em\hbox{\char3}}), 5. % 2nd Sideways sum ($\nu@x$): Sum of binary digits, x,~143, 295, 374, 383, 682, 725. % 2nd Skolem, Thoralf Albert, ix, 8, 36, 514, 515. % 3rd Spanning cycles, \see Hamiltonian cycles. % 3rd Spanning paths, \see Hamiltonian paths. % 3rd Spira, Philip Martin, 561. % 3rd Stevenson, David Ian, 113, 564, 572, 574. % 2nd Toruses, x, 28, 41, 197, 309, 318, 327, 468, 469, 483, 680, 805, 808. % 3rd \sub directed, 41, 352, 808. % 3rd Transitive tournament ($K\orie_{\!n}^{\vphantom h}$), 18, 27, 40, 41, 808. % 3rd Triangles (3-cliques), 133, 374. % 3rd United States of America graph, 15, 34, 39--40, 210--211, 231--233, 244--246, 250, 254--255, 265, 269, 276, 277, 636, 670; \also {\it miles\/} graphs. % 3rd Vertex degree, 14, 19, 39, 43, 44, 264, 464, 483, 529. % 3rd Vertices in a graph, 11, 13. % 3rd \vfill \enddoublecolumns \endchange \bye [The next printing will be the 4th.] not listed above: page 17, better positioning of rightmost graph in (23) page 27, better positioning in (42) page 79, larger $n$ in caption page 115, larger $d$ and $c$ in caption page 172 is affected by the change to page 173 page 248, larger $z$s in captions page 411, line $-2$, slightly better positioning below the \sum signs page 519, better spacing in line 1 of answer 24(b) page 536, better spacing after \partial in answer 12(e) page 565, several changes from "=" to "<-" in answer 28 page 566, several changes from "=" to "<-" in answer 36 page 577, "77:" -> "77." in line 2 of answer 78 page 578, several changes from "=" to "<-" in answer 80 new index entries (which duplicate others): Directed graphs, diagrams for Directed graphs, isomorphisms between Golden ratio Graphs, connectivity of Graphs, diagrams for Graphs, isomorphisms between Graphs, planar Graphs, regular Linked lists, ..., \also Linked allocation. Subgraphs, induced Subgraphs, spanning Trees, Steiner Vertex covers, minimal remove the index entries for Torus graphs (they're now under Toruses) slightly changed index entries: generator routines graphs, generators for K\orie_n maximum indep sets orthogonal arrays, generalized P_n path graph tournament digraphs, transitive words graphs Doerr leaves the index Winker leaves the index Pi function now on p562 ARTICLES "TO APPEAR" THAT ARE STILL PENDING: Haanp\"a\"a and \"Osterg{\aa}rd, A dynamic programming approach to counting Hamiltonian cycles in bipartite graphs (submitted to Math Comp, Nov 2011)