% CHANGES TO VOLUME 4A OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2011, 2012, 2013 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, 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 \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.xii 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 \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.13 line 14 (12.02.01) permitted.) \becomes permitted, and in which repeated edges are allowed too.) \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.17 lines 5--7 (13.03.04) Franz Heinen \dots 1836). \becomes Joseph Gergonne had, however, already posed and solved the problem for {\it any\/} $k$ points in the plane [{\sl Annales de math\'ematiques pures et appliqu\'ees\/ \bf1} (1811), 292, 375--384 and planche~6]. \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 \improvepage 4a.29 line 6 (11.12.30) graphical; therefore \becomes graphical, because a (simple) graph cannot contain more than one edge between two vertices. Therefore \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 \amendpage 4a.32 line $-8$ (12.06.29) of colors \becomes of at most $k$ colors \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 \bugonpage 4a.52 line 2 (12.02.11) % affects also page 51 line break constants. \becomes constants, together with the variables $\{x_1,\ldots,x_n\}$. \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 \amendpage 4a.56 rearrangment of {\eq(32)} (12.10.24) $$\def\\#1#2{\if#11\bar\fi x_#2} \def\|#1#2#3#4#5#6{(\\#1#2{@\lor@}\\#3#4{@\lor@}\\#5#6)} \displaylines{\qquad \|010213@\land@\|111203@\land@\|020314@\land@\|121304 \hfill\cr\hfill {}@\land@\|010304@\land@\|111314@\land@\|110204@\land@\|011214@. \qquad\eq(32)\cr}$$ [also change `first seven' to `last seven' on line $-2$.] \endchange \bugonpage 4a.60 line $-19$ (12.01.02) Scutell\'a \becomes Scutell\`a \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 \bugonpage 4a.94 line 5 (12.01.22) $A_{n0}$, $A_{(n-1)1}$, \dots,~$A_{0n}$ \becomes $A_{m0}$, $A_{(m-1)1}$, \dots,~$A_{0m}$ \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 \bugonpage 4a.110 line 3 before {\eq(35)} (13.01.14) {\sl Isvestiia} \becomes {\sl Izvesti{\t\i}a} \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 \amendpage 4a.189 rating of exercise 71 (11.09.07) \ninepoint {\it17\/} \becomes {\it20\/} \endchange \bugonpage 4a.194 line 3 of exercise 127 (11.02.24) \ninepoint boardword \becomes broadword \endchange \amendpage 4a.198 line 9 of exercise 176 (12.04.25) $u'\adj^*v'$ in $G'$ \becomes $u'\adj^*v'$ in $G'$ (that is, they are in the same component). \endchange \amendpage 4a.198 line 3 of exercise 184 (12.03. 20) \ninepoint order. \becomes order. \em Hint: There is a simple answer. \endchange \amendpage 4a.198 rating of exercise 185 (12.03.21) \ninepoint {\it 22\/} \becomes {\it 23\/} \endchange \amendpage 4a.199 line 2 of exercise 189 (12.03.23) \ninepoint rotate it \becomes rotate it counterclockwise \endchange \improvepage 4a.200 line 4 of exercise 196 (12.03.30) \ninepoint$\alpha_j=2^7+x_{l-j}$ \becomes $\alpha_j\gets2^7+x_{l-j}$ \endchange \improvepage 4a.207 line $-6$ (11.02.12) is best possible \becomes is the best possible \endchange \improvepage 4a.208 line $-5$ (12.06.08) So we set $x_1\gets0$ with probability 13/18, and \becomes So, with probability~13/18, we set $x_1\gets0$ and \endchange \improvepage 4a.209 line 2 of step B3 (12.06.01) Then if $h\ne0$, compute \becomes Then if $h\ne0$, do the following: Compute \endchange \amendpage 4a.214 append a sentence to the paragraph preceding Theorem M (12.06.08) Kenneth McMillan has discovered an interesting upper bound that holds whenever we can formulate a computation using this general setup. \endchange \improvepage 4a.235 line 1 before {\eq(86)} (12.06.08) \eq(84) implies \becomes \eq(85) implies \endchange \bugonpage 4a.243 line 5 (12.05.18) $\half B(f)^2$ \becomes ${1\over8}B(f)^2$. \endchange \bugonpage 4a.248 line $-3$ (12.05.20) $3\cdot2^{n/2}$ \becomes $3\cdot2^{@(n+1)/2}$ \endchange \bugonpage 4a.256 line $-10$ (12.05.21) complete different \becomes completely different \endchange \amendpage 4a.263 rating of exercise 77 (12.08.25) \ninepoint {\it M30\/} \becomes {\it M35\/} \endchange \amendpage 4a.266 rating of exercise 111 (12.09.15) \ninepoint {\it M21\/} \becomes {\it M22\/} \endchange \bugonpage 4a.267 last line of exercise 130 (11.11.01) $\Omega@(2^{m/3}\!/\sqrt m\,)$ \becomes $\Omega@(2^{m/3-O(\sqrt m)})$ \endchange \improvepage 4a.267 last line of exercise 131 (11.10.19) \ninepoint Prove, however, that \becomes Prove that \endchange \amendpage 4a.271 new ratings for exercises (13.04.29) exercise 172, {\it M27\/} \becomes {\it M28}\nl exercise 173, {\it\HM28\/} \becomes {\it\HM33} \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.327 line 9 after {\eq(12)} (13.03.07) {\sl Computational Methods} \becomes {\sl Computational Problems} \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 \amendpage 4a.462 line 16 (12.02.02) root. \becomes root. The algorithm sets $p_0\gets-1$. \endchange \bugonpage 4a.475 line 1 of exercise 31 (11.06.29) \ninepoint height $n-1$ \becomes height $n$ \endchange \improvepage 4a.495 lines $-13$ and $-12$ (12.06.09) respectively simplicity, rank, mercy, and sovereignty. \becomes simplicity, rank, mercy, and sovereignty, in that order. \endchange \amendpage 4a.502 lines $-9$ through $-6$ (12.01.24) Those pages \dots~by mistake. \becomes Bernoulli didn't actually intend to publish those pages in this now-famous book; but the proofreader who found them among his notes decided to include the full details, in order ``to gratify curiosity.'' \endchange \bugonpage 4a.509 line 7 (12.06.27) {\sl Papers}, Volume 4 \becomes {\sl Papers}, Volume 9 \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 \amendpage 4a.515 line 12 (12.04.24) $2^{30}+1$. \becomes $2^{30}+1$, because $2^{49}\perp2^{60}-1$. \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 \amendpage 4a.522 new paragraph at answer of answer 54 (12.07.18) [This digraph was first considered by Darryl~Francis, Philip Cohen, and A.~Ross Eckler in {\sl Word Ways\/ \bf19} (1976), 241; {\bf20} (1977), 8.] \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 \bugonpage 4a.545 line 3 (12.01.02) 5.24 \becomes 5.2.4 \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 \improvepage 4a.547 line $-5$ (12.01.02) $x=y$ \becomes $y=x$ \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 \amendpage 4a.555 line $-4$ of answer 111 (12.01.22) Exercise 70 tells us that \becomes Since $f_k$ is self-dual we have \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 \bugonpage 4a.563 in some copies of the third printing only (13.01.13) \noindent {\sl Pages 563 and 564 were erroneously replaced by duplicates of pages 565 and 566 when the third printing went to the presses. The correct pages can be found online:} $$\hbox{\tt http:/\kern-.1em/www-cs-faculty.stanford.edu/\char`\~knuth/% 4a-563,564.ps.gz}$$ \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 {\thinmuskip=3mu minus .5mu $(\\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 \amendpage 4a.589 line 1 of answer 41 (12.01.10) $\sum_{k=1}^{@\infty}z\losup{2^k}\!/(1-z\losup{2^k})$ \becomes $\sum_{k=1}^{@\infty}z\losup{2^k}\!/(1-z\losup{2^k})= \sum_{k=1}^{@\infty}kz\losup{2^k}\!/(1-z\losup{2^{k+1}})$ \endchange \bugonpage 4a.592 line 8 of answer 58 (12.02.02) $k>1$ \becomes $k>0$ \endchange \bugonpage 4a.594 line 1 of answer 71 (12.01.28) $\theta_k$ \becomes $\theta_k\lsh2^k$ \endchange \amendpage 4a.594 lines 4 and 5 of answer 72 (12.02.02) So $\varphi$ \dots\ 58(f). \becomes So $\varphi\in\Omega$ by exercises 5.3.4--11 and 58(f). \endchange \bugonpage 4a.594 line 12 of answer 72 (12.01.30) $\theta_1=(10010010)_2$ \becomes $\theta_1=(10010011)_2$ \endchange \bugonpage 4a.595 line $-6$ of answer 75 (12.01.31) $x_7x_5x_5x_3x_1x_1x_0$ \becomes $x_7x_5x_5x_3x_3x_1x_1x_0$ \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.605 lines $-4$ thru $-2$ of answer 141 (12.08.14) Calculations \dots\ smallest gap \becomes Calculations by Jud McCranie %and the author ^^{Knuth} for $U_n<640000000$ for $U_n\le 10^9$ indicate that the largest gap $U_n-U_{n-1}$ %occurs uniquely between $U_{69180}=933709$ and $U_{69181}=934296$; %may occur between $U_{24576523}=332250401$ and $U_{24576524}=332251032$; %may occur between $U_{49395953}=667752899$ and $U_{49395954}=667753657$; may occur between $U_{71482877}=966290117$ and $U_{71482878}=966291200$; the smallest gap \endchange \bugonpage 4a.608 line 3 (12.02.25) six operations \becomes seven operations \endchange \amendpage 4a.608 in answer 159 (12.04.24) line 5: 20-step \becomes 19-step\nl line 9: $z\gets z\xor(t\band(z\xor((w{+}1)\rsh1)))$ \becomes $z\gets (z\bor t)-(t\rsh1)$ \endchange \bugonpage 4a.608 line$-3$ of answer 159 (12.03.03) $t\gets y\band(y-1)\band\bar\mu_0$, $y\gets y-t+\[t\ne0]((t-1)\band\mu_0)$ \becomes\nl $t\gets y\band-y\band\bar\mu_0$, $y\gets(t@{=}@0{?}\ y: y-1-((t@{-}@1)\band\bar\mu_0))$ \endchange \amendpage 4a.608 line 2 of answer 161 (12.03.03) strips can \becomes strips, $y\mod2$, can \endchange \bugonpage 4a.610 replacement for step C1 in answer 168 (12.03.07) \algindentset{\hskip\parindent C1}% \algstep C1. [Loop on $k$.] Set $A_{j0}\gets0$ for $0\le j0$ \becomes $\ge0$ \qquad[twice] \endchange \bugonpage 4a.617 lines 21--22 of answer 192 (12.03.27) So $F_{2(2^{2e}-1)}(y)=y@F_{2^{2e}-1}(y)^2$ is a multiple of $(x^{2q}+1)/(x^2+1)$ \becomes So $F_{4(2^{2e}-1)}(y)=y^3F_{2^{2e}-1}(y)^4$ is a multiple of $(x^{2q}+1)/(x^2+1)=f_2(x)^2f_3(x)^2\ldots f_r(x)^2$ \endchange \bugonpage 4a.618 line 5 (12.03.28) $\lcm(c_1,\ldots,c_r)=n$ \becomes $\lcm(c_1,\ldots,c_r)\le n$ \endchange \amendpage 4a.620 improvement to answer 218 (12.04.13) 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 McMillan, Kenneth Lauchlin, 214, 627. % 4th Median graphs, 67--74, 89--90, 550. % 4th Midpoint, bytewise, 151, 191. % 4th Minimal vertex covers, 34--35, 259, 537. % 3rd Mod 4 parity, 126. % 3rd Modular arithmetic, 207, 260, 515. % 3rd Monotone Boolean functions, 55, 63, 79, 80--82, 85, 87, 95, 202, 231, 255, 256, 258, 263, 265, 270--271, 277, 278, 388, 460, 480, 536--537. % 4th \sub self-dual, 63--64, 70, 79, 87--89, 92--93, 133, 256, 263, 268, 546, 550, 631, 647. % 4th Muller, David Eugene, 143, 561, 567. % 3rd Mux (multiplex) operation, 96, 125, 566, 568, 569, \also If-then-else function. % 3rd Nonnegative coefficients, 439. % 4th 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 Palindromes, 38, 515, 544. % 4th Parallel addition, 108, 127--128, 569, 570. % 4th Perrin, Fran\c{c}ois Olivier Raoul, numbers, 537, 561, 623, 641. % 3rd Pitts, Walter Harry, Jr\period, 75. % 4th 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 Prime implicants of Boolean functions, 54, 64, 71, 81--84, 89, 94, 95, 129, 195, 258, 277--278, 577, 581. % 4th Prime clauses, 54, 81, 95, 129, 277. % 4th Products of digraphs and multigraphs, 42, 526. % 3rd Products of graphs, 27--28, 42--44, 483, 526. % 3rd Projections in a median algebra, 67, 69. % 4th Pure majority functions, 76, 93, 550. % 3rd Putzolu, Gianfranco Raimondo, 541. % 4th 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 Renaming (selectively complementing) Boolean variables, 87, 536, 543, 544. % 4th Scutell\`a, Maria Grazia, 60. % 4th Self-dual Boolean functions, 63, 79, 80, 92, 95. % 4th \sub monotone, 63--64, 70, 79, 87--89, 92--93, 133, 256, 263, 268, 546, 550, 631, 647. % 4th 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 Shortest paths in a graph, viii, 12, 16, 32, 66, 89, 646, 831. % 4th Sideways sum ($\nu@x$): Sum of binary digits, x,~77, 143, 295, 374, 383, 682, 725. % 4th Simple graphs, 29, \see Graphs. %4th Skolem, Thoralf Albert, ix, 8, 36, 514, 515. % 3rd Source vertices, 18, 62, 253. % 4th 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 Synthesis of Boolean functions, 96--133, 206, 261, \see Boolean chains. % 4th Theorem proving, 59, 539, 548. % 4th Toruses, x, 28, 41, 197, 309, 318, 327, 468, 469, 483, 680, 805, 808. % 3rd \sub directed, 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 Uri, Dario, 617, 841. % 4th 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 54, line 12, better spacing in `$f(x)$' page 56, slightly improved wording in line 8 after (31) page 87, better spacing in last line of exercise 59 page 320 line 6, equal spacing of the four dots page 358 and top of page 359, improved punctuation for "slower tempo" page 501, two lines after (22), semicolon after "dactyl" page 589, line 11, A08 -> A8 page 618 line 2, changed $\gets$ to $=$ page 761 answer 72, "Integers" reference made consistent with others page 765 answer 22, line breaks adjusted by writing more copy page 766 line 2 of ans 25, "deg" changed to "degree" (deg is for polynomials!) Index entry "Bitonic permutation" goes away Index entry for Gauss loses page 17 Index entry for Heinen goes away Index entry for Schumacher loses page 17 Index entry "Sources" goes away Index entry SAT-counting becomes {\mc SAT}-counting Index entries for S_m and S_{\ge m} now include page 77 I removed hyphens from "fan-in" and "fan-out" on pages 97 (top), 104 (bot), 105 (top), 124 (bot), 570 (ans 45) 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) (Math Comp website lists it "accepted, in press" together with maybe a hundred and fifty others -- Jan 2013) Answer 7.1.1--55 (page 544) should refer to Heule's better construction in 7.2.2.2, when I have a definite exercise number for it