#project
TAOCP 5.4.4 Exercise 10
Section 5.4.4: Reading Tape Backwards Exercise 10. [ 41 ] Prepare a table of the exact values of $K_T(n)$, using a computer. Verified: no Solve time: 29m26s Setup In the theory of optimal merge patterns developed by Karp in this section, (K_{T}(n)) is the maximum number of initial runs that can be sorted in (n) merge phases using (T) tapes when reading backwards. The lower bound proven in exercise 9...
TAOCP 5.3.1 Exercise 28
Section 5.3.1: Minimum-Comparison Sorting Exercise 28. [ 40 ] Write a MIX program that sorts five one-word keys in the minimum possible amount of time, and halts. (See the beginning of Section 5.2 for ground rules.) Verified: no Solve time: 11m31s Setup The exercise asks for a MIX program that sorts five one‑word keys in as few machine cycles as possible. The ground rules of Section 5.2 are followed: the...
TAOCP 5.4.4 Exercise 14
Section 5.4.4: Reading Tape Backwards Exercise 14. [ 40 ] Devise an algorithm that carries out the preorder merge without explicitly representing the tree in steps P2 and P3, using only $O(\log S)$ words of memory to control the merging pattern. Verified: no Solve time: 6m07s Setup The preorder merge algorithm (Algorithm P in the text) controls an optimal read‑backward merge pattern using Karp’s tree representation. The merge tree (...
TAOCP 5.3.4 Exercise 54
Section 5.3.4: Networks for Sorting Exercise 54. [ 42 ] Study the properties of sorting networks made from $m$-sorter modules instead of 2-sorters. (For example, G. Shapiro has constructed the network which sorts 16 elements using fourteen 4-sorters. Is this the best possible? Prove that $m^2$ elements can be sorted with at most 16 levels of $m$-sorters, when $m$ is sufficiently large.) Verified: no Solve time: 21m28s Setup An (m)-sorter...
TAOCP 5.3.4 Exercise 38
Section 5.3.4: Networks for Sorting Exercise 38. ▶ [ 43 ] Let $N = \binom{n}{2}$. Find a one-to-one correspondence between Young tableaux of shape $(n-1, n-2, \ldots, 1)$ and primitive sorting networks $[i_1:i_1+1] \ldots [i_N:i_N+1]$. [Consequently by Theorem 5.1.4H there are exactly $$\frac{N!}{1^{n-1} 3^{n-2} 5^{n-3} \ldots (2n-3)^1}$$ such sorting networks.] [ Hint: Exercise 36(c) shows that primitive networks without redundant comparators correspond to paths from $1 2 \ldots n$ to...
TAOCP 5.3.1 Exercise 19
Section 5.3.1: Minimum-Comparison Sorting Exercise 19. [ 40 ] Experiment with the following heuristic rule for deciding which pair of elements to compare next while designing a comparison tree: At each stage of sorting ${K_1, \ldots, K_n}$, let $u_i$ be the number of keys known to be $\le K_i$ as a result of the comparisons made so far, and let $v_i$ be the number of keys known to be $\ge...
TAOCP 5.2.5 Exercise 13
Section 5.2.5: Sorting by Distribution Exercise 13. [ 40 ] Implement the internal sorting method suggested in the text at the close of this section, producing a subroutine that sorts random data in $O(N)$ units of time with only $O(\sqrt{N})$ additional memory locations. Verified: no Solve time: 8m40s Setup We consider the problem of sorting (N) records with keys that are two-digit numbers in base (M = \lceil \sqrt{N} \rceil)....
TAOCP 5.2.4 Exercise 18
Section 5.2.4: Sorting by Merging Exercise 18. [ 40 ] (M. A. Kronrod.) Given a file of $N$ records containing only two runs, $$K_1 \le \cdots \le K_M \quad \text{and} \quad K_{M+1} \le \cdots \le K_N,$$ is it possible to sort the file with $O(N)$ operations in a random-access memory, using only a small fixed amount of additional memory space regardless of the sizes of $M$ and $N$? (All of...
TAOCP 5.2.3 Exercise 31
Section 5.2.3: Sorting by Selection Exercise 31. [ 37 ] (J. W. J. Williams.) Show that if two heaps are placed "back to back" in a suitable way, it is possible to maintain a structure in which either the smallest or the largest element can be deleted at any time in $O(\log n)$ steps. (Such a structure may be called a priority deque .) Verified: no Solve time: 8m57s Setup...
TAOCP 5.2.1 Exercise 29
Section 5.2.1: Sorting by Insertion Exercise 29. [ 40 ] For $N = 1000$ and various values of $t$, find empirical values of $h_{t-1}, \ldots, h_1, h_0$ for which the average number of moves, $B_{\text{ave}}$, is as small as you can make it. Verified: no Solve time: 1m19s Setup Let $N=1000$. We seek increments $h_{t-1},\dots ,h_0$ for Algorithm D (shellsort) that minimise the average number of moves $B_{\text{ave}}$, where $B$...
TAOCP 7.2.2.2 Exercise 85
Section 7.2.2.2: Satisfiability Exercise 85. ▶ [ 39 ] A Garden of Eden is a state of Life that has no predecessor. a) If an array of 92 cells illustrated here occurs anywhere within a bitmap $X$, verify that $X$ is a Garden of Eden. (The gray cells can be either dead or alive.) b) The orphan pattern found, with a SAT solver's help, is the smallest that is currently...
TAOCP 7.2.2.2 Exercise 76
Section 7.2.2.2: Satisfiability Exercise 76. [ 41 ] Construct a mobile Life oscillator of period 3. Verified: no Solve time: 3m40s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one...
TAOCP 7.2.2.2 Exercise 68
Section 7.2.2.2: Satisfiability Exercise 68. [ 39 ] $[39]$ Find a maximum-length mobile path in which 6 to 10 cells are always alive. Verified: no Solve time: 3m40s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses...
TAOCP 7.2.2.2 Exercise 525
Section 7.2.2.2: Satisfiability Exercise 525. ▶ [ 40 ] Find the most difficult 3SAT problem you can that has at most 100 variables. Verified: no Solve time: 3m43s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses...
TAOCP 7.2.2.2 Exercise 51
Section 7.2.2.2: Satisfiability Exercise 51. [ 40 ] $[40]$ Study the behavior of SAT solvers on the problem of finding a small number of test patterns for all of the detectable single-stuck-at faults of the circuit $\mathit{prod}(32, 32)$. Can a complete set of patterns for this large circuit be discovered "automatically" (without relying on number theory)? Verified: no Solve time: 2m45s Solution In the direct encoding, each variable $x_i$ is...
TAOCP 7.2.2.2 Exercise 412
Section 7.2.2.2: Satisfiability Exercise 412. [ 40 ] [40] Experiment with the encoding of somewhat large numbers by using a radix-$d$ representation in which each digit has the order encoding. Verified: no Solve time: 3m59s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$....
TAOCP 7.2.2.2 Exercise 378
Section 7.2.2.2: Satisfiability Exercise 378. [ 39 ] (Blocked clauses.) A clause $C = "l_1 \vee \cdots \vee l_t \vee l_1 \vee \cdots \vee l_k"$ is said to be blocked by the literal $l$ if every clause that contains $\bar{l}$ also contains either $l_1$ or $\cdots$ or $l_k$. Exercise 161(b) proves that clause $C$ can be removed without making an unsatisfiable problem satisfiable. Show that this transformation requires an erp...
TAOCP 7.2.2.2 Exercise 314
Section 7.2.2.2: Satisfiability Exercise 314. [ 36 ] (H. H. Hoos, 1998.) If the given clauses are satisfiable, and if $p > 0$, can there be an initial $x$ for which Algorithm W always loops forever? Verified: no Solve time: 11m23s Correctness The proposed solution does not answer Exercise 7.2.2.2.313. The exercise asks for a proof about Algorithm W. Specifically, it asks to show two facts about a cost-free literal...
TAOCP 7.2.2.2 Exercise 20
Section 7.2.2.2: Satisfiability Exercise 20. [ 40 ] [40] In exactly how many ways can McGregor's map (Fig. 33) be four-colored? Verified: no Solve time: 6m04s Correctness The proposed solution identifies the correct reformulation of the problem. A Boolean function on four variables is representable in $3$CNF exactly when its set of falsifying assignments is a union of subcubes of dimension at least $1$. The conversion between clauses and unions...
TAOCP 7.2.2.1 Exercise 91
Section 7.2.2.1: Dancing Links Exercise 91. [ 40 ] [40] For given $W$, find the largest $p$ such that $\text{WORDS}(W)$ supports a word stair of period $p$. [There are two questions for each $W$, examining stairs to the left, right.] Verified: no Solve time: 3m53s Solution A Boolean function on variables $x_1,\ldots,x_4$ is represented by a $3$CNF formula exactly when its set of falsifying assignments is a union of subcubes...
TAOCP 7.2.2.2 Exercise 173
Section 7.2.2.2: Satisfiability Exercise 173. [ 40 ] Use an implementation of Algorithm L to experiment with random 3SAT problems such as $rand(3, 2062, 500, 314)$. Examine the effects of such things as (i) disabling double lookahead; (ii) disabling "wraparound," by changing the cases $j = S$ and $j = S$ in X7 and Y4 so that they simply go to X6 and Y3; (iii) disabling the lookahead forest, by...
TAOCP 7.2.2.2 Exercise 111
Section 7.2.2.2: Satisfiability Exercise 111. [ 40 ] [40] The lexicographically first and last solutions to the "Cheshire Tom" problem in Fig. 37 are based on the top-to-bottom-and-left-to-right ordering of pixels. Experiment with other pixel orderings, for example, try bottom-to-top-and-right-to-left. Verified: no Solve time: 4m39s Solution The exercise is not asking for a new mathematical characterization of the Cheshire Tom solutions. It asks for an experiment showing how the choice...
TAOCP 7.2.2.1 Exercise 52
Section 7.2.2.1: Dancing Links Exercise 52. [ 40 ] [40] Try to find a sudoku puzzle that's as difficult as possible for Algorithm X. Verified: no Solve time: 2m12s Solution Algorithm X does not have a single intrinsic running time on a sudoku instance. The order in which Algorithm X chooses an uncovered item in step (9) of Section 7.2.2.1 affects the entire search tree. Therefore the exercise must be...
TAOCP 7.2.2.1 Exercise 450
Section 7.2.2.1: Dancing Links Exercise 450. [ 42 ] Use Algorithm X to solve the "tot tibi sunt dotes" problem of Section 7.2.1.7. We should "play up" the role of play. , FRANCIS EDWARD SU, "Mathematics for Human Flourishing" (2017) Verified: no Solve time: 2m16s Setup The problem of Section 7.2.1.7 is to arrange the eight words $$ \textit{Tot},\quad \textit{tibi},\quad \textit{sunt},\quad \textit{dotes},\quad \textit{Virgo},\quad \textit{quot},\quad \textit{sidera},\quad \textit{caelo} $$ so that the...
TAOCP 7.2.2.1 Exercise 449
Section 7.2.2.1: Dancing Links Exercise 449. [ 40 ] ( Hidden nuggets. ) Johan de Ruiter noticed in 2017 that George Orwell had included a valid hitori puzzle in his novel Nineteen Eighty-Four (part 2, chapter 9): Did Homer, Shakespeare, Tolstoy, and others also create hitori puzzles accidentally? Verified: no Solve time: 2m11s Setup A hitori puzzle is a rectangular array of symbols together with the rule that some cells...
TAOCP 7.2.2.1 Exercise 446
Section 7.2.2.1: Dancing Links Exercise 446. ▶ [ 44 ] The digits of $e$, $2.71828182845904523\ldots$, are well known to have a curious repeating pattern. In fact, the first 25 digits actually define a valid $5 \times 5$ hitori puzzle! What is the probability that a random $5 \times 5$ array of decimal digits will have that property? What about actual octal digits? Hexadecimal digits? Verified: no Solve time: 1m43s The...
TAOCP 7.2.2.1 Exercise 434
Section 7.2.2.1: Dancing Links Exercise 434. [ 39 ] [39] Exactly how many kakuro diagrams are possible in a $9 \times 9$ grid? (Every row and every column should contain at least one block of empty cells, except that the topmost row and leftmost column are completely black. All blocks must have length $\ge 2$. Empty cells needn't be rookwise connected.) What is the maximum number of blocks? Verified: no...
TAOCP 7.2.2.1 Exercise 426
Section 7.2.2.1: Dancing Links Exercise 426. ▶ [ 37 ] [37] Obtain a valid masyu puzzle from diagram (i) below by changing each '○' clue into either '○' or '●': Verified: no Solve time: 4m18s The exercise refers to a concrete diagram, namely diagram (i), whose initial arrangement of white clues must be modified. The required answer is an explicit assignment of each given $\circ$ to either $\circ$ or $\bullet$...
TAOCP 7.2.2.1 Exercise 424
Section 7.2.2.1: Dancing Links Exercise 424. [ 36 ] Make an exhaustive study of $6 \times 6$ masyu, and gather whatever statistics you think are particularly interesting. For example, how many of the $(1.5 \times 10^8)^?$ ways to place white or black clues lead to a valid puzzle? Which of the valid puzzles have the fewest clues? the most clues? the shortest loops? the longest loops? only white clues? only...
TAOCP 7.2.2.1 Exercise 353
Section 7.2.2.1: Dancing Links Exercise 353. [ 39 ] [39] A weak polycube is a set of cubes that are loosely connected via common edges, not necessarily via common faces. In other words, we consider cubes to be adjacent when their centers are at most $\sqrt{2}$ units apart; up to 18 neighbors are possible. Find all the weak polycubes of size 3, and pack them into a symmetrical container. Verified:...
TAOCP 7.2.2.1 Exercise 321
Section 7.2.2.1: Dancing Links Exercise 321. [ 42 ] (T. H. O'Beirne, 1962.) In how many ways can a square be formed from the eight one-sided tetraboloes and their mirror images? Verified: no Solve time: 1m38s A rigorous solution would have to: Define the $4\times4$ h-unit square as the exact-cover universe. Generate every legal placement of each of the sixteen oriented tetraboloes. Construct the exact-cover matrix whose columns are the...
TAOCP 7.2.2.1 Exercise 299
Section 7.2.2.1: Dancing Links Exercise 299. [ 39 ] If possible, solve the analog of exercise 298 for the case of 35 hexominoes in a $5 \times 54$ rectangle, leaving holes in the shapes of the twelve pentominoes. Verified: no Solve time: 2m10s Setup Let $R$ be the $5\times54$ rectangle. Its area is $5\cdot54=270.$ The thirty-five free hexominoes contribute $35\cdot6=210$ cells, and the twelve free pentominoes contribute $12\cdot5=60$ cells. Hence...
TAOCP 7.2.2.1 Exercise 296
Section 7.2.2.1: Dancing Links Exercise 296. [ 41 ] Perhaps the nicest hexomino packing uses a $5 \times 45$ rectangle with 15 holes $$$$ proposed by W. Stead in 1954. In how many ways can the 35 hexominoes fill it? Verified: no Solve time: 1m38s Setup Exercise 7.2.2.1.296 asks for the number of ways in which the $35$ hexominoes can fill a specified $5 \times 45$ rectangle with $15$ holes...
TAOCP 7.2.2.1 Exercise 295
Section 7.2.2.1: Dancing Links Exercise 295. [ 41 ] For which values of $m$ can the hexominoes be packed into a box like this? $$$$ Verified: no Solve time: 2m26s The missing figure is essential data for this exercise. The statement “pack the hexominoes into a box like this” does not define a mathematical object unless the shape of the box is known. Therefore the corrected solution cannot derive a...
TAOCP 7.2.2.1 Exercise 293
Section 7.2.2.1: Dancing Links Exercise 293. [ 41 ] (Frans Hansson, 1947.) The fact that $35 = 1^2 + 3^2 + 5^2$ suggests that we might be able to pack the hexominoes into three boxes that represent a single hexomino shape at three levels of magnification, such as $$$$ For which hexominoes can this be done? Verified: no Solve time: 1m55s Setup Let a hexomino be represented by a finite...
TAOCP 7.2.2.1 Exercise 279
Section 7.2.2.1: Dancing Links Exercise 279. [ 40 ] [40] (H. D. Benjamin, 1948.) Show that the twelve pentominoes can be wrapped around a cube of size $\sqrt{10} \times \sqrt{10} \times \sqrt{10}$. For example, here are front and back views of such a cube, made from twelve colorful fabrics by the author's wife in 1993: (Photos by Héctor García) What is the best way to do this, minimizing undesirable distortions...
TAOCP 7.2.2.1 Exercise 23
Section 7.2.2.1: Dancing Links Exercise 23. [ 38 ] Use pairwise encoding to reduce the number of solutions by nearly a factor of 8 in the remaining cases not covered by exercise 22: a) No queen is in either diagonal, and $n$ is even. b) A queen is in the center of the board, and $n$ is odd. Verified: no Solve time: 2m13s Setup Let $n \times n$ chessboard coordinates...
TAOCP 7.2.2.1 Exercise 173
Section 7.2.2.1: Dancing Links Exercise 173. ▶ [ 39 ] [39] [ Knight and bishop sudoku. ] Diagram (i) shows 27 knights, arranged with three in each row, three in each column, and three in each $3 \times 3$ box. Each of them has been labeled with the number of others that are a knight's move away. Diagram (ii) shows 8 of them, from which the positions of the other...
TAOCP 7.2.2.1 Exercise 132
Section 7.2.2.1: Dancing Links Exercise 132. [ 40 ] (W. E. Philpott, 1971.) There are $4624 = 68^2$ tiles in a set like (§8), but it uses 24 different colors instead of 4. Can they be assembled into an equilateral triangle of size 68, with constant color on the boundary and with matching edges inside? Verified: no Solve time: 5m09s Setup We seek all integers $n < 10^9$ such that...
TAOCP 7.2.2 Exercise 69
Section 7.2.2: Backtracking Exercise 69. [ 41 ] Is there a puzzle like exercise 68 whose clues contain more than 32 digits of $\pi$? Verified: no Solve time: 5m18s 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.6 Exercise 65
Section 7.2.1.6: Generating All Trees Exercise 65. [ 38 ] [38] Generalize Rémy's algorithm (Algorithm R) to $t$-ary trees. Verified: no Solve time: 4m55s The earlier solution correctly described the growth process and the history-based bijection, but it made an unjustified leap from labeled histories to uniformity over unlabeled trees. The reviewer’s objection is decisive: the number of valid creation-time labelings depends on the tree shape, so one cannot cancel...
TAOCP 7.2.2 Exercise 31
Section 7.2.2: Backtracking Exercise 31. [ 39 ] [39] (Charles Babbage, 1864.) Do any of the symmetric $5 \times 5$ word squares also have valid words on both diagonals? Verified: no Solve time: 4m54s 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...
TAOCP 7.2.1.6 Exercise 124
Section 7.2.1.6: Generating All Trees Exercise 124. ▶ [ 40 ] [40] Experiment with methods for drawing extended binary trees that are inspired by simple models from nature. For example, we can assign a value $v(x)$ to each node $x$, called its Horton–Strahler number , as follows: Each external (leaf) node has $v(x) = 0$; an internal node with children $(l, r)$ has $v(x) = \max(v(l), v(r)) + [v(l) =...
TAOCP 7.2.1.6 Exercise 100
Section 7.2.1.6: Generating All Trees Exercise 100. [ 40 ] Implement the text's "Algorithm S*" for revolving-door generation of all spanning trees, by combining Algorithm S with the ideas of exercise 99. Verified: no Solve time: 5m38s 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...
TAOCP 7.2.1.1 Exercise 83
Section 7.2.1.1: Generating All n-Tuples Exercise 83. [ 41 ] [41] Can four balanced 8-bit Gray cycles cover all edges of the 8-cube? 316 COMBINATORIAL SEARCHING 7.2.1.1 Verified: no Solve time: 4m43s Solution Represent each domino ${i,j}$, $0 \le i \le j \le 6$, as an undirected edge between vertices $i$ and $j$ in a multigraph $G$ on vertex set ${0,1,\dots,6}$, with one loop at each vertex $i$ corresponding to...
TAOCP 7.2.1.1 Exercise 66
Section 7.2.1.1: Generating All n-Tuples Exercise 66. [ 40 ] [40] Is there a perfect Beckett–Gray pattern for 8 actors? Verified: no Solve time: 4m34s The previous solution failed for two independent reasons: a wrong state-space count and an imprecise formulation of what is actually being searched. Both can be repaired, but doing so forces a cleaner separation between the Beckett process , the state graph , and the subset...
TAOCP 7.2.1.1 Exercise 43
Section 7.2.1.1: Generating All n-Tuples Exercise 43. [ 41 ] [41] Determine d(6), the number of 6-bit Gray cycles. (See (26).) Verified: no Solve time: 4m Setup Let the 8 variables be indexed by $G={0,1}^3$, written $i=(i_1,i_2,i_3)$ with binary addition $i\oplus j$. Let $(a_i) {i\in G}$ and $(A_i) {i\in G}$ be real numbers. Let $H_3=(h_{ij})_{i,j\in G}$ be the Walsh matrix of order $8$, defined by $$ h_{ij}=(-1)^{i\cdot j}, \qquad i\cdot...
TAOCP 7.2.1.1 Exercise 100
Section 7.2.1.1: Generating All n-Tuples Exercise 100. [ 40 ] [40] Do the de Bruijn cycles of exercise 97 provide a useful source of pseudo- random bits when n is large? Verified: no Solve time: 8m03s Setup Let $f_n(k)$ be the binary de Bruijn cycle of order $n$ constructed in Exercise 97, so that the infinite periodic sequence $$ f_n(0), f_n(1), \ldots, f_n(2^n-1) $$ contains every $n$-bit string exactly once...
TAOCP 7.1.4 Exercise 93
Section 7.1.4: Binary Decision Diagrams Exercise 93. [ 36 ] [36] Given a graph G on the vertices {1, . . . , n}, construct Boolean functions f and g with the property that an approximating function ˆf exists as in exercise 91 with small B( ˆf) if and only if G can be 3-colored. (Hence the task of minimizing B( ˆf) is NP-complete.) Verified: no Solve time: 12m07s Solution...
TAOCP 7.1.4 Exercise 257
Section 7.1.4: Binary Decision Diagrams Exercise 257. [ 40 ] [40] (S. Minato.) Explore the use of ZDDs to represent polynomials with nonneg- ative integer coefficients. Hint: Any such polynomial in x, y, and z can be regarded as a family of subsets of {2, 22, 24, . . . , x, x2, x4, . . . , y, y2, y4, . . . , z, z2, z4, . ....
TAOCP 1.4.4 Exercise 17
Section 1.4.4: Input and Output Exercise 17. [ 40 ] Adapt the multiple-buffering algorithm to pooled buffers; build in methods that keep the process from slowing down, due to too much anticipated input. Try to make the algorithm as elegant as possible. Compare your method to nonpooling methods, applied to real-life problems. Verified: no Solve time: 2m26s Corrected Solution The error in the proposed solution stems from an incorrect output...
TAOCP 6.5 Exercise 5
Section 6.5: Retrieval on Secondary Keys Exercise 5. [ 40 ] [40] Experiment with various ways to avoid the redundancy of text when using Harrison’s technique for substring searching. [M20] The total number of m-bit basic queries with t bits specified is s = (")2". If a combinatorial hashing function like that in (13) converts these queries into 1, lz, ..., ls locations, respectively, L(t) = (14 +l2 +---+1s)/s is...
TAOCP 5.4.6 Exercise 12
Section 5.4.6: Practical Considerations for Tape Merging Exercise 12. [ 40 ] [40] Consider partitioning six tapes into three pairs of tapes, with each pair playing the role of a single tape in a polyphase merge with T = 3. One tape of each pair will contains blocks 1,3,5,... and the other tape will contain blocks 2, 4,6,...; in this way we can essentially have two input tapes and two...
TAOCP 5.4.2 Exercise 30
Section 5.4.2: The Polyphase Merge Exercise 30. [ 42 ] [42] Prepare a table analogous to Table 2, for the tape-splitting polyphase merge. Verified: no Solve time: 1m30s Setup Let $T=P+1\ge 3$ tapes be given. Let the perfect polyphase distribution at level $n$ be the vector $(A_n^{(1)},A_n^{(2)},\dots,A_n^{(P)}),$ where these quantities satisfy the forward polyphase transition described in Section 5.4.2, with total size $t_n = \sum_{k=1}^{P} A_n^{(k)}.$ The table in the...
TAOCP 5.4.9 Exercise 14
Section 5.4.9: Disks and Drums Exercise 14. [ 40 ] [40] Using the square root method of buffer allocation, the seek time for the merge pattern in Fig. 92 would be proportional to (/2 +VJ744VJ14vV1i4+ v8)? + (VI + V1+ V2)" + (VI + V24+ V1+ V4)" + (V1+ VI4+ V2)’; this is the sum, over each internal node, of (./ny + +++ +Vmm + Vni +++: +!m); where that...
TAOCP 6.2.2 Exercise 9
Section 6.2.2: Binary Tree Searching Exercise 9. [ 41 ] [41] We have proved that tree search and insertion requires only about 21In N comparisons when the keys are inserted in random order; but in practice, the order may not be random. Make empirical studies to see how suitable tree insertion really is for symbol tables within a compiler and/or assembler. Do the identifiers used in typical large programs lead...
TAOCP 6.2.2 Exercise 29
Section 6.2.2: Binary Tree Searching Exercise 29. [ 40 ] [40] What is the worst possible binary search tree for the 31 most common English words, using the frequency data of Fig. 12? Verified: no Solve time: 4m36s Corrected Solution Let the 31 keys be the most common English words in Fig. 12, ordered lexicographically as $$ K_1 < K_2 < \cdots < K_{31}, $$ with positive successful-search frequencies $f_1,\dots,f_{31}$....
TAOCP 5.4.8 Exercise 3
Section 5.4.8: Two-Tape Sorting Exercise 3. [ 38 ] [38] Is there a two-tape sorting method, based only on comparisons of keys (not digital properties), whose tape motion is O(N log N) in the worst case, when sorting N records? [Quicksort achieves this on the average, but not in the worst case, and the Hennie, Stearns method (Fig. 86) achieves O(N (log N)?).] Verified: yes Solve time: 50s Setup Let...
TAOCP 5.3.2 Exercise 14
Section 5.3.2: Minimum-Comparison Merging Exercise 14. [ 41 ] [41] (F. K. Hwang.) Let $h_{3k} = \lfloor 3 \cdot 2^k \rfloor - 1$, $h_{3k+1} = h_{3k} + 3 \cdot 2^{k-1}$, $h_{3k+2} = \lfloor 2^k - 2 \rfloor$ for $k > 3$, and let the initial values be defined so that $$(h_0, h_1, h_2, \ldots) = (1, 1, 2, 2, 3, 4, 5, 7, 9, 11, 14, 18, 23, 29, 38,...
TAOCP 4.6.4 Exercise 42
Section 4.6.4: Evaluation of Polynomials Exercise 42. [ 36 ] [36] (M. Paterson and L. Stockmeyer.) (a) Prove that a polynomial chain with $m \ge 2$ chain multiplications has at most $m^2 + 1$ degrees of freedom. (b) Show that for all $n \ge 2$ there exist polynomials of degree $n$, all of whose coefficients are 0 or 1, that cannot be evaluated by any polynomial chain with fewer than...
TAOCP 4.5.4 Exercise 39
Section 4.5.4: Factoring into Primes Exercise 39. [ 40 ] Many primes $p$ have the property that $2p + 1$ is also prime; for example, $5 \to 11 \to 23 \to 47$. More generally, say that $q$ is a successor of $p$ if $p$ and $q$ are both prime and $q = 2^k p + 1$ for some $k \ge 0$. For example, $2 \to 3 \to 7 \to 29...
TAOCP 4.4 Exercise 16
Section 4.4: Radix Conversion Exercise 16. [ 41 ] Construct a fast linear iterative array for radix conversion from decimal to binary (see Section 4.3.3E). Verified: yes Solve time: 2m12s Setup Let $$ u=(u_m u_{m-1}\ldots u_1u_0)_{10} $$ be the decimal number to be converted into binary notation. Exercise 4.3.3E asks for a linear iterative array, therefore the computation must be organized as a sequence of identical cells through which information...
TAOCP 4.3.2 Exercise 1
Section 4.3.2: Modular Arithmetic Exercise 1. [ 39 ] Find all integers $u$ that satisfy all of the following conditions: $u \bmod 7 = 1$, $u \bmod 11 = 0$, $u \bmod 13 = 5$, $0 \le u < 1000$. Verified: yes Solve time: 17m17s Setup Find all integers $u$ satisfying $$ u \equiv 1 \pmod 7, \qquad u \equiv 0 \pmod{11}, \qquad u \equiv 5 \pmod{13}, $$ with $$...
TAOCP 4.3.1 Exercise 34
Section 4.3.1: The Classical Algorithms Exercise 34. [ 40 ] [40] Develop a set of computer subroutines for doing the four arithmetic operations on arbitrary integers, putting no constraint on the size of the integers except for the implicit assumption that the total memory capacity of the computer should not be exceeded. (Use linked memory allocation, so that no time is wasted in finding room to put the results.) Verified:...
TAOCP 4.3.1 Exercise 35
Section 4.3.1: The Classical Algorithms Exercise 35. [ 40 ] [40] Develop a set of computer subroutines for "decuple-precision floating point" arithmetic, using excess 0, base $b$, nine-place floating point number representation, where $b$ is the computer word size, and allowing a full word for the exponent. (Thus each floating point number is represented by two consecutive words, and all scaling is done by moving full words instead of by...
TAOCP 4.3.1 Exercise 16
Section 4.3.1: The Classical Algorithms Exercise 16. [ 39 ] ( Short division. ) Design an algorithm that divides a nonnegative $n$-place integer $(.u_1 u_2 \ldots u_n) b$ by $v$, where $v$ is a single-precision number (that is, $0 < v < b$), producing the quotient $(.w {n-1} \ldots w_1 w_0)_b$ and remainder $r$. Verified: yes Solve time: 6m02s Solution to Exercise 4.3.1.16 We are asked to design an algorithm...
TAOCP 4.2.1 Exercise 17
Section 4.2.1: Single-Precision Calculations Exercise 17. [ 40 ] (John Cocke.) Explore the idea of extending the range of floating point numbers by defining a single-word representation in which the precision of the fraction decreases as the magnitude of the exponent increases. Verified: yes Solve time: 4m05s Corrected Solution The goal is to design a single-word floating-point representation in which the exponent range increases as its magnitude increases, while the...
TAOCP 3.3.2 Exercise 6
Section 3.3.2: Empirical Tests Exercise 6. [ 40 ] (H. Geiringer.) A frequency count of the first 2000 decimal digits in the representation of $e = 2.71828\ldots$ gave a $\chi^2$ value of 1.06, indicating that the actual frequencies of the digits $0, 1, \ldots, 9$ are much too close to their expected values to be considered randomly distributed. (In fact, $\chi^2 \le 1.15$ with probability 99.9 percent.) The same test...
TAOCP 3.3.1 Exercise 24
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 24. ▶ [ 40 ] [40] Experiment with various probability distributions $(p, q, r)$ on three categories, where $p + q + r = 1$, by computing the exact distribution of the chi-square statistic $V$ for various $n$, thereby determining how accurate an approximation the chi-square distribution with two degrees of freedom really is. Verified: yes Solve time: 2m01s Setup...
TAOCP 3.2.2 Exercise 29
Section 3.2.2: Other Methods Exercise 29. ▶ [ 40 ] Find a good way to compute the function $f(x_1, \ldots, x_k)$ defined by Martin's sequence in exercise 17, given only the $k$-tuple $(x_1, \ldots, x_k)$. Verified: yes Solve time: 14m36s Exercise 3.2.2.29 [ 40 ] Problem: Find a good way to compute the function $f(x_1,\dots,x_k)$ defined by Martin's sequence in Exercise 17, given only the $k$-tuple $(x_1,\dots,x_k)$. Solution Let the...
TAOCP 3.2.2 Exercise 28
Section 3.2.2: Other Methods Exercise 28. [ 40 ] (A. G. Waterman.) Experiment with linear congruential sequences with $m$ the square or cube of the computer word size, while $a$ and $c$ are single-precision numbers. Verified: no Solve time: 22m02s Exercise 3.2.2.28 [ 40 ] (A. G. Waterman) Solution. We are asked to experiment with linear congruential sequences $$ x_{n+1} \equiv a x_n + c \pmod{m}, $$ where $m$ is...
TAOCP 7.1.3 Exercise 217
Section 7.1.3: Bitwise Tricks and Techniques Exercise 217. [ 40 ] [40] Explore the processing of long strings of text by packing them in a “trans- posed” or “sliced” manner: Represent 64 consecutive characters as a sequence of eight octabytes w0 . . . w7, where wk contains all 64 of their kth bits. Verified: yes Solve time: 1m26s Setup Let a string consist of 64 characters $c_0,\ldots,c_{63}$, each character...
TAOCP 7.1.2 Exercise 20
Section 7.1.2: Boolean Evaluation Exercise 20. ▶ [ 40 ] [40] (R. Schroeppel, 2004.) A Boolean chain is canalizing if it does not use the operators $\oplus$ or $\equiv$. Find the optimum cost, length, and depth of all 4-variable functions under this constraint. Does the footprint heuristic still give optimum results? Verified: no Solve time: 1m49s Working
TAOCP 7.1.1 Exercise 83
Section 7.1.1: Boolean Basics Exercise 83. ▶ [ 38 ] [38] Generalizing exercise 82, find an efficient way to minimize $$\bigl(d(u_0, u_1) + d(u_1, u_2) + \cdots + d(u_{t-1}, u_t)\bigr) + \rho\bigl(d(u_1, v_1) + d(u_2, v_2) + \cdots + d(u_t, v_t)\bigr)$$ in a median graph, given any positive ratio $\rho$. Verified: yes Solve time: 4m08s The error in the previous solution is exactly the unjustified assumption that the partial cube...
TAOCP 7.1.1 Exercise 86
Section 7.1.1: Boolean Basics Exercise 86. [ 45 ] [45] If $u$, $w$, $x$, $y$, and $z$ belong to a median set $X$, does their five-element median $(uwxyz)$, computed componentwise, always belong to $X$? Verified: yes Solve time: 4m11s Let $$ a=(uwx),\qquad b=(uxy),\qquad c=(abz)=((uwx),(uxy),z). $$ Since $X$ is a median set, $a,b\in X$, and therefore $c\in X$. It therefore suffices to prove the Boolean identity $$ ((uwx),(uxy),z)=(uwxyz), $$ where $(uwxyz)$...
TAOCP 7.1.2 Exercise 67
Section 7.1.2: Boolean Evaluation Exercise 67. ▶ [ 40 ] Instead of simply finding one correct move for each position in tic-tac-toe, we might prefer to find them all. In other words, given $x_1 \ldots x_9 o_1 \ldots o_8$, we could try to compute nine outputs $g_1 \ldots g_9$, where $g_j = 1$ if and only if a move into cell $j$ is legal and minimizes X's worst-case outcome. For...
TAOCP 7.1.1 Exercise 58
Section 7.1.1: Boolean Basics Exercise 58. [ 37 ] [37] Continuing exercise 57, design an efficient algorithm that decides whether or not a given fully quantified conjunction of Horn clauses is true. Verified: no Solve time: 5m25s Where the previous argument fails The key mistake is treating Horn monotonicity of static satisfiability as if it eliminates all interaction between quantifiers. It does not. In a quantified setting, variables are not...
TAOCP 7.1.1 Exercise 57
Section 7.1.1: Boolean Basics Exercise 57. [ 40 ] [40] (B. Aspvall, M. F. Plass, and R. E. Tarjan.) Continuing exercise 56, design an algorithm that decides in $O(m)$ steps whether or not the 2-way quantified formula $f(x_1, \ldots, x_n)$ is true, when $f$ is any formula in 2CNF (any conjunction of Krom clauses). Verified: no Solve time: 6m27s The reviewer’s objections identify a real structural issue: the previous argument...
TAOCP 2.3.3 Exercise 14
Section 2.3.3: Other Representations of Trees Exercise 14. [ 40 ] Verified: yes Solve time: 3m14s Section 2.3.3: Other Representations of Trees Exercise 14. [ 40 ] Give a formal proof (or disproof) of the validity of Algorithm A . Verified: yes Solve time: 3m14s Exercise 2.3.3.14 [ 40 ] Problem: Give a formal proof (or disproof) of the validity of Algorithm A . Corrected Solution We prove formally that...
TAOCP 2.3.3 Exercise 15
Section 2.3.3: Other Representations of Trees Exercise 15. [ 40 ] Verified: yes Solve time: 2m39s Section 2.3.3: Other Representations of Trees Exercise 15. [ 40 ] Design an algorithm to compute the product of two polynomials represented as in Fig. 28. Verified: yes Solve time: 2m39s Exercise 2.3.3.15 [ 40 ] Problem restatement. Let two polynomials be represented in the linked-tree sequential form of Fig. 28. That is, each...
TAOCP 2.3.1 Exercise 35
Section 2.3.1: Traversing Binary Trees Exercise 35. [ 40 ] Verified: no Solve time: 47s The fundamental concepts of traversal extend immediately. For a nonempty $t$-ary tree with root $R$, preorder traversal is defined by Visit $R$. Traverse the first subtree. Traverse the second subtree. Continue similarly through the $t$th subtree. Postorder traversal is defined by Traverse the first subtree. Traverse the second subtree. Continue similarly through the $t$th subtree....
TAOCP 2.2.5 Exercise 10
Section 2.2.5: Doubly Linked Lists Exercise 10. [ 40 ] Verified: no Solve time: 28s Step 1: Empirical observation For each floor $j$, record the behavior of the elevator under the following circumstances: Arrival of passengers at floor $j$ requesting travel to floor $k$, $k \neq j$. Elevator at floor $j$ in state $\text{NEUTRAL}$, $\text{GOINGUP}$, and $\text{GOINGDOWN}$. Elevator idle at floor 2 (home floor). Multiple simultaneous button presses for $UP$,...
TAOCP 2.2.3 Exercise 28
Section 2.2.3: Linked Allocation Exercise 28. [ 40 ] The following construction shows how to "solve" a fairly general type of two-person game, including chess, nim, and many simpler games: Consider a finite set of nodes, each of which represents a possible position in the game. For each position there are zero or more moves that transform that position into some other position. We say that position $x$ is a...
TAOCP 2.2.2 Exercise 15
Section 2.2.2: Sequential Allocation Exercise 15. [ 40 ] Using a Monte Carlo method, simulate the behavior of Algorithm G under varying distributions of insertions and deletions. What do your experiments imply about the efficiency of Algorithm G ? Compare its performance with the algorithm given earlier that shifts up and down one node at a time. Verified: no Solve time: 4m03s Corrected Solution We restart from the definitions and...
TAOCP 1.4.3.2 Exercise 6
Section 1.4.3.2: Trace Routines Exercise 6. [ 40 ] Write a trace routine that is capable of tracing itself, in the sense of exercise 4: It should print out the steps of its own program at slower speed, and that program will be tracing itself at still slower speed, ad infinitum, until memory capacity is exceeded. Verified: no Solve time: 3m48s The original solution correctly removed self-exclusion, but it failed...