% CHANGES TO VOLUME 4B OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 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 err4b"

\newif\ifall % \alltrue means show the trivial items too
\relax % hook

\def\vertical{|}
\def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname}
\catcode`|=\active
\let|\inref \input \jobname.ref
\catcode`|=12

\input taocpmac % use the format for TAOCP, with modifications below

\def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change

\def\bugonpage#1.#2 #3 (#4) {
  \medbreak\defaultpointsize
  \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin
   {\bf Page #2}\enspace #3
   \leaders\hrule\hfill\ \eightrm\date#4.}
  \nobreak\smallskip\iftrue\noindent}
\def\amendpage#1.#2 #3 (#4) {
  \medbreak\defaultpointsize
  \line{\kern-5pt{\bf Page #2}\enspace #3
   \leaders\hrule\hfill\ \eightrm\date#4.}
  \nobreak\smallskip\iftrue\noindent}
\def\improvepage#1.#2 #3 (#4) {\ifall
  \medbreak\ninepoint
  \line{\kern-6pt{\sl Page #2\enspace #3\/}
   \leaders\hrule\hfill\ \eightrm\date#4.}
  \nobreak\smallskip\noindent}
\def\planforpage#1.#2 #3 (#4) {
  \medbreak\defaultpointsize
  \line{\kern-5pt{\bf Page #2}\enspace #3
   \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.}
  \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent}
\let\endchange=\fi
\def\nl{\par\noindent}
\def\nlh{\par\noindent\hangit}
\def\hangit{\hangindent2em}
\def\cutpar{{\parfillskip=0pt\par}}

\def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy"
  #3
  \ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or
               Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi
  \ \ifnum #1<97 \hundred#1\else19#1\fi}
\def\hundred{20} % the "century" for dates before '97

\def\ex #1. [#2]{\ninepoint
  \textindent{\bf#1.}[{\it#2\/}]\kern6pt}
\def\EX #1. [#2]{\ninepoint
  \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt}

\def\foottext#1{\medskip
        \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint
        \smallskip\textindent{#1}}
\def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill
       \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}}
\def\refin#1 {\let|\inref \input #1.ref \let|\crossref}

\let\defaultpointsize=\tenpoint

%%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%%

\def\lhead{INTRODUCTION}
\let\rhead=\lhead
\titlepage
\volheadline{THE ART OF COMPUTER PROGRAMMING}
\bigskip
\volheadline{ERRATA TO VOLUME 4B}
\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~4B
since it was first printed in 2022.

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

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

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

\def\hundred{19}

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

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

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

\medskip
\tenpoint

\beginconstruction
The ultimate, glorious, future editions of {\sl The Art of Computer
Programming\/} are works in progress.
Please let me know of any improvements that you think I ought to make.
Send your comments either by snail mail to D.~E. Knuth, Computer
Science, Gates Building 1B, Stanford University, Stanford CA~94305-9015,
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~4C these days, I~will try to reply to all such messages
within a year of receipt. Current news is posted on
$$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$
and updated regularly.
\par\endconstruction
\rightline{\dash---Don Knuth, July 2022}

\bigskip
\bigskip
{\quoteformat
Next to the promulgation of new truth,
the best thing, I conceive, that a man can do,
is the recantation of published error.
\author JOSEPH LISTER (1878)
% Trans. Pathol. Soc. Lond. 29 (1878), 425--467;
% I saw it in Notes&Records 67(2013)228 in note 23 by R Richardson

\bigskip\bigskip
\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 4B %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\lhead{CHANGES TO VOLUME 4B: COMBINATORIAL ALGORITHMS, PART 2}
\let\rhead=\lhead
\titlepage
\volheadline{COMBINATORIAL ALGORITHMS, PART 2}
\bigskip
\rightline{Copyright \copyright\ 2022
  Addison\with Wesley}
\rightline{Last updated \today}
\bigskip
\rightline{\sl Most of these corrections have already been made in
                  recent printings.}
\smallskip
\let\defaultpointsize=\tenpoint
\def\bland{@\land@} % \land as wide as \xor
\def\blor{@\lor@}
\def\nbool#1{\mathbin{\mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}}
\def\nimp{\?\nbool\supset\?}

\improvepage 4b.90 near the top (22.09.30)
line 2: like cover$(i)$ \becomes like cover$(i)$ in \eq(12)\nl
line 3: like hide$(p)$ \becomes like hide$(p)$ in \eq(13)
\endchange

% ANSWERS BEGIN ON PAGE 370
\let\defaultpointsize=\ninepoint % get ready for answer pages

\amendpage 4b.459 line 13 of answer 151 (22.11.05)
with Algorithm X \becomes with Algorithm X and exercise 413
\endchange

\bugonpage 4b.512 line 8 of answer 343 (22.09.12)
`y 212 311 312 412 512' \becomes
`y 122 113 123 124 125'
\endchange

\bugonpage 4b.624 last line of answer 379 (22.09.13)
property. The erp rule \dots\ sufficient. \becomes
property, and no erp rule is needed.
\endchange

\bugonpage 4b.632 in answer 410 (22.10.08)
line 4: $(c_0z_0)_2\ge x_0+x_1$ \becomes
        $(c_0z_0)_2\ge x_0+x_2$\nl
line 8: $z_i\ge v\xor s$, $q_i\ge v\land s$ \becomes
        $z_i\ge v\xor s_i$, $q_i\ge v\land s_i$\nl
lines 11--13: ternary clauses; \dots But the order encoding \becomes
 ternary clauses, together with $(\bar c_7)\land(\bar z_7)$.
 Unit propagation, and the removal
of clauses with the ^{pure literals} $z_0$, $z_2$, $z_4$, $z_6$,
now reduce the result. But the order encoding
\endchange

\bugonpage 4b.662 line $-4$ (22.08.15)
saturated subtraction \becomes saturating subtraction
\endchange

\expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi
\amendpage 4b.674 and following (22.07.23)
Miscellaneous changes to the existing index of Volume~4B 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
Model RB, 333--334. % 2nd
RB random instances, 333--334. % 2nd
\vfill
\enddoublecolumns
\endchange

\bye

[The next printing will be the 3rd.]
not listed above:
page 674, adjusted spacing slightly in the epsilon entries

ARTICLES "TO APPEAR" THAT ARE STILL PENDING:
Simkin arXiv 2107.13460 [ans 7.2.2--15]
Nobel,Agrawal,Boyd arXiv 2112.03336 about Simkin's constant [ans 7.2.2--15]