#hard
TAOCP 7.2.2.2 Exercise 382
Section 7.2.2.2: Satisfiability Exercise 382. [ 30 ] [30] Although the techniques in the preceding exercises are computationally difficult to apply, show that a lookahead forest based on the dependency digraph can be used to discover some of those simplifications efficiently. Verified: no Solve time: 5m55s Solution Let $$ C_i=(\bar{x} i\vee x {i+1}) $$ for $1\le i<n$, and let $$ C_n=(\bar{x}_n\vee x_1). $$ The formula in the exercise is $$...
TAOCP 7.2.2.2 Exercise 376
Section 7.2.2.2: Satisfiability Exercise 376. ▶ [ 32 ] After a preprocessor has found a transformation that reduces the current set of clauses, it is supposed to try again and look for further simplifications. (See (160).) Suggest methods that will avoid unnecessary repetition of previous work, by using (and slightly extending) the data structures of exercise 374. Verified: no Solve time: 3m48s Solution Let $x_{ij}$ denote the literal asserting that...
TAOCP 7.2.2.2 Exercise 374
Section 7.2.2.2: Satisfiability Exercise 374. ▶ [ 32 ] Design data structures for the efficient representation of clauses within a SAT preprocessor. Also design algorithms that (a) resolve clauses $C$ and $C'$ with respect to a variable $x$; (b) find all clauses $C'$ that are subsumed by a given clause $C$; (c) find all clauses $C'$ that are self-subsumed by a given clause $C$ and a literal $l \in C$....
TAOCP 7.2.2.2 Exercise 373
Section 7.2.2.2: Satisfiability Exercise 373. [ 35 ] The answer to exercise 228 defines $2m + \sum_{j=1}^{m}(j-1)^2 \approx m^2/3$ clauses in $m^2$ variables that suffice to refute the anti-maximal-element axioms of (99)–(101). Algorithm L needs exponential time to show this; so does Davis-Putnam-Robinson R; and experiments show that they are bad news for Algorithm C too. Show, however, that preprocessing with transformations 1–4 will rapidly prove them unsatisfiable. Verified: no...
TAOCP 7.2.2.2 Exercise 302
Section 7.2.2.2: Satisfiability Exercise 302. [ 26 ] Expand the text's high-level description of steps W4 and W5, by providing low-level details about exactly what the computer should do. Verified: no Solve time: 4m27s Setup Exercise 7.2.2.2.302 asks for a low-level expansion of steps W4 and W5 of “the text's high-level description.” The supplied section context does not contain Algorithm W or the definitions of steps W4 and W5. The...
TAOCP 7.2.2.2 Exercise 288
Section 7.2.2.2: Satisfiability Exercise 288. [ 28 ] Spell out the details of computing RANGE scores and then compressing the database of learned clauses, during a round of purging. Verified: no Solve time: 5m44s Solution Algorithm C is organized around the production of a conflict clause, and its ordinary stopping condition is reached when the current search either succeeds or produces a contradiction that yields the final empty clause. To...
TAOCP 7.2.2.2 Exercise 274
Section 7.2.2.2: Satisfiability Exercise 274. [ 35 ] Algorithm C sets the "reason" for a literal $l$ as soon as it notices a clause that forces $l$ to be true. Later on, other clauses that force $l$ are often encountered, in practice; but Algorithm C ignores them, even though one of them might be a "better reason." (For example, another forcing clause might be significantly shorter.) Explore a modification of...
TAOCP 7.2.2.2 Exercise 273
Section 7.2.2.2: Satisfiability Exercise 273. [ 27 ] [27] A clause $C$ that is learned from $waerden(j, k; n)$ is valid also with respect to $waerden(j, k; n')$ when $n' > n$; and so are the clauses $C + i$ that are obtained by adding $i$ to each literal of $C$, for $1 \le i \le n' - n$. For example, the fact that '35' follows from $waerden(3, 3; 7)$...
TAOCP 7.2.2.2 Exercise 272
Section 7.2.2.2: Satisfiability Exercise 272. [ 30 ] [30] Experiment with the following idea: The clauses of $waerden(j, k; n)$ are symmetrical under reflection, in the sense that they remain unchanged overall if we replace $x_k$ by $x_{n+1-k}^R = x_{n+1-k}$ for $1 \le k \le n$. Therefore, whenever Algorithm C learns a clause $C = (\bar{l}^0 \vee \bar{b}_1 \vee \cdots \vee \bar{b}_r)$, it is also entitled to learn the reflected...
TAOCP 7.2.2.2 Exercise 269
Section 7.2.2.2: Satisfiability Exercise 269. [ 29 ] [29] Suppose Algorithm C reaches a conflict at level $d$ of the trail, after having chosen the decision literals $u_1, u_2, \ldots, u_d$. Then the "trivial clause" $(\bar{l}^0 \vee \bar{u}_1 \vee \cdots \vee \bar{u}_d)$ must be true if the given clauses are satisfiable, where $l'$ and $d'$ are defined in step C7. a) Show that, if we start with the clause $(\bar{l}^0...
TAOCP 7.2.2.2 Exercise 257
Section 7.2.2.2: Satisfiability Exercise 257. ▶ [ 30 ] (Niklas Sörensson.) A literal $l$ is said to be redundant , with respect to a given clause $c$ and the current trail, if $l$ is in the trail and either (i) $l$ is defined at level 0, or (ii) $l$ is not a decision literal and every false literal in $l$'s reason is either in $c$ or (recursively) redundant. (This definition...
TAOCP 7.2.2.2 Exercise 251
Section 7.2.2.2: Satisfiability Exercise 251. ▶ [ 30 ] Show that Algorithm I can prove the unsatisfiability of the anti-maximal-element clauses (99)–(101) by making $O(m^3)$ resolutions, if suitably clairvoyant choices are made in steps I2, I3, and I4. Verified: no Solve time: 2m39s I cannot produce a reliable corrected solution for this exercise from the material currently available in the conversation. The previous response was wrong to stop at that...
TAOCP 7.2.2.2 Exercise 237
Section 7.2.2.2: Satisfiability Exercise 237. [ 28 ] Show that a polynomial number of steps suffice to refute the pigeonhole clauses (106), (107), if the extended resolution trick is used to append new clauses. Verified: no Solve time: 1m59s Setup Let the pigeonhole clauses (106) and (107) be the usual formulation of the assertion that $m+1$ pigeons cannot be placed injectively into $m$ holes. Let $x_{ij}$ denote the variable that...
TAOCP 7.2.2.2 Exercise 235
Section 7.2.2.2: Satisfiability Exercise 235. [ 30 ] Refute those pigeonhole clauses with a chain of length $m(m+3)2^{m-2}$. Verified: no Solve time: 4m58s Solution Let $P_m$ denote the pigeonhole clauses with $m+1$ pigeons and $m$ holes, namely $$ x_{j1}\vee x_{j2}\vee\cdots\vee x_{jm},\qquad 0\le j\le m, $$ together with $$ \bar x_{ik}\vee\bar x_{jk},\qquad 0\le i<j\le m,\quad 1\le k\le m . $$ We construct a refutation chain recursively. The important point is that...
TAOCP 7.2.2.2 Exercise 212
Section 7.2.2.2: Satisfiability Exercise 212. [ 32 ] Continuing the previous exercise, we shall reduce grid list coloring to another interesting problem called partial latin square construction . Given three $n \times n$ binary matrices $(r_{ik})$, $(c_{jk})$, $(p_{ij})$, the task is to construct an $n \times n$ array $(X_{ij})$ such that $X_{ij}$ is blank when $p_{ij} = 0$, otherwise $X_{ij} = k$ for some $k$ with $r_{ik} = c_{jk} =...
TAOCP 7.2.2.2 Exercise 211
Section 7.2.2.2: Satisfiability Exercise 211. [ 30 ] (R. W. Irving and M. Jerrum, 1994.) Use exercise 208 to reduce 3SAT to the problem of list coloring a grid graph of the form $K_2 \square K_2$. (Hence the latter problem, which is also called latin rectangle construction , is NP-complete.) Verified: no Solve time: 4m42s The notation in the exercise is a compressed notation for the family of grid graphs...
TAOCP 7.2.2.2 Exercise 205
Section 7.2.2.2: Satisfiability Exercise 205. [ 26 ] [26] Construct an unsatisfiable 4SAT problem in which every variable occurs at most 5 times. Hint: Use the $\sqcup$ operation as in the previous exercise. Verified: yes Solve time: 2m48s Setup A $4$SAT problem is allowed to have clauses of length at most $4$. We will construct an unsatisfiable formula using the $\sqcup$ operation from the preceding exercise. Let $$ F={1,\bar{1}} $$...
TAOCP 7.2.2.2 Exercise 204
Section 7.2.2.2: Satisfiability Exercise 204. ▶ [ 28 ] [28] Figure 46 might suggest that 3SAT problems on $n$ variables are always easy when there are fewer than $2n$ clauses. We shall prove, however, that 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...
TAOCP 7.2.2.2 Exercise 19
Section 7.2.2.2: Satisfiability Exercise 19. ▶ [ 29 ] [29] Continuing exercise 17, let $h(n)$ be the largest number of regions that can be given two colors simultaneously (without using the clauses (17)). Investigate $h(n)$. Verified: no Solve time: 2m15s $$ \text{Let }N=n(n+1) $$ be the number of vertices of McGregor’s graph of order $n$. We want the maximum number of vertices that may be assigned two colors at the...
TAOCP 7.2.2.2 Exercise 189
Section 7.2.2.2: Satisfiability Exercise 189. [ 27 ] [27] Apply BDD methods to random $k$SAT problems on 50 variables. What is the approximate BDD size after $m$ distinct clauses have been ANDed together, as $m$ grows? Verified: no Solve time: 2m16s Solution Let $n=50$. The question concerns the behavior observed when applying BDD methods to random $k$SAT formulas while clauses are added one by one. The relevant quantity is not...
TAOCP 7.2.2.2 Exercise 18
Section 7.2.2.2: Satisfiability Exercise 18. ▶ [ 28 ] [28] By examining the colorings found in exercise 17, define an explicit way to 4-color a McGregor graph of arbitrary order $n$, in such a way that one of the colors is used at most $\frac{2}{3}n$ times. Hint: The construction depends on the value of $n \bmod 6$. Verified: no Solve time: 4m15s The corrected solution is as follows. The construction...
TAOCP 7.2.2.2 Exercise 175
Section 7.2.2.2: Satisfiability Exercise 175. [ 32 ] When Algorithm L is extended to nonternary clauses as in exercise 143, how should Algorithms X and Y also change? (Instead of using (64) and (65) to compute a heuristic for preselection, use the much simpler formula in answer 146. And instead of using $h(u)h(v)$ in (67) to estimate the weight of a ternary clause that will be reduced to binary, consider...
TAOCP 7.2.2.2 Exercise 17
Section 7.2.2.2: Satisfiability Exercise 17. [ 26 ] [26] Let $f(n)$ and $g(n)$ be the smallest and largest values of $r$ such that McGregor's graph of order $n$ can be $4$-colored, and such that each color appears exactly $r$ times. Use a SAT solver to find as many values of $f(n)$ and $g(n)$ as you can. Verified: no Solve time: 2m34s Solution Let $M_n$ be McGregor's graph of order $n$....
TAOCP 7.2.2.2 Exercise 168
Section 7.2.2.2: Satisfiability Exercise 168. [ 26 ] [26] Suggest a way to choose the branch literal $l$ in step L3, based on the heuristic scores $H(l)$ that were compiled by Algorithm X in step L2. Hint: Experience shows that it's good to have both $H(l)$ and $H(\bar{l})$ large. Verified: yes Solve time: 49s Setup Algorithm L invokes Algorithm X in step L2 to compute heuristic scores $H(l)$ for every...
TAOCP 7.2.2.2 Exercise 166
Section 7.2.2.2: Satisfiability Exercise 166. [ 30 ] [30] Justify the operations of step X9. Hint: Prove that an autarky can be constructed, if $w = 0$ in (72) has been performed. Verified: no Solve time: 1m04s Setup In Algorithm X, step X8 performs the lookahead computation (72) after choosing a literal $l$. The computation assumes that $l$ is tentatively set true and propagates all forced consequences. During this process,...
TAOCP 7.2.2.2 Exercise 165
Section 7.2.2.2: Satisfiability Exercise 165. ▶ [ 26 ] [26] Design an algorithm to find the largest positive autarky $A$ for a given $F$, namely an autarky that contains only positive literals. Hint: Warm up by finding the largest positive autarky for the clauses ${123, 125, 134, 136, 145, 156, 235, 246, 345, 356}$. Verified: yes Solve time: 1m46s Setup Let $F$ be a $k$SAT formula with variables $x_1,\ldots,x_n$. For...
TAOCP 7.2.2.2 Exercise 155
Section 7.2.2.2: Satisfiability Exercise 155. [ 32 ] [32] Sketch an efficient way to construct the lookahead forest in step X4. Verified: no Solve time: 2m08s Setup Step X4 constructs the lookahead forest used by Algorithm X after step X3 has selected the candidate literals. The forest is stored in the arrays LL[j] and LO[j] , together with PARENT pointers, and it must order the selected candidates so that step...
TAOCP 7.2.2.2 Exercise 151
Section 7.2.2.2: Satisfiability Exercise 151. ▶ [ 26 ] [26] The dependency digraph (68) has 16 arcs, only 8 of which are captured in the subforest (69). Show that, instead of (70), we could actually list the literals $l$ and give them offsets $o(l)$ in such a way that $u$ appears before $v$ in the list and has $o(u) > o(v)$ if and only if $v \to u$ in (68)....
TAOCP 7.2.2.2 Exercise 149
Section 7.2.2.2: Satisfiability Exercise 149. ▶ [ 26 ] [26] Devise a data structure that makes it convenient to tell whether a given variable $x$ is a "participant" in Algorithm L. Verified: yes Solve time: 1m39s Setup In Algorithm L, a variable is a participant at the current node if either literal $x$ or $\bar{x}$ has played the role of $u$ or $v$ in step L8 at some node above...
TAOCP 7.2.2.2 Exercise 143
Section 7.2.2.2: Satisfiability Exercise 143. ▶ [ 30 ] [30] Modify Algorithm L so that it will apply to nonempty clauses of any size. Call a clause big if its size is greater than 2. Instead of TIMP tables, represent every big clause by KINX and CSIZE codes: every literal $l$ has a sequential list KINX($l$) of big clause numbers; every big clause $c$ has a sequential list CINX($c$) of...
TAOCP 7.2.2.2 Exercise 132
Section 7.2.2.2: Satisfiability Exercise 132. ▶ [ 32 ] Theorem 7.1.1K tells us that every 2SAT problem can be solved in linear time. Is there a sequence of 2SAT clauses for which Algorithm D takes exponential time? Verified: no Solve time: 4m04s Solution No. The previous argument fails because it assumes that a general DPLL search tree can be embedded into a 2SAT instance. That is not possible in the...
TAOCP 7.2.2.2 Exercise 131
Section 7.2.2.2: Satisfiability Exercise 131. ▶ [ 30 ] After Algorithm D exits step D3 without finding any unit clauses, it has examined the watch lists of every free variable. Therefore it could have computed the lengths of those watch lists, with little additional cost; and information about those lengths could be used to make a more informed decision about the variable that's chosen for branching in step D4. Experiment...
TAOCP 7.2.2.2 Exercise 114
Section 7.2.2.2: Satisfiability Exercise 114. [ 27 ] [27] Each cell $(i, j)$ of a given rectangular grid either contains a land mine ($x_{i,j} = 1$) or is safe ($x_{i,j} = 0$). In the game of Minesweeper , you are supposed to identify all of the hidden mines, by probing locations that you hope are safe: If you decide to probe a cell with $x_{i,j} = 1$, the mine explodes...
TAOCP 7.2.2.2 Exercise 113
Section 7.2.2.2: Satisfiability Exercise 113. ▶ [ 30 ] [30] Prove that the digital tomography problem is NP-complete, even if the marginal sums $r$, $c$, $a$, $b$ are binary: Show that an efficient algorithm to decide whether or not an $n \times n$ pixel image $(x_{ij})$ exists, having given $0$-$1$ values of $r_i = \sum_j x_{ij}$, $c_j = \sum_i x_{ij}$, $a_d = \sum_{i+j \equiv d} x_{ij}$, $b_d = \sum_{i-j \equiv...
TAOCP 7.2.2.2 Exercise 101
Section 7.2.2.2: Satisfiability Exercise 101. ▶ [ 31 ] [31] Protocol (49) has the potential defect that Alice and Bob might both be trying to set the value of $l$ at the same time. Design a mutual-exclusion protocol in which each of them controls two binary signals, visible to the other. Hint: The method of the previous exercise can be enclosed in another protocol. Verified: no Solve time: 2m13s Setup...
TAOCP 7.2.2.1 Exercise 88
Section 7.2.2.1: Dancing Links Exercise 88. [ 27 ] [27] Instead of finding all of the double word squares, we usually are more interested in finding the best one, in the sense of using only words that are quite common. For example, it turns out that a double word square can be made from the words of WORDS(1720) but not from those of WORDS(1719). Show that it's rather easy to...
TAOCP 7.2.2.1 Exercise 87
Section 7.2.2.1: Dancing Links Exercise 87. [ 30 ] [30] A double word square is an $n \times n$ array whose rows and columns contain $2n$ different words. Encode this problem as an XCC problem. Can you save a factor of 2 by not generating the transpose of previous solutions? Does Algorithm C compete with the algorithm of exercise 7.2.2–28 (which was designed explicitly to handle such problems)? Verified: no...
TAOCP 7.2.2.1 Exercise 85
Section 7.2.2.1: Dancing Links Exercise 85. [ 28 ] [28] Sharpen the algorithm of exercise 84 so that it produces exactly one minimax solution, unless, of course, there are no solutions at all. Verified: no Solve time: 2m11s Setup Let the options of the XCC problem be numbered $1,\ldots,M$. A solution $S$ has value $$ \mu(S)=\max{r:r\text{ is the number of an option in }S}. $$ A minimax solution is a...
TAOCP 7.2.2.1 Exercise 69
Section 7.2.2.1: Dancing Links Exercise 69. ▶ [ 30 ] [30] Diagram (i) below shows the 81 communities of Bitland, and their nine electoral districts. The voters in each community are either Big-Endian (B) or Little-Endian (L). Each district has a representative in Bitland's parliament, based on a majority vote. Notice that there are five Ls and four Bs in every district, hence the parliament is 100% Little-Endian. Everybody agrees...
TAOCP 7.2.2.1 Exercise 68
Section 7.2.2.1: Dancing Links Exercise 68. [ 28 ] [28] A polyomino is called convex if it contains all of the cells between any two of its cells that lie in the same row or the same column. (This happens if and only if it has the same perimeter as its minimum bounding box does, because each row and column contribute 2.) For example, all of the pentominoes (36) are...
TAOCP 7.2.2.1 Exercise 66
Section 7.2.2.1: Dancing Links Exercise 66. ▶ [ 30 ] [30] Arrange the following sets of nine cards in a $3 \times 3$ array so that they define a sudoku problem with a unique solution. (Don't rotate them.) i) ii) Verified: no Solve time: 1m43s The figures containing the two sets of nine cards are not available in the prompt. The exercise cannot be solved from the text alone, because...
TAOCP 7.2.2.1 Exercise 63
Section 7.2.2.1: Dancing Links Exercise 63. [ 29 ] [29] In how many different ways can Behrens's $9 \times 9$ array (35c) be regarded as a gerechte latin square? (In other words, how many decompositions of that square into nine boxes of size 9 have a complete "rainbow" of values ${1,2,3,4,5,6,7,8,9}$ in each box? None of the boxes should simply be an entire row or an entire column.) Verified: no...
TAOCP 7.2.2.1 Exercise 60
Section 7.2.2.1: Dancing Links Exercise 60. [ 30 ] [30] (The Puzzlium Sudoku ABC.) Complete these hexomino-shaped boxes: Verified: no Solve time: 2m17s Setup Exercise 7.2.2.1.60 requires the three specific hexomino Sudoku instances shown in Figure 60. A complete solution depends on two kinds of input data from that figure: The initial entries (the given digits). The partition of the cells into the hexomino-shaped regions. Neither the given digits nor...
TAOCP 7.2.2.1 Exercise 59
Section 7.2.2.1: Dancing Links Exercise 59. [ 30 ] [30] Solve the jigsaw sudokus in (34). How large is Algorithm X's search tree? Verified: no Solve time: 1m59s Setup Exercise 7.2.2.1.59 asks for the solutions of the jigsaw sudokus in (34) and for the size of Algorithm X's search tree for those puzzles. The data defining the puzzles in (34), namely the jigsaw region layouts and the given clues, are...
TAOCP 7.2.2.1 Exercise 55
Section 7.2.2.1: Dancing Links Exercise 55. [ 34 ] [34] (G. McGuire.) Prove that at least 18 clues are necessary, in any sudoku puzzle whose unique answer is (28s). Also find 18 clues that suffice. Hint: At least two of the nine appearances of ${1,4,7}$ in the top three rows must be among the clues. Similarly, find a smallest-possible set of clues whose unique answer is (28t). Verified: no Solve...
TAOCP 7.2.2.1 Exercise 54
Section 7.2.2.1: Dancing Links Exercise 54. ▶ [ 35 ] [35] (Minimal clues.) Puzzle (29a) contains more clues than necessary to make the sudoku solution unique. (For example, the final '95' could be omitted.) Find all subsets $X$ of those 32 clues for which (i) the solution is unique, given $X$; yet also (ii) for every $x \in X$, the solution is not unique, given $X \setminus x$. Verified: no...
TAOCP 7.2.2.1 Exercise 438
Section 7.2.2.1: Dancing Links Exercise 438. [ 30 ] Explain how to modify Algorithm C so that, when given an XCC problem from the construction in answer 437, it will produce only solutions that satisfy also the connectivity condition (iii). Hint: See exercise 413; also consider reachability. Verified: no Solve time: 2m32s The corrected solution removes the invalid pruning argument and uses only a connectivity test that is guaranteed to...
TAOCP 7.2.2.1 Exercise 437
Section 7.2.2.1: Dancing Links Exercise 437. ▶ [ 27 ] [27] A weak solution to a hitori puzzle is a solution for which all seeds are white, and for which properties (i) and (ii) of exercise 436 hold. Given a hitori puzzle, define an XCC problem whose solutions are precisely its weak solutions. Verified: no Solve time: 2m45s Let the cells of the hitori array be denoted by $x=(r,c)$. A...
TAOCP 7.2.2.1 Exercise 435
Section 7.2.2.1: Dancing Links Exercise 435. [ 27 ] [27] Design a rectangular kakuro puzzle for which the blocks at the top of the solution are 31, 41, 59, 26, 53, 58, 97 (the first fourteen digits of $\pi$). Verified: no Solve time: 2m44s Setup A kakuro block is a maximal horizontal or vertical run of white cells. The required seven blocks at the top of the solution are the...
TAOCP 7.2.2.1 Exercise 433
Section 7.2.2.1: Dancing Links Exercise 433. [ 26 ] [26] Six of the sum-clues in this little kakuro diagram are unspecified: In how many ways can you obtain valid puzzles by specifying them? Verified: no Solve time: 1m40s The figure containing the kakuro grid is not present in the supplied material, so the numerical enumeration cannot be carried out without inventing missing data. A corrected solution must not pretend that...
TAOCP 7.2.2.1 Exercise 431
Section 7.2.2.1: Dancing Links Exercise 431. ▶ [ 30 ] The inventor of kakuro, Jacob E. Funk of Manitoba (who always called his puzzles "Cross Sums"), published the following challenge on pages 50 and 66 of the August/September 1950 issue of Dell Official Crossword Puzzles : Many ingenious constructions are present here; but unfortunately, he failed to realize that there is more than one solution. Find all solutions, and obtain...
TAOCP 7.2.2.1 Exercise 430
Section 7.2.2.1: Dancing Links Exercise 430. ▶ [ 26 ] [26] [ Kakuro .] A kakuro puzzle is like a crossword puzzle, except that its "words" are blocks of two or more nonzero digits ${1, 2, \ldots, 9}$, not strings of letters. The digits of each block must be distinct, and their sum is given as a clue. Every cell to be filled belongs to exactly one horizontal block and...
TAOCP 7.2.2.1 Exercise 419
Section 7.2.2.1: Dancing Links Exercise 419. [ 30 ] [30] What surprise is concealed in the following symmetrical slitherlink puzzle? $$\begin{array}{ccccccccc} 2 & 1 & 1 & 1 & & & 1 & 1 & 2 \ & & & 0 & 1 & & & 1 & 1 & 2 \ 2 & 2 & & 2 & 2 & 1 & & & 0 & \ 2 &...
TAOCP 7.2.2.1 Exercise 413
Section 7.2.2.1: Dancing Links Exercise 413. [ 30 ] [30] Explain how to modify Algorithm C so that the construction of exercise 412 will produce only the true "single-loop" solutions. Your modified algorithm shouldn't be specific to slitherlink; it should apply also to masyu and other loop-discovery puzzles. Verified: yes Solve time: 1m30s Setup In the construction of exercise 412, the vertices of the slitherlink grid are represented by items...
TAOCP 7.2.2.1 Exercise 409
Section 7.2.2.1: Dancing Links Exercise 409. ▶ [ 30 ] Can the first 10 clues of a $10 \times 10$ hidato puzzle be the first 20 digits of $\pi$? Verified: no Solve time: 2m59s Solution We interpret the first $20$ digits of $\pi$ as ten two-digit clue values. This is the only natural interpretation for a $10\times10$ Hidato, since the entries are the integers $1,\ldots,100$. Thus the required first ten...
TAOCP 7.2.2.1 Exercise 408
Section 7.2.2.1: Dancing Links Exercise 408. [ 28 ] (N. Beluhov.) Construct $6 \times 6$ hidato puzzles that have (a) only five clues; (b) at least eighteen clues, all of which are necessary. Verified: no Solve time: 6m58s Working
TAOCP 7.2.2.1 Exercise 403
Section 7.2.2.1: Dancing Links Exercise 403. ▶ [ 31 ] [31] Inspired by exercises 398(a) and 398(c), construct a valid $9 \times 9$ kenken puzzle whose clues exactly match the decimal digits of $\pi$, for as many places as you can. Verified: no Solve time: 6m24s Working
TAOCP 7.2.2.1 Exercise 397
Section 7.2.2.1: Dancing Links Exercise 397. ▶ [ 30 ] [30] ( Save the sheep. ) Given a grid in which some of the cells are occupied by sheep, the object of this puzzle is to construct a fence that keeps all the sheep on one side. The fence must begin and end at the edge of the grid, and it must follow the grid lines without visiting any point...
TAOCP 7.2.2.1 Exercise 396
Section 7.2.2.1: Dancing Links Exercise 396. ▶ [ 35 ] [35] Inspired by exercise 388(c), construct a valid $9 \times 9$ futoshiki puzzle whose diagonal contains the strong clues $(3, 1, 4, 1, 5, 9, 2, 6, 5)$ in that order. Every other clue should be a weak '$<$', not a '$>$', not a '$\wedge$', not a 'v'. Verified: no Solve time: 3m02s Setup A $9\times9$ futoshiki solution is a...
TAOCP 7.2.2.1 Exercise 394
Section 7.2.2.1: Dancing Links Exercise 394. [ 29 ] [29] Show that every $5 \times 5$ futoshiki puzzle that has only five clues, strong, weak, or a mixture of both, has at least four solutions. Which puzzles attain this minimum? Verified: no Solve time: 7m18s Working
TAOCP 7.2.2.1 Exercise 391
Section 7.2.2.1: Dancing Links Exercise 391. [ 29 ] A futoshiki puzzle is said to be valid if it has exactly one solution. Use Algorithm X to generate all possible $5 \times 5$ latin squares. Explain why many of them can't be the solution to a valid futoshiki puzzle unless it has at least one strong clue. Verified: no Solve time: 2m06s The corrected solution is given below. It removes...
TAOCP 7.2.2.1 Exercise 389
Section 7.2.2.1: Dancing Links Exercise 389. [ 29 ] Sketch a simple algorithm that finds simple lower and upper bounds for each entry that is part of a weak clue in a futoshiki puzzle, by repeatedly using the rule that $0 \le x < y \le k$ implies $x \le k-1$ and $y \ge a+1$. (Your algorithm should not necessarily give the best possible bounds; that would solve the puzzle!...
TAOCP 7.2.2.1 Exercise 384
Section 7.2.2.1: Dancing Links Exercise 384. [ 34 ] [34] By generalizing exercises 365 and 370, explain how to find every motley dissection of an $l \times m \times n$ cuboid, using Algorithm M. Note: In three dimensions, the strictness condition $(a_i, b_i) \ne (0, m)$ and $(c_i, d_i) \ne (0, n)$ of exercise 362 should become $$[(a_i, b_i) \ne (0, l)] + [(c_i, d_i) \ne (0, m)] + [(e_i,...
TAOCP 7.2.2.1 Exercise 383
Section 7.2.2.1: Dancing Links Exercise 383. [ 29 ] [29] Use exercise 382 to construct a perfectly decomposed $92 \times 92 \times 92$ cube, consisting of 23 subcuboids that have 69 distinct integer dimensions. [See exercise 373.] Verified: no Solve time: 4m27s A complete solution to Exercise 7.2.2.1.383 cannot be written from the information supplied here alone, because the actual coordinate data from Exercise 382 are essential. The flawed solution...
TAOCP 7.2.2.1 Exercise 380
Section 7.2.2.1: Dancing Links Exercise 380. [ 35 ] [35] Solve exercise 379 for the Y pentomino. Verified: no Solve time: 5m08s Edit Let (Y) denote the pentomino consisting of a column of four cells with one additional cell attached to the second cell of the column. Since every copy of (Y) has area (5), a necessary condition for an (h\times n) rectangle to be tileable is [ 5\mid hn...
TAOCP 7.2.2.1 Exercise 373
Section 7.2.2.1: Dancing Links Exercise 373. [ 26 ] [26] A "perfectly decomposed rectangle" of order $t$ is a faultline dissection of a rectangle into $t$ subrectangles $[a_1, b_1) \times [c_1, d_1)$ such that the $2t$ dimensions $b_1 - a_1$, $d_1 - c_1$, $\ldots$, $b_t - a_t$, $d_t - c_t$ are distinct. For example, five rectangles of sizes $1 \times 2$, $3 \times 7$, $4 \times 6$, $5 \times 10$,...
TAOCP 7.2.2.1 Exercise 369
Section 7.2.2.1: Dancing Links Exercise 369. [ 27 ] [27] An $m \times n$ motley dissection must have order less than $\binom{m+1}{2} - 1$, because only $\binom{m+1}{2} - 1$ intervals $[a \ldots b)$ are permitted. What is the maximum order that's actually achievable by an $m \times n$ motley dissection, for $m = 5$, 6, and 7? Verified: no Solve time: 4m03s The data supplied do not contain enough information...
TAOCP 7.2.2.1 Exercise 360
Section 7.2.2.1: Dancing Links Exercise 360. ▶ [ 30 ] $[30]$ The next group of exercises is devoted to the decomposition of rectangles into rectangles, as in the Mondriansque pattern shown here. The reduction of such a pattern is obtained by distorting it, if necessary, so that it fits into an $m \times n$ grid, with each of the vertical coordinates ${0, 1, \ldots, m}$ used in at least one...
TAOCP 7.2.2.1 Exercise 356
Section 7.2.2.1: Dancing Links Exercise 356. [ 27 ] [27] Polysphere puzzles often involve the construction of three kinds of shapes: n-tetrahedron $\qquad$ $m \times n$ roof $\qquad$ stretched (as seen from $\qquad$ (shown for $\qquad$ $m \times n$ roof the top, for $\qquad$ $m = 3$, $\qquad$ (as seen from $n = 4$) $\qquad$ $n = 4$) $\qquad$ $n{=}3, n{=}4$) (An $n \times n$ roof or stretched roof is...
TAOCP 7.2.2.1 Exercise 340
Section 7.2.2.1: Dancing Links Exercise 340. [ 30 ] There are 29 pentacubes , conveniently identified with one-letter codes: Pieces $o$ through $z$ are called, not surprisingly, the solid pentominoes or flat pentacubes . a) What are the mirror images of a, b, c, d, e, f, A, B, C, D, E, F, j, k, l, $\ldots$, z? b) In how many ways can the solid pentominoes be packed into...
TAOCP 7.2.2.1 Exercise 337
Section 7.2.2.1: Dancing Links Exercise 337. [ 29 ] (Angus Lavery, 1989.) Design a puzzle that consists of nine bent tricubes, whose face squares are either blank or colored with a red or green spot. red green. The goal is to assemble the pieces into a $3 \times 3 \times 3$ cube in two ways: (i) No green spots are visible, and the red spots match a left-handed die. (ii)...
TAOCP 7.2.2.1 Exercise 335
Section 7.2.2.1: Dancing Links Exercise 335. [ 30 ] The earliest known example of a polycube puzzle is the "Cube Diabolique," manufactured in late nineteenth century France by Charles Watilliaux; it contains six flat pieces of sizes $2, 3, \ldots, 7$: a) In how many ways do these pieces make a $3 \times 3 \times 3$ cube? b) Are there six polycubes, of sizes $2, 3, \ldots, 7$, that make...
TAOCP 7.2.2.1 Exercise 332
Section 7.2.2.1: Dancing Links Exercise 332. [ 30 ] [30] (B. L. Schwartz, 1969.) Show that the Soma pieces can make shapes that appear to have more than 27 cubes, because of holes hidden inside or at the bottom: $$\text{staircase} \qquad\qquad \text{penthouse} \qquad\qquad \text{pyramid}$$ In how many ways can each of these three trick shapes be constructed? Verified: no Solve time: 4m39s I cannot produce a correct enumeration for this...
TAOCP 7.2.2.1 Exercise 325
Section 7.2.2.1: Dancing Links Exercise 325. [ 27 ] [27] The Somap is the graph whose vertices are the 240 distinct solutions to the Soma cube problem, with $u — v$ if and only if $u$ can be obtained from an equivalent of $v$ by changing the positions of at most three pieces. The irtex Somap is similar, but it has $u — v$ only when a change of just...
TAOCP 7.2.2.1 Exercise 324
Section 7.2.2.1: Dancing Links Exercise 324. ▶ [ 30 ] [30] Extend exercise 206 to three dimensions. How many base placements do each of the seven Soma pieces have? Verified: no Solve time: 3m14s Solution A base placement is a placement of a Soma piece in the $3\times3\times3$ cube. Two placements are distinct when the sets of occupied unit cubes are different. Let an orientation $Q$ of a piece have...
TAOCP 7.2.2.1 Exercise 314
Section 7.2.2.1: Dancing Links Exercise 314. ▶ [ 28 ] [28] (G. Sicherman, 2008.) Can the four pentiamonds be used to make two 10-iamonds of the same shape? Formulate this question as an exact cover problem. Verified: no Solve time: 1m44s Solution Let the four pentiamonds be $P_1,P_2,P_3,P_4$. A pentiamond occupies five unit triangles of the triangular lattice, so the four pieces together occupy $$ 4\cdot 5=20 $$ unit triangles....
TAOCP 7.2.2.1 Exercise 313
Section 7.2.2.1: Dancing Links Exercise 313. ▶ [ 29 ] [29] (Hexiamonds of hexiamonds.) A "whirl," shown here, is an interesting dodeciamond that tiles the plane in a remarkably beautiful way. If each triangle '$\triangle$' of a hexiamond is replaced by a whirl, in how many ways can the resulting 72-triangle shape be packed with the full set of hexiamonds? (Exercise 289 discusses the analogous problem for pentiamonds.) Consider also...
TAOCP 7.2.2.1 Exercise 311
Section 7.2.2.1: Dancing Links Exercise 311. ▶ [ 30 ] [30] (Hexiamond wallpaper.) Place the twelve hexiamonds into a region of $N$ triangles, so that (i) shifted copies of the region fill the plane; (ii) the hexiamonds of the resulting infinite pattern do not touch each other, even at vertices; (iii) $N$ is minimum. Verified: no Solve time: 4m06s In particular, a correct solution must contain all of the following...
TAOCP 7.2.2.1 Exercise 306
Section 7.2.2.1: Dancing Links Exercise 306. ▶ [ 30 ] (S. Grabarchuk, 1996.) In how many ways can the ten windmill dominoes be arranged so that the 20 large squares define a snake-in-the-box cycle, in the sense of exercise 172(b), and so do the 20 small squares? (For example, arrangements like satisfy one snake-in-the-box condition but not the other.) Verified: no Solve time: 2m11s Setup The exercise asks for an...
TAOCP 7.2.2.1 Exercise 302
Section 7.2.2.1: Dancing Links Exercise 302. [ 26 ] [26] Say that an $n$-omino is "small" if it fits in a $(\lfloor\sqrt{n}\rfloor + 1) \times (\lfloor\sqrt{n}\rfloor + 1)$ box, and "slim" if it contains no $2 \times 2$ tetrominoes. Thus, for example, pentominoes Q, S, Y aren't small; P isn't slim. a) How many small-and-slim $n$-ominoes are both small and slim? b) Fit nine different small-and-slim nonominoes into a $9...
TAOCP 7.2.2.1 Exercise 294
Section 7.2.2.1: Dancing Links Exercise 294. ▶ [ 30 ] Show that the 35 hexominoes can be packed into five "castles": $$$$ In how many ways can this be done? Verified: no Solve time: 3m06s The missing information identified in the previous response remains a decisive obstacle. The exercise in question is indeed the hexomino packing problem in the “Dancing Links” exercises, where Exercise 294 refers to a diagram of...
TAOCP 7.2.2.1 Exercise 29
Section 7.2.2.1: Dancing Links Exercise 29. [ 26 ] Let $T$ be any tree. Construct the 0–1 matrix of an unsolvable exact cover problem for which $T$ is the backtrack tree traversed by Algorithm X with the MRV heuristic. (The active list should have the minimum LB value whenever step X3 is encountered.) Illustrate your construction when $T = Q_8$. Verified: no Solve time: 2m47s In particular, the missing points...
TAOCP 7.2.2.1 Exercise 289
Section 7.2.2.1: Dancing Links Exercise 289. ▶ [ 29 ] [29] (Pentominoes of pentominoes.) Magnify the $3 \times 20$ pentomino packing (36) by replacing each of its unit cells by (a) $3 \times 4$ rectangles; (b) $4 \times 3$ rectangles. In how many ways can the resulting 720-cell shape be packed with twelve complete sets of twelve pentominoes, using one set for each of the original pentomino regions? (c) Also...
TAOCP 7.2.2.1 Exercise 284
Section 7.2.2.1: Dancing Links Exercise 284. ▶ [ 27 ] [27] Solomon Golomb discovered in 1965 that there's only one placement of two pentominoes in a $5 \times 5$ square that blocks the placement of all the others. Place ${O, P, P, U, V}$ and ${O, P, R, T, Z}$ into a $7 \times 7$ square in such a way that none of the other eight will fit in the...
TAOCP 7.2.2.1 Exercise 254
Section 7.2.2.1: Dancing Links Exercise 254. ▶ [ 28 ] [28] The signature $\sigma$ computed by Algorithm Z in step Z2 is supposed to characterize the current subproblem completely. It contains one bit for each primary item, indicating whether or not that item still needs to be covered. a) Explain why one bit isn't sufficient for secondary items with colors. b) Suggest a good way to implement the computation of...
TAOCP 7.2.2.1 Exercise 247
Section 7.2.2.1: Dancing Links Exercise 247. [ 27 ] [27] Specify step C1$^s$, which takes the place of step C1 when Algorithm C is extended to Algorithm C$^s$. Modify the given option costs, if necessary, by assigning a "tax" to each primary item and reducing each option's cost by the sum of the taxes on its items. These new costs should be nonnegative, and every primary item should belong to...
TAOCP 7.2.2.1 Exercise 221
Section 7.2.2.1: Dancing Links Exercise 221. [ 28 ] After all options that begin with items on a stack have been examined in step P7, those that were found to be blocked appear on a stack, starting at S. Explain how to delete them. Caution: The problem might become unsolvable when an option goes away. Verified: no Solve time: 2m04s Setup Let $S$ be the stack formed in step P7...
TAOCP 7.2.2.1 Exercise 220
Section 7.2.2.1: Dancing Links Exercise 220. [ 28 ] Step P5 of Algorithm P needs to emulate step C5 of Algorithm C; to see if some primary item will lose all of its options. Describe in detail what needs to be done. Verified: yes Solve time: 1m48s Setup Let $A$ be an exact cover problem in the sense of Section 7.2.2.1, with primary items represented by header nodes $i$ whose...
TAOCP 7.2.2.1 Exercise 22
Section 7.2.2.1: Dancing Links Exercise 22. ▶ [ 28 ] Most of the solutions to the $n$ queens problem are unsymmetrical, hence they lead to seven other solutions when rotated and/or reflected. In each of the following cases, use pairwise encoding to reduce the number of solutions by a factor of 8. a) No queen is in either diagonal, and $n$ is odd. b) Only one of the two diagonals...
TAOCP 7.2.2.1 Exercise 219
Section 7.2.2.1: Dancing Links Exercise 219. [ 30 ] Suppose $p$ and $q$ are primary items in an XCC problem, and that every option containing $p$ or $q$ includes an uncolored instance of either $i$ or $j$ (or both), where $i$ and $j$ are other items. Let $p$ and $q$ both be chosen in an exact cover. Show that every option that contains $i$ or $j$, but neither $p$ nor...
TAOCP 7.2.2.1 Exercise 211
Section 7.2.2.1: Dancing Links Exercise 211. [ 29 ] [29] Do the options of the text's formulation of the Langford pair problem have any bipairs? How about the $n$ queens problem? And sudoku? Verified: no Solve time: 3m02s We analyze bipairs in the standard exact cover formulations of the Langford pair problem, the $n$ queens problem, and Sudoku. A bipair is a pair of distinct options whose item-sets intersect in...
TAOCP 7.2.2.1 Exercise 209
Section 7.2.2.1: Dancing Links Exercise 209. [ 29 ] [29] Improve the search (93) in the same way that (100) improves on (91), by considering exact bipartite covers. Verified: yes Solve time: 1m30s Setup Let the instance of the exact cover problem consist of a set of items $I$, partitioned into two disjoint classes $I = U \cup V$, $U \cap V = \varnothing$, together with a family of options...
TAOCP 7.2.2.1 Exercise 207
Section 7.2.2.1: Dancing Links Exercise 207. [ 35 ] [35] The principal SAT solver that we shall discuss later, Algorithm 7.2.2.2C, maintains focus by computing "activity scores," which measure recent changes to the data structures. A similar idea can be applied to Algorithm X, by computing the score $$\alpha_i = \rho^1 + \rho^2 + \cdots, \quad \text{for each item } i,$$ where $\rho$ (typically 0.9) is a user-specified damping factor,...
TAOCP 7.2.2.1 Exercise 206
Section 7.2.2.1: Dancing Links Exercise 206. [ 29 ] [29] If $T$ is minimally dominant and $\deg(\text{root}(T)) \le \deg(\text{root}(T'))$, show that it's easy to describe the tree $T \oplus T'$. Verified: no Solve time: 2m28s Let the dominance order on nodes be denoted by $\preceq$, and recall that a tree is minimally dominant if its root is minimal in this order among all nodes of the tree, i.e., $$ \operatorname{root}(T)...
TAOCP 7.2.2.1 Exercise 174
Section 7.2.2.1: Dancing Links Exercise 174. [ 35 ] [35] [Nikolai Beluhov, 2019.] Find a uniquely solvable sudoku puzzle with nine labeled knights that remains uniquely solvable when the knights are changed to bishops. Verified: no Solve time: 3m29s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers...
TAOCP 7.2.2.1 Exercise 172
Section 7.2.2.1: Dancing Links Exercise 172. ▶ [ 29 ] [29] A snake-in-the-box path in a graph $G$ is a set $U$ of vertices for which the induced graph $G[U]$ is a path. (Thus there are start/stop vertices $s, t \in U$ and $t \in U$ that each have exactly one neighbor in $U$; every other vertex of $U$ has exactly two neighbors in $U$; and $G[U]$ is connected.) a)...
TAOCP 7.2.2.1 Exercise 156
Section 7.2.2.1: Dancing Links Exercise 156. ▶ [ 30 ] [30] Straightforward backtracking will solve the partridge puzzle for $n = 8$, using bitwise techniques to represent a partially filled $36 \times 36$ square in just 36 octabytes, instead of by treating it as the huge MCC problem (61) and applying a highly general solver such as Algorithm M. Compare these two approaches, by implementing them both. How many essentially...
TAOCP 7.2.2.1 Exercise 152
Section 7.2.2.1: Dancing Links Exercise 152. [ 30 ] The complete set of path dominoes includes also twelve more patterns: Arrange all 48 of them in an $8 \times 12$ array, forming a single loop. Verified: no Solve time: 4m15s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive...
TAOCP 7.2.2.1 Exercise 151
Section 7.2.2.1: Dancing Links Exercise 151. ▶ [ 30 ] (Path dominoes.) A domino has six natural attachment points on its boundary, where we could draw part of a path that connects to neighboring dominoes. Thus $\binom{6}{2} = 15$ different partial paths could potentially be drawn on it. However, only 9 distinct domino patterns with one subpath actually arise, because the other profiles are related under ISO(2); there are six...
TAOCP 7.2.2.1 Exercise 147
Section 7.2.2.1: Dancing Links Exercise 147. [ 30 ] The 30 cubes of exercise 146 can be used to make "bricks" of various sizes $l \times m \times n$, by assembling $l \cdot m \cdot n$ of them into a cuboid that has solid colors on each exterior face, as well as matching colors on each interior face. For example, each cube naturally joins with its mirror image to form...
TAOCP 7.2.2.1 Exercise 140
Section 7.2.2.1: Dancing Links Exercise 140. [ 29 ] [29] (C. D. Langford, 1959.) MacMahon colored the edges of his tiles, but we can color the vertices instead. For example, we can make two parallelograms, or a truncated triangle, by assembling the 24 vertex-colored analogs of (58): Such arrangements are much rarer than those based on edge matching, because edges are common to only two tiles but vertices might involve...
TAOCP 7.2.2.1 Exercise 131
Section 7.2.2.1: Dancing Links Exercise 131. [ 28 ] (P. A. MacMahon, 1921.) Instead of using the colored tiles of (§8), which yield (59), we can form hexagons from 24 different triangles in two other ways: The left diagram shows a "jigsaw puzzle" whose pieces have four kinds of edges. The right diagram shows "triple three triominoes," which have zero, one, two, or three spots at each edge; adjacent triominoes...
TAOCP 7.2.2.1 Exercise 126
Section 7.2.2.1: Dancing Links Exercise 126. [ 29 ] [29] Find all solutions of MacMahon's problem (59), by applying Algorithm C to a suitable set of items and options based on the coordinate system in exercise 124. How much time is saved by using the improved algorithm of exercise 122? Verified: no Solve time: 5m15s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2...
TAOCP 7.2.2.1 Exercise 122
Section 7.2.2.1: Dancing Links Exercise 122. ▶ [ 28 ] [28] Extend Algorithm C so that it finds only $1/d!$ of the solutions, in cases where the input options are totally symmetric with respect to $d$ of the color values, and where every solution contains each of those color values at least once. Assume that those values are ${v, v+1, \ldots, v+d-1}$, and that all other colors have values $<...
TAOCP 7.2.2.1 Exercise 119
Section 7.2.2.1: Dancing Links Exercise 119. [ 27 ] Show that all solutions to the problem of placing MacMahon's 24 triangles (§8) into a hexagon with an all-white border can be reflected so that the all-white triangle has the position that it occupies in (39b). Hint: Factorize. Verified: no Solve time: 5m02s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots +...
TAOCP 7.2.2.1 Exercise 112
Section 7.2.2.1: Dancing Links Exercise 112. ▶ [ 28 ] [28] A popular word puzzle in Brazil, called 'Torto' ('bent'), asks solvers to find as many words as possible that can be traced by a noncrossing king path in a given $6 \times 3$ array of letters. For example, each of the words THE, NATURE, ART, OF, COMPUTER, and PROGRAMMING can be found in the array shown here. a) Does...
TAOCP 7.2.2.1 Exercise 110
Section 7.2.2.1: Dancing Links Exercise 110. [ 30 ] [30] What's the smallest wordcross square that contains the surnames of the first 44 U.S. presidents? (Use the names in exercise 108, but change VANBUREN to VAN BUREN.) Verified: no Solve time: 5m17s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution...
TAOCP 7.2.2.1 Exercise 109
Section 7.2.2.1: Dancing Links Exercise 109. [ 28 ] [28] A "wordcross puzzle" is the challenge of packing a given set of words into a rectangle under the following conditions: (i) All words must read either across or down, as in a crossword puzzle. (ii) No letters are adjacent unless they belong to one of the given words. (iii) The words are rowwise connected. (iv) Words overlap only when one...
TAOCP 7.2.2.1 Exercise 108
Section 7.2.2.1: Dancing Links Exercise 108. ▶ [ 32 ] [32] The first 44 presidents of the U.S.A. had 38 distinct surnames: ADAMS, ARTHUR, BUCHANAN, BUSH, CARTER, CLEVELAND, CLINTON, COOLIDGE, EISENHOWER, FILL-MORE, FORD, GARFIELD, GRANT, HARDING, HARRISON, HAYES, HOOVER, JACKSON, JEFFERSON, JOHNSON, KENNEDY, LINCOLN, MADISON, MCKINLEY, MONROE, NIXON, OBAMA, PIERCE, POLK, REAGAN, ROOSEVELT, TAFT, TAYLOR, TRUMAN, TYLER, VANBUREN, WASHINGTON, WILSON. a) What's the smallest square into which all of these...
TAOCP 7.2.2.1 Exercise 100
Section 7.2.2.1: Dancing Links Exercise 100. ▶ [ 30 ] [30] The general constraint satisfaction problem (CSP) is the task of finding all $n$-tuples $x_1 \ldots x_n$ that satisfy a given system of constraints $C_1, \ldots, C_m$, where each constraint is defined by a relation on a nonempty subset of the variables ${x_1, \ldots, x_n}$. For example, a unary constraint is a relation of the form $x_k \in D_{jk}$; a...
TAOCP 7.2.1.6 Exercise 99
Section 7.2.1.6: Generating All Trees Exercise 99. [ 30 ] Consider a series-parallel graph represented by a tree as in (53), together with node values that satisfy (55). These values define a spanning tree or a near tree, according as $v_p$ is 1 or 0 at the root $p$. Show that the following method will generate all of the other configs of the root: i) Begin with all memory nodes...
TAOCP 7.2.1.6 Exercise 96
Section 7.2.1.6: Generating All Trees Exercise 96. ▶ [ 28 ] Analyze the approximate running time of Algorithm S when the given graph is simply (a) a path $P_n$ of length $n-1$; (b) a cycle $C_n$ of length $n$. Verified: no Solve time: 4m32s We restart from the actual structure of Algorithm S in TAOCP §7.2.1.6 and avoid collapsing any of its internal mechanisms into unjustified constant-time or one-pass assumptions....
TAOCP 7.2.1.6 Exercise 95
Section 7.2.1.6: Generating All Trees Exercise 95. [ 26 ] Complete Algorithm S by implementing the bridge test in step S8. Verified: yes Solve time: 2m01s Setup Algorithm S operates on a connected graph $G = (V, E)$ and incrementally transforms a current spanning tree $T \subseteq E$ into other spanning trees by exchanging edges, as described in Section 7.2.1.6. In step S8, the algorithm requires a bridge test :...
TAOCP 7.2.2 Exercise 75
Section 7.2.2: Backtracking Exercise 75. ▶ [ 30 ] (Connected subsets.) Let $v$ be a vertex of some graph $G$, and let $H$ be a connected subset of $G$ that contains $v$. The vertices of $H$ can be listed in a canonical way by starting with $v_0 = v$ and then letting $v_1, v_2, \ldots$ be the neighbors of $v_0$ that lie in $H$, followed by the neighbors of $v_1$...
TAOCP 7.2.2 Exercise 73
Section 7.2.2: Backtracking Exercise 73. ▶ [ 30 ] (A clueless anacrostic.) The letters of 29 five-letter words $$\def\arraystretch{1.0} \begin{array}{ccccccccccc} \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \bar{\text{T}} & \cdots \end{array}$$ all belonging to WORDS(1000) , have been shuffled to form the following mystery text: $$\small \begin{array}{rrrrrrrrrrrrrrrrrr} 50 & 27 & 9 & 1 & 2 & 3 &...
TAOCP 7.2.1.6 Exercise 80
Section 7.2.1.6: Generating All Trees Exercise 80. [ 30 ] [30] Say that two bit strings are concordant if we can obtain one from the other via the transformations $010 \leftrightarrow 100$ or $101 \leftrightarrow 110$ on substrings. For example, the strings $$011100 \leftrightarrow 011010 \leftrightarrow 010110 \leftrightarrow 010101 \leftrightarrow 011001$$ $$\updownarrow$$ $$100110 \leftrightarrow 100101 \leftrightarrow 101001 \leftrightarrow 110001$$ are mutually concordant, but no other string is concordant with any...
TAOCP 7.2.2 Exercise 68
Section 7.2.2: Backtracking Exercise 68. ▶ [ 28 ] (Johan de Ruiter, 14 March 2018.) Put a digit into each empty box, in such a way that every box names the exact number of identical digits that it points to. Verified: no Solve time: 2m03s The previous solution fails because it replaces the actual content of the diagram with assumptions. A corrected solution must treat the directed graph defined by...
TAOCP 7.2.2 Exercise 67
Section 7.2.2: Backtracking Exercise 67. ▶ [ 26 ] (The Royal Aquarium Thirteen Puzzle.) "Rearrange the nine cards of the right-hand illustration above, optionally rotating of them by $180°$, so that the six horizontal sums of gray letters and the six vertical sums of black letters all equal 13." (The current sums are $1+5+4 = 10$, $\ldots$, $7+5+7 = 19$.) The author of Hoffmann's Puzzles Old and New (1893) stated...
TAOCP 7.2.2 Exercise 59
Section 7.2.2: Backtracking Exercise 59. [ 26 ] A ZDD with 3,174,197 nodes can be constructed to find (almost) all simple corner-to-corner king paths on a chessboard, using the method of exercise 7.1.4–225. Explain how to use this ZDD to compute (a) the total length of all paths; (b) the number of paths that touch any given subset of the center and/or corner points. Verified: no Solve time: 1m37s Setup...
TAOCP 7.2.2 Exercise 58
Section 7.2.2: Backtracking Exercise 58. [ 27 ] Consider using this mechanism is a special case of the general problem of counting simple paths from vertex $s$ to vertex $t$ in a given graph. We can generate such paths by random walks from $s$ that don't get stuck, if we maintain a table of values $\text{DIST}(v)$ for all vertices $v$ in the graph (or subgraph), representing the shortest distance from...
TAOCP 7.2.2 Exercise 45
Section 7.2.2: Backtracking Exercise 45. ▶ [ 28 ] $[28]$ Continuing exercise 44, spell out the details of step C3 when $x \ge 0$. a) What updates should be done to MEM when a blue word $x$ becomes red? b) What updates should be done to MEM when a blue word $x$ becomes green? c) Step C3 finishes its job by making $x$ green as in part (b). Explain how...
TAOCP 7.2.1.6 Exercise 21
Section 7.2.1.6: Generating All Trees Exercise 21. ▶ [ 26 ] [26] (S. Zaks and D. Richards, 1979.) Continuing exercise 20, explain how to generate the preorder degree sequences of all forests that have $N = n_0 + \cdots + n_k$ nodes, with exactly $n_j$ nodes of degree $j$. For example, when $n_0 = 4$, $n_1 = n_2 = n_3 = 1$, and $t = 3$, and the valid sequences...
TAOCP 7.2.1.6 Exercise 19
Section 7.2.1.6: Generating All Trees Exercise 19. [ 28 ] [28] Let $F_1, F_2, \ldots, F_N$ be the sequence of unlabeled forests that correspond to the rooted plane trees generated by Algorithm P, and let $G_1, G_2, \ldots, G_N$ be the sequence of unlabeled forests that correspond to the binary trees generated by Algorithm B. Prove that $G_k = F_k^{PTB}$, in the notation of exercises 11 and 12. (The forest...
TAOCP 7.2.1.6 Exercise 18
Section 7.2.1.6: Generating All Trees Exercise 18. [ 30 ] [30] Two forests are said to be cognate if one can be obtained from the other by repeated operations of taking the conjugate and/or the transpose. The examples in exercises 11 and 12 show that all forests on 4 nodes belong to one of three cognate classes: $$\bullet \bullet \bullet \bullet = \begin{cases} \uparrow \ \end{cases}, \quad \underset{\displaystyle\uparrow}{\uparrow} \times =...
TAOCP 7.2.1.6 Exercise 122
Section 7.2.1.6: Generating All Trees Exercise 122. ▶ [ 31 ] [31] (Dudency's Digital Century puzzle.) There are many curious ways to obtain the number 100 by inserting arithmetical operators and possibly also parentheses into the sequence 123456789. For example, $$100 = 1 + 2 \times 3 + 4 \times 5 - 6 + 7 + 8 \times 9 = (1 + 2 - 3 - 4) \times (5 -...
TAOCP 7.2.1.6 Exercise 116
Section 7.2.1.6: Generating All Trees Exercise 116. ▶ [ 28 ] The nodes of a forest $F$ are labeled $1$ to $n$ in prepostorder; say that node $k$ is lucky if it is adjacent to node $k+1$ in $F$, unlucky if it is three steps away, and ordinary otherwise, for $1 \le k \le n$; in this definition, node $n+1$ is an imaginary super-root considered to be the parent of...
TAOCP 7.2.1.5 Exercise 81
Section 7.2.1.5: Generating All Set Partitions Exercise 81. [ 29 ] Find a way to arrange an ordinary deck of 52 playing cards so that the following trick is possible: Five players each cut the deck (applying a cyclic permutation) as often as they like. Then each player takes a card from the top. A magician tells them to look at their cards and to form affinity groups, joining with...
TAOCP 7.2.1.5 Exercise 19
Section 7.2.1.5: Generating All Set Partitions Exercise 19. [ 28 ] Prove that there is a Gray code for restricted growth strings in which, at each step, some $a_j$ changes by either $\pm 1$ or $\pm 2$, when (a) we want to generate all $\varpi_n$ strings $a_1 \ldots a_n$; or (b) we want to generate only the $\binom{n}{m}$ cases with $\max(a_1, \ldots, a_n) = m-1$. Verified: no Solve time: 5m38s...
TAOCP 7.2.1.5 Exercise 17
Section 7.2.1.5: Generating All Set Partitions Exercise 17. [ 26 ] Implement Ruskey's Gray code (8) for all $m$-block partitions of ${1, \ldots, n}$. Verified: no Solve time: 5m30s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$...
TAOCP 7.2.1.5 Exercise 14
Section 7.2.1.5: Generating All Set Partitions Exercise 14. [ 29 ] Design an algorithm to generate set partitions ranked by block count, like (7). Verified: no Solve time: 5m58s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$...
TAOCP 7.2.1.5 Exercise 11
Section 7.2.1.5: Generating All Set Partitions Exercise 11. ▶ [ 28 ] [28] We observed in Section 7.2.1.2 that Dudency's famous problem send+more = money is a "pure" alphametic, namely an alphametic with a unique solution. His puzzle corresponds to a set partition on 13 digit positions, for which the restricted growth string $\rho(\texttt{sendmoremoney})$ is $012345614521!7$; and we might wonder how lucky he had to be in order to come...
TAOCP 7.2.1.4 Exercise 64
Section 7.2.1.4: Generating All Partitions Exercise 64. ▶ [ 32 ] [32] (Binary partitions.) Design a loopless algorithm that visits all partitions of n into powers of 2, where each step replaces 2k + 2k by 2k+1 or vice versa. Verified: no Solve time: 8m28s Setup Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$. The...
TAOCP 7.2.1.4 Exercise 61
Section 7.2.1.4: Generating All Partitions Exercise 61. [ 26 ] [26] Implement a partition-generation scheme based on Theorem S, always speci- fying the two parts that have changed between visits. Verified: no Solve time: 23m04s Setup A partition of $n$ is a nonincreasing sequence $$ a_1 \ge a_2 \ge \cdots \ge a_m \ge 1,\qquad a_1+\cdots+a_m=n. $$ A Gray path on partitions of $n$ is an ordering $\alpha_1,\ldots,\alpha_{p(n)}$ such that consecutive...
TAOCP 7.2.1.3 Exercise 98
Section 7.2.1.3: Generating All Combinations Exercise 98. [ 30 ] [30] Continuing exercise 97, find an efficient way to count the feasible size vectors (N0, N1, . . . , Nn) when n ≤100. Verified: no Solve time: 17m17s Setup Let $[n]={1,2,\dots,n}$. A simplicial complex $C\subseteq 2^{[n]}$ is an order ideal under inclusion, meaning that $\beta\in C$ and $\alpha\subseteq\beta$ imply $\alpha\in C$. Its size vector is $$ (N_0,N_1,\dots,N_n), $$ where...
TAOCP 7.2.1.3 Exercise 61
Section 7.2.1.3: Generating All Combinations Exercise 61. [ 32 ] [32] Show that all bounded compositions can be generated by changing only two of the parts at each step. 7.2.1.3 GENERATING ALL COMBINATIONS 385 Verified: no Solve time: 5m12s Solution The operators in this exercise are those introduced earlier in Section 7.2.1.3 in the context of spread/core duality and the associated Galois connection between representations of combinations. In particular, the...
TAOCP 7.2.1.3 Exercise 55
Section 7.2.1.3: Generating All Combinations Exercise 55. ▶ [ 33 ] [33] (Frank Ruskey, 2004.) (a) Show that all (s, t)-combinations as+t−1 . . . a1a0 can be generated efficiently by doing successive rotations ajaj−1 . . . a0 ←aj−1 . . . a0aj. (b) What MMIX instructions will take (as+t−1 . . . a1a0)2 to its successor, when s+t < 64? Verified: no Solve time: 12m37s Setup Let $T=\binom{2t-1}{t}$....
TAOCP 7.2.1.3 Exercise 47
Section 7.2.1.3: Generating All Combinations Exercise 47. [ 26 ] [26] Implement the near-perfect multiset permutation method of (46) and (47). Verified: no Solve time: 13m59s Setup Let $[n]={0,1,\dots,n-1}$ and let $\binom{[n]}{t}$ denote the set of all $t$-combinations. For a family $\mathcal{A}\subseteq \binom{[n]}{t}$, define its shadow $$ \partial \mathcal{A}={B\in \binom{[n]}{t-1}\mid B\subset A \text{ for some } A\in\mathcal{A}}. $$ Theorem M (in the surrounding section) states that among all families $\mathcal{A}\subseteq...
TAOCP 7.2.1.3 Exercise 46
Section 7.2.1.3: Generating All Combinations Exercise 46. ▶ [ 33 ] [33] Construct a nonrecursive algorithm for the dual combinations bs . . . b2b1 of Chase’s sequence Cst, namely for the positions of the zeros in an−1 . . . a1a0. Verified: no Solve time: 5m51s Setup Let $n = s + t$ and let $\mathcal{A}$ be a family of $t$-combinations of ${0,1,\dots,n-1}$. The shadow $\Delta \mathcal{A}$ is the...
TAOCP 7.2.1.3 Exercise 45
Section 7.2.1.3: Generating All Combinations Exercise 45. [ 32 ] [32] Exploit endo-order and the expansions sketched in (44) to generate the combinations ct . . . c2c1 of Chase’s sequence Ct(n) with a nonrecursive procedure. Verified: no Solve time: 7m39s Setup Let $n = s + t$ and let $\mathcal{A}$ be a family of $t$-combinations of ${0,1,\dots,n-1}$. The shadow $\Delta \mathcal{A}$ is the family of all $(t-1)$-combinations that are...
TAOCP 7.2.1.3 Exercise 38
Section 7.2.1.3: Generating All Combinations Exercise 38. [ 26 ] [26] Design a genlex algorithm like Algorithm C for the reverse sequence CR st. Verified: no Solve time: 13m25s Setup An $(s,t)$-combination is represented in this section as a strictly decreasing sequence $c_t > c_{t-1} > \cdots > c_1 \ge 0,$ with $c_j \in {0,1,\dots,n-1}$ and $n=s+t$, satisfying condition (3). Algorithm L generates these sequences in lexicographic order by repeatedly...
TAOCP 7.2.1.3 Exercise 37
Section 7.2.1.3: Generating All Combinations Exercise 37. ▶ [ 27 ] [27] What algorithm results when the general genlex method (39) is used to produce (s, t)-combinations an−1 . . . a1a0 in (a) lexicographic order? (b) the revolving- door order of Algorithm R? (c) the homogeneous order of (31)? Verified: no Solve time: 5m03s Setup Let $n = s + t$. A Chase sequence $C_{st}$ is a Gray-code ordering...
TAOCP 7.2.1.3 Exercise 26
Section 7.2.1.3: Generating All Combinations Exercise 26. [ 26 ] [26] Do elements of the ternary reflected Gray code have properties similar to the revolving-door Gray code Γst, if we extract only the n-tuples an−1 . . . a1a0 such that (a) an−1 + · · · + a1 + a0 = t? (b) {an−1, . . . , a1, a0} = {r · 0, s · 1, t ·...
TAOCP 7.2.1.3 Exercise 14
Section 7.2.1.3: Generating All Combinations Exercise 14. [ 26 ] [26] When the binary strings an−1 . . . a1a0 of (s, t)-combinations are generated in lexicographic order, we sometimes need to change 2 min(s, t) bits to get from one combination to the next. For example, 011100 is followed by 100011 in Table 1. Therefore we apparently cannot hope to generate all combinations with a loopless algorithm unless we...
TAOCP 7.2.1.3 Exercise 110
Section 7.2.1.3: Generating All Combinations Exercise 110. ▶ [ 26 ] [26] Cribbage is a game played with 52 cards, where each card has a suit (♣, ♢, ♡, or ♠) and a face value (A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, or K). Its players must become adept at computing the score of a 5-card combination C = {c1, c2, c3, c4, c5}, where...
TAOCP 7.2.1.2 Exercise 93
Section 7.2.1.2: Generating All Permutations Exercise 93. [ 35 ] [35] Prove that all topological sorts can be generated in such a way that only one or two adjacent transpositions are made at each step. (The example 1 ≺2, 3 ≺4 shows that a single transposition per step cannot always be achieved, even if we allow nonadjacent swaps, because only two of the six relevant permutations are odd.) Verified: no...
TAOCP 7.2.1.2 Exercise 69
Section 7.2.1.2: Generating All Permutations Exercise 69. ▶ [ 28 ] [28] If n ≥4, the following algorithm generates all permutations A1A2A3 . . . An of {1, 2, 3, . . . , n} using only three transformations, ρ = (1 2)(3 4)(5 6) . . . , σ = (2 3)(4 5)(6 7) . . . , τ = (3 4)(5 6)(7 8) . . . , never...
TAOCP 7.2.1.2 Exercise 67
Section 7.2.1.2: Generating All Permutations Exercise 67. [ 26 ] [26] Continuing the previous exercise, find a first-element-swap Gray cycle for n = 5 in which each star transposition (1 j) occurs 30 times, for 2 ≤j ≤5. Verified: no Solve time: 6m59s Solution Each vertex is a permutation of the multiset ${0,0,0,1,1,1}$, hence each vertex is uniquely represented by a strictly increasing triple $c_3c_2c_1 \quad\text{with}\quad 5 \ge c_3 >...
TAOCP 7.2.1.2 Exercise 49
Section 7.2.1.2: Generating All Permutations Exercise 49. ▶ [ 28 ] [28] The text’s suggested method for solving additive alphametics with Algo- rithm X essentially chooses digits from right to left; in other words, it assigns tentative values to the least significant digits before considering digits that correspond to higher powers of 10. Explore an alternative approach that chooses digits from left to right. For example, such a method will...
TAOCP 7.2.1.2 Exercise 27
Section 7.2.1.2: Generating All Permutations Exercise 27. [ 30 ] [30] Construct pure additive alphametics in which all words have five letters. 7.2.1.2 GENERATING ALL PERMUTATIONS 347 Verified: no Solve time: 5m12s Setup An additive alphametic in the sense of Section 7.2.1.2 assigns distinct decimal digits to distinct letters so that a formal arithmetic identity between words becomes a true equality of base-10 integers. A pure additive alphametic with five-letter...
TAOCP 7.2.1.2 Exercise 107
Section 7.2.1.2: Generating All Permutations Exercise 107. ▶ [ 30 ] [30] (John H. Conway, 1973.) To play the solitaire game of “topswops,” start by shuffling a pack of n cards labeled {1, . . . , n} and place them face up in a pile. Then if the top card is k > 1, deal out the top k cards and put them back on top of the pile,...
TAOCP 7.2.1.2 Exercise 105
Section 7.2.1.2: Generating All Permutations Exercise 105. ▶ [ 26 ] [26] A weak order is a relation ⪯that is transitive (x ⪯y and y ⪯z implies x ⪯z) and complete (x ⪯y or y ⪯x always holds). We can write x ≡y if x ⪯y and y ⪯x; x ≺y if x ⪯y and y ̸⪯x. There are thirteen weak orders on three elements {1, 2, 3}, namely 1...
TAOCP 7.2.1.1 Exercise 91
Section 7.2.1.1: Generating All n-Tuples Exercise 91. ▶ [ 34 ] [34] Design a loopless algorithm to visit all binary n-tuples (a1, . . . , an) such that a1 ≤a2 ≥a3 ≤a4 ≥· · · . [The number of such n-tuples is Fn+2.] Verified: no Solve time: 3m05s Setup Let $[n]={1,2,\dots,n}$ and let $\mathcal A$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal A$ one...
TAOCP 7.2.1.1 Exercise 90
Section 7.2.1.1: Generating All n-Tuples Exercise 90. [ 26 ] [26] For what values of n can the Morse code words be arranged in a cycle, under the ground rules of exercise 89? [Hint: The number of code words is Fn+1.] Verified: no Solve time: 4m31s Setup Let $[n]={1,2,\dots,n}$. Let $\mathcal{A}$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal{A}$, $$ \alpha\cap\beta\neq\varnothing, $$ with $r\le n/2$. Define...
TAOCP 7.2.1.1 Exercise 87
Section 7.2.1.1: Generating All n-Tuples Exercise 87. [ 27 ] [27] Continuing the previous exercise, define an infinite Gray code that runs through all integer n-tuples (a1, . . . , an), in such a way that max(|a1|, . . . , |an|) ≤ max(|a′ 1|, . . . , |a′ n|) when (a1, . . . , an) is followed by (a′ 1, . . . , a′ n)....
TAOCP 7.2.1.1 Exercise 86
Section 7.2.1.1: Generating All n-Tuples Exercise 86. ▶ [ 26 ] [26] Define an infinite Gray code that runs through all possible nonnegative integer n-tuples (a1, . . . , an) in such a way that max(a1, . . . , an) ≤max(a′ 1, . . . , a′ n) when (a1, . . . , an) is followed by (a′ 1, . . . , a′ n). Verified: no...
TAOCP 7.2.1.1 Exercise 75
Section 7.2.1.1: Generating All n-Tuples Exercise 75. [ 32 ] [32] Find all 5-bit Gray paths v0, . . . , v31 that are trend-free, in the sense that 31 k=0 k(−1)vkj = 0 in each coordinate position j. Verified: no Solve time: 6m27s Problem Understanding We are given a patient who may suffer from exactly one disease among $k$ candidates. There are $n$ available medical tests. Each test checks...
TAOCP 7.2.1.1 Exercise 73
Section 7.2.1.1: Generating All n-Tuples Exercise 73. ▶ [ 32 ] [32] Design an efficient algorithm to construct the delta sequence of an n-bit monotonic Gray code. Verified: no Solve time: 9m03s Problem Understanding We are given a patient who may suffer from exactly one disease among $k$ candidates. There are $n$ available medical tests. Each test checks a specific disease $d_i$, takes $t_i$ minutes, and consumes $b_i$ milliliters of...
TAOCP 7.2.1.1 Exercise 65
Section 7.2.1.1: Generating All n-Tuples Exercise 65. [ 30 ] [30] (Brett Stevens.) In Samuel Beckett’s play Quad, the stage begins and ends empty; n actors enter and exit one at a time, running through all 2n possible subsets, and the actor who leaves is always the one whose previous entrance was earliest. When 7.2.1.1 GENERATING ALL n-TUPLES 315 n = 4, as in the actual play, some subsets are...
TAOCP 7.2.1.1 Exercise 63
Section 7.2.1.1: Generating All n-Tuples Exercise 63. [ 30 ] [30] (Luis Goddyn.) Prove that r(10) ≥8. Verified: no Solve time: 4m29s Setup Let $\Gamma_n = g(0), g(1), \dots, g(2^n-1)$ denote the $n$-bit Gray cycle as defined in (5)–(7). For a vertex $x \in {0,1}^n$, write $\mathrm{pos}_n(x)$ for its position in $\Gamma_n$. The run-length-bound function $r(n)$ is defined (in the preceding exercises of this section) as the largest integer $r$...
TAOCP 7.2.1.1 Exercise 57
Section 7.2.1.1: Generating All n-Tuples Exercise 57. [ 32 ] [32] Consider a graph whose vertices are the 2688 possible 4-bit Gray cycles, where two such cycles are adjacent if they are related by one of the following simple transformations: Before After Type 1 After Type 2 After Type 3 After Type 4 (Type 1 changes arise when the cycle can be broken into two parts and reassembled with one...
TAOCP 7.2.1.1 Exercise 55
Section 7.2.1.1: Generating All n-Tuples Exercise 55. ▶ [ 35 ] [35] (F. Ruskey and C. Savage, 1993.) If (v0, . . . , v2n−1) is an n-bit Gray cycle, the pairs { {v2k, v2k+1} | 0 ≤k < 2n−1 } form a perfect matching between the vertices 314 COMBINATORIAL SEARCHING 7.2.1.1 of even and odd parity in the n-cube. Conversely, does every such perfect matching arise as “half” of...
TAOCP 7.2.1.1 Exercise 42
Section 7.2.1.1: Generating All n-Tuples Exercise 42. [ 35 ] [35] (M. L. Fredman.) Algorithm L uses Θ(n log n) bits of auxiliary memory for focus pointers as it chooses the Gray binary bit aj to complement next. Step L3 examines Θ(log n) of the auxiliary bits, and it occasionally changes Ω(log n) of them. Show that, from a theoretical standpoint, we can do better: The n-bit Gray binary code...
TAOCP 7.1.4 Exercise 91
Section 7.1.4: Binary Decision Diagrams Exercise 91. ▶ [ 26 ] [26] In practice we often want to simplify a Boolean function f with respect to a “care set” g, by finding a function ˆf with small B( ˆf) such that f(x) ∧g(x) ≤ˆf(x) ≤f(x) ∨¯g(x) for all x. In other words, ˆf(x) must agree with f(x) whenever x satisfies g(x) = 1, but we don’t care what value ˆf(x)...
TAOCP 7.1.4 Exercise 38
Section 7.1.4: Binary Decision Diagrams Exercise 38. ▶ [ 27 ] [27] Let Is−1, . . . , I0 be branch instructions that define a nonconstant Boolean function f(x1, . . . , xn) as in (8) and (10). Design an algorithm that computes the status variables t1 . . . tn, where tj = +1, if f(x1, . . . , xn) = 1 whenever xj...
TAOCP 7.1.4 Exercise 250
Section 7.1.4: Binary Decision Diagrams Exercise 250. [ 28 ] [28] There are 7581 monotone Boolean functions f(x1, x2, x3, x4, x5). What are the average values of B(f) and Z(PI(f)) when one of them is chosen at random? What is the probability that Z(PI(f)) > B(f)? What is the maximum of Z(PI(f))/B(f)? Verified: no Solve time: 4m19s Setup A monotone Boolean function $f(x_1,\dots,x_5)$ is uniquely represented by its set...
TAOCP 7.1.4 Exercise 241
Section 7.1.4: Binary Decision Diagrams Exercise 241. ▶ [ 28 ] [28] The queen graph Q8 consists of the 64 squares of a chessboard, with u−−−v when squares u and v lie in the same row, column, or diagonal. How large are the ZDDs for its (a) kernels? (b) maximal cliques? (c) minimal dominating sets? (d) minimal dominating sets that are also cliques? (e) maximal induced bipartite subgraphs? Illustrate each...
TAOCP 7.1.4 Exercise 225
Section 7.1.4: Binary Decision Diagrams Exercise 225. ▶ [ 30 ] [30] Design an algorithm that will produce a ZDD for all sets of edges that form a simple path from s to t, given a graph and two distinct vertices {s, t} of the graph. Verified: yes Solve time: 2m48s Setup Let $G = (V, E)$ be a finite graph and let $s, t \in V$ be distinct vertices....
TAOCP 7.1.4 Exercise 223
Section 7.1.4: Binary Decision Diagrams Exercise 223. [ 28 ] [28] A “median word” is a five-letter word µ = µ1 . . . µ5 that can be obtained from three words α = α1 . . . α5, β = β1 . . . β5, γ = γ1 . . . γ5 by the rule [αi = µi] + [βi = µi] + [γi = µi] = 2 for...
TAOCP 7.1.4 Exercise 222
Section 7.1.4: Binary Decision Diagrams Exercise 222. ▶ [ 27 ] [27] When family algebra is applied to five-letter words as in (131), the 130 variables are called a1, b1, . . . , z5 instead of x1, x2, . . . , x130; and the corresponding elementary families are denoted by the symbols a1, b1, . . . , z5 instead of e1, e2, . . . , e130....
TAOCP 7.1.4 Exercise 217
Section 7.1.4: Binary Decision Diagrams Exercise 217. [ 29 ] [29] The monomino/domino/tromino covering illustrated in (130) happens to satisfy an additional constraint: No two congruent pieces are adjacent. How many of the 92 sextillion coverings mentioned in the text are “separated,” in this sense? Verified: no Solve time: 1m Working
TAOCP 7.1.4 Exercise 216
Section 7.1.4: Binary Decision Diagrams Exercise 216. ▶ [ 30 ] [30] Figure 29(b) shows a chessboard covered with red, white, and blue domi- noes, in such a way that no two dominoes of the same color are next to each other. a) In how many ways can this be done? b) How many of the 12,988,816 domino coverings are 3-colorable? Verified: no Solve time: 2m04s Setup An 8×8 chessboard...
TAOCP 7.1.4 Exercise 17
Section 7.1.4: Binary Decision Diagrams Exercise 17. [ 32 ] [32] If possible, improve the algorithm of exercise 16 so that its running time is O(B(f)) + O(N) when there are N solutions. Verified: no Solve time: 6m15s Setup A reduced ordered binary decision diagram (BDD) for a Boolean function $f(x_1,\dots,x_n)$ consists of a rooted directed acyclic graph in which each non-sink node $v$ has a variable index $V(v)\in{1,\dots,n}$ and...
TAOCP 7.1.4 Exercise 162
Section 7.1.4: Binary Decision Diagrams Exercise 162. ▶ [ 30 ] [30] (Caged Life.) If X and L(X) are tame but L(L(X)) is wild, we say that X “escapes” its cage after three steps. How many 6 × 6 matrices escape their 6 × 6 cage after exactly k steps, for k = 1, 2, . . . ? Verified: no Solve time: 6m30s Setup Let $X = (x_{ij})$ be...
TAOCP 7.1.4 Exercise 161
Section 7.1.4: Binary Decision Diagrams Exercise 161. [ 28 ] [28] Continuing exercise 160, write L(X) = Y = (yij) if X is a tame matrix such that Lij(X) = yij for 1 ≤i, j ≤8. a) How many X’s satisfy L(X) = X (“still Life”)? b) Find an 8 × 8 still Life with weight 35. c) A “flip-flop” is a pair of distinct matrices with L(X)=Y, L(Y )=X....
TAOCP 7.1.4 Exercise 156
Section 7.1.4: Binary Decision Diagrams Exercise 156. [ 30 ] [30] Theorems J+ and J−suggest that we could save reordering time by only jumping up when sifting, not bothering to jump down. Then we could eliminate steps J3, J5, J6, and J7 of Algorithm J. Would that be wise? Verified: yes Solve time: 1m16s Setup Algorithm J (sifting) for dynamic variable reordering in reduced ordered BDDs operates by selecting a...
TAOCP 7.1.4 Exercise 153
Section 7.1.4: Binary Decision Diagrams Exercise 153. [ 30 ] [30] Put the tic-tac-toe functions {y1, . . . , y9} of exercise 7.1.2–65 into a BDD base. How many nodes are present when variables are tested in the order x1, x2, . . . , x9, o1, o2, . . . , o9, from top to bottom? What is Bmin(y1, . . . , y9)? Verified: no Solve time:...
TAOCP 7.1.4 Exercise 150
Section 7.1.4: Binary Decision Diagrams Exercise 150. [ 30 ] [30] When repeated swaps are used to implement jump-up or jump-down, the intermediate results might be much larger than the initial or final BDD. Show that variable jumps can actually be done more directly, with a method whose worst-case running time is O(B(f1, . . . , fm) + B(f π 1 , . . . , f π m))....
TAOCP 7.1.4 Exercise 147
Section 7.1.4: Binary Decision Diagrams Exercise 147. ▶ [ 27 ] [27] Flesh out the details of Rudell’s swap-in-place algorithm, using the conven- tions of Algorithm U and the reference counters of exercise 82. 7.1.4 BINARY DECISION DIAGRAMS 269 Verified: no Solve time: 3m42s Solution Let level $0$ contain the root nodes of the BDD base, level $1$ the next variable layer, and level $2$ the layer below. Let $b_i$...
TAOCP 7.1.4 Exercise 141
Section 7.1.4: Binary Decision Diagrams Exercise 141. [ 30 ] [30] True or false: If X1, X2, . . . , Xm are disjoint sets of variables, then an opti- mum BDD ordering for the variables of g(h1(X1), h2(X2), . . . , hm(Xm)) can be found by restricting consideration to cases where the variables of each Xj are consecutive. Verified: no Solve time: 4m42s Setup Let $d(n)$ denote the...
TAOCP 7.1.4 Exercise 140
Section 7.1.4: Binary Decision Diagrams Exercise 140. [ 27 ] [27] Explain how to find Bmin(f) without knowing all of f’s master profile chart. Verified: no Solve time: 5m31s Solution Number the vertices of the cycle $C_n$ as in the statement, so edges are ${x_i,x_{i+1}}$ for $1 \le i < n$ and ${x_n,x_1}$. Let variables be ordered $x_1,\dots,x_n$ in the BDD. (a) Independent sets of $C_n$ Let $f(x_1,\dots,x_n)$ be the...
TAOCP 7.1.4 Exercise 132
Section 7.1.4: Binary Decision Diagrams Exercise 132. [ 32 ] [32] What Boolean functions f(x1, x2, x3, x4, x5) have the largest Bmin(f)? Verified: no Solve time: 4m38s Setup Let $f(x_1,x_2,x_3,x_4,x_5)$ be a Boolean function and let $B_{\min}(f)$ denote the minimum, over all variable orderings, of the number of nodes in its reduced ordered binary decision diagram, including the sink nodes $\bot$ and $\top$. For an ordering $x_{i_1},\dots,x_{i_5}$, each node...
TAOCP 7.1.4 Exercise 124
Section 7.1.4: Binary Decision Diagrams Exercise 124. ▶ [ 27 ] [27] Design an efficient algorithm to compute the profile and quasi-profile of hπ n, given a permutation π. Hint: When does the slate [r0, . . . , rn−k] correspond to a bead? 7.1.4 BINARY DECISION DIAGRAMS 267 Verified: no Solve time: 4m55s Solution Let a slate of offset $s$ be defined as in the construction preceding formula (97),...
TAOCP 7.1.4 Exercise 122
Section 7.1.4: Binary Decision Diagrams Exercise 122. [ 27 ] [27] Construct an FBDD for hn that has fewer than n2 nodes, when n > 1. Verified: no Solve time: 6m18s Setup Let $h_n(x_1,\dots,x_n)$ denote the hidden weighted bit function, and let $x^\psi$ be the permutation on ${0,1}^n$ defined in part (c) of Exercise 121 by $$ \epsilon^\psi=\epsilon,\quad (x_1\cdots x_n0)^\psi=(x_1\cdots x_n^\psi)0,\quad (x_1\cdots x_n1)^\psi=(x_2\cdots x_nx_1)^\psi1. $$ Part (d) of Exercise 121...
TAOCP 7.1.4 Exercise 107
Section 7.1.4: Binary Decision Diagrams Exercise 107. [ 26 ] [26] Continuing exercise 106, show that it’s possible to determine whether or not f is a Krom function in O(B(f)4) steps. [Hint: See Theorem 7.1.1S.] Verified: no Solve time: 4m10s Setup Let $f(x_1,\dots,x_n)$ be a Boolean function represented by a reduced ordered BDD, and let $B(f)$ denote its number of nodes including sinks, as defined in Section 7.1.4. From Exercise...
TAOCP 7.1.3 Exercise 99
Section 7.1.3: Bitwise Tricks and Techniques Exercise 99. ▶ [ 28 ] Find hexadecimal constants $a, b, c, d, e$ such that the six bitwise operations $$y \leftarrow x \oplus a, \quad t \leftarrow ((((y \mathbin{&} b) + c) \mid y) \oplus d) \mathbin{&} e$$ will compute the flags $t = (f_7 \ldots f_1 f_0) {256} \ll 7$ from any bytes $x = (x_7 \ldots x_1 x_0) {256}$, where $$f_0...
TAOCP 7.1.3 Exercise 91
Section 7.1.3: Bitwise Tricks and Techniques Exercise 91. ▶ [ 26 ] [26] ( Alpha channels. ) Recipe (88) is a good way to compute bytewise averages, but applications to computer graphics often require a more general blending of 8-bit values. Given three octabytes $x = (x_7 \ldots x_0) {256}$, $y = (y_7 \ldots y_0) {256}$, $\alpha = (\alpha_7 \ldots \alpha_0) {256}$, show that bitwise operations allow us to compute...
TAOCP 7.1.3 Exercise 83
Section 7.1.3: Bitwise Tricks and Techniques Exercise 83. ▶ [ 33 ] Continuing exercise 82, find a way to shift a scattered $2^d$-bit accumulator to the right by 1, given $z$ and $\chi$, in $O(d)$ steps. Verified: no Solve time: 10m48s Setup Let $\chi$ be a mask with exactly $2^d$ one-bits. Let these bits occur at positions $$ \chi = \sum_{j=0}^{2^d-1} 2^{p_j}, \qquad p_0 < p_1 < \cdots < p_{2^d-1}....
TAOCP 7.1.3 Exercise 77
Section 7.1.3: Bitwise Tricks and Techniques Exercise 77. [ 26 ] (R. W. Floyd and V. R. Pratt.) Design an algorithm that tests whether or not a given standard $n$-network is a sorting network, as defined in the exercises of Section 5.3.4. When the given network has $r$ comparator modules, your algorithm should use $O(r)$ bitwise operations on words of length $2^n$. Verified: no Solve time: 5m48s Setup A mapping...
TAOCP 7.1.3 Exercise 76
Section 7.1.3: Bitwise Tricks and Techniques Exercise 76. [ 27 ] A mapping network is analogous to a sorting network or a permutation network, but it uses $2 \times 2$ mapping modules instead of comparators or crossbars, and it is supposed to be able to output all $n^n$ possible mappings of its $n$ inputs. Exercise 75, in conjunction with Fig. 12, shows that a mapping network for $n = 2^d$...
TAOCP 7.1.3 Exercise 75
Section 7.1.3: Bitwise Tricks and Techniques Exercise 75. ▶ [ 32 ] The method of Chung and Wong replicates bit $l$ of a register exactly $c_l$ times, but it produces results in scrambled order. For example, the case $(c_0, \ldots, c_7) = (1, 2, 0, 2, 0, 2, 0, 1)$ unblends the bits of the produces $(x_7x_3x_5x_3x_5x_1x_5x_0)_2$. In some applications this can be a disadvantage; we might prefer to have...
TAOCP 7.1.3 Exercise 70
Section 7.1.3: Bitwise Tricks and Techniques Exercise 70. ▶ [ 31 ] (Guy L. Steele Jr., 1994.) What's a good way to compute the masks $\theta_0$, $\theta_1$, $\ldots$, $\theta_{d-1}$ that are needed in the general compression procedure (80), given $\chi \ne 0$? Verified: no Solve time: 11m36s Correctness The solution does not correctly address what Steele’s problem is asking in the context of method (80). The exercise is not asking...
TAOCP 7.1.3 Exercise 33
Section 7.1.3: Bitwise Tricks and Techniques Exercise 33. ▶ [ 26 ] (Leiserson, Prokop, and Randall, 1998.) Show that if '58' is replaced by '49' in (52), we can use that method to identify both bits of the number $y = 2^j + 2^k$ quickly, when $64 > j > k \ge 0$. (Altogether $\binom{64}{2} = 2016$ cases need to be distinguished.) Verified: no Solve time: 10m10s Setup Let $y...
TAOCP 7.1.3 Exercise 23
Section 7.1.3: Bitwise Tricks and Techniques Exercise 23. ▶ [ 27 ] [27] A sequence of nested parentheses can be represented as a binary number by putting a 1 in the position of each right parenthesis. For example, '(())()' corresponds in this way to $(001101)_2$, the number 13. Call such a number a parenthesis trace . a) What are the smallest and largest parenthesis traces that have exactly $n$ 1s?...
TAOCP 1.4.3.1 Exercise 7
Section 1.4.3.1: A MIX Simulator Exercise 7. [ 32 ] Modify the solutions of the previous exercise in such a way that execution of IN or OUT does not cause I/O transmission immediately; the transmission should take place after approximately half of the time required by the simulated devices has elapsed. (This will prevent a frequent student error, in which IN and OUT are used improperly.) Verified: no Solve time:...
TAOCP 1.4.4 Exercise 18
Section 1.4.4: Input and Output Exercise 18. [ 30 ] A proposed extension of MIX allows its computations to be interrupted, as explained below. Your task in this exercise is to modify Algorithms and Programs A, R, and B of the text so that they use these interrupt facilities instead of the JRED instructions. The new MIX features include an additional 3999 memory cells, locations $-3999$ through $-0001$. The machine...
TAOCP 6.5 Exercise 14
Section 6.5: Retrieval on Secondary Keys Exercise 14. [ 28 ] [28] Discuss the problem of deleting nodes from quadtrees, k-d trees, and postoffice trees like Fig. 45. Verified: no Solve time: 3m35s Corrected Solution The three structures all support dynamic sets of points in the plane, but they differ in what is structurally invariant. Deletion is therefore easy in none of them: it either destroys a recursively defined decomposition...
TAOCP 5.3.2 Exercise 10
Section 5.3.2: Minimum-Comparison Merging Exercise 10. [ 33 ] [33] Prove that five elements can be merged with nine in at most twelve steps. [Hint: Experience with the adversary suggests first comparing $A_1:B_2$, then trying Verified: no Solve time: 4m14s Working
TAOCP 5.4.2 Exercise 18
Section 5.4.2: The Polyphase Merge Exercise 18. [ 30 ] [30] Does the optimum polyphase distribution produce the best possible merging pattern, in the sense that the total number of initial runs processed is minimized, if we insist that the initial runs be placed on at most T’', 1 of the tapes? (Ignore rewind time.) Verified: no Solve time: 1m18s Setup Let $T > 3$ be fixed and set $P...
TAOCP 5.4.1 Exercise 10
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 10. [ 26 ] [26] The initial setting of the LOSER pointers in step R1 usually doesn’t correspond to any actual tournament, since external node P + 7 may not lie in the subtree below internal node j. Explain why Algorithm R works anyway. [Hint: Would the algorithm work if {LOSER (LOC(X[0])),..., LOSER(LOC(.X [P, 1]))} were set to an arbitrary permutation of...
TAOCP 6.3 Exercise 44
Section 6.3: Digital Searching Exercise 44. [ 30 ] [30] (J. L. Bentley and R. Sedgewick.) Explore a ternary representation of tries, in which left and right links correspond to the horizontal branches of (2) while middle links correspond to the downward branches. Verified: yes Solve time: 1m41s Setup Let $\Sigma$ be an ordered alphabet corresponding to the $M$ characters used in Section 6.3, with a total order $<$ consistent...
TAOCP 5.4.9 Exercise 26
Section 5.4.9: Disks and Drums Exercise 26. [ 26 ] [26] How many output buffers will guarantee that a P-way merge with randomized striping will never have to pause for lack of a place in internal memory to put newly merged output? Assume that the time to write a block equals the time to read a block. Verified: yes Solve time: 1m29s Setup A $P$-way merge produces one output block...
TAOCP 6.2.2 Exercise 45
Section 6.2.2: Binary Tree Searching Exercise 45. [ 30 ] [30] Explain how to implement Subroutine C so that the total running time of the Garsia, Wachs algorithm is at most O(nlogn). Verified: no Solve time: 1m21s Setup Let the sequence maintained by the Garsia–Wachs algorithm be $L = (l_1, l_2, \dots, l_m)$ in symmetric order. A merge replaces two adjacent entries $l_i, l_{i+1}$ by a single entry $l_i +...
TAOCP 5.4.2 Exercise 17
Section 5.4.2: The Polyphase Merge Exercise 17. [ 32 ] [32] Prove or disprove: There is a way to disperse runs for an optimum polyphase distribution in such a way that the distribution for S + 1 initial runs is formed by adding one run (on an appropriate tape) to the distribution for S initial runs. Verified: no Solve time: 2m26s The previous argument failed because it replaced the polyphase...
TAOCP 6.2.1 Exercise 6
Section 6.2.1: Searching an Ordered Table Exercise 6. [ 28 ] [28] (K. E. Iverson.) Exercise 5 suggests that it would be best to have a hybrid method, changing from binary search to sequential search when the remaining interval has length less than some judiciously chosen value. Write an efficient MIX program for such a search and determine the best changeover value. Verified: no Solve time: 4m41s 1. Cost model...
TAOCP 6.2.1 Exercise 30
Section 6.2.1: Searching an Ordered Table Exercise 30. [ 27 ] [27] (Involution coding.) Using the idea of the previous exercise, find a way to arrange N distinct keys in such a way that their relative order implicitly encodes an arbitrarily given array of t-bit numbers 21, 2, ..., tm, when m < N/4+4+1, 2. With your arrangement it should be possible to determine the leading k bits of x;...
TAOCP 6.3 Exercise 15
Section 6.3: Digital Searching Exercise 15. [ 28 ] [28] Design an efficient algorithm that can be used to construct the tree used by Patricia, or to insert new TEXT references into an existing tree. Your insertion algorithm should refer to the TEXT array at most twice. Verified: yes Solve time: 4m43s The flaw in the previous argument is real: the insertion point cannot depend on the unknown divergence index...
TAOCP 5.4.2 Exercise 23
Section 5.4.2: The Polyphase Merge Exercise 23. [ 29 ] [29] What changes would be made to (25), (27), and (28), if (23) were changed to Unt1 = Un, 1 + Un-1 + Un, 2; Un = Un, 2 + Un, 3 + Un, 3 + Un, 4 + Un, 4? Verified: no Solve time: 4m15s The reviewer is correct that the original attempt destroys the essential feature of TAOCP...
TAOCP 5.3.2 Exercise 9
Section 5.3.2: Minimum-Comparison Merging Exercise 9. [ 27 ] [27] Prove that three elements can be merged with six in at most seven steps. Verified: no Solve time: 4m44s We construct a single, explicit decision tree of comparisons whose worst-case depth is at most 7. Every branch is fully specified, and no cost is attributed without an actual comparison path. Let $$ A_1 < A_2 < A_3,\quad B_1 < B_2...
TAOCP 5.3.3 Exercise 11
Section 5.3.3: Minimum-Comparison Selection Exercise 11. [ 32 ] [32] (P. V. Ramanan and L. Hyafil.) Prove that $W_t(2^k + 2^{t!} - 1) < (f - 1)(k - 1)$, when $k > t > 2$; also show that equality holds for infinitely many $k$ and $t$, because of exercise 4. [Hint: Maintain two knockout trees and merge their results cleverly.] Verified: no Solve time: 4m07s Setup Let $t > 2$...
TAOCP 5.4.6 Exercise 7
Section 5.4.6: Practical Considerations for Tape Merging Exercise 7. [ 26 ] [26] The initial distribution in example 7 of Chart A produces (AiD1)'' ~, -Di(A1D1)'°, Di (Ai Di)? iD (A1.D1)" on tapes 1-4, where (AiD1)* means A, D,A1,D,A1,D,A1D1A1D,A1D1Ai1D. Show how to insert additional Ao’s and Dos in a “best possible” way (in the sense that the overall number of initial runs processed while merging is minimized), bringing the distribution...
TAOCP 5.1.2 Exercise 9
Section 5.1.2: Permutations of a Multiset Exercise 9. [ 33 ] [33] Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C. Verified: no Solve time: 20m23s Exercise 5.1.2.9 [ 33 ] 9. Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C. Solution Let $M$ be a...
TAOCP 4.6.4 Exercise 3
Section 4.6.4: Evaluation of Polynomials Exercise 3. [ 30 ] Give a method, analogous to Horner's rule, for evaluating a polynomial in two variables $\sum_{i,j} u_{ij} x^i y^j$. (This polynomial has $(n+1)(n+2)/2$ coefficients, and its "total degree" is $n$.) Count the number of additions and multiplications you use. Verified: yes Solve time: 1m46s Setup Let $u(x,y)=\sum_{i+j\le n} u_{ij} x^i y^j$ be a bivariate polynomial of total degree $n$. For each...
TAOCP 4.4 Exercise 6
Section 4.4: Radix Conversion Exercise 6. [ 30 ] Discuss using Methods 1a, 1b, 2a, and 2b when $b$ or $B$ is $-2$. Verified: yes Solve time: 1m49s Setup Methods 1a, 1b, 2a, and 2b are stated for positive radices $b$ and $B$. The exercise asks how these methods behave when either the input radix or the output radix is $-2$. A radix-$(-2)$ representation of an integer has the form...
TAOCP 4.3.3 Exercise 5
Section 4.3.3: How Fast Can We Multiply? Exercise 5. ▶ [ 35 ] [35] Show that if in step T1 of Algorithm T we set $R \leftarrow \lceil \sqrt{2Q} \rceil + 1$ instead of setting $R \leftarrow \lfloor \sqrt{Q} \rfloor$, with initial values of $q_0, q_1, r_0$, and $r_1$, then (20) can be improved to $t_k \le q_{k+1} 2^{2(q_k+r_k)} \ell(q_{k+1})$. Verified: no Solve time: 7m14s Let $\ell(n)$ denote the binary...
TAOCP 4.3.3 Exercise 4
Section 4.3.3: How Fast Can We Multiply? Exercise 4. ▶ [ 28 ] [28] (K. Baker.) Show that it is advantageous to evaluate the polynomial $W(x)$ at the points $x = -r, \ldots, 0, \ldots, r$ instead of at the nonnegative points $x = 0, 1, \ldots, 2r$ as in Algorithm T. The polynomial $U(x)$ can be written $$U(x) = U_e(x^2) + xU_o(x^2),$$ and similarly $V(x)$ and $W(x)$ can be...
TAOCP 4.3.2 Exercise 4
Section 4.3.2: Modular Arithmetic Exercise 4. [ 29 ] Continue the process shown in (13); what would $m_5, m_6, m_9, \ldots$ be? Verified: yes Solve time: 6m27s Setup Equation (13) is obtained by the rule stated immediately before it. Starting from the largest odd number below the word size, each subsequent modulus is chosen to be the largest odd integer smaller than the preceding modulus and relatively prime to every...
TAOCP 4.3.1 Exercise 31
Section 4.3.1: The Classical Algorithms Exercise 31. [ 28 ] [28] Assume that $b = 3$ and that $u = (u_{m+n-1} \ldots u_1 u_0) 3$, $v = (v {n-1} \ldots v_1 v_0) 3$ are integers in balanced ternary notation (see Section 4.1), $v {n-1} \ne 0$. Design a long-division algorithm that divides $u$ by $v$, obtaining a remainder whose absolute value does not exceed $\frac{1}{2}|v|$. Try to find an algorithm...
TAOCP 4.3.1 Exercise 25
Section 4.3.1: The Classical Algorithms Exercise 25. [ 26 ] Write a MIX routine for step D1, which is needed to complete Program D. Verified: no Solve time: 7m30s Corrected Solution to Exercise 4.3.1.25 [ 26 ] Step D1 of Algorithm D in TAOCP, Section 4.3.1, is responsible for initializing the quotient digit index $j$ before beginning the main quotient estimation loop. Specifically, it sets $j = n - m$,...
TAOCP 4.2.2 Exercise 17
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 17. [ 28 ] Write a MIX subroutine, FCMP, that compares the floating point number $u$ in location ACC with the floating point number $v$ in register A, setting the comparison indicator to LESS, EQUAL, or GREATER according as $u < v$, $u = v$, or $u > v$ ${e}$; here $e$ is stored in location EPSILON as a nonnegative fixed point...
TAOCP 4.2.1 Exercise 15
Section 4.2.1: Single-Precision Calculations Exercise 15. ▶ [ 28 ] Write a MIX subroutine, to be used in connection with the other subroutines of this section, that calculates $u \pmod{1}$, namely $u - \lfloor u \rfloor$ rounded to the nearest floating point number, given a floating point number $u$. Notice that when $u$ is a very small negative number, $u \pmod{1}$ should be rounded so that the result is unity...
TAOCP 4.2.1 Exercise 13
Section 4.2.1: Single-Precision Calculations Exercise 13. [ 30 ] When doing "interval arithmetic" we don't want to round the results of a floating point computation; we want rather to implement operations such as $\triangledown$ and $\triangle$, which give the tightest possible representable bounds on the true sum: $$u \triangledown v \le u + v \le u \triangle v.$$ How should the algorithms of this section be modified for such a...
TAOCP 4.2.1 Exercise 7
Section 4.2.1: Single-Precision Calculations Exercise 7. [ 27 ] Discuss floating point arithmetic using balanced ternary notation. Verified: yes Solve time: 5m46s Exercise 4.2.1.7 [ 27 ] Problem. Discuss floating point arithmetic using balanced ternary notation. Solution 1. Balanced ternary setup Balanced ternary uses radix $b = 3$ with digit set $$ d \in {-1,0,+1}. $$ A normalized floating point fraction with $p$ digits has the form $$ f =...
TAOCP 4.1 Exercise 3
Section 4.1: Positional Number Systems Exercise 3. [ 29 ] Express $-49 + i$ in the quarter-imaginary system. Verified: yes Solve time: 4m35s Exercise 4.1.3.3 [ 29 ] Express $-49+i$ in the quarter-imaginary system. Solution The quarter-imaginary system has base $$ b = 2i, $$ and a numeral $$ (a_n a_{n-1} \cdots a_0 . a_{-1} a_{-2} \cdots )_{2i}, $$ with digits $a_j \in {0,1,2,3}$, represents $$ \sum_{j} a_j (2i)^j. $$...
TAOCP 3.5 Exercise 43
Section 3.5: What Is a Random Sequence? Exercise 43. [ 26 ] It seems just as difficult to find the factors of any fixed $R$-bit Blum integer $M$ as to find the factors of a random $R$-bit integer. Why then is Theorem P stated for random $M$ instead of fixed $M$? Verified: no Solve time: 5m15s Problem Understanding We are given a set of boxes, each containing some number of...
TAOCP 3.4.2 Exercise 15
Section 3.4.2: Random Sampling and Shuffling Exercise 15. ▶ [ 30 ] (Ole-Johan Dahl.) If $X_k = k$ for $1 \le k \le t$ at the start of Algorithm P, and if we terminate the algorithm when $j$ reaches the value $t - n$, the sequence $X_{t-n+1}, \ldots, X_t$ is a random permutation of a random combination of $n$ elements. Show how to simulate the effect of this procedure using...
TAOCP 3.4.1 Exercise 33
Section 3.4.1: Numerical Distributions Exercise 33. [ 29 ] [29] Algorithms P, M, F, and R generate normal deviates by consuming an unknown number of uniform random variables $U_1, U_2, \ldots$ How can they be modified so that the output is a function of just one $U$? Verified: yes Solve time: 10m56s Solution Algorithms P, M, F, and R generate a normal deviate by reading a sequence of independent uniform...
TAOCP 3.4.1 Exercise 7
Section 3.4.1: Numerical Distributions Exercise 7. ▶ [ 26 ] [26] (A. J. Walker.) Suppose we have a bunch of cubes of $k$ different colors, say $n_j$ cubes of color $C_j$ for $1 \le j \le k$, and we also have $k$ boxes ${B_1, \ldots, B_k}$ each of which can hold exactly $n$ cubes. Furthermore $n_1 + \cdots + n_k = kn$, so the cubes will just fit in the...
TAOCP 3.3.1 Exercise 9
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 9. ▶ [ 28 ] [28] The experiment described in the text consisted of plotting 20 values of $K_{10}^+$, computed from the maximum-of-5 test applied to different parts of a random sequence. We could have computed also the corresponding 20 values of $K_{10}^-$; since $K_{10}^-$ has the same distribution as $K_{10}^+$, we could lump together the 40 values thus obtained...
TAOCP 3.2.2 Exercise 25
Section 3.2.2: Other Methods Exercise 25. [ 26 ] $[26]$ Discuss the alternative to Program A that changes all 55 entries of the $Y$ table every 55th time a random number is required. Verified: no Solve time: 5m59s Solution In Program A of Section 3.2.2, the table $$ Y[1],Y[2],\ldots ,Y[55] $$ is updated one position at a time. If the current position is $k$, the program computes $$ Y[k]\leftarrow (Y[k]+Y[k+31])\pmod{2^e},...
TAOCP 3.2.1.1 Exercise 6
Section 3.2.1.1: Choice of Modulus Exercise 6. ▶ [ 28 ] $[28]$ The previous exercise suggests that subtraction mod $m$ is easier to perform than addition mod $m$. Discuss sequences generated by the rule $$X_{n+1} = (a X_n - c) \bmod m.$$ Are these sequences essentially different from linear congruential sequences as defined in the text? Are they more suited to efficient computer calculation? Verified: yes Solve time: 14m32s Setup...
TAOCP 3.2.1.1 Exercise 5
Section 3.2.1.1: Choice of Modulus Exercise 5. [ 29 ] $[29]$ Given that $m$ is less than the word size, and that $x$ and $y$ are nonnegative integers less than $m$, show that the difference $(x - y) \bmod m$ may be computed in just four MIX instructions, without requiring any division. What is the best code for the sum $(x + y) \bmod m$? Verified: yes Solve time: 17m48s...
TAOCP 7.1.3 Exercise 179
Section 7.1.3: Bitwise Tricks and Techniques Exercise 179. ▶ [ 34 ] [34] Design an algorithm that constructs the surroundedness tree of a given M × N bitmap, scanning the image one row at a time as discussed in the text. (See (162) and (163).) Verified: no Solve time: 4m20s The failure in the proposed solution is not a technical detail. It is a structural mistake: it tries to recover...
TAOCP 7.1.3 Exercise 136
Section 7.1.3: Bitwise Tricks and Techniques Exercise 136. [ 29 ] [29] Suggest two-bit encodings for binary operations on the set {a, b, c} that are defined by the following “multiplication tables”: (a) a b c b c c c c c ; (b) a c b c b a b a c ; (c) a b a a a c a b c . Verified: yes...
TAOCP 7.2.2.1 Exercise 359
Section 7.2.2.1: Dancing Links Exercise 359. [ 29 ] $[29]$ Nick Baxter devised an innocuous-looking but maddeningly difficult "Square Dissection" puzzle for the International Puzzle Party in 2014, asking that the nine pieces be placed flat into a $65 \times 65$ square. One quickly checks that $17 \times 20 + 18 \times 20 + \cdots + 24 \times 25 = 65^2$; yet nothing seems to work! Solve his puzzle with...
TAOCP 7.1.3 Exercise 55
Section 7.1.3: Bitwise Tricks and Techniques Exercise 55. ▶ [ 26 ] Suppose an $n \times n$ bit matrix is stored in the rightmost $n^2$ bits of an $n^2$-bit register. Prove that $18d + 2$ bitwise operations suffice to multiply two such matrices, when $n = 2^d$; the matrix multiplication can be either Boolean (like MOR) or mod 2 (like MXOR). Verified: no Solve time: 4m47s The previous solution fails...
TAOCP 7.1.3 Exercise 142
Section 7.1.3: Bitwise Tricks and Techniques Exercise 142. ▶ [ 33 ] [33] A subcube such as ∗10∗1∗01 can be represented by asterisk codes 10010100 and bit codes 01001001, as in (85); but many other encodings are also possible. What representation scheme for subcubes works best, for finding prime implicants by the consensus-based algorithm of exercise 7.1.1–31? Verified: yes Solve time: 4m06s Corrected Solution We work with subcubes (implicants) on...
TAOCP 7.1.3 Exercise 141
Section 7.1.3: Bitwise Tricks and Techniques Exercise 141. ▶ [ 30 ] [30] The Ulam numbers ⟨U1, U2, . . . ⟩= ⟨1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, . . . ⟩are defined for n ≥3 by letting Un be the smallest integer > Un−1 that has a unique representation Un = Uj + Uk for 0 < j < k < n. Show that...
TAOCP 7.1.3 Exercise 140
Section 7.1.3: Bitwise Tricks and Techniques Exercise 140. [ 27 ] [27] Design an economical full adder for balanced ternary numbers: Show how to compute signed bits u and v such that 3u + v = x+ y + z when x, y, z ∈{0, +1, −1}. Verified: yes Solve time: 1m18s Setup Let $x,y,z \in {0,+1,-1}$. Let $s = x+y+z.$ Then $s \in {-3,-2,-1,0,1,2,3}$. We seek signed bits $u,v...
TAOCP 7.1.3 Exercise 118
Section 7.1.3: Bitwise Tricks and Techniques Exercise 118. [ 30 ] [30] According to Lemma A, we cannot compute the function x ≫1 for all n- bit numbers x by using only additions, subtractions, and bitwise Boolean operations (no shifts or branches). Show, however, that O(n) such operations are necessary and sufficient if we include also the “monus” operator y .−z in our repertoire. Verified: no Solve time: 5m The...
TAOCP 7.1.2 Exercise 28
Section 7.1.2: Boolean Evaluation Exercise 28. [ 26 ] [26] Prove that $C(u'v') = C(u''v'') = 5$ for the two-output functions defined by $$\langle u'v'\rangle_2 = (x + y - \langle uv\rangle_2) \bmod 4, \qquad \langle u''v''\rangle_2 = \langle -x - y - \langle uv\rangle_2\rangle \bmod 4.$$ Use these functions to evaluate $\langle (x_1 + \cdots + x_n) \bmod 4 \rangle = 0$, in fewer than $2.5n$ steps. Verified: no...
TAOCP 7.1.1 Exercise 80
Section 7.1.1: Boolean Basics Exercise 80. [ 27 ] A partial cube is an "isometric" subgraph of a hypercube, a subgraph in which the distance between two vertices are the same as they are in the full graph. The vertices of a partial cube can therefore be labeled in such a way that the distance from $u$ to $v$ is the "Hamming distance" between $l(u)$ and $l(v)$, namely $\nu(l(u) \oplus...
TAOCP 7.1.1 Exercise 84
Section 7.1.1: Boolean Basics Exercise 84. [ 30 ] [30] Write a program to find all monotone self-dual Boolean functions of five variables. What are the edges of the corresponding median graph? (Table 2 illustrates the four-variable case.) Verified: no Solve time: 4m36s The reviewer correctly identifies two independent problems: The enumeration of maximal antichains of $B_5$ was asserted without proof. The description of the median graph was unsupported and...
TAOCP 7.1.1 Exercise 81
Section 7.1.1: Boolean Basics Exercise 81. [ 26 ] Is every median graph bipartite? Verified: yes Solve time: 2m21s We correct the proof by using the median property directly on a triple involving the root and the endpoints of an edge. Corrected Solution Let $G$ be a median graph and fix a vertex $r \in V(G)$. For each vertex $v$, define its distance parity from $r$ by $$ \chi(v) =...
TAOCP 7.1.3 Exercise 110
Section 7.1.3: Bitwise Tricks and Techniques Exercise 110. ▶ [ 30 ] [30] Suppose n = 22e and 0 ≤x < n. Show how to compute 1 ≪x in O(e) broadword steps, using only shift commands that shift by a constant amount. (Together with Algorithm B we can therefore extract the most significant bit of an n-bit number in O(log log n) such steps.) Verified: no Solve time: 5m13s The...
TAOCP 7.1.3 Exercise 108
Section 7.1.3: Bitwise Tricks and Techniques Exercise 108. [ 26 ] Adapt Algorithm B to cases where $n$ does not have the form $d \cdot 2^d$. 7.1.3 BITWISE TRICKS AND TECHNIQUES 193 Verified: no Solve time: 7m26s Let $m = d\cdot 2^d$ and let Algorithm B be a fixed sequence of primitive operations on vectors in ${0,1}^m$, where each primitive operation is either a permutation of coordinates, or a coordinatewise...
TAOCP 7.1.3 Exercise 105
Section 7.1.3: Bitwise Tricks and Techniques Exercise 105. [ 30 ] Given $x = (x_7 \ldots x_0) {256}$ and $y = (y_7 \ldots y_0) {256}$, discuss bitwise operations that will sort the bytes into order, so that $x_0 \le y_0 \le \cdots \le x_7 \le y_7$ afterwards. Verified: no Solve time: 2m08s Setup Let $x = (x_7 \ldots x_0) {256}$ and $y = (y_7 \ldots y_0) {256}$, where each $x_i$...
TAOCP 7.1.2 Exercise 79
Section 7.1.2: Boolean Evaluation Exercise 79. [ 32 ] (C. P. Schnorr, 1976.) Say that variables $u$ and $v$ are "mates" in a Boolean chain if there is exactly one simple path between them in the corresponding binary tree diagram. Two variables can be mates only if they are each used only once in the chain; but this necessary condition is not sufficient. For example, variables 2 and 4 are...
TAOCP 7.1.2 Exercise 78
Section 7.1.2: Boolean Evaluation Exercise 78. [ 26 ] (W. J. Paul, 1977.) Let $f(x_1, \ldots, x_m, y_0, \ldots, y_{2^m-1})$ be any Boolean function that equals $y_k$ whenever $(x_1 \ldots x_m)_2 = k \in S$, for some given set $S \subseteq {0, 1, \ldots, 2^m - 1}$; we don't care about the value of $f$ at other points. Show that $C(f) \ge 2|S| - 2$ whenever $S$ is nonempty. (In...
TAOCP 7.1.2 Exercise 77
Section 7.1.2: Boolean Evaluation Exercise 77. ▶ [ 35 ] (N. P. Red'kin, 1970.) Suppose a Boolean chain uses only the operations AND, OR, or NOT; thus, every step is either $x_i = x_{j(i)} \wedge x_{k(i)}$ or $x_i = x_{j(i)} \vee x_{k(i)}$ or $x_i = \bar{x}_{j(i)}$. Prove that if such a chain computes either the "odd parity" function $f_n(x_1, \ldots, x_n) = x_1 \oplus \cdots \oplus x_n$ or the "even...
TAOCP 7.1.2 Exercise 65
Section 7.1.2: Boolean Evaluation Exercise 65. ▶ [ 35 ] [35] Modify the tic-tac-toe strategy of (47)–(56) so that it always plays correctly. Verified: yes Solve time: 1m15s Setup Let a tic-tac-toe position $P$ be a configuration of marks on the $3 \times 3$ board together with the player to move. Let $\mathcal{M}(P)$ denote the set of legal moves from $P$, and for $m \in \mathcal{M}(P)$ let $P[m]$ be the...
TAOCP 7.1.2 Exercise 59
Section 7.1.2: Boolean Evaluation Exercise 59. [ 29 ] [29] One of the S-boxes satisfying the conditions of exercise 58 takes $(0, \ldots, f) \mapsto (0, 6, 5, b, 3, 9, f, e, c, 4, 7, 8, d, 2, a, 1)$; in other words, the truth tables of $(f_1, f_2, f_3, f_4)$ are respectively (179a, 63e8, 5b26, 3e29). Find a Boolean chain that evaluates these four "maximally difficult" functions in...
TAOCP 7.1.2 Exercise 58
Section 7.1.2: Boolean Evaluation Exercise 58. ▶ [ 30 ] [30] A $4 \times 4$-bit S-box is a permutation of the 4-bit vectors ${0000, 0001, \ldots, 1111}$; such permutations are used as components of well-known cryptographic systems such as the USSR All-Union standard GOST 28147 (1989). Every $4 \times 4$-bit S-box corresponds to a sequence of four functions $f_1(x_1, x_2, x_3, x_4), \ldots, f_4(x_1, x_2, x_3, x_4)$, which transform $x_1x_2x_3x_4...
TAOCP 7.1.2 Exercise 54
Section 7.1.2: Boolean Evaluation Exercise 54. [ 29 ] [29] Find a short Boolean chain to evaluate all six of the functions $f_j(x) = [x_1x_2x_3x_4 \in A_j]$, where $A_1 = {0010, 0101, 1011}$, $A_2 = {0001, 1111}$, $A_3 = {0011, 0111, 1101}$, $A_4 = {1001, 1111}$, $A_5 = {1101}$, $A_6 = {0101, 1011}$. (These six functions appear in the prime-number detector (37).) Compare your chain to the minterm-first evaluation scheme...
TAOCP 7.1.2 Exercise 44
Section 7.1.2: Boolean Evaluation Exercise 44. ▶ [ 26 ] (R. E. Ladner and M. J. Fischer, 1980.) Show that the problem of binary addition (25) can be viewed as a finite state transduction. Describe the Boolean chain that results from the construction of exercise 43 when $n = 2^m$, and compare it to the conditional-sum adder of exercise 41. Verified: yes Solve time: 1m40s Setup Let inputs be $(x_1,\ldots,x_n)$...
TAOCP 7.1.2 Exercise 43
Section 7.1.2: Boolean Evaluation Exercise 43. ▶ [ 28 ] A finite-state transducer is an abstract machine with a finite input alphabet $A$, a finite output alphabet $B$, and a finite set of internal states $Q$. One of those states, $q_0$, is called the "initial state." Given a string $\alpha = a_1 \ldots a_n$, where each $a_j \in A$, the machine computes a string $\beta = b_1 \ldots b_n$, where...
TAOCP 7.1.2 Exercise 42
Section 7.1.2: Boolean Evaluation Exercise 42. [ 30 ] In the binary addition (25), let $u_k = x_k \wedge y_k$ and $v_k = x_k \oplus y_k$ for $0 \le k < n$. a) Show that $z_k = c_k \oplus c_k$, where the carry bits $c_k$ satisfy $$c_k = u_{k-1} \vee (v_{k-1} \wedge (u_{k-2} \vee (v_{k-2} \wedge (\cdots (v_1 \wedge u_0) \cdots)))).$$ b) Let $U_k^k = 0$, $V_k^k = 1$, and...
TAOCP 7.1.2 Exercise 18
Section 7.1.2: Boolean Evaluation Exercise 18. ▶ [ 35 ] [35] Investigate optimum minimum-memory computations for $f(x_1, x_2, x_3, x_4, x_5)$: How many classes of five-variable functions have $C_m(f) = r$, for $r = 0, 1, 2, \ldots$? Verified: no Solve time: 2m46s Setup Let $C_m(f)$ denote the minimum-memory complexity of a Boolean function $f(x_1,\ldots,x_5)$, defined as the least number of working registers required in a straight-line Boolean chain in...
TAOCP 7.1.2 Exercise 15
Section 7.1.2: Boolean Evaluation Exercise 15. [ 28 ] [28] Find short-as-possible ways to evaluate the following Boolean functions using minimum memory: (a) $S_1(x_1, x_2, x_3)$; (b) $S_2(x_1, x_2, x_3, x_4)$; (c) $S_1(x_1, x_2, x_3, x_4)$; (d) the function in (18). Verified: no Solve time: 5m26s Let $S_k(x_1,\dots,x_n)$ denote the symmetric Boolean function that is $1$ iff exactly $k$ of its arguments are $1$. The key correction is that we...
TAOCP 7.1.1 Exercise 55
Section 7.1.1: Boolean Basics Exercise 55. ▶ [ 30 ] [30] Call $f(x_1, \ldots, x_n)$ a renamed Horn function if there are Boolean constants $y_1, \ldots, y_n$ such that $f(x_1 \oplus y_1, \ldots, x_n \oplus y_n)$ is a Horn function. a) Given $f(x_1, \ldots, x_n)$ in CNF, explain how to construct $g(y_1, \ldots, y_n)$ in 2CNF so that the clauses of $f(x_1 \oplus y_1, \ldots, x_n \oplus y_n)$ are Horn...
TAOCP 7.1.1 Exercise 31
Section 7.1.1: Boolean Basics Exercise 31. ▶ [ 28 ] $[28]$ The algorithm in exercise 30 requires a complete list of all points in $V$, and that list may be quite long. Therefore we may prefer to work directly with subcubes, never going down to the level of explicit $n$-tuples unless necessary. necessary. The key to such higher-level methods is the notion of consensus between subcubes $c$ and $c'$, denoted...
TAOCP 7.1.1 Exercise 30
Section 7.1.1: Boolean Basics Exercise 30. ▶ [ 27 ] $[27]$ The $j$-buddy of a number $a < 2^n$ is $a \oplus 2^j$, obtained by changing $b_j$ to $b_j \oplus 1$. Every subcube $c \subseteq V$ can be assigned a tag value $(t_{n-1} \ldots t_1 t_0)_2$ where $t_j = 1$ if and only if the $j$-buddy of $c$ is defined and contained in $V$. For example, $01{\bullet}0$ has three buddies,...
TAOCP 7.1.1 Exercise 18
Section 7.1.1: Boolean Basics Exercise 18. ▶ [ 30 ] [30] Let $u_1\wedge\cdots\wedge u_k$ be an implicant in a disjunctive normal form for a Boolean function $f$, and let $v_1\vee\cdots\vee v_p$ be a clause in a conjunctive normal form for the same function. Prove that $v_j = u_i$ for some $i, j$. Verified: yes Solve time: 4m The reviewer’s objections identify the key issue: the original proof tries to assign...
TAOCP 7.1.1 Exercise 128
Section 7.1.1: Boolean Basics Exercise 128. ▶ [ 29 ] Find a noncanalizing $f(x_1, \ldots, x_n)$ that is trivial at exactly two points. Verified: yes Solve time: 3m31s Solution A Boolean function $f : {0,1}^n \to {0,1}$ is canalizing if there exists an index $i$ and a bit $a \in {0,1}$ such that the restriction of $f$ to the set ${x : x_i = a}$ is constant. We seek a...
TAOCP 7.1.1 Exercise 124
Section 7.1.1: Boolean Basics Exercise 124. [ 29 ] Find a Boolean function of four variables that is equivalent to 767 other functions, under the ground rules of Table 5. Verified: no Solve time: 5m17s Let the group $G$ be the Table 5 symmetry group on Boolean functions of four variables: permutations of coordinates, independent complementation of variables, and complementation of the output. Then $$ |G| = 4!\cdot 2^4 \cdot...
TAOCP 7.1.1 Exercise 118
Section 7.1.1: Boolean Basics Exercise 118. [ 29 ] How many Boolean functions $f(x_1, x_2, x_3, x_4)$ have exactly $n$ prime implicants, for $m = 0, 1, \ldots,$? Verified: no Solve time: 7m33s Let $U={0,1}^4$. A cube $C$ is specified by fixing some coordinates and leaving the rest free. Write $C \subseteq F$ to mean $C$ is an implicant of $F$. A cube $C$ is a prime implicant of $F$...
TAOCP 2.3.3 Exercise 18
Section 2.3.3: Other Representations of Trees Exercise 18. [ 28 ] Verified: yes Solve time: 2m53s Let the forest be given in preorder sequential representation: INFO1[j] contains the node information. RLINK[j] is the index of the next sibling of node j , or 0 if no next sibling exists. We must construct: INFO2[1..n] , the nodes in postorder; DEGREE[1..n] , where DEGREE[k] is the number of children of the node...
TAOCP 2.3.3 Exercise 10
Section 2.3.3: Other Representations of Trees Exercise 10. [ 28 ] Verified: yes Solve time: 1m24s Associate with each root $r$ an integer $\mathrm{SIZE}(r)$ equal to the number of nodes in its tree. Initially, $$ PARENT(j)=0,\qquad \mathrm{SIZE}(j)=1 \qquad (1\le j\le n). $$ When an equivalence $j\equiv k$ is processed, first determine the roots $r_j$ and $r_k$ of the trees containing $j$ and $k$ by following PARENT links upward until a...
TAOCP 2.3.2 Exercise 13
Section 2.3.2: Binary Tree Representation of Trees Exercise 13. [ 26 ] Verified: yes Solve time: 1m40s Section 2.3.2: Binary Tree Representation of Trees Exercise 13. [ 26 ] Write a MIX program for the COPY subroutine (which fits in the program of the text between lines 063-104 ). [ Hint: Adapt Algorithm 2.3.1C to the case of right-threaded binary trees, with suitable initial conditions.] Verified: yes Solve time: 1m40s...
TAOCP 2.3.1 Exercise 33
Section 2.3.1: Traversing Binary Trees Exercise 33. [ 30 ] Verified: no Solve time: 37s Insertion Algorithm Let X be the new node to insert, and T be a pointer to the root of the tree. We assume a binary search tree structure for ordering, so the placement of X is determined by comparing keys. Let P traverse the tree to find the appropriate insertion point. Step I1. [Initialize.] Set...
TAOCP 2.3.1 Exercise 27
Section 2.3.1: Traversing Binary Trees Exercise 27. [ 28 ] Verified: yes Solve time: 3m02s Section 2.3.1: Traversing Binary Trees Exercise 27. [ 28 ] Design an algorithm that tests two given trees T and T' to see whether T \prec T' , T \succ T' , or T is equivalent to T' , in terms of the relation defined in exercise 25 , assuming that both binary trees are...
TAOCP 2.3.1 Exercise 21
Section 2.3.1: Traversing Binary Trees Exercise 21. [ 33 ] Verified: no Solve time: 32s We employ the threading during traversal method, also known as the Morris traversal , which creates temporary links to predecessors during the traversal to avoid using a stack. Let current denote the pointer to the node currently being processed. The algorithm proceeds as follows: Step 1. Initialize current <- T . Step 2. Repeat while...
TAOCP 2.3.1 Exercise 19
Section 2.3.1: Traversing Binary Trees Exercise 19. [ 27 ] Verified: yes Solve time: 1m41s (a) Right-threaded binary tree The preorder successor is characterized as follows. If LLINK(P)\ne\Lambda , the left subtree is traversed immediately after visiting NODE(P) , hence $$ P*=LLINK(P). $$ If LLINK(P)=\Lambda but RTAG(P)=0 , the node has no left subtree and a genuine right subtree; therefore $$ P*=RLINK(P). $$ The remaining case is $$ LLINK(P)=\Lambda,\qquad RTAG(P)=1....
TAOCP 2.2.3 Exercise 26
Section 2.2.3: Linked Allocation Exercise 26. [ 29 ] ( Subroutine allocation. ) Suppose that we have a tape containing the main subroutine library in relocatable form, for a 1960s-style computer installation. The loading routine wants to determine the amount of relocation for each subroutine used, so that it can make one pass through the tape to load the necessary routines. The problem is that some subroutines require others to...
TAOCP 2.2.3 Exercise 23
Section 2.2.3: Linked Allocation Exercise 23. [ 27 ] When the topological sort algorithm cannot proceed because it has detected a loop in the input (see step T8 ), it is usually of no use to stop and say, "There was a loop." It is helpful to print out one of the loops, thereby showing part of the input that was in error. Extend Algorithm T so that it will...
TAOCP 2.2.2 Exercise 17
Section 2.2.2: Sequential Allocation Exercise 17. [ 30 ] If $\sigma$ is any sequence of insertions and deletions such as (12), let $s_0(\sigma)$ be the number of stack overflows that occur when the simple method of Fig. 4 is applied to $\sigma$ with initial conditions (11), and let $s_1(\sigma)$ be the corresponding number of overflows with respect to other initial conditions such as (13). Prove that $s_0(\sigma) \le s_1(\sigma) +...
TAOCP 2.2.2 Exercise 8
Section 2.2.2: Sequential Allocation Exercise 8. [ 26 ] Explain how to modify (9), (10), and the repacking algorithms for the case that one or more of the lists is a queue being handled circularly as in (6a) and (7a). Verified: yes Solve time: 2m52s The key point of the exercise is that the global memory management (Algorithm G with rules (9), (10), and repacking) is unchanged in spirit: it...
TAOCP 2.2.2 Exercise 5
Section 2.2.2: Sequential Allocation Exercise 5. [ 35 ] The extension of MIX suggested in exercise 3 has an unfortunate restriction that " 7:7 " is not allowed in an indirectly addressed location. a) Give an example to indicate that, without this restriction, it would probably be necessary for the MIX hardware to be capable of maintaining a long internal stack of three-bit items. (This would be prohibitively expensive hardware,...
TAOCP 2.2.1 Exercise 14
Section 2.2.1: Stacks, Queues, and Deques Exercise 14. [ 26 ] Suppose you are allowed to use only stacks as data structures. How can you implement a queue efficiently with two stacks? The simplest and most natural way to keep a linear list inside a computer is to put the list items in consecutive locations, one node after the other. Then we will have $$ \operatorname{LOC}(X[j+1]) = \operatorname{LOC}(X[j]) + c,...
TAOCP 1.4.4 Exercise 16
Section 1.4.4: Input and Output Exercise 16. [ 29 ] Formulate the "green-yellow-red-purple" algorithm, suggested by Fig. 26, in the manner of the algorithms for multiple buffering given in the text, using three coroutines (one to control the input device, one for the output device, and one for the computation). Verified: no Solve time: 11m23s Setup The exercise asks for a formulation of the "green-yellow-red-purple" buffering scheme of Fig. 26...
TAOCP 1.4.3.2 Exercise 5
Section 1.4.3.2: Trace Routines Exercise 5. [ 28 ] In a manner similar to that used to solve the previous exercise, consider the situation in which two copies of the trace routine are placed in different places in memory, and each is set up to trace the other. What would happen? Verified: yes Solve time: 1m10s Setup Let $T_A$ and $T_B$ denote two physically distinct copies of the trace routine...
TAOCP 1.4.3.2 Exercise 2
Section 1.4.3.2: Trace Routines Exercise 2. [ 26 ] Modify the trace routine of the text so that before executing each program step it writes the following information on tape unit 0. Word 1, (0:2) field: location. Word 1, (4:5) field: register J (before execution). Word 1, (3:3) field: 2 if comparison is greater, 1 if equal, 0 if less; plus 8 if overflow is not on before execution. Word...
TAOCP 1.4.3.1 Exercise 6
Section 1.4.3.1: A MIX Simulator Exercise 6. [ 28 ] Write programs for the input-output operators JBUS , IOC , IN , OUT , and JRED , which are missing from the program in the text, allowing only units 16 and 18. Assume that the operations "read-card" and "skip-to-new-page" take $T = 10000u$, while "print-line" takes $T = 7500u$. [ Note: Experience shows that the JBUS instruction should be simulated...
TAOCP 1.3.3 Exercise 36
Section 1.3.3: Applications to Permutations Exercise 36. [ 27 ] Write a MIX subroutine for the algorithm in the answer to exercise 35, and analyze its running time. Compare it with the simpler method that goes from $\alpha\beta\gamma$ to $(\alpha\beta\gamma)^R = \gamma^R\beta^R\alpha^R$ to $\gamma\beta\alpha$, where $\sigma^R$ denotes the left-right reversal of the string $\sigma$. Verified: no Solve time: 14m48s Setup Let $x_0x_1\ldots x_{l+m+n-1} = \alpha\beta\gamma$, where $\alpha = x_0\ldots x_{l-1}$,...
TAOCP 1.3.1 Exercise 26
Section 1.3.1: Description of MIX Exercise 26. [ 32 ] This problem is to write a card-loading routine. Every computer has its own peculiar "bootstrapping" problems for getting information initially into the machine and for starting a job correctly. In MIX's case, the contents of a card can be read only in character code, and the cards that contain the loading program itself must meet this restriction. Not all possible...
TAOCP 1.3.1 Exercise 25
Section 1.3.1: Description of MIX Exercise 25. [ 30 ] Suppose that the manufacturer of MIX wishes to come out with a more powerful computer ("Mixmaster"?), and he wants to convince as many as possible of those people now owning a MIX computer to invest in the more expensive machine. He wants to design this new hardware to be an extension of MIX, in the sense that all programs correctly...
TAOCP 1.3.1 Exercise 23
Section 1.3.1: Description of MIX Exercise 23. [ 27 ] Location 0200 contains a word + a b c d e write two programs that compute the "reflected" word + e d c b a and halt with the result in register A . One program should do this without using MIX's ability to load and store partial fields of words. Both programs should take the minimum possible number of...
TAOCP 1.3.1 Exercise 22
Section 1.3.1: Description of MIX Exercise 22. [ 28 ] Location 2000 contains an integer number, X . Write two programs that compute X^{13} and halt with the result in register A . One program should use the minimum number of MIX memory locations; the other should require the minimum execution time possible. Assume that X^{13} fits into a single word. Verified: no Solve time: 4m39s Solution Location $2000$ initially...
TAOCP 1.3.1 Exercise 17
Section 1.3.1: Description of MIX Exercise 17. [ 26 ] This is the same as the previous exercise, except that locations 0000 through N , inclusive, are to be set to zero, where N is the current contents of rI2 . Your programs (a) and (b) should work for any value 0 \le N \le 2999 ; they should start in location 3000 . Verified: yes Solve time: 3m23s The...
TAOCP 1.2.8 Exercise 38
Section 1.2.8: Fibonacci Numbers Exercise 38. [ 35 ] Write a computer program that plays the game described in the previous exercise and that plays optimally. Verified: no Solve time: 2m16s The previous solution fails because it assumes the Fibonacci structure of winning play without proving it. The corrected solution must derive optimality from first principles of the game and then justify the greedy Fibonacci move rule. Game definition Let...