% CHANGES TO FASCICLE V4F5 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2019 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 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 www.pearson {\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 \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 \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.58 new rating for exercise 69 (19.12.05) [{\it40\/}] \becomes [{\it41\/}] \endchange \improvepage 4f5.66 just before Table 1 (20.01.01) are unused. \becomes are unused and can contain anything. \endchange \improvepage 4f5.66 first line of cover$(i)$ (20.01.01) (Here $p$, $l$, and $r$ are local.) \becomes (Undeclared variables like $p,l,r$ are local.) \endchange \improvepage 4f5.71 line 6 (19.11.29) amendment of \becomes amendment to \endchange \amendpage 4f5.84 line $-2$ (19.12.21) Exercises 325--345 \becomes Exercises 324--350 \endchange \amendpage 4f5.87 line 4 after {\eq(49)} (20.03.27) never examined. \becomes never examined, except in printouts (see the answer to exercise 12). \endchange \amendpage 4f5.87 new line for nodes $x=0, 1, 2, 3, 4, 5, 6$ in Table 2 (20.03.27) {\def\\{\hbox{---}}\tabskip=6pt plus 1fil \halign to \hsize{\hfil#:\hfil&&\hfil$#$\cr \.{COLOR($x$)}&\\&\\&\\&\\&\\&\\& 0\cr }} \endchange \amendpage 4c5.88 in first line of {\eq(55)} (20.03.27) $q\gets\.{DLINK($i$)}$. \becomes $\.{COLOR($i$)}\gets c$, $q\gets\.{DLINK($i$)}$. \endchange \bugonpage 4f5.107 line 19 (20.03.07) `$a$~$g$' and `$a$~$f$'. Further simplifications now arise. \becomes `$a$~$g$' and `$a$~$f$'. \endchange \amendpage 4f5.130 an additional sentence in exercise 77 (20.03.02) (In such a case we say that $G$ is {\it embedded\/} in~$H$.) \endchange \amendpage 4f5.135 better illustrations in exercise 116 (20.02.19) $$\def\\#1{\vcenter{\epsfbox{\figdir/v4b.328#1}}} M_2\;=\;\\1\,;\qquad M_3\;=\;\\2\,;\qquad M_4\;=\;\\3\,;\qquad \ldots\,.$$ \endchange \bugonpage 4f5.144 correction to puzzle {(ii)} in exercise 173 (19.12.04) \ninepoint \dots\ Diagram (ii) shows 8 \dots\ the other 19 can be deduced. \dots $$\def\epsfsize#1#2{.5#1}\vcenter{\epsfbox{\figdir/v4b.2121}}$$ \endchange \amendpage 4f5.170 and 171, in exercise 375 (20.02.10) smallest possible perimeter \becomes smallest possible semiperimeter (height plus width)\nl smallest perimeter \becomes smallest semiperimeter \endchange \let\defaultpointsize=\ninepoint % get ready for answer pages \bugonpage 4f5.211 line 3 of step O5 (19.12.18) while $b_{k-t}0$, 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.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.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 \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 \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.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 line $-2$ of answer 349 (19.12.14) [these illustrations should be darker, I've now thickened the lines] \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 4f6.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 Dickins, {\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 Brotchie, Alastair, 245. % 2nd Bucket elimination, \see Frontier. % 2nd Chuzzlewit, Martin, 356. % 2nd 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 Kernels of a graph (maximal independent sets), 143, 244, 269. % 2nd {\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 Linear programming problems, 287, 332--333. % 2nd McDonald, Gary, 250, 356. % 2nd Minimum cutsets, 344. % 2nd 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 Projection vectors, 345, 346--348. % 2nd Queen domination problems, 91--92, 142. % 2nd Social distancing, 157. % 3rd Stappers, Filip Jan Jos, 234. % 2nd Stork, David Geoffrey, 183. % 2nd Trybu{\l}a, Stanis{\l}aw Czes{\l}aw, 183. % 2nd \.{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 177, line 2 of exercise 423, boolean -> Boolean page 227, line -2 of answer 21, "; for" -> ". For" 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