% CHANGES TO FASCICLE V4F5 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2019, 2020, 2021 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 err4f5" \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\bugoverall#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Important Changes Throughout!}\enspace \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 5} \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~5, since it was first printed in 2019. \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, September 2019} \bigskip \bigskip {\quoteformat I thought there would be not much corrections. I honestly wrote what I thought, but was most grievously mistaken. I find the style incredibly bad, \& most difficult to make clear \& smooth. .\thinspace.\thinspace. How I could have written so badly is quite inconceivable, but I suppose it was owing to my whole attention being fixed on general line of argument, \& not on details. % "on general": sic All I can say is that I am very sorry. \author CHARLES DARWIN, letter to John Murray (14 June 1859) % The Correspondence of Charles Darwin, vol 7 (Cambridge Univ Press 1991) p303 \bigskip An opportunity to revise is a great luxury. There's always something that needs correcting or improving. And it's not just a matter of my own second thoughts. Many of the most important changes and additions start with letters from readers. \author BRIAN HAYES (2017) % American Scientist 105 (2017) 312 \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 6 %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO V4F5: MATH PRELIMINARIES, BACKTRACKING ET AL} \def\rhead{CHANGES TO V4F5: MATH PRELIMINARIES, BACKTRACKING ET AL} \titlepage \volheadline{MATH PRELIMINARIES REDUX} % the fascicle title \volheadline{INTRO TO BACKTRACKING} % the fascicle title \volheadline{DANCING LINKS} % the fascicle title \bigskip \rightline{Copyright \copyright\ 2019, 2020, 2021 Addison\with Wesley} \rightline{Last updated \today} \bigskip %\rightline{\sl Most of these corrections have already been made in % recent printings.} %\medskip %\noindent Important note: The changes below include nearly every difference %between the paperback fascicle and the first printing of Volume 4A, %published in January 2011. All subsequent changes can be found in %the errata list for that volume. \smallskip \let\defaultpointsize=\tenpoint \amendpage 4f5.ii line $-4$ (20.02.10) \ninepoint\tt {\tt www.pearsoned.com/permissions/} \becomes\nl {\tt www.pearson.com/permissions/} \endchange \amendpage 4f5.iv line 19 (20.02.09) will solve the \becomes will solve many \endchange \improvepage 4f5.13 in exercise {5(b)} (21.02.08) \ninepoint Suppose $A$ and $B$ \dots\ is odd. \becomes Suppose the random variable~$A$ takes the values $(m_0,m_2,m_4,\ldots{})$ with probabilities $(q_0,q_2,q_4,\ldots{})$; otherwise $A=0$. Independently, the random variable~$B$ takes the values $(m_1,m_3,m_5,\ldots{})$ with probabilities $(q_1,q_3,q_5,\ldots{})$; otherwise $B=0$. \endchange \amendpage 4f5.14 new rating for exercise 24 (20.10.27) \ninepoint [{\it\HM27\/}] \becomes [{\it\HM28\/}] \endchange \improvepage 4f5.18 line 3 of exercise 63 (20.08.16) \ninepoint those probabilities \becomes those nine probabilities \endchange \bugonpage 4f5.23 line 6 of exercise 112 (20.02.26) \ninepoint $\min_{a\in\pi}a\pi=\infty$ \becomes $\min_{a\in A}a\pi=\infty$ \endchange \improvepage 4f5.30 line 2 (20.11.14) level 5 \becomes level 5 below the root. \endchange \improvepage 4f5.35 lines $-19$ and $-17$ (20.05.15) line $-19$: four-letter words \becomes four-letter codewords\nl line $-17$: from words of the set \becomes from strings of the set \endchange \improvepage 4f5.36 lines 2 and 3 (20.05.15) line 2: Such a word \becomes Such a string\nl line 3: {\it aperiodic\/} words \becomes {\it aperiodic\/} strings \endchange \improvepage 4f5.37 line 15 (20.11.14) no commafree code \becomes no commafree code of length $(m^4-m^2)/4$ \endchange \amendpage 4f5.39 new copy for two lines after {\eq(23)} (20.08.16) \noindent (This data-structuring technique has been called a {\it sparse-set representation\/}; see P.~Briggs and L.~Torczon, {\sl ACM Letters Prog.\ Lang.\ and Syst.\ \bf2} (1993), 59--69.)\tighten \endchange \improvepage 4f5.39 line 10 (20.08.16) codes is not \becomes codes of maximum length is not \endchange \bugonpage 4f5.40 line 5 after the table (20.05.30) $\.{CLOFF}+m^4+cl(\alpha)$. \becomes $\.{S3OFF}+m^4+s_3(\alpha)$, $\.{CLOFF}+m^4+4cl(\alpha)$. \endchange \bugonpage 4f5.43 line 2 (20.05.30) we must backtrack \becomes we mustn't proceed \endchange \bugonpage 4f5.44 line 2 of step C6 (20.05.30) $f\gets f-1$ \becomes $f\gets f+1$ \endchange \bugonpage 4f5.47 line 6 (20.06.05) $y_1y_2\ldots{}$ \becomes $y_0y_1\ldots{}$ \endchange \improvepage 4f5.48 line 19 (20.11.14) shaky grounds \becomes shaky ground \endchange \amendpage 4f5.48 line 2 before {\eq(34)} (20.01.19) P.~Diaconis and S.~Chatterjee \becomes S.~Chatterjee and P.~Diaconis \endchange \amendpage 4f5.48 and 49 (20.01.19) \eightpoint\noindent [I'm now using the notation $\widehat\chi_N$ instead of $Q_N$, for eventual agreement with Section 7.2.2.9] \endchange \amendpage 4f5.53 replacement for exercise 15 (20.12.22) \ninepoint \ex15. [M33] Prove that \smash{$T(4^n\?+1)\ge\bigl(\prod_{k=0}^{4^{n-2}}(4^{n-1}\!+ 4^{n+1}k)\bigr)/(4^{n-2}\!+1)!\ge(4^{n+1})^{4^{n-2}}$}. \endchange \amendpage 4f5.54 new rating for exercise 19 (20.11.14) \ninepoint [{\it M19\/}] \becomes [{\it M10\/}] \endchange \bugonpage 4f5.55 line 9 of exercise 37 (20.12.22) \ninepoint $x_k>x_{k+1}\le x_{k+2}$ \becomes $x_k\ge x_{k+1}0$ it suffices\nl line 12: increases \becomes is nondecreasing \endchange \amendpage 4f5.186 last line of answer 24 (20.10.27) 332.] \becomes 332. See also S.~Janson, \arXiv:2009.13781 [math.PR] (2020), 12~pages.] \endchange \improvepage 4f5.191 new answer 63 (20.08.16) \ans63. If $\omega$ is the event `$Z_0=a$ and $Z_1=b$', we have $Z_0(\omega)=a$ and $\E(Z_1\given Z_0)(\omega)=\break(p_{a1}+2p_{a2})/(p_{a0}+p_{a1}+p_{a2})$. Hence $p_{01}=p_{02}=p_{20}=p_{21}=0$, and $p_{10}=p_{12}$. Those conditions are necessary and sufficient for $\E(Z_1\given Z_0)=Z_0$. \endchange \bugonpage 4f5.194 in answer 83 (20.08.16) line 2: $\min(m,N)$ \becomes $N'_n(x_0,\ldots,x_{n-1})=\[n0$, otherwise $c=\.{COLOR(TOP($q$))}$.] \endchange \bugonpage 4f5.229 last line of answer 29 (19.12.14) $\{1,2\}$ \becomes $\{0,1\}$. [Also change $\vcenter{\baselineskip6pt\sevenrm\halign{#\hfil\cr01\cr10\cr}}$ to $\vcenter{\baselineskip6pt\sevenrm\halign{#\hfil\cr10\cr01\cr}}$ in lines 4--5, 9--10, 13--14 of the matrix.] \endchange \amendpage 4f5.231 last line of answer 37 (20.05.17) {\sl Combinatorics}, to appear. \becomes {\sl Combin.\ \bf27} (2020), \#P1.52, 27~pages. \endchange \amendpage 4f5.231 replacement for step G3 in answer 38 (21.02.07) \algindentset{G1} \algstep G3. [Found?] If $k>n-r$ go to G4. Otherwise if $a_k=b_{k+n}=c_{k-n}=0$, go to G5. Otherwise set $k\gets k+1$ and repeat this step. \endchange \amendpage 4f5.234 replacement for answer 52 (19.12.14) \ans52. (Solution by F. Stappers.) Puzzles claiming to be ``the world's hardest sudoku'' keep appearing in online forums. Rated by search tree size with Algorithm~X, the toughest among nearly 27,000 such extreme puzzles is shown here in a canonical form. (It's number 6539 in a list available from {\tt sites.google.com/site/sudoeleven/} (2011).) % 1000 trials, seeds 314??? Its random\-ized search tree sizes are $24400\pm1900$\dash---astonishingly high for sudoku; and its mean running time is about 12~M$\mu$.) {\hangindent-1in \hangafter0\tighten\parfillskip=0pt\hfil \def\epsfsize#1#2{.85#1}% \smash{\rlap{\quad\raise2pt\hbox{\epsfbox{\figdir/v4b.2898}}}}\par} \endchange \bugonpage 4f5.236 lines 6 and 7 (21.02.05) There are only two solutions \dots\ symmetric. \becomes Include `$\ast_j{:}k$' in option $(0,j,k)$. There are only four solutions, found in 3~G$\mu$, centrally symmetric and reducing under transposition to only two. \endchange \bugonpage 4f5.239 line $-3$ of answer 72 (20.07.04) 1292687 packings \becomes 1292697 packings \endchange \bugonpage 4f5.241 line 2 of answer 77 (20.03.02) each pair of vertices \becomes each pair of edges \endchange \bugonpage 4f5.241 in the table for answer 80 (20.03.27) [the entries for \.{COLOR($x$)} in nodes $x=11, 16, 19, 22, 25$ should be zero, not `\hbox{---}'.] \endchange \bugonpage 4f5.241 line 2 of answer 83 (20.01.01) $j>N$ \becomes $j>N_1$ \endchange \bugonpage 4f5.248 line 1 of answer 104 (19.12.16) We may \becomes (a) We may \endchange \amendpage 4f5.259 replacement for $Q$ in answer 136, line 16 (20.10.27) $\displaystyle Q= {1\over2}\pmatrix{-1&-\phi&1/\phi\cr -\phi&1/\phi&-1\cr1/\phi&-1&-\phi\cr}$ \becomes $\displaystyle Q= {1\over2}\pmatrix{1&-\phi&1/\phi\cr \phi&1/\phi&-1\cr1/\phi&1&\phi\cr}$ \endchange \bugonpage 4f5.260 line 9 of answer 138 (20.07.23) $96/6=12$ cases \becomes $96/6=16$ cases \endchange \bugonpage 4f5.263 line 5 of answer 145 (20.07.24) 3 three odd \becomes 3 odd \endchange \bugonpage 4f5.277 replacement for answer 189{(a)} (19.12.19) (a) $\vert e^{e^z}\vert=\vert e^{e^x\cos y+ie^x\sin y}\vert= \exp(e^x\cos y)$; $\vert e^{-e^z}\vert=\exp(e^{-x}\cos y)$.\par \endchange \amendpage 4f5.280 line $-4$ of answer 207 (20.11.06) 96 G$\mu$, with a 55-meganode \becomes 92 G$\mu$, with a 54-meganode \endchange \bugonpage 4f5.284 replacement for answer 232 (20.10.18) \def\dol/{$\losup\$$}% \ans232. No. Algorithm X\dol/ finds 96 solutions of minimum cost \$84; but the true solution in Fig.~\fig74/(a) actually costs \$86 by this measure. The effects of 16 rounding errors, each potentially changing the result by nearly~\$1, have invalidated everything. [Therefore the author used $\$\lfloor 2^{32}d(i,j)\rfloor$ when preparing Fig.~\fig74/. This was safe, because the distance between the first 8 solutions and the 9th was greater than 16\dash---in fact, {\it much\/} greater, although a difference of only 17 would have been convincing.]\tighten \endchange \bugonpage 4f5.286 in answer 239 (19.11.26) line 3: cost $\epsilon^i$ \becomes cost $\epsilon^j$\nl line 9: {\sl Graphs and Algorithm\/} \becomes {\sl Graphs and Algorithms\/} \endchange \improvepage 4f5.286 line 8 of answer 239 (19.11.28) smaller cost $\epsilon^4$ \becomes smaller additional cost $0+\epsilon^4$ \endchange \bugonpage 4f5.288 line 3 of answer 249 (20.01.26) Set $l=t=0$. \becomes Set $l\gets t\gets0$. \endchange \bugonpage 4f5.293 lines 1 and 2 (20.08.28) exact problem \becomes exact cover problem \endchange \bugonpage 4f5.298 line 2 of answer 283 (20.09.02) 365(b) \becomes 282(b) \endchange \bugonpage 4f5.304 replacement for first paragraph of answer 303 (20.02.06) \ans303. (a) Represent the tree as a sequence $a_0a_1\ldots a_{2n-1}$ of nested parentheses; then $a_0$ will match $a_{2n-1}$. The left boundary of the corresponding parallomino is obtained by mapping each `\.(' into N or~E, according as it is immediately followed by `\.(' or `\.)'. The right boundary, similarly, maps each `\.)' into N or~E according as it is immediately {\it preceded\/} by `\.)' or `\.('. For example, if we take 7.2.1.6--\eq(1) and enclose it in an additional pair of parentheses, the corresponding parallomino is shown below with part~(d).\tighten\par \endchange \bugonpage 4f5.304 replacement for lines 6, 7, 8 of part {(b)} (20.01.19) \noindent $1+1+1+1+2+2+2+2+2+2+2+2+2+1+1$; there's an ``outer''~$G$, whose $H$ is $yxyGy$, and an ``inner''~$G$, whose $H$ is $xyyxyxxy$.) Thus we can write $G$ as a continued fraction,\tighten $$G(w,x,y)=wxy\big/\bigl(1-wx-wy-w^3\?xy/(1-w^2\?x-w^2\?y-w^5\?xy/ (\,\cdots\,))\bigr).$$ \endchange \amendpage 4f5.315 in last paragraph of answer 327 (19.12.22) Hall (clip, underpass) \becomes Hall (piano, clip, underpass)\nl Morgan (face, gorilla, smile) \becomes Morgan (piano, face, gorilla, smile) \endchange \amendpage 4f5.318 line $-6$ of answer 337 (19.12.14) [these illustrations should be darker, I've now thickened the lines] \endchange \bugonpage 4f5.322 line 7 (19.12.25) {\sl Budapestiensis\/} \becomes {\sl Budapestinensis\/} \endchange \amendpage 4f5.322 lines $-3$ and $-2$ of answer 346 (19.12.14) (online 18 June 2018) \becomes {\bf61} (2019), 271--284 \endchange \amendpage 4f5.322 replacement for line $-2$ of answer 349 (20.10.18) \noindent $$\def\epsfsize#1#2{.27#1} \def\\#1{\vcenter{\epsfbox{\figdir/v4b.72#1}}} \let\quad=\enspace \centerline{$\\0\quad\\0\quad\\0\quad\\0\quad\\1\quad\\2\quad\\3\quad \\4\quad\\5\quad\\6\quad\\7\quad\\8\quad\\8\quad\\8\quad\\8$}$$\par \endchange \amendpage 4f5.322 replacement for line $-3$ of answer 350 (20.10.18) \noindent $$\def\epsfsize#1#2{.4#1} \def\\#1{\vcenter{\epsfbox{\figdir/v4b.71#1}}} \let\quad=\enspace \\0\quad\\0\quad\\0\quad\\1\quad\\2\quad\\3\quad \\4\quad\\5\quad\\6\quad\\7\quad\\7\quad\\7$$ \endchange \bugonpage 4f5.325 line 13 (20.09.25) planar places \becomes planar pieces \endchange \bugonpage 4f5.326 line 4 of answer 357 (20.09.28) if and only the \becomes if and only if the \endchange \amendpage 4f5.332 and 333, in answer 375 (20.02.10) perimeter \becomes semiperimeter \quad [throughout] \endchange \bugonpage 4f5.333 in answer 375{(b)} (20.02.10) $h_6,h_4)$ \becomes $h_6,h_5)$\qquad [four times] \endchange \bugonpage 4f5.333 line 4 of answer 376 (20.02.09) $d=(w+1)/(w(w+2))$ \becomes $d=(w+2)/((w+1)(w+3))$ \endchange \improvepage 4f5.335 line 4 of answer 383 (19.11.30) dissection, into \becomes dissection, of a $92\times92\times92$ cube into \endchange \amendpage 4f5.340 last line of answer 398 (20.03.30) published by Tatsuo Yano \becomes published by Ryuoh Yano \endchange \amendpage 4f5.344 replacement for answer 413 (19.12.23) \ans413. (Solution simplified by R. Molinari.) Let each record for an item include two new fields \.U and \.V. The \.U and \.V fields of a secondary item that represents edge $u\adj v$ will point to the primary items $u$ and~$v$. The \.U and \.V fields of a primary item that represents vertex~$v$ are renamed \.{MATE} and \.{INNER}. \.{MATE($v$)} is zero until $v$ first becomes the endpoint of an edge, after which it points to the other endpoint of the path fragment containing that edge. \.{INNER($v$)} is nonzero when $v$~lies within a path fragment.\par Introduce two new global variables: Global variable \.F is the current number of fragments. Global variable \.E is the edge that closed a loop, or zero if there's no loop.\par For example, suppose two edges currently have color~1, say $v_1\adj v_2$ and $v_3\adj v_4$. Then we've set $\.{MATE($v_1$)}\gets v_2$, $\.{MATE($v_2$)}\gets v_1$, $\.{MATE($v_3$)}\gets v_4$, $\.{MATE($v_4$)}\gets v_3$, and $\.F\gets2$. If now $v_2\adj v_5$ joins the fray, we set $\.{MATE(MATE($u$))}\gets u$, $\.{MATE(MATE($v$))}\gets v$, and $\.{INNER($v_2$)}\gets1$; but we leave \.{MATE($v_2$)} unchanged. Subsequent edges to~$v_2$ are rejected.\tighten\par When the `purify' routine \eq(55) is called to give color~1 to a new edge~$i$, it will refuse to do~so when \.E is nonzero, because a loop has already been closed. Furthermore, when $\.E=0$, it will know that edge~$i$ shouldn't be chosen if \.{U($i$)} and \.{V($i$)} are mates and $\.F\ne1$, because that would close a loop disjoint from other fragments. On the other hand, it {\it will\/} close the loop if $\.F=1$, also setting $\.E\gets i$.\par All of these operations are nicely and easily undone when we need to `unpurify'. For example, suppose edge~$i$ loses color~1 when $u=\.{U($i$)}$ and $v=\.{V($i$)}$. If $v=\.{MATE($u$)}$, we unclose the loop (and set $\.E\gets0$) if $i=\.E$; otherwise we zero the mates and set $\.F\gets\.F-1$. If $\.{MATE($u$)}\ne\.{MATE($v$)}$, we set $\.{MATE($u$)}\gets u$, $\.{MATE($v$)}\gets v$, $\.{INNER($u$)}\gets\.{INNER($v$)}\gets0$, $\.F\gets\.F+1$. The case $\.{MATE($u$)}=\.{MATE($v$)}$ is easy too.\par \em Caution: Algorithm P must be modified so that it never discards redundant items, when it is used to preprocess a problem for this extension of Algorithm~C. \endchange \amendpage 4f5.346 {(originally page 347)} line $-3$ of answer 421 (20.03.30) by Tatsuo Yano \becomes by Ryuoh Yano \endchange \bugonpage 4f5.346 {(originally page 347)} last line of answer 421 (19.12.24) {\bf89} \becomes {\bf90} \endchange \amendpage 4f5.348 replacement for lines 3--5 of answer 425 (19.12.25) \noindent not. Solutions for $k=2$ exist for all $n\ge3$; solutions for $k=3$ exist for all $n\ge4$; solutions for $k=4$, due to B.~S. Ho, exist for all $n\ge5$; solutions for $k=5$ and $k=6$, due to G.~J.~H. Goh, exist for all $n\ge6$. (See (xviii)--(xxiv) in Fig.~\fig A--5/.) Goh has also discovered analogous constructions for $k=7$, 8, 9,~10. \endchange \improvepage 4f5.348 lines 4 and 5 of answer 426 (20.03.30) \setbox1= \hbox{$\def\epsfsize#1#2{.75#1}\,\vcenter{\epsfbox{\figdir/v4b.951}}\,$}% \setbox0= \hbox{$\def\epsfsize#1#2{.75#1}\,\vcenter{\epsfbox{\figdir/v4b.950}}\,$}% there cannot be three consecutive `\copy1', nor five `\copy0's that form an X or~T. \becomes there cannot be three consecutive `\copy1's. \endchange \bugonpage 4f5.349 replacement for {(xx), (xxi), (xxii)} in Fig.~A--5 (19.12.24) \begingroup \def\epsfsize#1#2{.7#1}% \noindent\epsfbox{\figdir/v4b.4920}\qquad \epsfbox{\figdir/v4b.4921}\qquad \epsfbox{\figdir/v4b.4922} \endgroup \endchange \bugonpage 4f5.355 line 14 of answer 445 (19.12.04) {\mc MCC problem} \becomes {\mc MCC} problem \endchange \amendpage 4f5.356 three new lines for the end of answer 449 (20.02.07) \noindent The current record for largest literary hitori nugget, $12\times5=60$, was found by Gary McDonald in September 2019: ``Ruth intimated that, as far as she could judge, he was a very eligible swain.'' [Charles Dickens, {\sl Martin Chuzzlewit}.] \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 4f5.361 and following (19.09.17) Miscellaneous changes to the existing index of Volume~4 Fascicle~5 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 Ase, Mitsuhiro (\JC46:48:-2:40% J1604 %% unicode char "963f \JC48:48:0:40% J3205 <1c003000000c0f003c00001e07c03e03ffff03e03e01ffff01f03c0001e001f03c0003e0% 00f03c3003c000603c780780000ffffcc7180007fffcee3c00003c00fffe00003c00fffe% c00c3c20f03c700e3c70f03c780ffff8f03c3c0ffff8f03c3e0e3c70f03c3e0e3c70f03c% 3e4e3c70fffc1c4e3c70fffc004e3c70f03c004e3c70f03c004e3c70f03c00ce3c70f03c% 00ce3c70f03c00ce3c70f03c00cffff0f03c01cffff0fffc01ce3c70fffc018c3c20f03c% 03803c00f03c03803c00f03c07807f00f03c1f007f80f03cff007fc0f03c7f00fde0f03c% 3f00fcf0fffc3e01fcf0fffc1e03fcf060181e03bc6000001f073c0010e01f0e3c003878% 0f9c3c003c3e0fb03c007c1f0fc03c00780f0fc03c01f00f07c03c07e00f0380181f0006% >%% unicode char "702c \JC48:48:0:40% J2487 <000007800000000007c00000000003e00380000003e003e0038003c003f003c003c003f0% 01f003c003e001fc03c003e000fe03c007c0007e03c00780003f03c00f00003f03c00e00% 001f03c01c00000f03c03800000f03c07000000603c0e000000003c3c000000003c30000% 000003c0000c000003c0001effffffffffff7fffffffffff0000f03c00000000f03c0000% 0000f03c00000000f03c00000000f03c00000000f03c00000000f03c00000000f03c0000% 0000f03c00000000f03c00000001f03c00000001f03c00000001f03c00000001e03c0000% 0003e03c00080003e03c000c0007c03c000c0007c03c000e000f803c000f001f003c000f% 003e003c000f007c003e001f00f8003fffff07e0003fffffffc0001ffffefe00000ffffc% >%% unicode char "5149 \JC46:48:-2:40% J3572 <00000c00000000000f00000000000f80000000000f80000004000f00000004000f000000% 0c000f0000300c000f0000781ffffffffffc1ffffffffffc3c00000000787c0000000078% fc00000000f0f8000c0001e0f8000f0003c070000f80038000000f80000000000f000000% 00000f00000000000f00000003000f00180003c00f003c0003fffffffe0003fffffffe00% 03c00f003c0003c00f003c0003c00f003c0003c00f003c0003c00f003c0003c00f003c00% 03c00f003c0003c00f003c0003fffffffc0003fffffffc0003c00f003c0003c00f003c00% 03c00f003c0003c00f003c0003c00f003c0003c00f003c0003c00f003c0003c00f003c00% 03fffffffc0003fffffffc0003c000003c0003c000003c0003c000001800018000000000% >%% unicode char "5b99 ), 346. % 2nd Baumert, Leonard Daniel, 52, 221, 371. % 3rd Bitwise {\mc AND} ($\band$), 17, 126, 208, 227, 350. % 2nd Bitwise {\mc OR} ($\bor$), 17, 126. % 2nd Briggs, Preston, 39. % 3rd Brotchie, Alastair, 245. % 2nd Bucket elimination, \see Frontier. % 2nd Chuzzlewit, Martin, 356. % 2nd Coffin, Stewart Temple, 324. % 3rd Cutsets, 344. % 2nd $d^+(v)$ (out-degree of $v$), 218, 247, 337. % 2nd Dickens, Charles John Huffam, 356. % 2nd Distance, dynamically updating, 57. % 2nd Embedded graphs, 130. % 3rd $f^\uparrow$ (maximal elements of family~$f$), 353--354. % 2nd Franel, J\'er\^ome, 207. % 2nd Goh, Jun Herng Gabriel (\GC76:74:-3:60% G4666 <00000000000001c000000000f000000007e0000000007c0000000fe0000000007fffffff% fff0000000007ffffffffff8000000007ffffffffff8000000007e00000007e000000000% 7e00000007e0000000007e00000007e0000000007e00000007e0000000007e00000007e0% 000000007e00000007e0000000007e00000007e0000000007e00000007e0000000007e00% 000007e0000000007e00000007e0000000007e00000007e0000000007e00000007e00000% 00007e00000007e0000000007fffffffffe0000000007fffffffffe0000000007fffffff% ffe0000000007e00000007e0000000007e00000007e0000000007e00000007e000000000% 7e00000007e000000000fc000000001c00000000fc000000003e0000000000000000007f% 000000000000000000ff8000003fffffffffffffc000001fffffffffffffe000001fffff% ffffffffe000000800003f0000000000000000003f0000000000000000003f0000000000% 000000003f0000000000000000007f0000000000000000007f0000000000000000007f00% 00000000000000007f0000003800000000007f000000fc00000000007e000001fe000000% 00007e000003ff003fffffffffffffffff801fffffffffffffffffc01fffffffffffffff% ffc008000001fdc00000000000000001f9e00000000000000001f8f00000000000000003% f0f80000000000000003f0780000000000000003f07c0000000000000007e03e00000000% 00000007e03f000000000000000fc01f800000000000001fc00fc00000000000003f8007% e00000000000003f0007f00000000000007e0003fc000000000000fe0001ff0000000000% 01fc0000ffc00000000007f800007ff0000000000fe000001ffe000000003fc000000fff% 800000007f80000007fff0000001fe00000001fffff00007fc000000007ffff0001ff000% 0000003fffc0007fc0000000000fff8003ff000000000003fe001ffc0000000000007800% fff00000000000001000e0000000000000000000>%% unicode char "5434 \GC79:77:-1:63% G3094 <000000000001e0000000000000000001f8000000000000000003fe000000000000000003% fe000000000700000007fc0000000007e0000007f00000000007f800000fe00000000007% f800001fc0e000000007f000001f80f000000007e000003f007c00000007e000007e001f% 80000007e00000fc000fe0000007e00001f80007f0000007e00003f00003fc000007e000% 07e00001fe000007e0001fc00000ff000007e0007f800000ff000007e007ffffffffff80% 0007e007ffffffffff803807e1c3fffffffc1fc03e07e1f1ffffff801fc03f87e1f8ffff% e0000fc03fe7e1fe7ffc00000fc03fe7e1fe00e0000007c03f87e1fc00f000f006003f07% e1f801f801fc00003f07e1f801fc00fe00003f07e1f803fc007f80003f07e1f807f8001f% e0003f07e1f80ff0000ff8003f07e1f80fe00007fc003f07e1f81fc00003ff003f07e1f8% 3f9c0001ff803f07e1f8fe3f8000ffc03f07e1f9fc3fe0007fc03f07e1fbf03fe0003fc0% 3f07e1ffe07fe0001fc03f07e1ff807f80000fc03f07e1fe007f001c0f803f07e1f800fc% 001e07003f07e1f800f8003f02003f07e1f801ffffff80003f07e1f801ffffffc0003f07% e1f803ffffffe0003f07e1f807f0001fe0003f07e1f807f8003fe0003f07e1f80f78003f% 00003f07e1f80e7c003e00003f07e1f81c3c003e00003f07e1f8383c007e00003f07e1f8% 781e007c00003f07e1f9f01e00fc00003f07e1fbf01e00f800003f07e1ffe00f01f80000% 3f07e1ff800f01f000003f07e3ff000f83f000003f07fff80007cfe000003f0ffdf80007% dfe000007ffff1f80003ffc00000ffffc1f80003ff8000007ffe01f80001ff0000003ff0% 01c00003ff8000001f0001000007ffc0000008000000000ffff0000000000000001ffff8% 000000000000003feffe000000000000007f83ffc0000000000001ff01fff00000000000% 07fe00fffe00000000001ff8003ffffc000000007ff0001ffffe0000000fffc00007fffe% 000000fffe000003fff000001ffff8000000ffc00001ffffe00000001f000001fffc0000% 000002000001ffc0000000000000>%% unicode char "5cfb \GC74:74:-3:61% G2667 <001c0000000000000000001f8000000000000000001fe000000000000000001ff0000000% 00000000001fe000000000000000001fe00000000000e000001fc00000000001f000001f% 800000000003fc00001f800000000007fe00001f807fffffffffff00001f803fffffffff% ff00001f801c000000000000001f8000000000000000001f8000000000000000001f8000% 000000000000001f8000000000000000001f8000000000000000001ff001c000003c0000% 001ffe01f000007e0000001fff81f800007f0000061f9fc1fc0000ff8000061f8ff1ffff% ffffc000071f87f1ffffffffc000071f83f8f800007f8000071f83f8f800007f0000071f% 81f8f800007e0000071f81f8f800007e00000f1f81f0f800007e00000f1f81f0f800007e% 00000f1f8040f800007e00001f1f8000f800007f00001f1f8000f800007f00007f1f8000% f800007f0000ff1f8000f800007f0000ff1f8000f800007f00007f1f8000f800007f0000% 7f1f8000ffffffff00003c1f8000ffffffff0000001f8000f800007f0000001f8000f800% 007f0000001f8000f800007f0000001f8000f800007f0000001f8000f800007f0000001f% 8000f800007f0000001f8000f800007f0000001f8000f800007f0000001f8000f800007f% 0000001f8000f800007f0000001f8000f800007f0000001f8000f800007f0000001f8000% f800007f0000001f8000ffffffff0000001f8000ffffffff0000001f8000ffffffff0000% 001f8001f800007f0000001f8001f800007f0000001f8001f800007e0000001f8001f800% 007e0000001f8001f00000000000001f8001f00000000000001f8000000000000000001f% 8000000000003800001f8000000000007c00001f800000000000fe00001f800000000001% ff00001f9fffffffffffff80001f8fffffffffffffc0001f87ffffffffffffc0001f8000% 000000000000001f8000000000000000001f8000000000000000001f8000000000000000% 001f8000000000000000001e0000000000000000>%% Unicode char "6052 ), 348. % 2nd Golomb, Solomon Wolf, 35, 52, 77, 78, 82, 155, 221, 294, 310, 371. % 3rd Historical notes, 28, 31--32, 51--52, 79--80, 121, 198--200, 210, 226, 248, 258--262, 265, 277, 290--291, 293, 295, 301, 308, 317--319, 322, 325--326, 334, 337, 340, 343, 346. % 2nd Ho, Boon Suan (\GC74:73:-4:60% G2646 <0000f0000000000000000000f8000000000000000000fe000000000000000001ff000000% 000000000001ff000000000078000001fe0000000000fc000001fc0000000000fe000001% f00000000001ff000003f00000000003ff800003e7ffffffffffffc00007e1ffffffffff% ffc00007c0ffffffffffffc0000fc0000000007e0000000f80000000007e0000001f8000% 0000007e0000001f00000000007e0000003f00000000007e0000003e00000000007e0000% 007e00000000007e0000007c00000000007e0000007f80000000007e000000ffe0000007% 007e000000fff038000f807e000000efc03e001fc07e000001ef803fffffe07e000001cf% 803ffffff07e000003cf803ffffff07e0000038f803f000fe07e0000078f803f000f807e% 0000070f803f000f807e00000f0f803f000f807e00000e0f803f000f807e00001e0f803f% 000f807e00003c0f803f000f807e00007c0f803f000f807e0000f80f803f000f807e0000% e00f803f000f807e0000400f803f000f807e0000000f803f000f807e0000000f803f000f% 807e0000000f803f000f807e0000000f803f000f807e0000000f803f000f807e0000000f% 803f000f807e0000000f803fffff807e0000000f803fffff807e0000000f803f000fc07e% 0000000f803f000fc07e0000000f803f000fc07e0000000f803f000fc07e0000000f803f% 000f807e0000000f803f000f807e0000000f803e0000007e0000000f80380000007e0000% 000f80000000007e0000000f80000000007e0000000f80000000007e0000000f80000000% 007e0000000f80000000007e0000000f80000000007e0000000f80000000007e0000000f% 80000000007e0000000f80000000007e0000001f80000000007e0000001f8000000fff7e% 0000001f8000000ffffc0000001f800000007ffc0000001f800000001ffc0000001f8000% 00000ffc0000001f8000000003f80000001f8000000003f80000001f8000000003e00000% 00000000000003c00000>%% Unicode char "4f55 \GC73:72:-4:61% G4636 <0000000380000000000000000001e0000000000000000000f0000000000000000000fc00% 00000000000000007e0000000000000000007f0000000000000000003f80000000000000% 00003f8000000000000000003fc000000000000000001fc000000000000000001fc00000% 0000000000001fc00000e000000000001f800001f000000000000f800003f80000000000% 07000007fc00000000000000000ffe007fffffffffffffffff003fffffffffffffffff80% 1fffffffffffffffff80000007c00003f0000000000007c00003f0000000000007c00007% f0000000000003c00007f0000000000003e00007f0000000000003e00007f00000000000% 03e00007f0000000000003e00007f0000000000001f0000ff0000000000001f0000ff000% 0000000001f0000fe0000000000001f8000fe0000000000000f8001fe0000000000000fc% 001fc0000000000000fc001fc0000000000000fc001fc00000000000007e003f80000000% 0000007e003f800000000000003f007f000000000000003f007f000000000000003f007e% 000000000000001f80fe000000000000001f80fc000000000000001fc1fc000000000000% 000fc3f8000000000000000fe7f8000000000000000fe7f00000000000000007ffe00000% 000000000007ffc00000000000000003ffc00000000000000003ff800000000000000001% ff800000000000000001ffc00000000000000001fff00000000000000003fff800000000% 00000007fffc000000000000000ff7fe000000000000001fe3ff800000000000003fc1ff% c0000000000000ff807ff0000000000001ff003ff8000000000007fe001ffe0000000000% 0ff8000fffe0000000003fe00007fffe00000000ffc00001ffffff000007ff0000007fff% ff80001ffc0000001fffff80007ff000000007fffc0003ffe000000001fff8001fff8000% 0000000ff000fffe0000000000004000fff00000000000000000ffc00000000000000000% >%% Unicode char "6587 \GC78:79:-1:64% G4889 <0000e0000000000000000001f8000000000000000001fc000000000000000001ff000000% 000000000003ff000000000000000003fe000000000000000003fe00000000003c000003% fc00000000007e000007fc0000000000ff000007f80381ffffffff800007f807c0ffffff% ffc0000ff00ff07fffffffc0000ff01ff8700fc00000fffffffffc000fc000007fffffff% fc000fc000003c1fc00000000fc00000001fc00000000fc00000001f800000000fc00000% 003f800000000fc00000003f800000000fc00000003f800000000fc00000007f00000000% 0fc00000007f700000000fc00000007f7c0000000fc00000007f7f0000000fc0000000fe% 7fc000000fc0000000fe3fe000000fc0000000fc3fc000000fc0000001fc3fc000000fc0% 000001f83e0000000fc0000001f83e0000000fc0000003f83e0000000fc0000003f03e00% 00000fc0038003f03e0000000fc007c003e03e0700000fc00fe003e03e0f80000fc01ff0% 3fc03e1fdffffffffff83ffffffffffffffffffc1ffffffffffffffffffc0ffffffff780% 0fc0000007003e0000000fc0000002003e0000000fc0000000003e0000000fc000000000% 3e0000000fc0000000003e0000000fc0000000003e0000000fc0000000003e0000000fc0% 000000003e0000000fc0000000003e00fc000fc0000000003e07fc000fc0000000003e7f% e0000fc0000000003fff80000fc0000000003ffc00000fc000000000fff000000fc00000% 000fff8000000fc0000001fffe0000000fc000001ffffe0000000fc00000fffffe000000% 0fc000007fff3e0000000fc000003ffe3e0000000fc000001ff03e0000000fc000001fc0% 3e0000000fc0000000003e0000000fc0000000003e0000000fc0000000003e0000000fc0% 000000003e0000000fc0000000003e0000000fc0000000003e0000000fc0000000003e00% 00000fc0000000003e0000000fc0000000003e0000000fc0000000003e0000000fc00000% 00003f0000000fc0000000003f0000000fc0000000007f0000001fc0000000007f000000% 1fc0000000007f0000001fc0000000007f0000001fc000000000780000001e000000>%% u"8f69 ), 348. % 2nd Janson, Carl Svante, vi, 186, 194, 196, 200. % 3rd Kernels of a graph (maximal independent sets), 143, 244, 269. % 2nd L-twist, 80, 172, 336. % 3rd Linear programming problems, 287, 332--333. % 2nd Lou, Xingliang David (\GC79:78:-1:63% G3406 <000000001e0000000000000000001f8000000000000000000fe000000000000000000ff0% 000000000003c0000ff0007800000001e0000fc0007c00000000fc000f8000fe00000000% 7e000f8000ff000000003f000f8001ff800000001f800f8001fe000000000fc00f8003f8% 0000000007e00f8003f00000000007e00f8007e00000000003f00f800fc00000000003f0% 0f800f000000000001f00f801e003800000001e00f807c007c00000000e00f81f000fe00% 000000c00f87c001ff0003ffffffffffffffff8001ffffffffffffffffc001ffffffffff% ffffffc000f0001fff8f000000000000003fefc7c00000000000003fcfc3e00000000000% 007f8fc3f0000000000000ff0fc1f8000000000001fe0fc0fe000000000003fc0fc07f80% 0000000007f80fc03fe0000000001fe00fc01ff8000000003fc00fc007ff000000007f80% 0fc003ffe0000000ff000fc001fffc000003fc001fc000fffffe000ff0007f80003ffffe% 001fc0007f800007fff8007f00007c000001ffe003fc00007e0000001f801fe000007f00% 00000100ff800000ff0000000000e0000000ff000000000000000001fe0000001c000000% 0001fe0000003e0000000003fc0000003f0000000007f80000007f800000000fc0000000% ffc007ffffffffffffffffe003fffffffffffffffff001e0001f80003f8000000000003f% 00003f8000000000003f00003f0000000000003e00007f0000000000007e00007f000000% 0000007c0000ff000000000000f80001fe000000000001f00003fc000000000003f80007% fc000000000007ff800ff8000000000007fff81ff00000000000007fffffe00000000000% 0007ffffc0000000000000001ffff80000000000000003ffff8000000000000007fffff8% 0000000000001ffffffe0000000000003ff8ffff800000000000ffe03fffe00000000003% ffc007fff0000000001fff0001fff0000000007ffe00007ff800000001fff800003ff800% 00003fff8000000ff8000007fff800000003f8003fffff8000000001f8003ffff8000000% 000070000010000000000000300000000000000000001000>%% unicode char "5a04 \GC77:74:-2:62% G4839 <00000000000000380000000e00000000007c0000000f80000000007e00000007c0000000% 00fe00000007f000000001ff00000007ffffffffffff80000007ffffffffffff80000007% c0000000007f00000007c0000000007e00000007c0000000007c00000007c0000000007c% 00000007c0000000007c00000007c0000000007c00000007c0000000007c00000007c000% 0000007c00000007c0000000007c00000007fffffffffffc00000007fffffffffffc0000% 0007c0000000007c00000007c0000000007c00000007c0000000007c00000007c0000000% 007c00000007c0000000007c00000007c0000000007c00000007c0000000007c00000007% c0000000007e00000007c0000000007e00000007c0000000007e0000000ffffffffffffe% 0000000ffffffffffffe0000000fc0000000007e0000000fc0001e00007e0000000fc000% 1f80007e0000000fc0001ff000780000000fe0001ff0000000000001f0001ff000000000% 0001fc001fe0000000000001fe001fc0000000000003fe001fc0000380000003fc001f80% 000fc0000003f8001f80001fe0000007f8001f80003ff0000007fffffffffffff800000f% fffffffffffffc00000ffffffffffffffe00001f00001f8000000000001f00001f800000% 0000003e00001f8000000000003e00001f8000000000007c00001f800000000000fc0000% 1f800000000000f800001f800070000001f800001f8000f8000001f000001f8001fc0000% 03f000001f8003fe000003e000001f8007ff000007c7ffffffffffff80000f81ffffffff% ffff80001f80ffffffffffff80003f0030001f80000000007e0000001f8000000000f800% 00001f8000000000f00000001f8000000000400000001f8000000000400000001f800000% 0000000000001f8000001e00000000001f8000003f00000000001f8000007f8000000000% 1f800000ffc0000000001f800001ffe0fffffffffffffffffff07ffffffffffffffffff8% 7ffffffffffffffffff820000000000000000000>%% unicode char "661f \GC79:80:0:64% G3333 <00000000380000000000000000007e0000000000000000003f0000000000000000001f80% 00000000000000001fc000000000000000000fc0000000000000000007e0000000000000% 000007e000001c000000000003c000003e000000000003c000007f800000000003800000% ffc00000000003800001ffe00ffffffffffffffffff007fffffffffffffffff002000000% 0000000000000000000000000000000000000000000003c0000000003800000003c00000% 00003e00000007f8000000003f80000007fc000000001ffffffffffc000000001fffffff% fffc000000001f80000003f8000000001f80000003f0000000001f80000003f000000000% 1f80000003f0000000001f80000003f0000000001f80000003f0000000001f80000003f0% 000000001f80000003f0000000001f80000003f0000000001f80000003f0000000001fff% fffffff0000000001ffffffffff0000000001f80000003f0000000001f80000003f00000% 00e01f80000003c0000000e01f0000000000070000e01f00000000000f8000e000000000% 00000fe000e00000000000001ff000fffffffffffffffff803fffffffffffffffffc03e0% 0000000000003ffe03e00000000000003ff003e00000000000003fe007e0000000000000% 7f800fe00000000000007c007fe000000000e000f0007fe000380001f007c0007fc0003e% 0001fc0780003f80003f0003fe0600003e00003fffffff0200000800003fffffff000000% 0000003f0003ff0000000000003f0003ff0000000000003f0003fc0000000000003f0003% f00000300000003f0003f00000300000003f0003f00000300000003f0003f00000300000% 007f0003f00000300000007f0003f00000300000007f0003f00000300000007e0003f000% 0030000000fe0003f0000030000000fc0003f0000078000001fc0003f00000f8000001f8% 0003f00000fc000003f80003f80000fe000007f00003fc0000fe00000fe00003fffffffe% 00001fc00001fffffffe00003f800001fffffffe0001ff000000fffffff80007fc000000% 3ffffff001ffe000000000000000ffff8000000000000000fff80000000000000000ffc0% 0000000000000000>%% unicode char "4eae ), 224. % 3rd Luria, Zur ({\heb\Haa/\Hyy/\Hrr/\Hvv/\Hll/ \Hrr/\Hvv/\Hts/}), 207. % 3rd Magen, Avner ({\heb\Hfn/\Hgg/\Hmm/ \Hrr/\Hnn/\Hbb/\Haa/}), 26. % 3rd {\mc MCC} problems: Multiple covering with colors, iv, 91--93, 121, 142--144, 239, 240, 251, 267--271, 280, 302, 303, 306, 325, 355. % 2nd McDonald, Gary, 250, 356. % 2nd Median function ($\langle xyz\rangle$), vi, 24, 201, 353. % 3rd Median value of a random variable, 14, 204. % 3rd Minimum cutsets, 344. % 2nd Mirror images, \see Reflection symmetry. % 3rd Modifications of Algorithm 7\period2\period2\period1C and related algorithms, 124, 125, 130, 131, 136, 181, 230, 250, 253, 350. % 2nd Molinari, Rory Benedict, 344. % 2nd $n$ queens problem (independent queens), 29--32, 44--46, 51--53, 68--71, 103, 108, 110--111, 116, 120, 121, 124--126, 143, 148, 232. % 2nd $n$-queens problem (dominating queens), 91--92, 142. % 2nd Nixon, Dennison, 319. % 2nd OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}), 230, 231, 263, 277, 312, 324. % 3rd Onnen, Hendrik, Sr\period, 32. % 2nd Ordered options, \see Pairwise ordering trick. % 2nd Pendant vertex: A vertex of degree one, 314. % 2nd Pinch, Ruth, 356. % 2nd Pittel, Boris Gershon ({\rus Pittelp1, Boris Gershonovich}), 196, 231. % 3rd Projection vectors, 345, 346--348. % 2nd Queen domination problems, 91--92, 142. % 2nd R-twist, \see L-twist. % 3rd Reflection symmetry, 40, 53, 81, 89, 165, 169, 172, 206, 236--237, 257, 260--262, 303. % 3rd Social distancing, 157. % 3rd Stappers, Filip Jan Jos, 234. % 2nd Stork, David Geoffrey, 183. % 2nd Ternary commafree codes, 36--37, 39, 214. % 3rd Torczon, Linda Marie, 39. % 3rd Trybu{\l}a, Stanis{\l}aw Czes{\l}aw, 183. % 2nd Windsor, Aaron Andrew, 213, 214. % 3rd \.{WORDS}($n$), the $n$ most common five-letter words of English, 34, 54, 60, 92, 131, 181, 209, 242, 251, 271--272, 292. % 2nd Yano, Tatsuo (= Ryouh, \JC48:47:0:40% J4480 <000800000000000e00000000000f80000000000fe0000000001ff0000000001fe0000000% 001fc0000000001f80000000003f80000600003f00000f00003fffffff80007fffffff80% 007c0600000000f807c0000000f007e0000001e007e0000003c007c00000038007c00000% 070007c000000e0007c00000180007c00000300007c00018000007c0003c7ffffffffffe% 3ffffffffffe000007c00000000007c0000000000fc0000000000fe0000000001fe00000% 00001f70000000003e70000000003e38000000007e38000000007c1c00000000f81e0000% 0001f80f00000003f00780000007e007c000000fc003f000001f8001fc00003f0000ff80% 00fe00007ff801f800003fff07e000000ffe3f00000003fef8000000007c>%% unicode "77e2 \JC48:48:0:40% J4478 <3000180000183c003c00003c3ffffefffffe3ffffe7ffffe3c3c3c0001fc3c3c3c0001f8% 3c3c3c0003f03c3c3c0003e03c3c3c0007803c3c3c1c07003c3c3c070c003c3c3c07c000% 3ffffc03e0003ffffc01f0003c3c3c01f0003c3c3c00f0003c3c3c00e00c3c3c3c00001e% 3c3c3fffffff3c3c3dffffff3c3c3c00f83f3c3c3c00f83e3ffffc00f87c3ffffc00f878% 3c3c3c00f8f0183c1800f8e0003c0000f9c0003c0000f980003c0000fb00003c1800fa00% 003c3c00f8003ffffe00f8001ffffe00f800003c0000f800003c0000f800003c0000f800% 003c0000f800003c0000f800003c0000f800003c3fc0f800007ffc00f800fffff000f800% ffff0000f8007ff80001f8007fe0003ff8007c000007f80020000001f00000000000e000% >%% unicode char "91ce \JC48:48:0:40% J4622 <003000600000003c00780000003e007c0000003e007c0060003c307800f0003c787ffff8% 3ffffc7ffff81ffffc7800000303807800000383c07800c001c3e07801e001c3c07ffff0% 01e7807ffff001e7007801e001e70c3001e000c61e0001e0ffffff0001e07fffff6001e0% 0000007801e00c00607fffe00f00f07fffe00ffff87801e00ffff87800c00f00f0780000% 0f00f07803000f00f07807800f00f07fffc00ffff07fffc00ffff07800000f00f0780000% 0f00f07803000f00f07807800f00f07fffc00ffff07fffc00ffff07800000f00f0780000% 0f00f07803000f00f07807840f00f07fffc40f00f07fffc40f00f078000c0f00f078000e% 0f00f078000e0f01f078001f0f3ff07c003f0f07f07fffff0f01f07ffffe0600e03ffffc% >%% unicode char "9f8d \JC48:44:0:38% J1806 <0000000000300000000000783ffffffffffc1ffffffffffc000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c000c0000003c001e00ffffffffff007fffffffff0000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c00000000003c00000% 000003c00000000003c00000000003c00000000003c00000000003c0001c000003c0003e% ffffffffffff7fffffffffff>%% unicode char "738b ), 340, 346. % 3rd \vfill % TEMPORARY \enddoublecolumns \endchange \bye [The next printing will be the 3rd.] not listed above: page 30, I've made the lines of Fig 68 twice as thick page 45, lines 11-12 after the caption, "Incidentally, ..." page 56, better wording of exercise 42 page 65, changed wording just before (9) page 177, line 2 of exercise 423, boolean -> Boolean page 185 gains a line because of the change to page 186 page 219, better line breaks in answer 70 page 227, line -2 of answer 21, "; for" -> ". For" page 242, line -2 of answer 86, "Sum those estimates" page 346, 2nd line of answer 419, more-or-less and I've made the polyspheres a bit darker (pages 167, 324) ARTICLES "TO APPEAR" THAT ARE STILL PENDING: Fischetti, Salvagnin, ans 7.2.2.1--36 (arXiv:1907.08246 [cs.DS]) Harris's G4G9 presentation, ans 7.2.2.1--62 Beluhov snake-in-box knight paths, ans 7.2.2.1--173 Beluhov symmetric plane partitions and diamond/lozenge tilings, ans 7.2.2.1--261 Svante Janson arXiv:2009.13781 [ans MPR24(c)] Windsor's commafree codes?