#hard
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.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: 5m49s Setup We seek all integers $n < 10^9$...
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: 5m18s Corrected Solution We restate the problem in the...
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.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 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.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 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 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 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.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 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 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.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.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 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.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.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: 3m21s The reviewer’s objections concern only the missing computational execution...
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: 1m04s Setup Let $F$ be the clause set at step L3, and let Algorithm X have produced...
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: 3m41s Corrected solution We justify step X9 by reconstructing the missing link between the condition $w=0$ in (72) and the existence of a positive autarky extension. The key point is that $w=0$ implies the...
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: 2m37s The previous maximality argument fails because it tries to compare an...
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: yes Solve time: 1m10s Setup Let $F = {C_1,\dots,C_m}$ be a formula in CNF over variables ${x_1,\dots,x_n}$, and let literals be ordered by variable index with complements $\bar{l}$. In step X4 a lookahead forest is constructed in order to record consequences of tentative assignments, using unit propagation as...
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: 1m03s Setup Let the current instance of SAT in Algorithm L consist of a family $F$ of clauses over variables $x_1,\ldots,x_n$. At any stage of the computation, some clauses have been deleted and some literals...
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: 3m43s The previous construction fails because it makes the formula satisfied at the root, so Algorithm D halts immediately. To obtain exponential behavior, we must construct a satisfiable 2CNF...
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: 3m48s The...
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: yes Solve time: 2m26s The flaw in the previous solution is the attempt to force first-found optimality via local ordering of option numbers. That does not interact correctly with Algorithm C’s adaptive choice of items, so...
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: 1m14s Setup Two independent instances are given. Each instance consists of nine cards, and the task is to place them in a $3 \times 3$ grid...
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: 1m28s Setup Let the three puzzles in Figure 60 be denoted by $(a)$, $(b)$, and $(c)$. Each is an exact cover instance derived from a Sudoku-like constraint system in which the regions are hexomino-shaped rather than standard $3\times 3$ boxes. A complete solution requires the explicit specification of...
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: 3m12s The previous solution fails at a single foundational point: it treats the omission of the instances in (34) from the prompt as mathematical information. In TAOCP, it is not. The instances are fixed, finite inputs defined earlier in the text, and all...
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: 4m17s The previous solution failed because it attempted to introduce an additional pruning condition based on an informal notion...
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: yes Solve time: 1m22s Setup Let the hitori instance consist of an $m \times n$ array...
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: 3m03s The previous argument fails because it confuses “cell value equals clue” with Kakuro’s actual constraint system. In Kakuro, each white cell contains a digit in ${1,\dots,9}$,...
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: 3m28s The previous solution fails because it replaces the actual constraint analysis of the given Kakuro instance with an unproved claim of uniqueness. A correct argument must model the six unspecified clues as...
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: 1m38s Setup Let Algorithm C be the exact cover procedure derived from Algorithm X in Section 7.2.2.1, applied...
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: yes Solve time: 1m13s Setup A $10 \times 10$ Hidato puzzle assigns each cell either blank or a number from ${1,2,\dots,100}$ such that every number in this set appears exactly once in the completed grid. A clue fixes the value...
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: 1m13s Setup A Hidato puzzle on a $6\times 6$ grid is a labeling of the $36$ cells by the integers $1,2,\dots,36$ such that consecutive integers occupy adjacent cells (adjacency in the king sense,...
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: 5m13s The previous solution fails because it incorrectly restricts KenKen clues, ignores the need for a defined ordering of clues, and introduces an irrelevant Latin-square...
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: 2m57s The review correctly identifies two fatal flaws...
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: 4m51s The previous solution fails because it never works on the actual solution set $S$, and instead replaces it with an artificial labeling model that does...
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: 1m57s Let Exercise 382 provide a decomposition principle in the following form: there exist three ordered sequences of positive integers $$ (a_1,\dots,a_{23}),\quad (b_1,\dots,b_{23}),\quad (c_1,\dots,c_{23}), $$ such that all 69...
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: 3m31s Working
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: 2m42s The flaw in the previous solution is not...
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 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.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: 3m23s A correct solution must actually perform a complete...
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: yes Solve time: 2m34s We recompute the number of base placements using the orbit–stabilizer theorem under the action of the proper rotation group of the cube, which has order $24$. A base placement of a polycube $P$ is an orbit...
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: 2m14s The core mistake in the proposed encoding is the failure to represent the two tilings as two independent exact-cover constraints. In exact cover, every item must be covered exactly...
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 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 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 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 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 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...