% CHANGES TO FASCICLE V4F6 OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 2015, 2016, 2017, ..., 2020, 2021, 2022 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 err4f6"

\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 6}
\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~6, since it was first printed in 2015.

\ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,''
   and ``improvements''\dash---appear, indicated by four
\else Three levels of updates\dash---``errors,'' ``amendments,'' and
   ``plans''\dash---appear, indicated by three \fi
different typographic conventions:
\begingroup\def\hundred{17}

\bugonpage 0.666 line 1 (76.07.04)
Technical or typographical errors (aka bugs) are the most critical items, so
they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page
number. The date on which I first was told about the bug is shown; this is the
effective date on which I paid the finder's fee. The necessary
corrections are indicated in
a straightforward way. If,~for example, the book says
`$n$' where it should have said `$n+1$', the change is shown thus:
\smallskip
$n$ \becomes $n+1$
\endchange

\amendpage 0.666 line 2 (89.07.14)
Amendments to the text appear in the same format as bugs, but without
the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known
about or thought of when I wrote the original text, so I added them later.
The date is the date I drafted the new text.
\endchange

\def\hundred{19}

\planforpage 0.666 line 3 (17.11.20)
Plans for the future represent a third kind of item. In such notes I~sketched
my intentions about things that I wasn't ready to flesh out further when
I~wrote them down. You can identify these items because they're written in
slanted type, and preceded by a bunch of dots
`\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on
which I recorded the plan in my files.
\endchange

\improvepage 0.666 line 4 (38.01.10)
The fourth and final category\dash---indicated by page and line number in
smaller, slanted type\dash---consists of minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
You wouldn't even
be seeing these items if you hadn't specifically chosen to print the complete
errata list in all its gory details.
Are you sure you wanted to do that?
\endchange

\endgroup
\ifall\else\medskip\ninepoint
My personal file of updates also includes a fourth category of items, not
shown in this list. They are miscellaneous minor corrections or improvements
that most readers don't want to know about, because they are so trivial.
If you really want to see all of the gory details,
you can download the full list from Internet webpage
$$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$
by selecting the ``long form'' of the errata.
\fi

\medskip
\tenpoint
\beginconstruction
The ultimate, glorious, future editions of Volumes 1--5 are works in progress.
Please let me know of any improvements that you think I ought to make.
Send your comments either by snail mail to D.~E. Knuth, Computer
Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045,
or by email to
{\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions
only, please\dash---all
other correspondence is returned unread to the sender, or discarded,
because I have no time to
read ordinary email.) Although I'm working full time on
Volume~4 these days, I~will try to reply to all such messages
within a year of receipt. Current news about {\sl The Art of Computer
Programming\/} is posted on
$$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$
and updated regularly.
\par\endconstruction
\rightline{\dash---Don Knuth, March 2006}

\bigskip
\bigskip
{\quoteformat
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

\bigskip
I still feel fine, but I'm making more or more little errors.
\author DONALD E. KNUTH, letter to Matthew Ginsberg (28 April 2022)

\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 V4F6: SATISFIABILITY}
\def\rhead{CHANGES TO V4F6: SATISFIABILITY}
\titlepage
\volheadline{SATISFIABILITY} % the fascicle title
\bigskip
\rightline{Copyright \copyright\ 2015, 2016, \dots, 2020, 2021, 2022
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

\bugoverall 4f6.0 throughout (19.07.28)
The Figures in Volume 4 Fascicle 6 have all received new numbers, now
that Volume 4 Fascicle 5 is complete! Figures formerly numbered 33--56
are now numbered 76--99. Figures in the answers, formerly numbered
A--5 through A--10, are now numbered A--7 through A--12.
\endchange

\bugonpage 4f6.i line $-2$ (16.05.11)
\ninepoint Sa\~o Paulo \becomes S\~ao Paulo
\endchange

\amendpage 4f6.iii line 18 (19.07.26)
combinatorial algorithms \becomes combinatorial searching
\endchange

\bugonpage 4f6.v line 7 (19.07.26)
Information Systems Laboratory \becomes InfoLab
\endchange

\bugonpage 4f6.v line 20 (16.01.17)
\.{\char`\~/fasc5a} \becomes \.{\char`\~knuth/fasc5a}
\endchange

\amendpage 4f6.v replacement for lines 18--23 (19.12.16)
\noindent 
the word ``improvement.'')
That section, together with the introductory material about backtracking
and dancing links, can be found in Fascicle~5 of Volume~4.
\endchange

\improvepage 4f6.vi line 4 (18.10.04)
defined in Section 1.3.1\mm.  \becomes
defined in Section 1.3.1\mm\ of Volume 1, Fascicle~1.
\endchange

\amendpage 4f6.vii lines 3 and 11 (19.12.16)
\ninepoint
{\bf00.} \becomes {\bf15.}
\endchange

\amendpage 4f6.vii lines 4, 10, 11, 12 (17.05.31)
\ninepoint
rows \becomes options\qquad[four changes]\nl
columns \becomes items\qquad[one change]
\endchange

\amendpage 4f6.viii line 5 (19.07.26)
\ninepoint
Basic Backtrack \becomes Backtrack Programming
\endchange

\improvepage 4f6.3 line $-11$ (19.12.19)
is equivalent to \becomes can be replaced by
\endchange

\improvepage 4f6.3 line $-9$ (19.12.19)
equivalent to two \becomes equivalent to the {\mc AND} of two
\endchange

\improvepage 4f6.4 line $-8$ (17.02.15)
{\sl equally spaced $1$s\/} \becomes
{\sl equally spaced $1$s\/} (or both)
\endchange

\amendpage 4f6.5 bottom and page 6 top (17.05.31)
row \becomes option\qquad[three changes]\nl
rows \becomes options\qquad[four changes]\nl
column \becomes item\qquad[three changes]\nl
columns \becomes items\qquad[two changes]
\endchange

\bugonpage 4f6.9 line $-18$ (16.04.10)
\rightline{\eightssi
it can be put into the conjunctive normal form ``piece by piece'',}
\endchange

\improvepage 4f6.14 line 15 (18.07.17)
$R_{23}^{46}$, $R_{23}^{46,1}$ and $R_{23}^{46,2}$ \becomes
$R_{23}^{46}$, $R_{23}^{46,1}\!$, and $R_{23}^{46,2}$
\endchange

\amendpage 4f6.16 insert new paragraph 10 lines before {\eq(32)} (21.08.22)
\indent
D.~Morgenstern has found a much simpler formula that also matches Table~2:
$$f(x_1,\ldots,x_{20})\;=\;
 \bar x_4 x_{10} \bar x_{12} \lor
 \bar x_6 \bar x_{10} \bar x_{12} \lor
 x_9\bar x_{10}x_{11}.
$$
But it's actually further than \eq(27) from the ``true'' $\!f$ that's
revealed in exercise 53.\tighten
\endchange

\improvepage 4f6.19 line $-5$ (17.04.08)
predictable pattern \becomes repetitive pattern
\endchange

\amendpage 4f6.28 line 4 after {\eq(57)} (19.05.17)
Furthermore \.{C($l$)} \becomes
Furthermore, if $l$ is a literal whose value has not yet been fixed, \.{C($l$)}
\endchange

\amendpage 4f6.30 line 23 (18.05.24)
we can assume that \becomes we can adjust the data so that
\endchange

\bugonpage 4f6.32 line $-11$ (15.11.22)
$\bar5 \bar3 \bar4$ \becomes $\bar5 \bar3 \bar7$
\endchange

\bugonpage 4f6.33 replacement for Fig.~82 {(formerly Fig.~39)} (16.02.10)
\centerline{\epsfbox{\figdir/ch7b.50}}
\endchange

\improvepage 4f6.34 line 2 after {\eq(60)} (16.07.05)
moves. \becomes moves (the 4s and the 5s).
\endchange

\bugonpage 4f6.41 line 8 after {\eq(67)} (18.08.13)
$h(3)@h(6)$ \becomes $h(4)@h(6)$
\endchange

\bugonpage 4f6.41 lines 4--8 after {\eq(67)} (19.04.27)
$h(2)@h(3)$ \becomes $h(\bar2)@h(\bar3)$,
$h(3)@h(5)$ \becomes $h(\bar3)@h(\bar5)$, etc.\nl
$=$ \becomes $\approx$
\endchange

\bugonpage 4f6.42 line 5 after {\eq(70)} (19.10.01)
$h(\bar4)@h(\bar6)$ \becomes
$h(\bar3)@h(\bar4)+h(\bar4)@h(\bar6)$
\endchange

\bugonpage 4f6.43 in {\eq(71)} (20.10.21)
for $1<j<E$ \becomes for $1\le j<E$
\endchange

\bugonpage 4f6.43 line 1 after {\eq(71)} (20.07.09)
proto truth, etc. \becomes proto truths, etc.
\endchange

%\bugonpage 4f6.44 in step X2 (20.01.30)
\bugonpage 4f6.44 in step X2 (20.07.09)
Set $N=n-F$ and use \eq(65) to
compute a rough score $h(l)$ for each free literal~$l$. \becomes
Set $N\gets n-F$. For each free
literal~$l$, set $\.{VAL[$l$]}\gets0$, and use \eq(65) to
compute a rough score $h(l)$.
\endchange

\bugonpage 4f6.44 line 6 of step X3 (20.01.14)
whose rating exceeds \becomes whose rating is less than
\endchange

\amendpage 4f6.44 line 3 of step X7 (20.11.07)
$\.{BASE}+2S\ge\.{PT}$. \becomes
$\.{BASE}+2S\ge\.{PT}$ (beware of overflow).
\endchange

\bugonpage 4f6.46 line 1 of step Y3 (20.01.30)
\def\jhat{{\hat\jmath}}%
Set $l\gets\.{LL[$j$]}$ and $T\gets\.{BASE}+\.{LO[$j$]}$. \becomes
Set $l\gets\.{LL[$\jhat@$]}$ and $T\gets\.{BASE}+\.{LO[$\jhat@$]}$.
\endchange

\bugonpage 4f6.46 in step Y7 (20.11.11)
[Make $\hat l_0$ false.] \becomes [Assume also $l$.]\nl
with $l\gets\hat l_0$ and $T\gets\.{DT}$. \becomes with $T\gets\.{DT}$.
\endchange

\bugonpage 4f6.46 in step Y8 (20.01.30)
set $\.{CONFLICT}\gets\rm X13$ and exit \becomes
set $\.{BASE}\gets\.{LBASE}$, $\.{CONFLICT}\gets\rm X13$, and exit
\endchange

\amendpage 4f6.51 the line after {\eq(82)} (19.08.12)
[See A. C. Kaporis \becomes
[See M. Hajiaghayi and G. B. Sorkin, \arXiv:math/0310193 [math.CO] (2003),
8~pages; A.~C. Kaporis
\endchange

\amendpage 4f6.51 line $-9$ (18.04.05)
to appear \becomes 59--68
\endchange

\bugonpage 4f6.52 line 6 after {\eq(84)} (21.11.11)
Section 7.4.1 \becomes Section 7.4.4
\endchange

\bugonpage 4f6.55 replacement for Fig.~91 {(formerly Fig.~48)} (16.02.10)
\centerline{\epsfbox{\figdir/ch7b.51}}
\endchange

\amendpage 46.57 line 10 (20.04.22)
$\bar1\bar2\bar3,\bar12\bar4,$ \becomes
$\bar12\bar4,\bar1\bar2\bar3,$
\endchange

\bugonpage 4f6.65 replacement for last line of Table 3 (22.06.21)
\def\\#1#2{\overline{#1#2}}%
\ninepoint\centerline{(Here $**$ denotes the previously learned clause
$\\50\,
\\26\,
27\,
\\30\,
\\32\,
\\35\,
\\38\,
\\40\,
\\41\,
\\44\,
\\45\,
\\47\,
\\50\,
\\55\,
\\60\,
\\65\,
\\70$.)}
\endchange

\bugonpage 4f6.66 line $-2$ or $-1$ (19.06.16)
(see exercise~261) \becomes (see exercise~265)
\endchange

\amendpage 4f6.66 new sentence at bottom of page (18.03.15)
The ``reason'' for literal~$l$'s current value is kept in variable~$R_l$.
\endchange

\improvepage 4f6.67 lines 10 and 22 (18.05.06)
100 conflicts \becomes $M=100$ conflicts\nl
$\rho^{-100}$ times \becomes $\rho^{-M}=\rho^{-100}$ times
\endchange

\bugonpage 4f6.68 line $-2$ (19.04.21)
$L_F\gets l'$, \becomes
$L_F\gets \bar l'$,
$\.{VAL($\vert l'\vert$)}\gets 2d+(\bar l'\band1)$,
\endchange

\amendpage 4f6.74 in {\eq(124)} (19.12.16)
$m_j>0$\quad and \quad \becomes
\endchange

\amendpage 4f6.80 line 14 (17.05.17)
on variables that need \becomes on clauses whose variables need
\endchange

\amendpage 4f6.80 line 22 (17.05.17)
tackled. \becomes tackled and when $N=\infty$.
\endchange

\bugonpage 4f6.86 line 2 of the proof of Theorem F (22.06.21)
$\sum_{\alpha,\beta}\mu_G(\alpha)=
\sum_\gamma\sum_{\alpha,\beta}\mu_G(\alpha)\[\gamma=\alpha\beta]$ \becomes\nl
\breathe
$\sum_{\alpha,\beta}\mu_G(\alpha)\alpha\beta=
\sum_\gamma\sum_{\alpha,\beta}\mu_G(\alpha)\gamma@\[\gamma=\alpha\beta]$
\endchange

\bugonpage 4f6.86 bottom line (17.02.02)
(this is, \becomes (that is,
\endchange

\amendpage 4f6.94 new paragraph at bottom of page (19.04.28)
\indent Even better results occur when step S8 is allowed to backtrack, resetting
less-biased variables when problems arise. See R.~Marino, G.~Parisi,
and F.~Ricci-Tersenghi,
{\sl Nature Communications\/ \bf7},\thinspace12996 (2016), 1--8.
\endchange

\improvepage 4f6.95 line $-5$ (21.03.14)
so-called because \becomes so called because
\endchange

\improvepage 4f6.96 bottom two lines (18.07.03)
75] that introduced \dots\ omitted \becomes
75], which introduced important special cases that allow many
of the $pq$ potential clauses to be omitted
\endchange

%\amendpage 4f6.97 line $-2$ (21.02.07)
%12, due to Marijn Heule, does \becomes 12 does
%\endchange
%
%\amendpage 4f6.98 line 4 (21.02.07)
%Heule's method \becomes the alternative method
%\endchange
%
%\amendpage 4f6.104 line $-24$ (21.02.07)
%Heule's $3(n-2)$ \becomes $3(n-2)$
%\endchange

\bugonpage 4f6.113 line 5 (18.07.17)
$i_1<j_1$, $i_2<j_2$, \dots, $i_t<j_t$ \becomes
$i_1\le j_1$, $i_2\le j_2$, \dots, $i_t\le j_t$
\endchange

\improvepage 4f6.114 problem D5 (18.07.17)
\ninepoint $\times'$ \becomes $\times$
\endchange

\amendpage 4f6.118 line 27 (17.05.17)
tests, \becomes tests with $N=50n$ and $p=.4$,
\endchange

\amendpage 4f6.121 lines $-15$ through $-13$ (17.05.31)
the dancing links method of Section 7.2.2.1 \becomes
the backtrack method of exercise 7.2.2--21\nl
7.2 T$\mu$ \becomes 4 T$\mu$\nl
90 minutes \becomes 50 minutes
\endchange

\improvepage 4f6.121 line $-12$ (18.07.17)
trumps \becomes trounces
\endchange

\improvepage 4f6.125 the line after {\eq(193)} (19.05.25)
these defaults \becomes those defaults
\endchange

\bugonpage 4f6.126 line 16 (18.07.17)
$(\alpha_i,\rho_i,\ldots,\psi_i)$ \becomes
$(\alpha,\rho,\ldots,\psi)$
\endchange

\improvepage 4f6.129 line 11 (21.02.07)
conflict-driven \becomes conflict driven
\endchange

\improvepage 4f6.130 line $-18$ (21.02.07)
first order logic \becomes first-order logic
\endchange

\bugonpage 4f6.131 line $-14$ (16.07.09)
benchmark programs of 1992 \becomes benchmark problems of 1992
\endchange

\bugonpage 4f6.132 line 23 (16.08.23)
Independent Decreasing Sum \becomes Independent Decaying Sum
\endchange

\improvepage 4f6.133 line 19 (20.07.16)
In future, the next breakthrough \becomes The next future breakthrough
\endchange

%\amendpage 4f6.134 line 1 of exercise 12 (21.02.07)
%\ninepoint (M. J. H. Heule.) Simplify \becomes Simplify
%\endchange

\improvepage 4f6.134 better wording in exercise 15 (16.05.14)
that has an arbitrary order~$n\ge3$ \becomes
whose order is a given number~$n\ge3$
\endchange

\amendpage 4f6.135 new rating for exercise 24 (17.02.15)
\ninepoint{\it M32\/} \becomes {\it M34\/}
\endchange

\bugonpage 4f6.135 line 3 of exercise 31 (22.04.21)
\ninepoint $F_t(n)$ \becomes $F_t(r)$
\endchange

\improvepage 4f6.136 end of exercise 38 (17.05.10)
each side. \becomes each side?
\endchange

\amendpage 4f6.136 line 3 of exercise 43 (18.01.21)
$(z_{m+n}\ldots z_1)_2=(z_1\ldots z_{m+n})_2$ \becomes
$(z_{2n}\ldots z_1)_2=(z_1\ldots z_{2n})_2$
\endchange

\bugonpage 4f6.138 last line of exercise 70 (20.06.01)
\def\\#1{\vcenter{\epsfbox{\figdir/ch7b.350#1}}}%
$@\\7\to\\3\to\\4\to\\7@@$ \qquad\becomes\qquad
$@\\7\to\\4\to\\3\to\\7@@$
\endchange

\amendpage 4f6.145 new rating for exercise 150 (19.12.15)
\ninepoint{\it 21\/} \becomes {\it 24}
\endchange

\amendpage 4f6.147 last lines of exercise 176 (22.05.26)
\ninepoint together with $b_{1,1}$ \dots\ by \eq(17). \becomes
together with $(b_{1,1})\land(c_{1,2})\land(d_{1,3})$
to set the colors of $(b_1,c_1,d_1)$ to $(1,2,3)$.
\endchange

\amendpage 4f6.150 replacement for exercise 204 (19.05.01)
\EX204. [28] Figure 89 might suggest that {\mc 3SAT} problems
on $n$ variables are always easy when there are fewer than $2n$ clauses.
We shall prove, however, that~{\it any\/} set of $m$ ternary clauses
on $n$ variables can be transformed mechanically into another set of ternary
clauses on $N=O(m)$ variables in which no variable occurs more than four times.
The transformed problem has the same number of solutions as the original one;
thus it isn't any simpler, although (with at most $4N$ literals)
it has at most ${4\over3}N$ clauses.\tighten\breathe
\item{a)}First replace the original $m$ clauses by $m$ new clauses $(X_1\lor
X_2\lor X_3)$, \dots, $(X_{3m-2}\lor X_{3m-1}\lor X_{3m})$, on $3m$ new
variables, and show how to add $3m$ clauses of size~2 so that
the resulting $4m$ clauses have exactly as many solutions as the
original.\tighten
\breathe\item{b)} Construct ternary clauses that have a unique solution, yet no
variable occurs more than four times.
\item{c)} Use (a) and (b) to prove the $N$-variable result claimed above.
\endchange

\amendpage 4f6.150 replacement for exercise 205 (19.05.01)
\ex205. [26] If $F$ and $F'$ are sets of clauses, let $F\sqcup F'$ stand for
any other set obtained
from $F\cup F'$ by replacing one or more clauses~$C$ of $F$
by $x\lor C$ and one or more clauses~$C'$ of $F'$ by $\bar x\lor C'$,
where $x$ is a new variable. Then $F\sqcup F'$ is unsatisfiable
whenever $F$ and $F'$ are both unsatisfiable.
For example, if $F=\{\epsilon\}$ and $F'=\{1,\bar1\}$, then
$F\sqcup F'$ is either
$\{2,1\bar2,\bar1\bar2\}$ or
$\{2,1,\bar1\bar2\}$ or
$\{2,1\bar2,\bar1\}$.
\item{a)} Construct 16 unsatisfiable ternary clauses on 15 variables,
where each variable occurs at most four times.
\item{b)} Construct an unsatisfiable {\mc4SAT} problem in which every
variable occurs at most five times.
\endchange

\amendpage 4f6.151 new rating for exercise 215 (18.07.09)
\ninepoint{\it \HM23\/} \becomes {\it \HM28\/}
\endchange

\bugonpage 4f6.154 the displayed equation on line 13 (18.07.17)
$\ell(v)$ \becomes $l(v)$
\endchange

\bugonpage 4f6.154 in exercise 245 (20.08.30)
\ninepoint
line 2 in part (a): $G'=\vcenter{\epsfbox{\figdir/v4b.71}}@$ and
$G''=\vcenter{\epsfbox{\figdir/v4b.72}}@$
\becomes
$G'=\vcenter{\epsfbox{\figdir/v4b.72}}@$ and
$G''=\vcenter{\epsfbox{\figdir/v4b.71}}@$\nl
line 1 in part (c): if $\vert V'\vert=\mu(C)$ \becomes
if $\bigcup_{v\in V'}\alpha(v)\vdash C$ and $\vert V'\vert=\mu(C)$\nl
last line of part (d): $s/n+8$ \becomes $s/m+8$
\endchange

\improvepage 4f6.154 line 3 of exercise 246 (22.04.03)
\ninepoint extended \becomes {\it extended}
\endchange

\amendpage 4f6.159 new rating for exercise 305 (17.05.17)
\ninepoint {\it M25\/} \becomes {\it \HM29\/}
\endchange

\bugonpage 4f6.165 line 7 of exercise 356 (17.08.17)
Theorems M and~K \becomes Theorems M and~S
\endchange

\bugonpage 4f6.166 line $-5$ of exercise 363 (20.03.21)
\ninepoint The sets in~(d) \becomes The sets in~(f)
\endchange

\amendpage 4f6.167 new rating for exercise 372 (22.07.21)
\ninepoint {\it 25\/} \becomes {\it 30\/}
\endchange

\amendpage 4f6.167 last line of exercise 374 (22.07.13)
\ninepoint literal $l\in C$ \becomes literal $\bar x\in C$
\endchange

\amendpage 4f6.167 new rating for exercise 376 (22.07.21)
\ninepoint {\it 32\/} \becomes {\it 36\/}
\endchange

\bugonpage 4f6.167 line 3 of exercise 379 (22.01.25)
\ninepoint $(b\lor c\lor d)$ \becomes $(a\lor b\lor c)$
\endchange

\improvepage 4f6.168 in exercise {385(b)} (22.06.21)
\ninepoint in (7) \becomes in \eq(7)
\endchange

\bugonpage 4f6.169 in exercise 386 (22.06.09)
\ninepoint line 1: [{\it M25}\/] \becomes [{\it M31}\/]\nl
line 6: returns to~C2. The data structures \.{HEAP}, \.{OVAL}, and \.{ACT} \becomes
returns to~C5. The data structures \.{HEAP}, \.{HLOC}, \.{OVAL}, \.{ACT}\nl
line 17: on a helpful round \becomes on a round that's helpful for $C$~and~$l$\nl
bottom line: $\mu\ln n\ln\ln n$ \becomes $\mu n\ln n$
\endchange

\improvepage 4f6.170 line 1 of exercise {392(c)} (22.06.21)
\ninepoint {\mc SAT solver} \becomes {\mc SAT} solver
\endchange

\amendpage 4f6.172 lines 2 and 3 of exercise 404 (22.06.21)
\ninepoint using either \dots\ variable. \becomes
using $d+1-a$ clauses of length $\le4$ and no auxiliary variables.
\endchange

\bugonpage 4f6.173  line 2 of exercise 417 (16.02.23)
\ninepoint via~\eq(174) \becomes via~\eq(173)
\endchange

\amendpage 4f6.174 last line of exercise 428 (16.03.26)
\ninepoint $M$ and $N$ cannot be \becomes $M$ and $N$ cannot both be
\endchange

\amendpage 4f6.174 exercise 433 (22.06.04)
[this exercise now is `Recommended'; that is, it's now
preceded by {\manfnt x\hskip3pt}]
\endchange

\amendpage 4f6.178 first line of exercise 474 (20.03.18)
\ninepoint A signed permutation is a symmetry \becomes
A signed permutation $\sigma$ is a {\it symmetry\/}
\endchange

\improvepage 4f6.179 line 2 of exercise 481 (16.08.01)
\ninepoint $(x@{\xor}@y)y$ \becomes $(x@{\xor}@y)\,y$
\endchange

\amendpage 4f6.179 replacement for final paragraph of exercise 483 (19.05.25)
Experiment with this scheme by applying it to the Mycielski graphs
of exercise 7.2.2.1--116.
\endchange

\bugonpage 4f6.183 row 16, column 39 of the big matrix in exercise 518 (16.01.11)
$\scriptscriptstyle0$ \becomes
$\scriptscriptstyle2$
\endchange

\improvepage 4f6.183 line 2 of exercise {518(a)} (16.01.11)
\ninepoint $r$ \becomes $p$\quad
$s$ \becomes $q$\quad
$t$ \becomes $r$
\endchange

\bugonpage 4f6.184 line 2 of exercise 520 (19.12.23)
\ninepoint {\it feasability\/} \becomes {\it feasibility\/}
\endchange

\bugonpage 4f6.184 line 2 of exercise 521 (22.06.21)
Forget a learned clause \becomes Keep a learned clause
\endchange

\let\defaultpointsize=\ninepoint % get ready for answer pages

\amendpage 4f6.185 lines 4 and 5 of answer 5 (19.08.22)
Bloom in \dots, shows \becomes\nl
Bloom in {\sl J.~London Math.\ Society\/ \rm(2) \bf93} (2016), 643--663, shows
\endchange

\bugonpage 4f6.185 line 6 of answer 6 (17.06.02)
By Theorem~J, \becomes By Theorem~L,
\endchange

\amendpage 4f6.186 replacement for lines 3--7 of answer 11 (16.02.04)
\indent
Furthermore, the only way to match $j'1$ is to choose one of the satisfiability
triples for clause~$j$. Suppose $\bar l_k j$ belongs to the chosen triple;
then we must also have chosen the true triples for literal $l_k$.
Thus a perfect matching implies satisfiable clauses.
\endchange

\amendpage 4f6.186 in answer 12 (17.05.31)
columns \becomes items\qquad[three changes]
\endchange

\amendpage 4f6.186 in answer 13 (17.05.31)
rows \becomes options\qquad[two changes]
\endchange

\bugonpage 4f6.186 last line of answer 13 (22.06.21)
3600 cells \becomes 3600 literals
\endchange

\amendpage 4f6.186 line 1 of answer 16 (21.04.05)
when $n\ge5$ \becomes for all $n\ge3$
\endchange

\bugonpage 4f6.186 or 187 at end of answer 16 (19.05.30)
Laurier, {\sl Artificial Intelligence\/ \bf14} \becomes
Lauriere, {\sl Artificial Intelligence\/ \bf10}
\endchange

\bugonpage 4f6.187 line 1 of answer 17 (22.06.21)
Add clauses \eq(19) \becomes
Add clauses \eq(18) and \eq(19)
\endchange

\amendpage 4f6.189 simplifying the formula for $f$ in answer 24 (17.02.15)
$r-l<n''{?}$ \dots $f(n'',0,n'')\bigr)$ for $n\ge2$ \becomes
$f(n',(n'+l)\monus r,n')+f(n'',(n''+l)\monus r,n'')\bigr)$ for $n\ge2$
\endchange

\bugonpage 4f6.190 line 2 of answer 33 (19.07.28)
$v_{j-1}\lor v_{j+1}\lor v_k$ \becomes
$v_{j-1}\lor v_{j+1}\lor\cdots\lor v_k$
\endchange

\amendpage 4f6.191 line 2 of answer 35 (15.12.23)
$W_6$ \becomes $W_5$\nl
$C_{n-1}$ \becomes $C_n$
\endchange

\bugonpage 4f6.192 in answer 43 (18.01.21)
seem to be quite rare \dots\ when $n=32$. \becomes
aren't at all rare. For example,
$(x,y)=(\Hex{C4466223},\Hex{E26E7647})$ is one of 293 instances when $n=32$.
\endchange

\amendpage 4f6.192 in answer 46 (19.12.18)
Indeed, there's a nice \dots\ 2009.] \becomes
Indeed, M.~Coriand has discovered a nice way to find all $n$-bit examples
by considering only $O(2^{n/4})$ cases, because the left and right halves
of a binary number are nearly forced by the left and right {\it quarters\/}
of its square. The first eight
square binary palindromes were found by G.~J. Simmons, {\sl JRM\/
\bf5} (1972), 11--19; see OEIS sequence A003166 for many further results.]
\endchange

\bugonpage 4f6.194 line 6 of answer 56 (22.06.21)
on the left be $u_k$ and $v_l$ as \becomes
on the left be $u_k$ and those on the right be $v_l$, as
\endchange

\amendpage 4f6.196 lines 17--18 (16.12.15)
{\ninepoint{\tt arXiv:1410.2736} [cs.DS]} (2014), 10~pages \becomes
{\sl LNCS \bf9136} (2015), 167--176
\endchange

\improvepage 4f6.199 lines $-11$ and $-7$ (17.04.08)
tarnishing \becomes tainting
\endchange

\amendpage 4f6.200 line 2 (17.04.08)
size less than $16\times18$. \becomes
size $15\times18$ or $16\times17$.
\endchange

\amendpage 4f6.202 line $-3$ of answer 85 (21.03.03)
(August 2013), \#P16 \becomes
(2013), \#P16, 1--19
\endchange

\bugonpage 4f6.204 bottom line and top lines of page 205 (16.01.11)
nonzero top row \dots\ $(n-k)$, which \becomes
nonzero first row and column has all entries zero except that
$y_{1t}=-y_{t1}=y_{(k+1-t)1}=-y_{kt}=
y_{k(k+1-t)}=-y_{(k+1-t)k}=y_{tk}=-y_{1(k+1-t)}$,
for some~$t$ and~$k$ with $1<t\le k/2\le m/2$. So the answer is
$2\sum_{k=4}^m\lfloor k/2-\nobreak1\rfloor(m+1-k)(n+1-k)$, which
\endchange

\bugonpage 46.205 line 4 of answer {105(e)} (22.06.21)
for $n=(5,7,9)$ \becomes for $m=n=(5,7,9)$
\endchange

\bugonpage 4f6.209 replacement for answer 128 (16.02.10)
\ans128. $\vtop{\halign{\hfil$#$\hfil\quad&
\tt\hfil#\hfil&
\tt\hfil#\hfil&
\tt\hfil#\hfil&
\tt\hfil#\hfil&
\quad\hfil$#$\hfil&
\quad\hfil$#$\hfil&
\quad$#$\hfil\kern-10pt\cr
\hbox{Active ring}&$x_1$&$x_2$&$x_3$&$x_4$&
\hbox{Units}&\hbox{Choice}&\hbox{Changed clauses}\cr
\noalign{\vskip2pt}
(1\,2\,3\,4)&-&-&-&-&&\bar1&21\bar3\cr
(2\,3\,4)   &0&-&-&-&&\bar2&\bar312,32\bar4\cr
(3\,4)      &0&0&-&-&\bar3&\bar3&\bar423,431\cr
(4)         &0&0&0&-&4,\bar4&\rlap{Backtrack}\hidewidth\cr
(3\,4)      &0&-&-&-&&2&\bar3\bar24\cr
(3\,4)      &0&1&-&-&\bar4&\bar4&341,\bar142\cr
(3)         &0&1&-&0&3,\bar3&\rlap{Backtrack}\hidewidth\cr
(4\,3)      &-&-&-&-&&1&4\bar12,\bar2\bar13\cr
(2\,4\,3)   &1&-&-&-&&\bar2&\cr
(4\,3)      &1&0&-&-&4&4&32\bar4,1\bar4\bar2\cr
(3)         &1&0&-&1&3,\bar3&\rlap{Backtrack}\hidewidth\cr
(4\,3)      &1&-&-&-&&2&3\bar1\bar2\cr
(4\,3)      &1&1&-&-&3&3&4\bar2\bar3,1\bar32,\bar4\bar3\bar1\cr
(4)         &1&1&1&-&4,\bar4&\rlap{Backtrack}\hidewidth\cr
}}$
\endchange

\bugonpage 4f6.211 line 7 of answer 137 (18.03.04)
$\.{LINK($t$)}\gets p''$. \becomes
$\.{LINK($t$)}\gets p''$, $p'\gets t$.
\endchange

\amendpage 4f6.211 last line of answer 137 (20.08.16)
\.{VAR} or \.{INX}.) \becomes
\.{VAR} or \.{INX}.
These efficient techniques based on swapping are examples of
``sparse-set representations''; see 7.2.2--\eq(16) thru \eq(23).)
\endchange

\amendpage 4f6.212 append new line to end of answer 143 (22.05.10)
\indent
ParamILS advises changing $\alpha$ from 3.5 to 0.001(!) in \eq(195).
\endchange

\improvepage 4f6.212 line 3 of answer 145 (19.04.27)
$=$ \becomes $\approx$
\endchange

\amendpage 4f6.212 recomputed values for the bottom three lines (18.08.13)
(2.10, \dots, 24.17). \becomes
(2.10,   9.10,   3.10,   6.60,   3.10,  13.60,   4.10,  11.10),
(5.63,   3.37,   9.24,   2.57,   5.48,   5.67,   8.37,   4.87),
(1.42,  10.00,   2.31,  10.42,   1.28,  17.69,   1.94,  16.07),
(8.12,   1.43,  12.42,   1.30,   7.51,   2.41,  12.02,   1.81),
(0.32,  14.72,   0.42,  16.06,   0.30,  26.64,   0.43,  24.84).
\endchange

\amendpage 4f6.213 recomputed values for lines 2 and 3 (19.04.27)
$$\openup-1\jot\displaylines{\qquad
(0.1017,20.6819,0.1027,21.6597,0.1021,32.0422,0.1030,33.0200)
\quad\hbox{and}\hfill\cr\hfill
( 8.0187,0.1712,11.9781,0.1361,11.9781,0.2071,15.9374,0.1718).\qquad\cr}$$
\endchange

\bugonpage 4f6.213 in answer 150 (19.10.01)
line 1: 147 \becomes $\bar1\bar4\bar7$\nl
line 3: 369 \becomes $\bar3\bar6\bar9$
\endchange

\bugonpage 4f6.214 line 4 of answer 152 (20.01.14)
$b$ and~$c$ both true \becomes
$x_2$ and~$x_3$ both true
\endchange

\amendpage 4f6.214 in answer 153 (20.11.11)
at the top (see Section 5.2.3). \becomes
at the top.
(See Section 5.2.3; but start indices at 0, with $r(\.{CAND[$k$]})\le
\min(r(\.{CAND[$2k{+}1$]}),\allowbreak r(\.{CAND[$2k{+}2$]}))$.)
\endchange

\bugonpage 4f6.214 line 6 of answer 155 (21.11.11)
Section 7.4.1 \becomes Section 7.4.1.2
\endchange

\amendpage 4f6.221 replacement for last line of answer 195 (19.08.12)
see A. Coja-Oghlan and K. Panagiotou,
{\sl Advances in Math.\ \bf288} (2016), 985--1068.]
\endchange

\amendpage 4f6.223 replacement for answer 204{(b,c,d)} (19.04.26)
(b) (Solution by E. Wynn.) The following 44 clauses in 35 variables are
satisfiable if and only if each variable is false:
$a_i\lor \bar b_i\lor c_i$,
$\bar a_i\lor \bar b_i\lor c_i$,
$\bar b_i\lor \bar c_i\lor \bar d_i$,
$\bar c_i\lor d_i\lor e_i$,
$d_i\lor \bar e_i\lor f_i$,
$\bar e_i\lor \bar f_i\lor \bar g_i$,
$\bar f_i\lor g_i\lor h_i$,
$\bar f_i\lor g_i\lor \bar h_i$, for $i\in\{1,2\}$;
$b_1\lor b_2\lor \bar A$,
$A\lor B\lor \bar C$,
$A\lor \bar B\lor D$,
$A\lor \bar D\lor E$,
$\bar B\lor \bar D\lor \bar E$,
$B\lor C\lor \bar F_1$,
$C\lor \bar E\lor G_1$,
$C\lor F_1\lor \bar G_1$;
$F_j\lor G_j\lor \bar F_{j+1}$,
$F_j\lor G_j\lor \bar G_{j+1}$, for $1\le j\le6$;
$D\lor E\lor \bar a_1$,
$F_2\lor G_2\lor \bar a_2$,
$F_3\lor G_3\lor \bar h_1$,
$F_4\lor G_4\lor \bar h_2$,
$a_1\lor h_1\lor \bar d_1$,
$a_2\lor h_2\lor \bar d_2$,
$F_5\lor G_5\lor \bar g_1$,
$F_6\lor G_6\lor \bar g_2$.\par
(c) Add the clauses of (b), and the clauses
$F_j\lor G_j\lor \bar F_{j+1}$,
$F_j\lor G_j\lor \bar G_{j+1}$ for $7\le j\le\lceil3m/2\rceil+3$,
to the $4m$ clauses of~(a).
We can stick the literals $\{F_7,G_7,\ldots{}\}$, which are always false,
into the 2-clauses without using any variable five times,
obtaining at most $(7m{+}39)$ 3-clauses in $N\approx7m+30$ variables.
\endchange

\amendpage 4f6.223 and 224, replacement for answer 205 (19.05.01)
\ans205. Let $F_0=\{\epsilon\}$, \dots \becomes\nl
\ans205. (a) After $F_0=\{\epsilon\}$,
$F_1=F_0\sqcup F_0$,
$F_2=F_0\sqcup F_1$,
$F_3=F_0\sqcup F_2$,
$F_4=F\losub3\sqcup F_3'$,
$F_5=F\losub4\sqcup F_4''$,
always putting the new variable into the
four shortest possible clauses, we get $F_5=\{345$,
$2\bar34$,
$1\bar2\bar3$,
$\bar1\bar2\bar3$,
$3'\bar45$,
$2'\bar3'\bar4$,
$1'\bar2'\bar3'$,
$\bar1'\bar2'\bar3'$,
$3''4''\bar5$,
$2''\bar3''4''$,
$1''\bar2''\bar3''$,
$\bar1''\bar2''\bar3''$,
$3'''\bar4''\bar5$,
$2'''\bar3'''\bar4''$,
$1'''\bar2'''\bar3'''$,
$\bar1'''\bar2'''\bar3'''\}$.\par
(b) Let $F_0=\{\epsilon\}$, \dots
\endchange

\amendpage 4f6.224 line $-2$ (17.05.08)
{\sl SODA\/ \bf22} (2011), 664--674 \becomes
{\sl JACM\/ \bf63} (2016), 43:1--43:32
\endchange

\amendpage 4f6.225 in answer 212 (17.05.31)
line 2: of the rows \becomes with options\nl
line 3: matching; see the discussion of sudoku in Section~7.2.2.1. 
\becomes matching.
\endchange

\bugonpage 4f6.226 replacement for lines 8 and 9 of answer 215 (18.07.09)
$${P_{L+k}\over P_L}=\exp\Bigl(-{\gamma k^2\over n}+O\Bigl({k\over n}\Bigr)
+O\Bigl({k^3\over n^2}\Bigr)\Bigr),\quad
\gamma={(\ln 2)^2\over6\alpha}\Bigl(1+{2\over t_\alpha^3}\Bigr),
\quad \hbox{when $L=2t_\alpha\!@n$;}$$
by trading tails, the expected total tree size is
$\sqrt{\pi n/\gamma}@P_L\bigl(1+O(1/\!@\sqrt n@)\bigr)$.\par
\endchange

\bugonpage 4f6.228 last line of answer 231 (20.04.19)
$G_{mm}\res I_{mm}=\epsilon$. \becomes
$G_{mm}\res I_m=\epsilon$.
\endchange

\bugonpage 4f6.229 replacement for first two lines of answer 233 (20.04.19)
\ans233. $C_{9}=C_{6}\res C_{8}$,
$C_{10}=C_{1}\res C_{9}$,
$C_{11}=C_{3}\res C_{10}$,
$C_{12}=C_{7}\res C_{10}$,
$C_{13}=C_{4}\res C_{11}$,
$C_{14}=C_{2}\res C_{12}$,
$C_{15}=C_{13}\res C_{14}$,
$C_{16}=C_{5}\res C_{15}$,
$C_{17}=C_{6}\res C_{15}$,
$C_{18}=C_{8}\res C_{15}$,{\parfillskip=0pt\par}
\endchange

\bugonpage 4f6.229 line 2 of answer 235 (22.06.21)
$k$ stages \becomes $m$ stages
\endchange

\bugonpage 4f6.229 in answer 237 (20.08.13)
line 2: $m$ pigeons to~$m-1$ \becomes $m+1$ pigeons to $m$\nl
line 2: $6(m-1)@(m-2)$ new clauses \becomes $6m(m-1)$ new clauses\nl
line 4: $2(m-1)@(m-2)$ new variables \becomes $2m(m-1)$ new variables\nl
line $-3$: reduce $m$ to $m-1$ \becomes reduce $m+1$ to $m$
\endchange

\bugonpage 4f6.231 in answer 245 (20.08.30)
lines 1--2:
When conditioning on $e_{uv}$, simply \dots also complement \becomes
When conditioning on $\bar e_{uv}$, simply delete the edge
$u\adj v$ from~$G$. When conditioning on $e_{uv}$, also complement\nl
line 6: $\alpha(G)\given\{\bar b,e\}$ \becomes
        $\alpha(G)\given\{b,\bar e\}$\quad and\quad
        $\alpha(G)\given\{\bar b,\bar e\}$ \becomes
        $\alpha(G)\given\{b,e\}$
\endchange

\improvepage 4f6.231 lines $-4$ and $-3$ of answer 245 (20.04.21)
are part of the Stanford GraphBase \becomes
can be found by the algorithms of the Stanford GraphBase
\endchange

\bugonpage 4f6.231 lines 9 and 10 of answer 246 (20.04.21)
$[s_v]^{@\ell(v)\oplus1}$, meaning $s_v=\ell(v)$. \becomes
$[s_v]^{@l(v)\oplus1}$, meaning $s_v=l(v)$.
\endchange

\bugonpage 4f6.231 line 14 of answer 246 (20.04.21)
$0\le v\le d$ \becomes $0\le k\le d$
\endchange

\bugonpage 4f6.232 line 3 (20.04.21)
$s_v=\ell(v)$ \becomes $s_v=l(v)$
\endchange

\bugonpage 4f6.233 line 10 of answer 257 (18.03.15)
where \id{red}$(l)$ is \becomes
where \id{red}$(\bar l)$ is
\endchange

\bugonpage 4f6.234 line 8 of answer 263 (19.04.21)
\.{TLOC($\vert l_1\vert$)} \becomes
\.{TLOC($\vert l_0\vert$)}
\endchange

\bugonpage 4f6.234 line 14 of answer 263 (19.04.21)
\id{lev}$(\vert b_j\vert)<d'$ \becomes
\id{lev}$(      b_j     )<d'$
\endchange

\bugonpage 4f6.235 second line of $(**)$ (21.12.23)
$l_0\gets R_H$ \becomes
$l_0\gets L_H$
\endchange

\bugonpage 4f6.236 line $-2$ of answer 271 (18.03.15)
$\.{VAL($\vert l_j\vert$)}\le2d'+1$ \becomes
$0\le\.{VAL($\vert l_j\vert$)}\le2d'+1$
\endchange

\bugonpage 4f6.239 line 8 of answer 288 (18.03.15)
If $v<2$ \becomes
Set $v\gets\.{VAL($\vert l_k\vert$)}$. If $v<2$
\endchange

\bugonpage 4f6.240 line 2 of answer 293 (19.12.05)
do this: If \becomes
do this: Set $M_{\rm f}\gets M_{\rm f}+v_{\rm f}$. If
\endchange

\amendpage 4f6.241 line 2 (16.09.14)
$\Pr(T\ge N)\le n/N$ \becomes
$\Pr(T\ge N\given\hbox{the algorithm terminates})\le n/N$
\endchange

\bugonpage 4f6.241 line 5 of answer 299, in the denominator (16.09.14)
$\lceil x^{3/2}\rceil$ \becomes $\lceil x\rceil^{3/2}$
\endchange

\amendpage 4f6.242 in answer 302 (20.06.22)
just as we need to know the literals \dots independent of the others.)
\becomes\nl
just as we need to know the literals of any given clause.
\algindentset{\hskip\parindent W4}
\algstep W4. [Choose $l$.] Set $g\gets\[U\ge p]$, $c\gets\infty$,
$j\gets z\gets0$, and do the following
while $j<k$: Set $j\gets j+1$.
Then if $c_{\vert l_j\vert}<c$ and either $c_{\vert l_j\vert}=0$ or $g=1$,
set $c\gets c_{\vert l_j\vert}$ and $z\gets0$.
Then if $c_{\vert l_j\vert}\le c$, set $z\gets z+1$, and
if $zU<1$ also set $l\gets l_j$.
(Here each random fraction~$U$ should be independent of the others.)\tighten
\endchange

\amendpage 4f6.243 line 10 of answer 304 (17.05.17)
$a\le n-2$, \becomes $a\le n-2$, $a\ne n/2$,
\endchange

\bugonpage 4f6.243 lines 23--30 of answer 304 (17.05.17)
Functions $t_m$ and $u_m$ \dots when $n$ is odd. \becomes\nl
Functions $t_k$ and $u_k$ can be
defined as in \MPR--105; but the new recurrences are
$t_{k+1}=(t_k-pz^2t_{k-1})/q$ and
$u_{k+1}=(u_k-pz^2u_{k-1})/q$. Hence
$$T(w)={q-pw\over q-w+pz^2w^2};\qquad
 U(w)={q-(1-qz)w\over q-w+pz^2w^2}.$$
Differentiating with respect to $z$, then setting $z=1$, now yields
$$t_k'(1)={2pq(1-(p/q)^k)\over(q-p)^2}-{2pk\over q-p},\qquad
u_k'(1)={(2p-(p/q)^k)q\over(q-p)^2}-{2p(k-1/2)\over q-p}.$$ It follows that
$g_a'(1)=a/(q-p)-2pq((p/q)^{m-a}-(p/q)^m)/(q-p)^2$ for $0\le a\le n/2$ when
$n$ is even, $a/(q-p)-q((p/q)^{m-a}-(p/q)^m)/(q-p)^2$ when $n$ is~odd.
\endchange

\amendpage 4f6.249 last line of answer 333 (20.05.29)
[{\sl Manuscripta} \dots\ 241.] \becomes
[{\sl Discrete Mathematics\/
\bf14} (1976), 215--239; {\sl Manuscripta Mathematica\/ \bf19} (1976), 211--243.
See also R.~Fr\"oberg,
{\sl Mathematica Scandinavica\/ \bf37} (1975), 29--39.]
\endchange

\bugonpage 4f6.253 line $-2$ (20.03.21)
is~$2$ \becomes is~$2n$
\endchange

\amendpage 4f6.257 lines 3 and 4 of answer 374 (17.05.31)
additional links as in the exact cover algorithms of Section 7.2.2.1: \becomes
additional links:
\endchange

\bugonpage 4f6.258 line 1 of answer {374(b)} (20.07.15)
a literal $l$ with \becomes a literal $l$ in $C$ with
\endchange

\amendpage 4f6.258 replacement for answer {374(c)} (22.07.13)
(c) Use (b), but set $p\gets\.{F($l=\bar x{?}\ x{:}\ l$)}$, and use
$\bigl((\.{SIG($c$)}\band\bcomp@\.{SIG($\bar x$)})\bor\.{SIG($x$)}\bigr)$
in place of \.{SIG($c$)}. Also modify the detailed test, by inserting
`if $u=\bar x$ then $u\gets x$' just after each occurrence of
`$u\gets\.{L($q$)}$'.\par
\endchange

\bugonpage 4f6.259 in answer 376 (22.07.21)
line 5: nonzero; \becomes \.{FF}, \.{FT}, or \.{EQ};\nl
line 10: $\.{TALLY($l$)}=0$ \becomes $\.{TALLY($\bar l$)}=0$\nl
line 26: subsumption stack \becomes exploitation stack\nl
lines 33--34: set nonzero when \dots\ output. \becomes
set nonzero when $x$ is eliminated or its elimination has been abandoned.
\endchange

\improvepage 4f6.261 line 1 of answer 385 (22.03.18)
$\overline C\land l\vdash_1\epsilon$ \becomes
$\overline C\land l\vdash_1\epsilon$ when $l\in C$
\endchange

\bugonpage 4f6.261 in answer 386 (22.03.18)
line 2: level $d$. \becomes level $d$ during the helpful round.\nl
line 7: $(\bar c,\bar d,\bar l)$ \becomes $(\bar c,\bar l)$\nl
line 8: ${1\over10}@{1\over6}@{1\over4}$, ${1\over10}@{1\over6}@{1\over4}$
\becomes ${1\over10}@{1\over6}@{1\over4}$, ${1\over10}@{1\over4}$
\endchange

\bugonpage 4f6.262 in answer 386 (22.03.18)
line 2: a suitable decision \becomes suitable decisions\nl
line 5: is a geometric \becomes is upper-bounded by a geometric
\endchange

\bugonpage 4f6.262 in answer 389 (20.03.02)
line 1: This is a \becomes This is similar to a\nl
line 2: $\.H\adj\.E$, \becomes $\.H\adj\.E$, $\.E\adj\.{\char`\ }@$,\nl
line 3: $\.N\adj\.G$. The \becomes
        $\.N\adj\.G$; however, we allow $v'=w'$ when $v\ne w$,
and labels must match. The
\endchange

\improvepage 4f6.262 second paragraph of answer 389 (19.01.19)
needs less than \becomes needs fewer than
\endchange

\bugonpage 4f6.262 and 263, new answer 390 {(but last paragraph remains
as before)} (16.02.09)
% part (d) was revised (16.05.13)
\ans390. Let $d(u,v)$ be the distance between vertices $u$ and $v$. Then
$d(v,v)=0$ and
$$d(u,v)\le j+1\;\iff\;
\hbox{$d(u,w)\le j$ for some $w\in N(v)=\{w\mid w\adj v\}$}$$
if $u\ne v$.
In parts (a), (d), we introduce variables $v_j$ for each vertex~$v$
and $0\le j\le k$. In part~(c) we do this for $0\le j<n$. But parts
(b), (e),~(f) use just $n$ variables, $\{v\mid v\in V\}$.\tighten\par
(a) Clauses $(s_0)\land\bigwedge_{v\in V\setminus s}\bigl((\bar v_0)\land
\bigwedge_{j=0}^{k-1}\bigl(\bar v_{j+1}\!\lor\bigvee_{w\in N(v)}w_j\bigr)\bigr)$
are satisfied only if $v_j\le\[d(s,v)\le j]$; hence the additional
clause $(t_k)$ is also satisfied only if $d(s,t)\le k$. Conversely,
if $d(s,t)\le k$, all clauses are satisfied by setting
$v_j\gets\[d(s,v)\le j]$.\par
(b) There's a path from $s$ to $t$ if and only if there's a subset
$H\subseteq V$ such that $s\in H\?$, $t\in H\?$, and every vertex~$v$
of the induced graph $G\given H$ has degree $2-\[v=s]-\[v=t]$. [The vertices
on a shortest path from $s$ to~$t$ yield one such~$H\?$. Conversely,
given~$H\?$, we can find vertices $v_j\in H$ such that
$s=v_0\adj v_1\adj\cdots\adj v_{k}=t$.]\par
We can represent that criterion via clauses on the binary variables
$v=\[v\in H]$ by asserting $(s)\land(t)$,
together with clauses to ensure that $\Sigma(v)=2-\[v=s]-\[v=t]$
for all $v\in H$, where
$\Sigma(v)=\sum_{w\in N(v)}w$ is the degree of $v$ in $G\given H$. 
The number of such clauses for each $v$ is at most $6@\vert N(v)\vert$,
because we can append $\bar v$ to each clause of \eq(18) and~\eq(19)
with $r=2$, and $\vert N(v)\vert$ additional clauses will rule
out $\Sigma(v)<2$. Altogether there are $O(m)$ clauses, because
$\sum_{v\in V}\vert N(v)\vert=2m$.\par
[Similar but simpler alternatives, such as
(i)~to require $\Sigma(v)\in\{0,2\}$ for all $v\in V\setminus\{s,t\}$, or
(ii)~to require $\Sigma(v)\ge2$ for all $v\in H\setminus\{s,t\}$, do
{\it not\/} work: Counterexamples are
(i)~$\vcenter{\epsfbox{\figdir/v4b.3900}}$ and
(ii)~$\vcenter{\epsfbox{\figdir/v4b.3901}}$.
Another solution, more cumbersome, associates a Boolean variable
with each {\it edge\/} of~$G$.]\par
(c) Let $s$ be any vertex;
use (a) with $k=n-1$, plus $(v_{n-1})$ for all~$v\in V\setminus s$.\par
(d) Clauses $(s_0)\land \bigwedge_{j=0}^{k-1}\bigwedge_{v\in V}
  \bigwedge_{w\in N(v)}(\bar v_j\!\lor w_{j+1})$
are satisfied only if we have $v_j\ge\[d(s,v)\le j]$; hence the additional
unit clause
$(\bar t_k)$ cannot also be satisfied when $d(s,t)\le k$. Conversely,
if $d(s,t)>k$ we can set $v_j\gets\[d(s,v)\le j]$.\par
(e) $(s)\land\bigl(\bigwedge_{v\in V}\bigwedge_{w\in N(v)}(\bar v\lor w)\bigr)
\land(\bar t)$.\par
(f) Letting $s$ be any vertex, use
$(s)\land\bigl(\bigwedge_{v\in V}\bigwedge_{w\in N(v)}(\bar v\lor w)\bigr)
\land\bigl(\bigvee_{v\in V\setminus s}\bar v\bigr)$.\par
\endchange

\bugonpage 4f6.263 line $-3$ of answer 391 (22.05.29)
$=k$ \becomes $=k-2^{l-1}$.
\endchange

\bugonpage 4f6.264 line $-3$ of answer 396 (20.01.31)
$(\bar u^3\lor\bar v^3)\land(u^1\lor v^1)\lor
(\overline{\hat u^3}\lor\overline{\hat v^3})\land
(\hat u^1\lor\hat v^1)$ \becomes
$(\bar u^3\lor\bar v^3)\land(u^1\lor v^1)\land
(\overline{\hat u^3}\lor\overline{\hat v^3})\land
(\hat u^1\lor\hat v^1)$ 
\endchange

\amendpage 4f6.265 line $-3$ of answer 397 (22.05.08)
but with \becomes but combined with
\endchange

\bugonpage 4f6.265 line $-3$ of answer 399 (19.04.26)
521--523 \becomes 521--522 % these are the pages that mention preclusion
\endchange

\amendpage 4f6.266 new answer for exercise 404 (22.06.21)
\ans404. $\bigwedge_{j=0}^{d-a}\bigl(\bar x^j\lor x^{j+a}\lor
 \bar y^j\lor y^{j+a}\bigr)$.
(As usual, omit literals with superscript 0 or $d$.)
\endchange

\bugonpage 4f6.267 lines $-5$ and $-4$ (18.07.17)
$\delta\ge w_{ij}$ and $\delta\ge w_{i'j'}$ \becomes
$\delta\le w_{ij}$ and $\delta\le w_{i'j'}$
\endchange

\amendpage 4f6.269 append to answer 415 (18.11.15)
[The clauses \eq(169) are due to K.~Sakallah, {\sl Handbook of
Satisfiability\/} (2009), Chapter 10, (10.32).]
\endchange

\bugonpage 4f6.269 line 2 of answer 417 (16.02.23)
as in \eq(174) \becomes as in \eq(173)
\endchange

\bugonpage 4f6.269 line 3 of answer 418 (16.02.23)
via~\eq(174) \becomes via~\eq(173)
\endchange

\amendpage 4f6.269 line 1 of answer 423 (16.04.04)
[But a {\it forcing\/} \becomes
[But Ab{\'\i}o, Gange,
Mayer-Eichberger, and Stuckey have shown
[{\sl LNCS\/ \bf9676} (2016), 1--17]
that weak forcing is always achieved if $(\bar a_j\!\lor a_l\lor a_h)$ is
added to~\eq(173). Furthermore, a~{\it forcing\/}
\endchange

\amendpage 4f6.270 line 7 of answer 426 (16.04.05)
variable elimination \becomes the elimination of an auxiliary variable
\endchange

\bugonpage 4f6.270 line 6 of answer 428 (20.03.30)
for $1\le t<N$ \becomes for $0\le t<N$
\endchange

\amendpage 4f6.271 line 6 of answer 436 (16.4.04)
$\bigvee\{q_{k-1}\mid(q,a,q')\in T\}\bigr)$; together with (vi) \becomes
$\bigvee\{q_{k-1}\mid(q,a,q')\in T\}\bigr)$,
for $a\!\in\!A$, $q'\!\in\!Q$.
And (vi)
\endchange

\bugonpage 4f6.271 replacement for lines 18--23 of answer 436 (16.4.04)
\indent
For example, the language $L_2$ of exercise 434 yields $20n+4$ clauses with
$8n+3$ auxiliary variables:
$F=\bigwedge_{k=1}^n\bigl(
(\bar t_{k00}\!\lor\bar x_k)\land(\bar t_{k00}\!\lor 0_k)\land
(\bar t_{k11}\!\lor x_k)\land(\bar t_{k11}\!\lor 1_k)\land
(\bar t_{k12}\!\lor x_k)\land(\bar t_{k12}\!\lor 2_k)\land
(\bar t_{k02}\!\lor\bar x_k)\land(\bar t_{k02}\!\lor 2_k)\land
(\bar 0_{k-1}\!\lor t_{k00}\lor t_{k11})\land
(\bar 1_{k-1}\!\lor t_{k12})\land
(\bar 2_{k-1}\!\lor t_{k02})\land
(\bar 0_k\!\lor t_{k00})\land
(\bar 1_k\!\lor t_{k11})\land
(\bar 2_k\!\lor t_{k02}\lor t_{k12})\land
(x_k\!\lor t_{k00}\lor t_{k02})\land
(\bar x_k\!\lor t_{k11}\lor t_{k12})\land
(\bar t_{k00}\!\lor 0_{k-1})\land
(\bar t_{k11}\!\lor 0_{k-1})\land
(\bar t_{k12}\!\lor 1_{k-1})\land
(\bar t_{k02}\!\lor 2_{k-1})\bigr)\land
(\bar 1_0)\land(\bar 2_0)\land(\bar 0_n)\land(\bar 1_n)$.
%(Unit~propagation will immediately assign values to 12 of the $8n+3$ variables,
%thereby satisfying 26 of these clauses, when $n\ge3$.
%For example, $\bar t_{112}$, $\bar t_{n11}$, $\bar 0_{n-1}$ are~forced.)\par
\endchange

\bugonpage 4f6.272 lines 6 and 10 of answer 440 (16.04.03)
$QR_{hik}$ \becomes $QP_{hik}$ \quad(twice)
\endchange

\amendpage 4f6.274  end of answer 448 (19.08.17)
Horsley has shown \dots\ preparation). \becomes
Horsley proved in 2015 that $Z(m,n)=3n+\lfloor1-m/14\rfloor$ in such cases.
\endchange

\bugonpage 4f6.275 line 1 of answer 455 (17.01.10)
1101 \becomes 1011
\endchange

\bugonpage 4f6.275 line 1 of answer 457 (22.06.21)
$51.3\times10^{16}$ \becomes $51.3\times10^{15}$
\endchange

\amendpage 4f6.276 new line for answer 465 (18.05.14)
(See also the more general result in Theorem 7.2.2.1S.)
\endchange

\bugonpage 4f6.276 line 8 of answer 466 (22.03.29)
$\max(i,m-i)\le j\le n/2$ \becomes
$1\le j\le\min(i,m-i,n/2)$
\endchange

\bugonpage 4f6.279 lines 4 and 5 of answer 479{(d)} (18.07.17)
$S_3=x_{11}$ \becomes $S_2=x_{11}$\qquad and\qquad
$S_2=x_{12}$ \becomes $S_3=x_{12}$
\endchange

\bugonpage 4f6.280 line 17 (19.05.09)
exercises 477--480 \becomes exercises 477--479
\endchange

\amendpage 4f6.281 replacement for second paragraph of answer 483 (19.05.25)
\indent It's not difficult to color the Mycielski graph $M_c$ with $c$ colors
(which is the minimum),
{\it without\/} any symmetry breaking. For example, the 191-vertex graph
$M_{12}$ leads to 2,446,271 clauses in 36852 variables (total length 4.9 million);
yet 12-color solutions are found by Algorithms C, W,
and~L respectively in 2.6, 523, and 12200 megamems. % average of ten runs each
The symmetry breaking clauses actually would {\it retard\/} that calculation,
because those clauses are much longer. % 52.1 million!
On the other hand, when we try to succeed with only $c-1$
colors, those clauses are extremely helpful: The runtime needed by
Algorithm C to show
that $M_6$ isn't 5-colorable goes down from 124~G$\mu$ to 32~M$\mu$!
%Altogether 23530+124021773586 mems, 8587751 bytes, 3010141 nodes, 2526544 clauses learned (ave 36.5->21.3), 2136430 memcells.
%Altogether 27859+32156820 mems, 277027 bytes, 8108 nodes, 5884 clauses learned (ave 22.5->14.3), 58749 memcells.
Furthermore, Algorithm~L does better here: Its runtime for that problem goes
down from 7.5~G$\mu$ to 28~M$\mu$.\tighten
\endchange

\bugonpage 4f6.281 line 4 of answer 484 (20.03.22)
$\bar s_{t,k}$ \becomes $\bar s_{t,l}$
\endchange

\bugonpage 4f6.281 line 2 of answer 485 (20.03.22)
$q_{t',l}$ \becomes $q_{t',k}$
\endchange

\amendpage 4f6.283 replacement for Fig.~A--11{(e)} {(formerly Fig.~A--9(e))} (19.04.27)
$\vcenter{\epsfbox{\figdir/v4b.1506}}$
\endchange

\amendpage 4f6.283 replacement for the paragraph after the illustration (19.04.27)
\indent The maximum army sizes for $3\le n\le 13$ are known to be
(1, 2, 4, 5, 7, 9, 12, 14, 17, 21, 24); see
OEIS sequence A250000. % an honorary number (see NAMS Oct18p1063! was A245783
 An extra black queen can actually
be included in the cases $n=3$, 4, 6, 8, 10, 11, and~13. Solutions appear
in Fig.~A--11; the construction shown in Fig.~A--11(d) generalizes to armies
of $2q(q+1)$ queens whenever $n=4q+1$, while the one in part (c)
belongs to another family of constructions that achieve the higher
asymptotic density ${7\over48}n^2$.\par
\endchange

\amendpage 4f6.283 replacement for the final lines of answer 488 (19.08.12)
respectively. [See Martin Gardner \dots\ \becomes
respectively. [B.~M. Smith, K.~E. Petrie, and I.~P. Gent obtained similar
results using {\mc CSP} methods in {\sl LNCS \bf3011} (2004), 271--286.]\par
$\bigl($This problem was posed by S. Ainley in his {\sl Mathematical
Puzzles\/} (1977), problem C1. He mentioned solutions for $n\le30$ that have
never yet been beaten, although he obtained them by hand.
See also Martin Gardner, {\sl Math Horizons\/ \bf7},\thinspace2 (November 1999),
2--16, for generalizations to coexisting armies of sizes $r$ and~$s$.
D.~M. Kane has proved, among other things, that the maximum value
of~$s$, if $r=3q^2+3q+1$, is asymptotically $n^2-(6q+3)n+O(1)$
[\arXiv:1703.04538 [math.CO] (2017), 19~pages].$\bigr)$\tighten
\endchange

\bugonpage 4f6.283 line 5 of answer 491 (20.03.21)
is a written as \becomes is written as
\endchange

\bugonpage 4f6.284 line 1 of answer 494 (18.07.17)
Exercise 504(b) \becomes
Exercise 475(d)
\endchange

\bugonpage 4f6.286 line 1 of answer 513 (20.03.17)
choose the values \becomes chose the values
\endchange

\improvepage 4f6.288 lines 3 and 7 (16.02.09)
$S_{1kk}\land\bar Z_{11}\land Z_{12}$ becomes
$(S_{1kk})\land(\bar Z_{11})\land(Z_{12})$\quad and\quad
$S_{553}\land\bar Z_{17}$ \becomes
$(S_{553})\land(\bar Z_{17})$
\endchange

\amendpage 4f6.288 in answer 516 (21.02.04)
line 2: there exists \becomes we can know\nl
line $-2$: no randomized \becomes no knowable randomized
\endchange

\amendpage 4f6.288 replacement for answer 517{(a)} (16.01.11)
\ans517. (a) (Solution by G\"unter Rote.) Replace the $j$th ternary clause
$(l_j\!\lor l'_j\!\lor l''_j)$ by three ternary equations
$l_j+a_j+c_j=1$, $\bar l'_j+a_j+b_j=1$, $\bar l''_j+c_j+d_j=1$,
where $a_j$, $b_j$, $c_j$, and $d_j$ are new variables.
\endchange

\amendpage 4f6.290 or 291 {(in third paragraph of answer 525)} (22.06.21)
$5n$ rows and $3n$ columns, \dots in each row \becomes
$3n$ items and $5n$ options, with five options for each item and
three items in each option
\endchange

%\amendpage 4f6.291 last line of answer 525 (18.01.01)
%Algorithm 7.2.2.1D \becomes Algorithm 7.2.2.1X
%\endchange
\amendpage 4f6.291 last lines of answer 525 (22.02.09)
(On the other hand \dots\ unsatisfiable.) \becomes
(The problem of this
kind that defeated all the {\mc SAT} solvers in the 2014 competition
corresponds to an instance of 3D matching that is solved almost
instantaneously by the dancing links method:
Algorithm 7.2.2.1X needs fewer than 60~$\rm M\mu$
to prove it~unsatisfiable. On the other hand, if we encode that 3D matching
problem with $3n$ quinary at-least-one and $3n\cdot10$ binary
at-most-one clauses, as in~\eq(13),
instead of using only $2n$ for at-least-one and $n\cdot10$ for at-most-one,
Algorithm~L will be almost as good as dancing links.)
\endchange

\expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi
\amendpage 4f6.293 and following (06.03.19)
Miscellaneous changes to the existing index of Volume~4 Fascicle~6
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
$\implies$: Implies. % 6th
$\iff$: If and only if. % 6th
1-in-3 {\mc SAT}, 183. % 2nd
a\period s\period: Asymptotically almost surely, 149, 153. % 7th
Ab{\'\i}o Roig, Ignasi, 269. % 2nd
Ainley, Eric Stephen, 283. % 4th
Alon, Noga Mordechai ({\heb\Hfn/\Hvv/\Hll/\Haa/ \Hyy/\Hcc/\Hdd/\Hrr/\Hmm/ \Hhh/\Hgg/\Hvv/\Hnn/}), 174, 254, 260. % 3rd
Automaton, 175, 272, \also Cellular automata. % 7th
Bayardo, Roberto Javier, Jr\period, 132. % 6th
{\it book} graphs, 126. % 3rd
Calabro, Christopher Matthew, 288. % 2nd
Connection puzzles, 114, 170. % 2nd
Contests, 131--133, 291. % 4th
Coriand, Michael Johannes Heinrich, 192. % 4th
{\mc CSP}: The constraint satisfaction problem, 283. % 2nd
Dancing links, 5, 134, 208, 288, 291. % 2nd
Exact cover problems, vii, 2, 5--6, 28, 134, 183, 186, 219, 225, 290. % 2nd
Exact (one-per-clause) satisfiability, 183. % 2nd
Extended resolution, 60, 71, 133, 153, 154, 168, 215. % 4th
Finite-state automata, 175, 272. % 7th
First-order logic, 59, 130. % 6th
Fixed point of endomorphisms, 109, 177. % 4th
Fr\"oberg, Ralf Lennart, 249. % 4th
Gange, Graeme Keith, 269. % 2nd
Grabarchuk, Petro (= Peter) Serhiyovych ({\rus Grabarchuk, Petro Sergi1i0ovich}), 263. % 3rd
Grabarchuk, Serhiy Oleksiyovych ({\rus Grabarchuk, Sergi1i0 Oleksi1i0ovich}), 263. % 3rd
Grabarchuk, Serhiy Serhiyovych ({\rus Grabarchuk, Sergi1i0 Sergi1i0ovich}), 263. % 3rd
Graham, Ronald Lewis (\GC72:74:-4:61% G2480
<0000007c000f8000000000007f800ff000000000003fc00ff000000000003f000fc000e0%
 0000003e000fc001f00000003e000fc003f80000003e000fc007f80000003e000fc00ffc%
 3ffffffffffffffffe1fffffffffffffffff0fffffffffffffffff0200003e000fc00000%
 0000003e000fc000000000003e000fc000000000003e000fc000000000f03e000fc78000%
 0000fc7e000fcfe0000000fffffffffff0000000fffffffffff8000000fffffffffff800%
 00007c00000007c00000007c00000007c00000007c00000007c00000007c00000007c000%
 00007c00000007c00000007c00000007c00000007fffffffffc00000007fffffffffc000%
 00007c00000007e00000007c00000007e00000007c00000007e00000007c00000007e000%
 00007c00000007e00000007c00000007e00000007fffffffffe0000000ffffffffffe000%
 0000fc1fe00007e0000000fc3fc00007e0000000fc7f800007c0000000fcff00000003c0%
 000001fe00000003e0000003fc00000007e0000007fffffffffff000000ffffffffffff8%
 00003ffffffffffff800007fc007e00007e00000ff000ff00007e00003fe000ff00007e0%
 0007fc001fe00007e0001ffe003fe00007e0003ffe003f800007e000fefe007fc00007e0%
 07fcfe007ff80007e01ff0f800f0ff0007e0ffc0f801e03fc007c0ff00f807e01fc007c0%
 7c00f80fc00fc00fc00000f81f8007c00fc00000f87e0007c01fc00000f8fc0003f81f80%
 0000fbf00003fc1f800003fbc00000fe1f800007fb000001ff1f800007ffffffffff9f80%
 0003ffffffffff9f000001f0000000003f000000e0000000007e00000040000003fffe00%
 0000000000007ffc000000000000003ff8000000000000000ff80000000000000007f000%
 000000000000038000000000000000020000>%% Unicode char "845b
\\\GC75:65:-3:60% G3302
<00000003e0000000000000000001f8000000000000000001fe000000000000000000ff00%
 00000000000000007f0000000000000000007f8000000000000000003f80000000000000%
 00001fc000000000000000001fc000000000000000000fc000000000000000000fc00000%
 0000000000000fc0000780000000000007c0000fc000000000000400001fe00000000000%
 0000003ff0000ffffffffffffffff80003fffffffffffffffc0001fffffffffffffffc00%
 000000000000000000000000000000000000000000000000000000000000000000000000%
 380000000000000000003e0000000000000000003f0000000000000000007fc000000000%
 700000007fe000000000380000007fc0000000003c0000007f80000000001e0000007f80%
 000000001f0000007f00000000000f0000007f00000000000f8000007e000000000007c0%
 0000fe000000000007e00000fc000000000007f00000fc000000000003f80000fc000000%
 000003f80000f8000000000001fc0001f8000000000001fc0001f0000000000001fe0001%
 f0000000000000fe0003f0000000000000ff0003e0000000000000ff0003e00000000000%
 007f8003c00000000000007f8007c00000000000007f8007c00000000000007f80078000%
 00000000003f800f800000000000003f800f000000000000003f800f000000000000003f%
 801f000000000000003f801e000000000000003f003e000000000000001f003c00000000%
 0000001e007c00000000000000180078000000000000001000f8000000000000000000f0%
 000000000000000001e000001c000000000001e000003e000000000003c000007f000000%
 000003c00000ff80ffffffffffffffffffc07fffffffffffffffffe03fffffffffffffff%
 ffe0>%% Unicode char "7acb
\JC48:48:0:40% J5581
<00fc0000000000f80000000000f00000006000f0000000f000f0fffffff800f07ffffffc%
 00f003c0000000f003c0000000f003c0000000f003c0000004f003c0000004f003c00000%
 04fc03c006000cf603c00f000cf703ffff800cf383ffffc018f383c00f8018f3c3c00f00%
 18f3c3c00f0038f183c00f0038f003cc0f0070f003c70f0070f003c38f00f0f003c1cf00%
 f0f003c1cf00e0f003c0cf0000f003c00f0000f003c00f0000f003cc0f0000f003c70f00%
 00f003c38f0000f003c1cf0000f003c1cf0000f003c0cf0000f003c00f0000f003c00f00%
 00f003c00f0000f001800f0000f000000f0000f000000f0000f000000f0000f000000f00%
 00f000000f1800f000000f3c00f0fffffffe00f07fffffff00f000000000006000000000%
 >%% Unicode char "6046
), 185. % 2nd
Gritzmann, Peter, 206. % 8th
Guilherme De Carvalho Resende, Mauricio, 15. % 6th
Hajiaghayi, MohammadTaghi\indexbreak ({\arab\Afam/\Aihy/\Afa/\Aiq/\Aamd/ \Afam/\Aij/\Afa/\Aihh/ \Afam/\Amq/\Ait/ \Afd/\Amm/\Amhh/\Aim/}), 51. % 2nd
Hsiang, Jieh (\JC48:48:0:40% J2564
<00000000001c00000000003e00000fffffff000007ffffff0001c000f0000003e000f000%
 fffff000e0007ffff001c00000f00303807000f0038700f800f003fffffc00f003fffffc%
 00f003c000f000f003c000f000f003c000f000f003c000f000f003c000f000f003c000f0%
 00f003fffff000f003fffff000f003c000f000f003c000f000f003c000f000f003c000f0%
 00f003c000f000f003c000f000f003fffff000f003fffff000f033c000f000f0f3c000f0%
 00f7c3c000f000ff03c000f0fffc03c000f0fff003c000f07fc003c000f03f0003c000f0%
 3c0003fffff0300003fffff0000001c00060000000e00000000000fc0f00000001fc0fc0%
 000003f003f0000007e000f800000f80007c00003e00003e0000f800003e0000e000001e%
 >%% Unicode char "9805
\JC48:48:0:40% J2373
<0c001e0000000e001f00000007c00f00001c03e00f00003e01f3fffdffff00f1fffcffff%
 00f00f003c3c00f00f003c3c00000f003c3c00000f003c3c0003fffc3c3c0001fffc3c3c%
 c0000f00383ce0000f00383c70000f00783c38000f00703c3c300ff0e03c3c300fe1c03c%
 3c33ff8383fc3c33fe0301fc0031f00000f80070e00000700060c0c0c000006080e0e000%
 00e000f0fc0000c000f0fc0001c031e0f80001c039c1f00003c01f83c30003c00f0783c0%
 0780078e01f0078003cc00f80f8fffffff7c1f8ffffffc3cff87ffffe03c7f03ff8f003c%
 3f03e00f00003f03000f00001f00300f0c001f00380f0e001f003f0f07800f003f0f03c0%
 0f003e0f01f00f807c0f00f807c0f00f007c07c3e00f003c07cf800f003c038f0006001c%
 >%% Unicode char "6f54
), 129. % 3rd
Intelligent design, 17, 137. % 4th
ILS: Iterated local search, 125. % 4th
{\mc ITE}, \see If-then-else operation. % 2nd
{\sl JRM\/}: {\sl Journal of Recreational Mathematics}, published 1970--2014. % 2nd
Kamath, Anil Prabhakar ({\dn aEnl \char'376BAkr kAmT}), 15. % 6th
Kane, Daniel Mertz, 283. % 2nd
Karmarkar, Narendra Krishna ({\dn nr\llap{\char3}\char'6d\kern-.5em\char'375\kern.5em\ \rlap{\kern.5em\char2}k\char'11\kern.05emZ krmrkr}), 15. % 6th
Kernels of a graph (maximal independent sets), 99, 134, 186, 188, 218. % 3rd
Lauri\`ere, Jean-Louis, 186. % 3rd
Linear hypergraphs, \see Quad-free matrices. % 2nd
Lower bounds for resolution, 57--60, 153--154. % 7th
$M_{\rm f}$ and $M_{\rm p}$, 68. % 3rd
M$\mu $: One megamem (one million memory accesses), 69, 98. % 4th
Marino, Raffaele, 94. % 3rd
Matchings, three-dimensional, \see {\mc 3D~MATCHING} problem. % 2nd
Maximal independent sets, \see Kernels of a graph. % 3rd
Mayer-Eichberger, Valentin Christian Johannes Kaspar, 269. % 2nd
Megamem (M$\mu$): One million memory accesses, 98, 123. % 2nd
M\"obius, August Ferdinand, functions, 86. % 4th
Monus operation ($x@{\dotminus}@y=\max\{0,x{-}y\}$), vi, 92, 189, 247, 268. % 2nd
Morgenstern, Detlef, 16. % 6th
Multivalued graph colorings, 6, 99, 187--188. % 7th
Mutzbauer, Otto Adolf, 275. % 3rd
Mycielski, Jan, graphs, 179. % 3rd
n\period f\period: Not falsified, 271. % 4th
Nonprimary items, 186. % 2nd
Notational conventions:\indexnoperiod
\sub $x@{\dotminus}@y$ (monus), 92, 189, 247, 268. % 2nd
\sub $F\vdash _k\epsilon $, $F\vdash _k l$, 175--176. % 2nd
OEIS\regtm: The On-Line Encyclopedia of Integer Sequences\regtm\ ({\tt oeis\period org}), 192, 283. % 4th
Overflow in arithmetic, 44, 67, 240. % 5th
ParamILS, 125, 212, 286--287. % 7th
Parisi, Giorgio Leonardo Renato, 94. % 6th
Patents, 132. % 2nd
Paturi, Ramamohan ({\tl
\|2103|\C129\|1128|\C101\\1\C238\|0128|\C111\\{-2.5}\|1148|\C90\
\|0129|\C209\\4\C86\C136\\1\C221}), 288. % 2nd
Peaceable queens, 180. % 2nd
Prins, Christian, 267. % 2nd
PSATO solver, 129. % 8th
Putnam, Hilary Whitehall, 9, 32, 130, 298. % 2nd
q\period s\period: Asymptotically quite surely, 149, 153, 169. % 7th
Ramakrishnan, Kajamalai Gopalaswamy, 15. % 6th
Ramani, Aarthi ({\tm\\102\\155\\147\\227 \\205\\203\\226}), 112, 281, 284. % 3rd
Reasons, 62--63, 66, 72, 157, 165, 233. % 2nd
Rectangle-free grids, \see Quad-free matrices. % 2nd
Ricci-Tersenghi, Federico, 94. % 3rd
Rickard, John Robert, 290. % 5th
Rote, G\"unter (= Rothe, G\"unther Alfred Heinrich), 288. % 2nd
Sa{\"\i}s, Lakhdar ({\tf \\323ay\\323 la\\330\\200ar}, {\arab\Afs/\Aiy/\Afa/\Ais/~$\!$\Afr/\Amdd/\Amkh/\Ail/}), 236, 289. % 4th
Sakallah, Karem Ahmad ({\arab\Allah/\Aa/$@$\Aq/\Afa/\Ais/ \Afd/\Amm/\Aihh/\Aha/ \Am/\Ar/\Afa/\Aic/}), 112, 132, 269, 281, 284. % 3rd
Set splitting, \see Not-all-equal {\mc SAT}. % 2nd
Socrates, son of Sophroniscus of Alopece ({\grk Swkr'aths Swfron'iskou >Alwpek=hjen}), 129. % 2nd
Sorkin, Gregory Bret, 51. % 2nd
Sparse-set representations, 211. % 5th
Stanford GraphBase, ii, 12, 13, 126, 214, 231. % 3rd
Stanford InfoLab, v. % 3rd
Stuckey, Peter James, 269. % 2nd
Subgraph isomorphism, \see Embedded graphs. % 4th
Sudoku, 183. % 2nd
Trading tails, 226. % 3rd
Tseytin, Gregory Samuelovich ({\rus Tsei0tin, Grigorii0 Samuilovich}), 9, 59--60, 71, 133, 152, 154, 168, 178, 215, 231, 290. % 2nd
Urquhart, Alasdair Ian Fenton, 231. % 3rd
Vaughan, Theresa Elizabeth Phillips, 162. % 3rd
Wainwright, Martin James, 166. % 4th
Wainwright, Robert Thomas, 138, 197, 198. % 4th
Wynn, Edward James William, 223. % 3rd
{\mc XSAT}, \see $\,$Exact (one-per-clause) satisfiability. % 2nd
$Z(m,n)$ (Zarankiewicz numbers), 106--107, 176. % 3rd

\enddoublecolumns
\endchange

\bye

[The next printing will be the 8th.] % but the 7th (July 22) probably the last!
not listed above:
PostScript removed from index
Ricci-Tersenghi was out of order in the index

ARTICLES "TO APPEAR" THAT ARE STILL PENDING: