% CHANGES TO FASCICLE V4F2 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 2005,2006,2007,2008,2009,2010 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 err4f2" \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{\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 2} \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~2, since it was first printed in 2005. \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, February 2005} \bigskip \bigskip {\quoteformat For a work of such scope as this, the first word of the author should be an apology for what is doubtless the too ambitious effort of a single writer. \author EDWARD W. BYRN (1900) % The Progress of Invention in the Nineteenth Century, page i \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 2 %%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO V4F2: GENERATING ALL TUPLES AND PERMUTATIONS} \let\rhead=\lhead \titlepage \volheadline{GENERATING ALL TUPLES AND PERMUTATIONS} \bigskip \rightline{Copyright \copyright\ 2005, 2006, 2007, 2008, 2009, 2010, Addison\with Wesley; all rights reserved} \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 4f2.iii line 12 (05.09.15) There will also be a Fascicle 1 for Volume 4. \becomes There will also be a Fascicle 1 for Volume 4, and even a Fascicle~0. \endchange \improvepage 4f2.iv line 20 (08.10.28) I shall happily pay a finder's fee of \$2.56 \becomes I happily offer a ``finder's fee'' of \$2.56 \endchange \improvepage 4f2.iv lines 24 and 25 (08.10.28) reward you with immortal glory instead of mere money \becomes do my best to give you immortal glory \endchange \improvepage 4f2.iv line $-13$ (05.12.04) indices \becomes indexes \endchange \amendpage 4f2.0 replacement for lines 3 and 4 (08.10.11) \begingroup\noindent\sl The opening sections of this chapter can be found in Volume~4, Fascicle~0, and Volume~4, Fascicle~1, published in 2008 and 2009. \endgroup \endchange \bugonpage 4f2.2 in the running headline {(also on pages 4, 6, 8, \dots!)} (08.01.29) \eightpoint SEARCHING \becomes SEARCHING (F2) \endchange \bugonpage 4f2.3 {(and throughout the fascicle!)} (08.04.04) \ninepoint{\bf Fig.\ 10} \becomes {\bf Fig.\ 30} [and all figure numbers need to increased by 20] \endchange \amendpage 4f2.4 line 16 (06.10.18) 7.1--00 \becomes 7.1.3--117 \endchange \improvepage 4f2.4 replacement for {\eq(12)} (09.03.11) \null $$\Gamma_n^R\,=\,\Gamma\losub n\oplus 1\smash{\overbrace{0\ldots0}^{n-1}}@, \ \hbox{also written $\Gamma\losub n\oplus 10^{n-1}$.}\eqno(12)$$ \endchange \improvepage 4f2.5, just before the footnote (09.03.11) $k\oplus(1^{j+1})_2=k\oplus(2^{@j+1}-1)$. \becomes $k\oplus(1^{j+1})_2=k\oplus(2^{@j+1}-1)$. [In this formula `$1^{j+1}$' stands for $j+1$ repetitions of `1', but `$2^{j+1}$' denotes a power of~2.] \endchange \amendpage 4f2.6 line 4 (06.10.18) 7.1--\eq(00) \becomes 7.1.3--\eq(44) \endchange \amendpage 4f2.8 in {\eq(17)} (09.04.19) $k=(b_{n-1}\ldots b_1b_0)_2$ \becomes $k=(\ldots b_2b_1b_0)_2$ \endchange \amendpage 4f2.9 line $-7$ (06.10.18) Section 7.1 \becomes Section 7.1.3 \endchange \amendpage 4f2.11 in step W1 (06.10.18) line 2: $\bigl((z-m)\oplus z\oplus m\bigr)\land m'\ne0$ \becomes $\bigl((z-m)\oplus z\oplus m\bigr)\band m'\ne0$\nl line 4: 7.1--\eq(00); it \becomes 7.1.3--\eq(90). It \endchange \amendpage 4f2.11 lines 1--2 of step W2 (05.05.19) $m_0\gets z\land(2^5-1)$, \dots\ $m_4\gets z\land(2^{25}-2^{20})$ \becomes $m_0\gets z\band(2^5-1)$, $m_1\gets z\band(2^{10}-2^5)$, $m_2\gets z\band(2^{15}-2^{10})$, $m_3\gets z\band(2^{20}-2^{15})$, and $m_4\gets z\band(2^{25}-2^{20})$ \endchange \improvepage 4f2.12 replacement for {\eq(23)} (05.04.23) $$\def\,{\kern1pt}\vcenter{\halign{{\tt#}\,,&&\quad{\tt#}\,,\cr ducks&ducky&duces&dunes&dunks&dinks&dinky\cr dines&dices&dicey&dicky&dicks&picks&picky\cr pines&piney&pinky&pinks&punks&punky&\omit\quad{\tt pucks}\,.\cr}}\eqno(23)$$ \endchange \amendpage 4f2.13 line $-7$ (09.03.26) 45 \becomes 47 \endchange \bugonpage 4f2.15 line $-12$ (08.09.05) $k<2^n$ \becomes $k<2^n-1$ \endchange \improvepage 4f2.18 line $-6$ (09.04.19) with coordinates \becomes with integer components \endchange \improvepage 4f2.19 line 4 (09.04.25) coordinate \becomes component \endchange \improvepage 4f2.20 line 7 (09.04.25) coordinate \becomes component \endchange \bugonpage 4f2.20 bottom line (05.04.17) $j$th forest \becomes $j$th tree \endchange \bugonpage 4f2.23 in Table 1 (09.03.02) \ninepoint $22:1,7$ \becomes $22:1$ \endchange \improvepage 4f2.24 line $-10$ (09.04.25) cycles are identical \becomes cycles may be identical \endchange \bugonpage 4f2.25 line 12 (09.04.19) {\tenthinbf step D6 \becomes step D5} \endchange \amendpage 4f2.26 line 9 (10.10.08) {\bf 68} (1958) \becomes (2) {\bf 68} (1958) \endchange \improvepage 4f2.28 line 2 of exercise 1 (09.04.25) \ninepoint coordinate \becomes component \endchange \improvepage 4f2.29 line 2 of exercise 16 (09.04.25) \ninepoint coordinates \becomes components \endchange \improvepage 4f2.29 last line of exercise 17 (09.04.25) \ninepoint changes \becomes position changes \endchange \amendpage 4f2.30 line 1 (07.07.05) \ninepoint [{\it21\/}] \becomes [{\it23\/}] \endchange \improvepage 4f2.30 line 3 (07.07.05) \ninepoint summed over \becomes a polynomial in the variables $z_0$, $z_1$, $z_2$, and $z_3$, summed over \endchange \bugonpage 4f2.31 replacement for line 4 of exercise 29 (09.03.23) $${1\over 2^n}\sum_{k@=@0}^{2^n\?-\?1}\,\Bigl\vert@ g\iter{-1}\bigl(g(k)\oplus p\bigr) -k@@\Bigr\vert,$$ \endchange \amendpage 4f2.32 line 2 of exercise 40 (09.03.02) \ninepoint $m_j=x\land(2\raise.7ex\hbox{$\scriptstyle5j$}-1)$ \becomes $m_j=z\band(2\raise.7ex\hbox{$\scriptstyle5j$}-1)$ \endchange \amendpage 4f2.33 replacement for exercises 44--48 (09.03.26) \ninepoint \ex 44. [M20] Show that $d(n)\le{M(n)\choose2}$, if the $n$-cube has $M(n)$ perfect matchings. \smallskip \ex 45. [M40] (T. Feder and C. Subi, 2009.) This exercise constructs a large number of Gray cycles in the $(4r+2)$-cube $G=G_4\cprod G_3\cprod G_2\cprod G_1\cprod G_0\cprod G_{-1}$, where $G_i$ is an $r$-cube for $i>0$ and $G_0=G_{-1}=P_2$. The vertices $v$ are $(4r+2)$-bit strings $v_4\ldots v_0v_{-1}$, where $v_i$ has~$r$ bits for $i>0$ and 1~bit for $i\le0$. The ``signature'' of~$v$ is the 4-bit string $\sigma(v)=s_4s_3s_2(s_1@{\oplus}@v_0)$, where $s_i$ is the parity of~$v_i$. We treat bit strings as binary numbers.\tighten\par For $1\le l\le4$, let ${\cal M}_l(v)$ be a matching in~$G$ with $v\adj v'=v'_4\ldots v'_0v'_{-1}$ and $v'_i=v\losub i$ for $i\ne l$. (Note that ${\cal M}_l(v')=v$.) Also define ${\cal M}_0(v)=v\oplus2$. Consider the cycles formed by the edges $v\adj{\cal M}_{l(v)}(v)$, where $l(v)$ depends on $v$'s signature: $$\advance\abovedisplayskip-2pt \advance\belowdisplayskip-2pt \def\\#1.#2{\vcenter{\halign{\hfil##\hfil\cr \strut\raise1.5pt\hbox{\sevenrm#1}\cr#2\cr}}} \vcenter{\halign{\hfil$#={}$\cr\strut\sigma(v)\cr l(v)\cr}}\ \\0000.0\ \\0001.2\ \\0011.0\ \\0010.3\ \\0110.1\ \\0111.2\ \\0101.0\ \\0100.4\ \\1100.1\ \\1101.2\ \\1111.1\ \\1110.3\ \\1010.1\ \\1011.2\ \\1001.0\ \\1000.4$$ \item{a)} Suppose $r=2$ and ${\cal M}_l(v)=v\oplus2^{2l+s_{l-1}}$ for $l>1$ and ${\cal M}_1(v)=v\oplus2^{2+(v_0\oplus v_{-1})}$. What cycle contains vertex $0\ldots 0$ in this case? \item{b)} A vertex whose signature is a power of 2 is called a ``ground vertex.'' Four vertices with the same $v_4\ldots v_1$ are called ``siblings.'' Define $u\equiv v$ if $u$ and $v$ are in the same cycle, or if $u$ and $v$ are sibling ground vertices, or if a chain of such equivalences leads from $u$ to~$v$. Explain how to construct cycles in~$G$ for each equivalence class. \item{c)} Furthermore, if $u$ and $v$ are sibling ground vertices, there is such a cycle that retains the edges $\{u@{\oplus}@2\adj u, v@{\oplus}@2\adj v\}$ of the original cycles. \item{d)} Finally, show how to convert the cycles of (b) and~(c) into a single cycle. \item{e)} When ${\cal M}_1$, \dots,~${\cal M}_4$ vary, how many different Hamiltonian cycles do we get? \smallskip \ex 46. [M23] Extend exercise 45 to the $(kr+2)$-cube, for $k$ even. \smallskip \ex 47. [\HM24] What asymptotic estimates do exercises 44 and 46 give for \smash{$d(n)^{1/2^n}$}? \smallskip \ex 48. [\HM48] Determine the asymptotic behavior of \smash{$d(n)^{1/2^n}$} as $n\to\infty$. \endchange \improvepage 4f2.33 line 1 of exercise 51 (08.10.11) \ninepoint Complete \becomes ({\it Balanced Gray cycles.}) Complete \endchange \amendpage 4f2.33 new rating for exercise 55 (07.08.28) \ninepoint[{\it47\/}] \becomes [{\it35\/}] \endchange \amendpage 4f2.36 in exercise 85 (07.02.02) $\sqtimes$ \becomes $\boust$ \qquad[This notational change also affects answers 85--87.] \endchange \amendpage 4f2.37 replacement for lines 1--4 of exercise 96 (10.01.19) \ninepoint \EX 96. [M28] Suppose a family of coroutines has been set up to generate a de~Bruijn cycle of length $m^n$ using Algorithms R and~D, based recursively on simple coroutines like Algorithm~S for the base case $n=2$, and using Algorithm~D when $n>2$ is even. \item{a)} How many coroutines $(R_n, D_n, S_n)$ of each type will there be? \endchange \amendpage 4f2.38 in exercise 107 (09.04.25) \ninepoint running time of Algorithm F. \becomes running time of Algorithm F, for fixed $m$ as $n\to\infty$. \endchange \improvepage 4f2.39 and 40 formatting change (05.06.11) [I'm moving the quotations from page 39 to page 40, for better page breaks. This change affects several entries in the index.] \endchange \improvepage 4f2.39 or 40, in step L4 (09.08.10) Then, if $k0$, set $t[k]\gets j$, $k\gets k+d$, and $j\gets j-1$. \algstep T4. [Offset.] Set $t[k]\gets t[k]+1$. \algstep T5. [Hunt up.] Set $k\gets k+d$, $j\gets 1$. While $jk$ \becomes $j2\lceil2^{n+1}\!/(n+2)\rceil \ge c'_k$ for $0\le jn_l']$ \endchange \bugonpage 4f2.102 replacement for line 2 of answer 7 (05.02.03) $${n_1+\cdots+n_t\over n}+{(n_1n_2+n_1n_3+\cdots+n_{t-1}n_t)+ n_1(n_1{-}1)+\cdots+n_t(n_t{-}1)\over n(n-1)}+\cdots{}\,.$$ \endchange \amendpage 4f2.102 insert a new sentence at the beginning of answer 9 (06.04.06) Assume that $r>0$ and that we begin with $a_01$. \endchange \bugonpage 4f2.116 line 8 (06.02.26) $\displaystyle \sum_{j+1}^{r-1}$ \becomes $\displaystyle \sum_{j=1}^{r-1}$ \endchange \bugonpage 4f2.116 line 9 (06.12.02) $F_{r+1}-2F_j+(-1)^{@j}F_{r+1-j}$ \becomes $F_{r+1}-2F_j-(-1)^{@j}F_{r+1-j}$ \endchange \amendpage 4f2.117 lines 3--5 of answer 100 (05.02.12) It appears likely \dots~for \becomes A.~D. King [{\sl Discrete Math.\ \bf306} (2006), 508--516] has shown that indecomposable permutations can be generated efficiently by making only a single transposition at each step. In fact, {\it adjacent\/} transpositions may well suffice; for example, when $n=4$ the indecomposable permutations are \endchange \bugonpage 4f2.118 line 4 of answer 105 (06.03.29) ments; \becomes ments''; \endchange \bugonpage 4f2.119 line 10 of answer 108 (07.03.21) 239--241 \becomes 739--741 \endchange \amendpage 4f2.120 new answer 109 (10.11.11) \begingroup \advance\parindent by 4pt % for them BIG exercise numbers \ans109. An ingenious construction by I. H. Sudborough and L.~Morales [{\sl Theoretical Comp. Sci.\ \bf411} (2010), 3965--3970] proves that $f(n)\ge {19\over128}n^2+O(1)$. \endchange \bugonpage 4f2.120 line 5 of answer 111 (06.03.29) Theorem 2.3.4.2D \becomes Theorem 2.3.4.2G \endchange \bugonpage 4f2.120 line $-2$ of answer 111 (06.04.21) Eulerian trials \becomes Eulerian trails \endchange \amendpage 4f2.120 new answer 112 (10.01.25) \ans112. (a) If the cycle is $a_1a_2\ldots{}@$, use $\sigma$ at step~$j$ if the subsequence $a_ja_{j+1}\ldots a_{j+n-1}$ is a permutation; otherwise use $\rho$.\par (b) This statement follows immediately from exercise 72.\par (c) Let $\Omegait_2=\sigma^2$, and obtain $\Omegait_{n+1}$ from $\Omegait_n$ by substituting $\sigma\mapsto\sigma^2\!\rho^{n-1}$ and $\rho\mapsto\sigma^2\!\rho^{n-2}\sigma$. For example, $\Omegait_3=(\sigma^2\!\rho)^2$ and $\Omegait_4=\bigl((\sigma^2\!\rho^2)^2\sigma^2\!\rho\sigma\bigr){}^2$. Generate permutations by starting with $n\ldots21$ and applying the successive elements of~$\Omegait_n$; for example, the sequence when $n=4$ is $$\displaylines{ 4321,3214,2143,1423,4213,2134,1342,3412,4132,1324,3241,2431,\cr 4312,3124,1243,2413,4123,1234,2341,3421,4231,2314,3142,1432,\cr}$$ and the corresponding universal cycle is (432142134132431241234231). Notice that $n$ moves cyclically in this sequence of permutations; and the permutations that begin with~$n$ correspond to the sequence obtained from~$\Omegait_{n-1}$.\par [See F.~Ruskey and A.~Williams, {\sl ACM Trans.\ on Algorithms\/ \bf6} (2010), 45:1--45:12. Similar methods are said to be known to bell-ringers. Universal cycles can also be constructed explicitly for permutations of an arbitrary~{\it multiset}, with a method analogous to 7.2.1.1--\eq(62); see A.~Williams, Ph.D. thesis (Univ.\ of Victoria, 2009).] \endgroup \endchange \amendpage 4f2.120 and 121, changes to old answer 112 (08.02.03) [This answer is now the answer to exercise 113. In the second and third paragraphs, change `Notice first \dots~Now consider' \becomes `Consider'. Also delete the final paragraph.] \endchange \expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi \amendpage 4f2.122 and following (05.02.07) Miscellaneous changes to the existing index of Volume~4 Fascicle~2 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 $\phi$ (golden ratio), as ``random'' example, 68. % 3rd \'Ad\'am, Andr\'as, 85. % 2nd Asymptotic methods, 33, 73, 98, 106, 109. % 2nd Bakos, Tibor, 85. % 2nd Balanced Gray codes, 14--17, 33, 35, 85. % 2nd Bell ringing, 39, 42--43, 59, 120. % 4th Binary Gray codes, enumeration of, 13, 33. % 2nd Brown, Joseph Alexander, 105. % 3rd Buckley, Michael Robert Warren, 66. % 2nd Castown, Rudolph William, 11. % 2nd Cayley graphs, 58, 69--72, 75, 111. % 2nd Codewords, 30. % 2nd Complete graph, 85. % 2nd Connected components, 34, 84. % 2nd Conway, John Horton, 74, 83. % 2nd Coroutines, 70--71. % 2nd \sub recursive, 24--25, 36--37. % 2nd Cyclic shifts, 26, 56, 58, 61, 68. % 2nd de Bruijn cycles, 22--27, 36--38, 74, 99, 121. % 2nd Dijkstra, Edsger Wybe, 42. % 2nd Direct product of matrices, 82. % 2nd Duval, Jean-Pierre, 98. % 2nd Feder, Tom\'as, 33. % 2nd Fibonacci, Leonardo, of Pisa (= Leonardo filio Bonacii Pisano), numbers, 36, 74, 116. % 2nd Field, finite, 31--32. % 2nd Fink, Ji\v{r}{\'\i}, 85. % 2nd Five-letter English words, 11, 32--33, 38, 66. % 2nd Generation of combinatorial patterns, 1. % 2nd Gray code for $n$-tuples,\indexnoperiod \sub nonbinary, 18--20, 35--36, 80, 82, 88, 90--92. % 2nd Hamilton cycle, 13, 34, 41, 58--59, 69--72, 75, 85, 111. % 2nd Hamilton path, 15, 33, 41, 58--59, 70--71, 75, 85, 110--111. % 2nd Inversion tables, 41, 72, 101, 116. % 2nd Iv\'anyi, Antal Mikl\'os, 99. % 2nd Jackson, Bradley Warren, 74. % 2nd K$\mu$: One thousand memory accesses, 105. % 2nd King, Andrew Douglas, 117. % 2nd Lexicographic permutation generation, 39, 50, 53, 54, 64--65. % 3rd Loony Loop, 36. % 3rd M$\mu$: One million memory accesses. % 2nd Matchings, 33--34, 63, 73, 84, 116--117. % 2nd \MMIX\ computer, ii, iv, 59--61, 72, 76. % 2nd Morales, Linda, 120. % 2nd Multisets, permutations of, 39--41, 62, 65, 71, 120--121. % 4th $n$-cube, matchings of, 33, 84. % 2nd $n$-cube, symmetries of, 66. % 2nd N\=ar\=aya\d{n}a Pa\d{n}\d{d}ita, \vadjust{\vskip1pt}son of N\d{r}si\:mha\indexbreak({\dn nArAyZ pE\char23Xt}, {\dn n\llap{\lower.12em\hbox{\char2}\kern.4em}Es\llap{\char92\kern-.05em}h-y p\llap{\lower.15em\hbox{\char0}\kern.3em}/,}), 39, 101. % 2nd Notational conventions:\indexnoperiod % 2nd \sub $x\xor y$ (bitwise exclusive or), 4. % 3rd \sub $\Gamma^R$ (reversal), 3. % 2nd \sub $\Gamma\boust\Gamma'$ (boustrophedon product), 36. % 2nd Novra, Henry, 92. % 2nd Organ-pipe order, 111, 118. % 2nd Permutation generation,\indexnoperiod \sub bypassing blocks, 51--54, 68, 117. % 3rd \sub lexicographic, 39, 50, 53, 54, 64--65. % 3rd Permutations,\indexnoperiod \sub of a multiset, 39--41, 62, 65, 71, 120--121. % 4th \sub order of, 58, 108. % 3rd \sub representation of, 47, 55. % 3rd Phi ($\phi$), as ``random'' example, 68. % 3rd Poll\'ak, Gy\"orgy, 85. % 2nd Preferential arrangements, \see Weak orderings. % 2nd Rapaport, Elvira Strasser, 111. % 3rd Recurrences, 23, 79, 81, 90, 95--96, 101. % 2nd Reflected Gray codes, 19--21, 35, 80, 90, 92. % 2nd Representation of permutations, 47, 55. % 3rd Ruskey, Frank, iv, 20, 21, 28, 31, 33, 59, 72, 94, 98, 111, 112, 115, 116, 120. % 2nd \'S\=ar\:ngadeva, son of So\d{d}haladeva ({\dn fA\kern-.1em\char'263\kern-.25em\char'15\kern.05em\llap{\raise.35em\hbox{\char'24}}\kern-.09emd\kern-.1em\llap{\char3}v}, {\dn soYld\kern-.02em\llap{\char3}v p\llap{\lower.15em\hbox{\char0}\kern.3em}/,}), 101. % 2nd Sch\"aff\/ler, Theodor Heinrich Otto, 5. % 2nd Shorthand universal cycles, \see Universal cycles of permutations. % 4th Smith, Derek Alan, 83. % 2nd Subi, Carlos Samuel, 33. % 2nd Sudborough, Ivan Hal, 120. % 2nd Suparta, I Nengah, 80. % 2nd Szab\'o, J\'ozsef, 105. % 3rd Traveling Salesrep Problem, 64. % 2nd Trowbridge, Terry Jay, 105. % 3rd Universal cycles of permutations, 74--75. % 2nd \sub modular, 120. % 2nd van Zanten, Arend Jan, 80. % 2nd Visiting an object, 1. % 2nd Weak orderings, 74, 118. % 2nd Williams, Aaron Michael, 75, 120--121. % 4th Zanten, Arend Jan van, 80. % 2nd \vfill \enddoublecolumns \endchange \bye [The next printing would have been the 5th.] not listed above: ARTICLES "TO APPEAR" THAT ARE STILL PENDING: Sudborough and Morales, accepted by TCS Aug 2010 but not yet edited CROSS-REFERENCES TO "00": 7.2.3--|5bit-gray| 7.10--|bandwidth-of-n-cube|