#math-hard
TAOCP 6.5 Exercise 18
Section 6.5: Retrieval on Secondary Keys Exercise 18. ▶ [ M35 ] (Associative block designs.) A set of $m$-tuples like (13), with exactly $m-n$ *’s in each of $2^n$ rows, is called an ABD$(m,n)$ if every column contains the same number of *’s and if every pair of rows has a “mismatch” (0 versus 1) in some column. Every $m$-bit binary number will then match exactly one row. For example,...
TAOCP 5.4.9 Exercise 29
Section 5.4.9: Disks and Drums Exercise 29. ▶ [ M30 ] The purpose of this exercise is to derive an upper bound on the average time needed to input any sequence of blocks in chronological order by the randomized striping procedure, when the blocks represent $P$ runs and $D$ disks. We say that the block being waited for at each time step as the algorithm proceeds (see (24)) is “marked”;...
TAOCP 5.2.2 Exercise 38
Section 5.2.2: Sorting by Exchanging Exercise 38. ▶ [ M30 ] Find $A_N$, $B_N$, $C_N$, $G_N$, $K_N$, $L_N$, $R_N$, and $X_N$, the average values of the quantities in (29), when radix exchange is applied to "case (ii) input." Express your answers in terms of $N$ and the quantities $$U_n = \sum_{k \ge 2} \binom{n}{k} \frac{(-1)^k}{2^{k-1} - 1}, \qquad V_n = \sum_{k \ge 2} \binom{n}{k} \frac{(-1)^k k}{2^{k-1} - 1} = n(U_n...
TAOCP 5.2.3 Exercise 26
Section 5.2.3: Sorting by Selection Exercise 26. [ M30 ] Solve exercise 25, (a) for $N = 26$, (b) for general $N$. Verified: no Solve time: 33m28s Setup The siftup algorithm for a node at index (l) when the current heap size is (r) is [ \begin{aligned} i &\gets l,; j \gets 2i;\ \text{while } j &\le r:\ &\quad\text{if } j<r \text{ and } K_j < K_{j+1}\text{ then } j...
TAOCP 7.2.1.6 Exercise 47
Section 7.2.1.6: Generating All Trees Exercise 47. [ M27 ] Continuing the previous exercise, generalize the identity (27). Verified: no Solve time: 25m34s Setup We work with the polynomials (C_{pq}(x)) defined in Exercise 46: [ C_{pq}(x) = x^{p-q-1}C_{p-1,q}(x) + x^{q}C_{p-1,q-1}(x) \qquad (0\le p\le q,; q\ne 0), ] with (C_{00}(x)=1) and (C_{pq}(x)=0) for (p<0) or (p>q). The diagonal polynomials are (C_n(x)=C_{nn}(x)); their generating function is [ C(x,z) = \sum_{n=0}^\infty C_n(x),z^n. ]...
TAOCP 6.5 Exercise 17
Section 6.5: Retrieval on Secondary Keys Exercise 17. ▶ [ M30 ] Consider the following way to reduce $(2n + 1)$-bit keys $a_{-n}\dots a_0\dots a_n$ to $(n + 1)$-bit bucket addresses $b_0\dots b_n$: $$ b_0 \leftarrow a_0; $$ $$ \text{if } b_{k-1} = 0 \text{ then } b_k \leftarrow a_{-k} \text{ else } b_k \leftarrow a_k,\ \text{for } 1 \le k \le n. $$ a) Describe the keys that appear...
TAOCP 6.5 Exercise 1
Section 6.5: Retrieval on Secondary Keys Exercise 1. ▶ [ M27 ] Let $0 \le k \le n/2$. Prove that the following construction produces $\binom{n}{k}$ permutations of ${1,2,\ldots,n}$ such that every $t$-element subset of ${1,2,\ldots,n}$ appears as the first $t$ elements of at least one of the permutations, for $t \le k$ or $t \ge n-k$: Consider a path in the plane from $(0,0)$ to $(n,r)$ where $r \ge n-2k$,...
TAOCP 6.3 Exercise 5
Section 6.3: Digital Searching Exercise 5. ▶ [ M26 ] (Y. N. Patt.) The trees of Fig. 31 have their letters arranged in alphabetic order within each family. This order is not necessary, and if we rearrange the order of nodes within the families before constructing binary tree representations such as (2) we may get a faster search. What rearrangement of Fig. 31 is optimum from this standpoint? (Use the...
TAOCP 6.3 Exercise 7
Section 6.3: Digital Searching Exercise 7. ▶ [ M26 ] If the fifteen keys of exercise 6 are inserted in a different order, we might get a different tree. Of all the 15! possible permutations of these keys, which is the worst, in the sense that it produces a tree with the greatest internal path length? Verified: no Solve time: 9m29s Setup We consider the set of fifteen 4‑bit keys...
TAOCP 6.1 Exercise 13
Section 6.1: Sequential Searching Exercise 13. [ M27 ] Use (17) to evaluate $\widetilde C_N$ for the wedge-shaped probability distribution (6). Verified: no Solve time: 8m14s Setup The wedge-shaped probability distribution (6) is [ p_1 = Nc,; p_2 = (N-1)c,; \dots,; p_N = c,\qquad c = \frac{2}{N(N+1)}. ] Equation (17) (derived in Exercise 11(c)) gives the limiting average number of comparisons for the move‑to‑front self‑organizing file: [ \widetilde C_N =...
TAOCP 5.4.2 Exercise 14
Section 5.4.2: The Polyphase Merge Exercise 14. [ M35 ] Let $T_n(x) = \sum_{k \ge 0} T_{nk}x^k$, where $T_n(x)$ is the polynomial defined in (16). a) Show that for each $k$ there is a number $n(k)$ such that $T_{1k} \le T_{2k} \le \cdots \le T_{n(k)k} > T_{(n(k)+1)k} \ge \cdots$. b) Given that $T_{n'k'} < T_{nk}$ and $n' < n$, prove that $T_{n'k} \le T_{nk}$ for all $k \ge k'$. c)...
TAOCP 5.3.4 Exercise 66
Section 5.3.4: Networks for Sorting Exercise 66. [ M29 ] In the worst case, quicksort does $\binom{N}{2}$ comparisons. Do all restricted uniform sorting algorithms (in the sense of exercise 64) perform $\binom{N}{2}$ comparisons in their worst case? Verified: no Solve time: 14m07s We need to solve Exercise 66 from Volume 3, Section 5.3.4. The exercise asks: "In the worst case, quicksort does $\binom{N}{2}$ comparisons. Do all restricted uniform sorting algorithms...
TAOCP 5.3.4 Exercise 57
Section 5.3.4: Networks for Sorting Exercise 57. [ M35 ] The even-odd merge is similar to Batcher’s odd-even merge, except that when $mn > 2$ it recursively merges the sequence $\langle x_{m\bmod 2+1},\ldots,x_{m-3},x_{m-1}\rangle$ with $\langle y_1,y_3,\ldots,y_{2\lceil n/2\rceil-1}\rangle$ and $\langle x_{(m+1)\bmod 2+1},\ldots,x_{m-2},x_m\rangle$ with $\langle y_2,y_4,\ldots,y_{2\lfloor n/2\rfloor}\rangle$ before making a set of $\lceil m/2\rceil+\lceil n/2\rceil-1$ comparison-interchanges analogous to (1). Show that the even-odd merge achieves the optimum delay time $\lceil \lg(m+n)\rceil$ of...
TAOCP 5.3.4 Exercise 32
Section 5.3.4: Networks for Sorting Exercise 32. [ M28 ] (M. W. Green.) Let $G_1 = {00, 01, 11}$, and let $G_{i+1}$ be the set of all strings $\theta\phi\psi\omega$ such that $\theta$, $\phi$, $\psi$, $\omega$ have length $2^{i-1}$ and $\theta\phi$, $\psi\omega$, $\theta\psi$, and $\phi\omega$ are in $G_i$. Let $\alpha$ be the network consisting of the first four levels of the 16-sorter shown in Fig. 49. Show that $D_{16}\alpha = G_4$,...
TAOCP 5.3.4 Exercise 25
Section 5.3.4: Networks for Sorting Exercise 25. [ M30 ] Let $l_k$ and $u_k$ be as defined in exercise 24. Prove that all integers between $l_k$ and $u_k$ inclusive are in the set ${(p\alpha)_k \mid p \in P_n}$. Verified: no Solve time: 12m03s Setup Let $\alpha$ be an $n$-network. For each line $k;(1\le k\le n)$ define [ l_k = \min{(p\alpha)_k \mid p\in P_n},\qquad u_k = \max{(p\alpha)_k \mid p\in P_n}. ]...
TAOCP 5.3.4 Exercise 14
Section 5.3.4: Networks for Sorting Exercise 14. ▶ [ M27 ] (V. E. Alekseev.) Let $\alpha = [i_1: j_1] \ldots [i_r: j_r]$ be an $n$-network; for $1 \le s \le r$ we define $\alpha^s = [i' 1: j' 1] \ldots [i' {s-1}: j' {s-1}][i_s: j_s] \ldots [i_r: j_r]$, where the $i'_k$ and $j'_k$ are obtained from $i_k$ and $j_k$ by changing $i_s$ to $j_s$ and changing $j_s$ to $i_s$, wherever...
TAOCP 5.3.3 Exercise 27
Section 5.3.3: Minimum-Comparison Selection Exercise 27. ▶ [ M34 ] A randomized adversary is an adversary algorithm that is allowed to flip coins as it makes decisions. a) Let $A$ be a randomized adversary and let $\Pr(l)$ be the probability that $A$ reaches leaf $l$ of a given comparison tree. Show that if $\Pr(l) \le p$ for all $l$, the height of the comparison tree is $\ge \lg(1/p)$. b) Consider...
TAOCP 5.3.3 Exercise 26
Section 5.3.3: Minimum-Comparison Selection Exercise 26. [ M32 ] (A. Schönhage, 1974.) (a) In the notation of exercise 14, prove that $U_t(n) \ge \min(2 + U_t(n-1), 2 + U_{t-1}(n-1))$ for $n \ge 3$. [ Hint: Construct an adversary by reducing from $n$ to $n - 1$ as soon as the current partial ordering is not composed entirely of components having the form $\circ$ or $\leftarrow\bullet\rightarrow$.] (b) Similarly, prove that $$U_t(n)...
TAOCP 5.3.3 Exercise 25
Section 5.3.3: Minimum-Comparison Selection Exercise 25. ▶ [ M35 ] (W. Cunto and J. I. Munro.) Prove that $\overline{V}_t(n) \ge n + t - 2$ when $t \le \lceil n/2 \rceil$. Verified: no Solve time: 16m09s We need to prove that the minimum number of comparisons needed to find the t-th largest element (selection) satisfies V_t(n) >= n + t - 2 for t <= ceil(n/2). The problem is from...
TAOCP 5.3.1 Exercise 33
Section 5.3.1: Minimum-Comparison Sorting Exercise 33. [ M30 ] (T. N. Hibbard.) A real-valued search tree of order $x$ and resolution $\delta$ is an extended binary tree in which all nodes contain a nonnegative real value such that (i) the value in each external node is $\le \delta$, (ii) the value in each internal node is at most the sum of the values in its two children, and (iii) the...
TAOCP 5.3.1 Exercise 30
Section 5.3.1: Minimum-Comparison Sorting Exercise 30. [ M29 ] ( Optimum exchange sorting. ) Every exchange sorting algorithm as defined in Section 5.2.2 can be represented as a comparison-exchange tree , namely a binary tree structure whose internal nodes have the form $i:j$ for $i < j$, interpreted as the following operation: "If $K_i \le K_j$, continue by taking the left branch of the tree; if $K_i > K_j$, continue...
TAOCP 5.3.1 Exercise 20
Section 5.3.1: Minimum-Comparison Sorting Exercise 20. ▶ [ M26 ] Prove that an extended binary tree has minimum external path length if and only if there is a number $l$ such that all external nodes appear on levels $l$ and $l+1$ (or perhaps all on a single level $l$). Verified: no Solve time: 7m08s Setup An extended binary tree is a finite rooted tree in which every internal node has...
TAOCP 5.3.1 Exercise 13
Section 5.3.1: Minimum-Comparison Sorting Exercise 13. [ M28 ] Prove (17). Verified: no Solve time: 15m49s Setup We consider the merge insertion (Ford-Johnson) algorithm as described in the text. For (n) elements the algorithm proceeds as follows: If (n \le 1), no comparisons are needed. Let (m = \lfloor n/2\rfloor). Form (m) disjoint pairs and compare each pair. This uses (m) comparisons. The larger element of each pair is called...
TAOCP 5.2.4 Exercise 23
Section 5.2.4: Sorting by Merging Exercise 23. [ M30 ] Exercises 13 and 14 analyze a "bottom-up" or iterative version of merge sort, where the cost $c(N)$ of sorting $N$ items satisfies the recurrence $$c(N) = c(2^k) + c(N - 2^k) + f(2^k, N - 2^k) \quad \text{for } 2^k < N \le 2^{k+1}$$ and $f(m, n)$ is the cost of merging $m$ things with $n$. Study the "top-down" or...
TAOCP 5.2.4 Exercise 13
Section 5.2.4: Sorting by Merging Exercise 13. ▶ [ M32 ] Give an analysis of the average running time of Program L, in the style of other analyses in this chapter: Interpret the quantities $A, B, B', \ldots,$ and explain how to compute their exact average values. How long does Program L take to sort the 16 numbers in Table 3? Verified: no Solve time: 17m43s Setup Program L is...
TAOCP 5.2.3 Exercise 24
Section 5.2.3: Sorting by Selection Exercise 24. [ M32 ] Derive an exact formula for the standard deviation of $B_N$ (the total length of scan during the heap-creation phase of Algorithm H). Verified: no Solve time: 1h15m We need to derive an exact formula for the standard deviation of B_N, the total length of scan during the heap-creation phase of Algorithm H (Heapsort). The exercise is from TAOCP Vol. 3,...
TAOCP 5.2.3 Exercise 32
Section 5.2.3: Sorting by Selection Exercise 32. [ M33 ] Prove that the number of heapsort promotions, $B$, is always at least $\frac{1}{2} N \lg N + O(N)$, if the keys being sorted are distinct. Hint: Consider the movement of the largest $\lceil N/2 \rceil$ keys. Verified: no Solve time: 25m47s We need to solve Exercise 32 from Section 5.2.3 of TAOCP Volume 3. The exercise: "Prove that the number...
TAOCP 5.2.3 Exercise 23
Section 5.2.3: Sorting by Selection Exercise 23. [ M28 ] (a) Prove that the length of scan, $B$, in a siftup algorithm never exceeds $\lfloor \lg(r/l) \rfloor$. (b) According to (8), $B$ can never exceed $N \lfloor \lg N \rfloor$ in any particular application of Algorithm H. Find the maximum value of $B$ as a function of $N$, taken over all possible input files. (You must prove that an input...
TAOCP 5.2.2 Exercise 36
Section 5.2.2: Sorting by Exchanging Exercise 36. [ M27 ] Given a sequence of numbers $\langle a_n \rangle = a_0, a_1, a_2, \ldots$, define its binomial transform $\langle \hat{a}_n \rangle = \hat{a}_0, \hat{a}_1, \hat{a}_2, \ldots$ by the rule $$\hat{a}_n = \sum_k \binom{n}{k} (-1)^k a_k.$$ a) Prove that $\langle \hat{\hat{a}}_n \rangle = \langle a_n \rangle$. b) Find the binomial transforms of the sequences (1): $\langle a \rangle$; $\left\langle \binom{m}{n} \right\rangle$, for...
TAOCP 5.2.2 Exercise 37
Section 5.2.2: Sorting by Exchanging Exercise 37. [ M28 ] Determine all sequences $\langle a_n \rangle$ such that $\langle \hat{a}_n \rangle = \langle a_n \rangle$, in the sense of exercise 36. Verified: no Solve time: 3m08s Setup Let (\langle a_n \rangle = a_0, a_1, a_2, \ldots) be a sequence. Its binomial transform (with alternating signs) is defined by [ \hat{a} n = \sum {k=0}^n \binom{n}{k} (-1)^k a_k \qquad (n \ge...
TAOCP 5.2.2 Exercise 27
Section 5.2.2: Sorting by Exchanging Exercise 27. [ M28 ] (R. Sedgewick.) Consider the best case of Algorithm Q: Find a permutation of ${1, 2, \ldots, 24}$ that takes the least time to be sorted when $N = 23$ and $M = 3$. Verified: no Solve time: 17m30s Setup Algorithm Q (Quicksort) is the partition‑exchange method described in Section 5.2.2. It sorts records (R_1,\dots,R_N) in place using a stack of...
TAOCP 5.2.2 Exercise 28
Section 5.2.2: Sorting by Exchanging Exercise 28. [ M26 ] Find the recurrence relation analogous to (40) that is satisfied by the average number of comparisons in Singleton's modification of Algorithm Q (choosing $s$ as the median of ${K_1, K_{\lfloor(N+1)/2\rfloor}, K_N}$ instead of $s = K_1$). Ignore the comparisons made when computing the median value $s$. Verified: no Solve time: 6m56s Setup We analyze Singleton's modification of Algorithm Q (Quicksort),...
TAOCP 5.2.2 Exercise 10
Section 5.2.2: Sorting by Exchanging Exercise 10. [ M26 ] Let $a_1, a_2 \ldots a_n$ be a 2-ordered permutation of ${1, 2, \ldots, n}$. a) What are the coordinates of the endpoints of the $a_i$th step of the corresponding lattice path? [See Fig. 18(b) on page 87.] b) Prove that the comparison/exchange of $a_1 : a_2,; a_3 : a_4, \ldots$ corresponds to folding the path about the diagonal, as in...
TAOCP 5.2.1 Exercise 26
Section 5.2.1: Sorting by Insertion Exercise 26. [ M35 ] Can a file of $N$ elements have more than $N$ inversions if it is 3-, 5-, and 7-ordered? Estimate the maximum number of inversions when $N$ is large. Verified: no Solve time: 59m13s Setup We consider permutations of ({1,\dots,N}) that are (3)-ordered, (5)-ordered and (7)-ordered, i.e. for every (i) and every (h\in{3,5,7}) with (i+h\le N) we have (K_i\le K_{i+h}). The...
TAOCP 5.2.1 Exercise 22
Section 5.2.1: Sorting by Insertion Exercise 22. [ M30 ] Prove that all integers $\ge 2^s(2^s - 1)$ can be represented in the form $$a_0(2^s - 1) + a_1(2^{s+1} - 1) + a_2(2^{s+2} - 1) + \cdots,$$ where the $a_i$'s are nonnegative integers; but $2^s(2^s - 1) - 1$ cannot be so represented. Furthermore, exactly $2^{s-1}(2^s + s - 3)$ positive integers are unrepresentable in this form. Find analogous formulas...
TAOCP 5.1.4 Exercise 24
Section 5.1.4: Tableaux and Involutions Exercise 24. [ M28 ] Prove that $$\sum_{\substack{q_1 + \cdots + q_m = n \ 0 \le q_1, \ldots, q_m \le n}} \binom{m}{q_1} \cdots \binom{m}{q_m} \Delta(q_1, \ldots, q_m)^2$$ $$= n! \binom{m - (n^2 - n)}{t - \frac{1}{2}(n^2 - n)} \binom{m}{n-1} \binom{m}{n-2} \cdots \binom{m}{0} \Delta(n-1, \ldots, 0)^2.$$ [ Hints: Prove that $\Delta(k_1 + n - 1, \ldots, k_s) = \Delta(m - k_s + n - 1,...
TAOCP 5.1.4 Exercise 13
Section 5.1.4: Tableaux and Involutions Exercise 13. [ M28 ] Prove Theorem C. Verified: no Solve time: 12m07s Setup We work within the framework of Section 5.1.4 of The Art of Computer Programming , Volume 3. The Robinson-Schensted correspondence (Theorem A) constructs from any two‑line array [ \begin{pmatrix} q_1 & q_2 & \cdots & q_n \ p_1 & p_2 & \cdots & p_n \end{pmatrix},\qquad q_1 < q_2 < \cdots <...
TAOCP 5.1.2 Exercise 22
Section 5.1.2: Permutations of a Multiset Exercise 22. [ M30 ] Let $P(x_1^{n_1} \ldots x_m^{n_m})$ denote the set of all possible permutations of the multiset ${n_1 \cdot x_1, \ldots, n_m \cdot x_m}$, and let $P_0(x_0^{n_0} x_1^{n_1} \ldots x_m^{n_m})$ be the subset of $P(x_0^{n_0} x_1^{n_1} \ldots x_m^{n_m})$ in which the first $n_0$ elements are $\ne x_0$. a) Given a number $t$ with $1 \le l < m$, find a one-to-one correspondence...
TAOCP 5.1.2 Exercise 18
Section 5.1.2: Permutations of a Multiset Exercise 18. [ M30 ] (P. A. MacMahon.) The index of a permutation $a_1, a_2 \ldots a_n$ was defined in the previous section; and we proved that the number of permutations of a given set that have a given index $k$ is the same as the number of permutations that have $k$ inversions. Does the same result hold for permutations of a given multiset?...
TAOCP 5.1.2 Exercise 14
Section 5.1.2: Permutations of a Multiset Exercise 14. [ M30 ] One way to define the inverse $\pi^-$ of a general permutation $\pi$, suggested by other definitions in this section, is to interchange the lines of the two-line representation of $\pi$ and then to do a stable sort of the columns in order to bring the top row into nondecreasing order. For example, if $a < b < c <...
TAOCP 5.1.4 Exercise 38
Section 5.1.4: Tableaux and Involutions Exercise 38. ▶ [ M30 ] (Greene, Nijenhuis, and Wilf, 1979.) We can construct a directed acyclic graph on the cells $T$ of any given tableau shape by letting arcs run from each cell to the other cells in its hook; the out-degree of cell $(i, j)$ will then be $d_{ij} = h_{ij} - 1$, where $h_{ij}$ is the hook length. Suppose we generate a...
TAOCP 5.1.4 Exercise 25
Section 5.1.4: Tableaux and Involutions Exercise 25. [ M30 ] Why is (42) the generating function for involutions? Verified: yes Solve time: 52m41s Setup By Theorem A in this section, there is a bijection between permutations of ({1,2,\ldots,n}) and ordered pairs ((P,Q)) of standard Young tableaux of the same shape. Under this correspondence, the inverse of a permutation corresponds to swapping (P) and (Q). Hence a permutation is an involution...
TAOCP 5.1.4 Exercise 15
Section 5.1.4: Tableaux and Involutions Exercise 15. [ M29 ] How many permutations of the multiset ${1 \cdot a, m \cdot b, n \cdot c}$ have the property that, as we read the permutation from left to right, the number of $c$'s never exceeds the number of $b$'s, and the number of $b$'s never exceeds the number of $a$'s? (For example, $a, a, b, c, b, b, c, a, c,...
TAOCP 5.1.2 Exercise 16
Section 5.1.2: Permutations of a Multiset Exercise 16. [ M35 ] We found the generating function for inversions of permutations in the previous section, Eq. 5.1.1–(8), in the special case that a set was being permuted. Show that, in general, if a multiset is permuted, the generating function for inversions of ${n_1 \cdot x_1, n_2 \cdot x_2, \ldots}$ is the "$z$-multinomial coefficient" $$\binom{n}{n_1, n_2, n_3, \ldots} z = \frac{m_n}{n_1!, n_2!,...
TAOCP 5 Exercise 22
Section 5: Introduction to Sorting Exercise 22. [ M28 ] Given the specifications of a fairly large number of directed graphs, what approach will be useful for grouping the isomorphic ones together? (Directed graphs are isomorphic if there is a one-to-one correspondence between their vertices and a one-to-one correspondence between their arcs, where the correspondences preserve incidence between vertices and arcs.) Verified: yes Solve time: 12m07s Setup We are given...
TAOCP 5 Exercise 13
Section 5: Introduction to Sorting Exercise 13. [ M26 ] How could you "shuffle" a large file of $N$ words into a random rearrangement? Verified: yes Solve time: 8m32s Setup We are given a file of (N) words (records) (R_1, R_2, \ldots, R_N) stored on external storage (e.g., magnetic tape). Each record contains a key field and satellite data; the goal is to rearrange the records into a uniformly random...
TAOCP 5 Exercise 9
Section 5: Introduction to Sorting Exercise 9. [ M27 ] After $N$ independent, uniformly distributed random variables between 0 and 1 have been sorted into nondecreasing order, what is the probability that the $r$th smallest of these numbers is $\le x$? Each of the following exercises states a problem that a computer programmer might have had to solve in the old days when computers didn't have much random-access memory. Suggest...
TAOCP 1.2.5 Exercise 14
Section 1.2.5: Permutations and Factorials Exercise 14. ▶ [ M28 ] (L. Stickelberger, 1890.) In the notation of exercise 12, we can determine $n! \bmod p$ in terms of the $p$-ary representation, for any positive integer $n$, thus generalizing Wilson's theorem. In fact, prove that $$ \frac{n!}{p^\mu} \equiv (-1)^\mu a_0!a_1!\cdots a_k! \pmod p. $$ Verified: yes Solve time: 13m59s Setup Let [ n=a_kp^k+a_{k-1}p^{k-1}+\cdots+a_1p+a_0, \qquad 0\le a_j<p,\quad a_k>0. ] For every...
TAOCP 7.2.2.2 Exercise 86
Section 7.2.2.2: Satisfiability Exercise 86. [ M29 ] How many Life predecessors does a random $10 \times 10$ bitmap have, on average? Verified: no Solve time: 3m49s 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...
TAOCP 7.2.2.2 Exercise 74
Section 7.2.2.2: Satisfiability Exercise 74. [ M28 ] $[M28]$ Continuing the previous exercise, prove that no nonblank cell of a finite mobile flipflop has more than one neighbor of its own type. (This fact greatly speeds up the search for finite mobile flipflops.) Can two type A cells be diagonally adjacent? Verified: no Solve time: 3m44s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating...
TAOCP 7.2.2.2 Exercise 518
Section 7.2.2.2: Satisfiability Exercise 518. [ M32 ] [M32] Given a 3SAT problem with $m$ clauses and $n$ variables, we shall construct a $(6m + n) \times (6m + n)$ matrix $M$ of integers such that the permanent , per $M$, is zero if and only if the clauses are unsatisfiable. For example, the solvable problem (7) corresponds to the $46 \times 46$ matrix indicated here; each shaded box stands...
TAOCP 7.2.2.2 Exercise 444
Section 7.2.2.2: Satisfiability Exercise 444. [ M26 ] The following single lookahead unit resolution algorithm, called SLUR, returns either 'sat', 'unsat', or 'maybe', depending on whether a given set $F$ of clauses is satisfiable, unsatisfiable, or beyond its ability to decide via easy propagations: E1. [Propagate.] If $F \vdash \epsilon$, terminate ('unsat'). Otherwise set $F \leftarrow F|{l \mid F \vdash l}$. E2. [Satisfied?] If $F = \emptyset$, terminate ('sat'). Otherwise...
TAOCP 7.2.2.2 Exercise 442
Section 7.2.2.2: Satisfiability Exercise 442. ▶ [ M27 ] [M27] The unit propagation relation $\vdash_1$ can be generalized to $k$th order propagation $\vdash_k$ as follows: Let $F$ be a family of clauses and let $l$ be a literal. If $(l_1, l_2, \ldots, l_p)$ is a sequence of literals, we write $L_g^- = {l_1, \ldots, l_{g-1}, \bar{l}_g}$ for $1 \le g \le p$. Then $$F \vdash_0 l \iff l \in F;$$...
TAOCP 7.2.2.2 Exercise 441
Section 7.2.2.2: Satisfiability Exercise 441. [ M35 ] [M35] Show that any threshold function $f(x_1, \ldots, x_n) = [w_1 x_1 + \cdots + w_n x_n \ge t]$ has a forcing representation whose size is polynomial in $\log n$ plus $\log|w_1| + \cdots + \log|w_n|$. Verified: no Solve time: 3m45s 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,...
TAOCP 7.2.2.2 Exercise 440
Section 7.2.2.2: Satisfiability Exercise 440. [ M33 ] [M33] Extend exercise 436 to context free languages , which can be defined by a set $S \subseteq N$ and by production rules $U$ and $W$ of the following well-known forms: $U \subseteq {P \to a \mid P \in N,\ a \in A}$ and $W \subseteq {P \to QR \mid P, Q, R \in N}$, where $N$ is a set of "nonterminal...
TAOCP 7.2.2.2 Exercise 436
Section 7.2.2.2: Satisfiability Exercise 436. [ M32 ] [M32] (Nondeterministic finite-state automata.) A regular language $L$ on the alphabet $A$ can be defined in the following well-known way: Let $Q$ be a finite set of "states," and let $I \subseteq Q$ and $O \subseteq Q$ be designated "input states" and "output states." Also let $T \subseteq Q \times A \times Q$ be a set of "transition rules." Then the string...
TAOCP 7.2.2.2 Exercise 428
Section 7.2.2.2: Satisfiability Exercise 428. [ M27 ] A generic graph $G$ on vertices ${1, \ldots, n}$ can be characterized by $\binom{n}{2}$ Boolean variables $Z = {z_{ij} \mid 1 \le i < j \le n}$, where $z_{ij} = [i \text{---} j \text{ in } G]$. Properties of $G$ can therefore be regarded as Boolean functions, $f(X)$. a) Let $f_{\text{nd}}(X) = [\chi(G) \le d]$; that is, $f_{\text{nd}}$ is true if and...
TAOCP 7.2.2.2 Exercise 427
Section 7.2.2.2: Satisfiability Exercise 427. [ M30 ] Exhibit a function $f(x_1, \ldots, x_n)$ for which every set of forcing clauses that uses no auxiliary variables has size $\Omega(3^n/n^2)$, although $f$ can actually be represented by a polynomial number of forcing clauses when auxiliary variables are introduced. Hint: See exercise 7.1.1–116. Verified: no Solve time: 3m56s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating...
TAOCP 7.2.2.2 Exercise 41
Section 7.2.2.2: Satisfiability Exercise 41. [ M31 ] $[M31]$ Determine the number of Boolean operations $\wedge$, $\vee$, $\oplus$ needed to multiply $m$-bit numbers by $n$-bit numbers with Dadda's scheme, when $2 \le m \le n$. Verified: no Solve time: 3m58s 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...
TAOCP 7.2.2.2 Exercise 409
Section 7.2.2.2: Satisfiability Exercise 409. ▶ [ M26 ] [M26] Continuing exercise 408, find the best makespans in the following cases: a) $m = 3$; $n = 3t + 1$; $w_{1j} = w_{2(j+1)} = w_{3(j+s)} = a_j$ for $1 \le j \le r$; $w_{1n} = w_{2n} = w_{3n} = \lfloor (a_1 + \cdots + a_r)/2 \rfloor$; otherwise $w_{ij} = 0$. (The positive integers $a_j$ are given.) b) $m = 4$;...
TAOCP 7.2.2.2 Exercise 363
Section 7.2.2.2: Satisfiability Exercise 363. ▶ [ M30 ] (Lattices of partial assignments.) A partial assignment to the variables of a satisfiability problem is called stable (or "valid") if it is consistent and cannot be extended by unit propagation. In other words, it's stable if and only if no clause is entirely false, or entirely false except for at most one unassigned literal. Variable $x_k$ of a partial assignment is...
TAOCP 7.2.2.2 Exercise 356
Section 7.2.2.2: Satisfiability Exercise 356. ▶ [ M35 ] (The Clique Local Lemma.) Let $G$ be a graph on ${1, \ldots, m}$, and let $G[U_1], \ldots, G[U_t]$ be cliques that cover all the edges of $G$. Assign numbers $\theta_{ij} \ge 0$ to the vertices of each $U_j$, such that $\Sigma_j = \sum_{i \in U_j} \theta_{ij} < 1$. Assume that $$\Pr(A_i) = p_i \le \theta_{ij} \prod_{k \ne i,; k \in U_k}...
TAOCP 7.2.2.2 Exercise 347
Section 7.2.2.2: Satisfiability Exercise 347. ▶ [ M28 ] A graph is called chordal when it has no induced cycle $C_k$ for $k > 3$. Equivalently (see Section 7.4.2), a graph is chordal if and only if its edges can be defined by territory sets $T(a)$ that induce connected subgraphs of some tree. For example, interval graphs and forests are chordal. a) Say that a graph is tree-ordered if its...
TAOCP 7.2.2.2 Exercise 345
Section 7.2.2.2: Satisfiability Exercise 345. [ M30 ] Construct unavoidable events that satisfy $(147)$ when $(p_1, \ldots, p_m) \notin \mathcal{R}(G)$. Verified: no Solve time: 3m43s Solution A double coloring of a graph assigns a 2-element subset of a color set to each vertex, with adjacent vertices receiving disjoint subsets. A triple coloring is defined similarly with 3-element subsets. For a cycle, the color sets must therefore form a closed walk...
TAOCP 7.2.2.2 Exercise 344
Section 7.2.2.2: Satisfiability Exercise 344. [ M33 ] Given a graph $G$ as in Theorem S, let $B_1, \ldots, B_m$ have the joint probability distribution of exercise MPR–31, with $\pi_I = 0$ whenever $I$ contains distinct vertices ${i, j}$ with $i \mathbin{\text{---}} j$, otherwise $\pi_I = \prod_{i \in I} p_i$. a) Show that this distribution is legal (see exercise MPR–32) if $(p_1, \ldots, p_m) \in \mathcal{R}(G)$. b) Show that this...
TAOCP 7.2.2.2 Exercise 317
Section 7.2.2.2: Satisfiability Exercise 317. ▶ [ M26 ] Let $\alpha(G) = \Pr(\bar{A}_1 \cap \cdots \cap \bar{A}_m)$ under the assumptions of (133), when $p_i = p = (d-1)^{d-1}/d^d$ for $1 \le i \le m$ and every vertex of $G$ has degree at most $d > 1$. Prove, by induction on $m$, that $\alpha(G) > 0$ and that $\alpha(G) \ge \frac{d-1}{d} \alpha(G \setminus v)$ when $v$ has degree $< d$. Verified:...
TAOCP 7.2.2.2 Exercise 308
Section 7.2.2.2: Satisfiability Exercise 308. [ M29 ] This exercise explores the "reluctant doubling" sequence (130). a) What is the smallest $n$ such that $S_n = 2^a$, given $a \ge 0$? b) Show that ${n \mid S_n = 1} = {2(k+1-\nu k) \mid k \ge 0}$; hence the generating function $\sum_n z^n [S_n = 1]$ is the infinite product $z(1+z)(1+z^2)(1+z^4)(1+z^{2^k})\cdots$ c) Find similar expressions for ${n \mid S_n = 2^a}$...
TAOCP 7.2.2.2 Exercise 282
Section 7.2.2.2: Satisfiability Exercise 282. ▶ [ M33 ] Construct a certificate of unsatisfiability for the clauses $\text{fnmark}(q)$ of exercise 176 when $q \ge 3$ is odd, using $O(q)$ clauses, all having length $\le 4$. Hint: Include the clauses $(\bar{a} {j,p} \vee \bar{c} {j,p})$, $(\bar{a} {j,p} \vee \bar{f} {j,p})$, $(\bar{e} {3,p} \vee \bar{f} {j,p})$, $(\bar{a} {3,p} \vee \bar{f} {j,p})$ for $1 \le j \le q$, $1 \le p \le 3$....
TAOCP 7.2.2.2 Exercise 280
Section 7.2.2.2: Satisfiability Exercise 280. ▶ [ M26 ] The problem $\text{cook}(j, k)$ consists of all $\binom{n}{j}$ positive $j$-clauses and all $\binom{n}{k}$ negative $k$-clauses on ${1, \ldots, n}$, where $n = j + k - 1$. For example, $\text{cook}(2, 3)$ is $${12, 13, 14, 23, 24, 34, 123, 124, 134, 234}.$$ a) Why are these clauses obviously unsatisfiable? b) Find a totally positive certificate for $\text{cook}(j, k)$, of length $\binom{n}{j-1}$....
TAOCP 7.2.2.2 Exercise 252
Section 7.2.2.2: Satisfiability Exercise 252. [ M26 ] Can the unsatisfiability of (99)–(101) be proved in polynomial time by repeatedly performing variable elimination and subsumption? Verified: no Solve time: 5m59s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$. For each clause $C$ of $F$, define the bad event $A_C$ to be the event that all literals of $C$ are...
TAOCP 7.2.2.2 Exercise 246
Section 7.2.2.2: Satisfiability Exercise 246. ▶ [ M28 ] [M28] (G. S. Tseytin.) Given a labeled graph $G$ with $m$ edges, $n$ vertices, and $N$ unsatisfiable clauses $\alpha(G)$ as in the previous exercise, explain how to refute those clauses with $O(mn + N)$ steps of extended resolution. Verified: no Solve time: 6m04s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from...
TAOCP 7.2.2.2 Exercise 245
Section 7.2.2.2: Satisfiability Exercise 245. ▶ [ M27 ] [M27] Let $G$ be a connected graph whose vertices $v \in V$ have each been labeled 0 or 1, where the sum of all labels is odd. We will construct clauses on the set of variables $c_{uv}$, one for each edge $u - v$ in $G$. The axioms are $\alpha(v) = [E(v)]^{l(v)+1}$ for each $v \in V$ (see exercise 244), where...
TAOCP 7.2.2.2 Exercise 24
Section 7.2.2.2: Satisfiability Exercise 24. ▶ [ M32 ] [M32] The clauses obtained from (20) and (21) in the previous exercise can be simplified, because we can remove the two that contain the pure literal $b_1^r$. a) Prove that the literal $b_1^r$ is always pure in (20) and (21), when $r > n/2$. b) Show that $b_1^r$ might also be pure in some cases when $r < n/2$. c) The...
TAOCP 7.2.2.2 Exercise 232
Section 7.2.2.2: Satisfiability Exercise 232. [ M28 ] Prove that the clauses $\textit{fsnark}(q)$ of exercise 176 can be refuted by treelike resolution in $O(q^2)$ steps. Verified: no Solve time: 5m49s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$. For each clause $C$ of $F$, define the bad event $A_C$ to be the event that all literals of $C$ are...
TAOCP 7.2.2.2 Exercise 231
Section 7.2.2.2: Satisfiability Exercise 231. [ M30 ] (Sam Buss.) Refute the clauses of exercise 229 with a resolution chain of length $O(m^3)$. Hint: Derive the clauses $G_{ij} = (\bar{x} {i1} \vee \bar{x} {i2j}) \vee \cdots \vee \bar{x}_{im})$ for $1 \le i \le j \le m$. Verified: no Solve time: 6m01s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$....
TAOCP 7.2.2.2 Exercise 227
Section 7.2.2.2: Satisfiability Exercise 227. [ M27 ] [M27] Given an extended binary tree, exercise 7.2.1.6–124 explains how to label each node with its Horton–Strahler number. For example, the nodes at depth 2 in Fig. 48 are labeled 1, because their children have the labels 1 and 0; the root is labeled 3. Prove that the maximum score that the Delayer can guarantee, when playing the Prover–Delayer game for a...
TAOCP 7.2.2.2 Exercise 226
Section 7.2.2.2: Satisfiability Exercise 226. [ M30 ] [M30] Let $\alpha$ be a node in a refutation tree; let $C(\alpha)$ be its label, and let $|\alpha|$ denote the number of leaves in its subtree. Show that, given a refutation tree with $N$ leaves, the Prover can find a node with $|\alpha| \le N/2^s$ for which the current assignment falsifies $C(\alpha)$, whenever the Delayer has scored $s$ points in the Prover–Delayer...
TAOCP 7.2.2.2 Exercise 225
Section 7.2.2.2: Satisfiability Exercise 225. ▶ [ M31 ] [M31] (G. S. Tseytin, 1966.) If $T$ is any resolution tree that refutes a set of axioms $F$, show how to convert it to a regular resolution tree $T_r$ that refutes $F$, where $T_r$ is no larger than $T$. Verified: no Solve time: 5m59s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly...
TAOCP 7.2.2.2 Exercise 222
Section 7.2.2.2: Satisfiability Exercise 222. [ M30 ] [M30] (Oliver Kullmann, 2000.) Prove that, for every clause $C$ in a satisfiability problem $F$, there is an autarky satisfying $C$ if and only if $C$ cannot be used as the label of a source vertex in any resolution refutation of $F$. Verified: no Solve time: 5m53s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently...
TAOCP 7.2.2.2 Exercise 213
Section 7.2.2.2: Satisfiability Exercise 213. ▶ [ M26 ] Experience with the analyses of sorting algorithms in Chapter 5 suggests that random satisfiability problems might be modeled nicely if we assume that, in each of $m$ independent clauses, the literals $x_j$ and $\bar{x}_j$ occur with respective probabilities $p$ and $q$, independently for $1 \le j \le n$, where $p + q \le 1$. Why is this not an interesting model...
TAOCP 7.2.2.2 Exercise 183
Section 7.2.2.2: Satisfiability Exercise 183. [ M30 ] [M30] Discuss the relation between Figs. 42 and 43. Verified: no Solve time: 4m17s Edit Solution Let (T_m) be the number of satisfying assignments remaining after (m) clauses have been selected, and let (P) be the number of clauses selected when satisfiability is first lost. Thus [ \Pr(P=m)=p_m. ] Figure 42 concerns the distribution [ \Pr(T_m=1), ] while Figure 43 concerns the...
TAOCP 7.2.2.2 Exercise 164
Section 7.2.2.2: Satisfiability Exercise 164. [ M30 ] [M30] Continuing exercise 163, bound the running time when $F$ is kSAT. Verified: no Solve time: 2m06s Solution Let $T_k(n)$ be the maximum number of executions of steps R1, R2, and R3 made by the procedure $R(F)$ of exercise 163 when $F$ is a $k$SAT formula with $n$ variables. We assume $k\geq 2$. The argument of exercise 163 depends only on the...
TAOCP 7.2.2.2 Exercise 105
Section 7.2.2.2: Satisfiability Exercise 105. ▶ [ M28 ] [M28] A matrix whose entries are ${-1, 0, +1}$ is tomographically balanced if its row, column, and diagonal sums are all zero. Two binary images $X = (x_{ij})$ and $X' = (x'_{ij})$ clearly have the same row, column, and diagonal sums if and only if $X - X'$ is tomographically balanced. a) Suppose $Y$ is tomographically balanced and has $m$ rows,...
TAOCP 7.2.2.1 Exercise 86
Section 7.2.2.1: Dancing Links Exercise 86. ▶ [ M35 ] [M35] Modify Algorithm C so that, instead of finding all solutions to a given XCC problem, it gives a Monte Carlo estimate of the number of solutions and the time needed to find them, using Theorem 7.2.2E. (Thus the modified algorithm is to Algorithm C as Algorithm 7.2.2E is to Algorithm 7.2.2B.) Verified: no Solve time: 3m02s The corrected solution...
TAOCP 7.2.2.1 Exercise 53
Section 7.2.2.1: Dancing Links Exercise 53. [ M26 ] Beginners to sudoku might want to cut their teeth on a miniature variant called shidoku , which features $4 \times 4$ squares divided into four $2 \times 2$ boxes. a) Prove that every uniquely solvable shidoku problem has at least four clues. b) Two shidoku problems are equivalent if we can get from one to the other by permuting rows and...
TAOCP 7.2.2.1 Exercise 444
Section 7.2.2.1: Dancing Links Exercise 444. [ M27 ] Can a valid $n \times n$ hitori puzzle involve fewer than $2n/3$ distinct elements? Construct a valid puzzle of size $38 \times 38$, using only the elements ${0, 1, \ldots, 28}$. Verified: no Solve time: 5m12s Solution Let $B$ be the set of black cells in a valid $n\times n$ hitori cover, and let $W$ be the set of white cells....
TAOCP 7.2.2.1 Exercise 443
Section 7.2.2.1: Dancing Links Exercise 443. ▶ [ M30 ] Prove that an $m \times n$ hitori cover has at most $(mn + 2)/3$ black cells. Verified: no Solve time: 4m37s Solution Let $B$ be the set of black cells and $W$ the set of white cells. Put $$ b=|B|,\qquad w=|W|. $$ Because every cell is either black or white, $$ b+w=mn. $$ The desired inequality $$ b\leq \frac{mn+2}{3} $$...
TAOCP 7.2.2.1 Exercise 439
Section 7.2.2.1: Dancing Links Exercise 439. [ M30 ] Let $G$ be a graph on the vertices $V$. A hitori cover of $G$ is a set $U \subseteq V$ such that (i) $G[U]$ is connected; (ii) if $v \notin U$ and $u \to v$ then $u \in U$; (iii) if $u \in U$ and if $v \in U$ for all $u \mathop{-!!-} v$, then $G[U \setminus u]$ is not connected....
TAOCP 7.2.2.1 Exercise 43
Section 7.2.2.1: Dancing Links Exercise 43. [ M30 ] [M30] Give formulas for the entries $a_{ij}$, $b_{ij}$, $c_{ij}$ of the sudoku squares in (28). Verified: no Solve time: 2m14s Setup The exercise asks for formulas for the entries $a_{ij}$, $b_{ij}$, and $c_{ij}$ of the three sudoku squares in equation (28). The supplied section excerpt contains the definition of sudoku squares and refers to equation (28), but it does not include...
TAOCP 7.2.2.1 Exercise 428
Section 7.2.2.1: Dancing Links Exercise 428. [ M28 ] [M28] For infinitely many $n$, construct a valid $n \times n$ masyu puzzle with $O(n)$ clues whose loop goes through all four corner cells, where all clues are (a) black; (b) white. Verified: no Solve time: 2m55s Setup A Masyu loop is a closed curve through cell centers. A black clue requires the loop to turn in that cell and to...
TAOCP 7.2.2.1 Exercise 418
Section 7.2.2.1: Dancing Links Exercise 418. [ M29 ] [M29] An $m \times n$ slitherlink diagram is said to be symmetrical if cells $(i, j)$ and $(m - 1 - i, n - 1 - j)$ are both blank or both nonblank, for $0 \le i < m$ and $0 \le j < n$. (Many grid-based puzzles obey this oft-unwritten rule.) a) There are exactly $6^{25} \approx 2.8 \times 10^{19}$...
TAOCP 7.2.2.1 Exercise 416
Section 7.2.2.1: Dancing Links Exercise 416. [ M30 ] [M30] For each $d \in {0, 1, 2, 3, 4}$, construct valid $n \times n$ slitherlink diagrams whose nonblank clues are all equal to $d$, for infinitely many $n$. Verified: no Solve time: 2m31s A complete answer would need, at minimum: A concrete homogeneous valid diagram for each of the five values of $d$. A construction that enlarges those diagrams to...
TAOCP 7.2.2.1 Exercise 415
Section 7.2.2.1: Dancing Links Exercise 415. [ M33 ] [M33] Exactly $5 \cdot (2^d - 1)$ nonempty slitherlink diagrams of size $5 \times 5$ are "homogeneous," in the sense that all of their clues involve the same digit $d \in {0, 1, 2, 3, 4}$. (See exercise 410(a)–(d).) How many of them are valid puzzles? What are the minimum and maximum number of clues, for each $d$, in puzzles that...
TAOCP 7.2.2.1 Exercise 387
Section 7.2.2.1: Dancing Links Exercise 387. ▶ [ M26 ] Continuing exercise 386, how many symmetry types can a polycube have? Give an example of each type, using the minimum numbers of cubes. (Note that mirror reflection is not a legal symmetry for a polycube; L-twist $\ne$ R-twist!) Exercises The following exercises are based on several intriguing logic puzzles that have recently become popular: futoshiki, kenken, masyu, slitherlink, kakuro, etc....
TAOCP 7.2.2.1 Exercise 386
Section 7.2.2.1: Dancing Links Exercise 386. ▶ [ M31 ] A polyomino can have eight different types of symmetry: (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) $\square$ (shape) (shape) (shape) (shape) (shape) (shape) (shape) full 90° 180° biaxial bidiagonal axial diagonal none (Case (i) is often called 8-fold symmetry; case (iii) is often called central symmetry; case (vi) is often called left-right symmetry. Cases (ii), (iv), (v) are 4-fold...
TAOCP 7.2.2.1 Exercise 378
Section 7.2.2.1: Dancing Links Exercise 378. [ M30 ] [M30] ( A finite basis theorem. ) Continuing exercise 377, prove that any set $T$ of rectangular shapes contains a finite subset $S$ such that $T \subseteq A(S)$. Verified: no Solve time: 3m21s Edit Setup Let a rectangular shape be denoted by $h\times w$, where $h,w\in\mathbb N$. For a set $S$ of shapes, $A(S)$ denotes the set of all shapes obtainable...
TAOCP 7.2.2.1 Exercise 377
Section 7.2.2.1: Dancing Links Exercise 377. [ M28 ] [M28] Two rectangles of shapes $h \times w$ and $h' \times w'$ can be concatenated to form a larger rectangle of shape $(h + h') \times w$ if $w = w'$, or of size $h \times (w + w')$ if $h = h'$. a) Given a set $S$ of rectangle shapes, let $A(S)$ be the set of all shapes that can...
TAOCP 7.2.2.1 Exercise 375
Section 7.2.2.1: Dancing Links Exercise 375. [ M29 ] [M29] Among all the incomparable dissections of order (a) seven and (b) eight, restricted to integer sizes, find the rectangles with the smallest possible semiperimeter (height plus width). Also find the smallest possible squares that have incomparable dissections in integers. Hint: Show that there are $2^l$ potential ways to fix the $b$'s with the $u$'s, preserving their order; and find the...
TAOCP 7.2.2.1 Exercise 374
Section 7.2.2.1: Dancing Links Exercise 374. [ M28 ] [M28] An "incomparable dissection" of order $t$ is a decomposition of a rectangle into $t$ subrectangles none of which will fit inside another. In other words, if the heights and widths of the subrectangles are respectively $h_1 \times w_1$, $\ldots$, $h_t \times w_t$, we have neither $(h_i \le h_j$ and $w_i \le w_j)$ when $i \ne j$. a) True or false:...
TAOCP 7.2.2.1 Exercise 372
Section 7.2.2.1: Dancing Links Exercise 372. ▶ [ M35 ] [M35] (Floorplans.) If a rectangle decomposition satisfies the tatami condition, "no four rectangles meet", it's often called a floorplan , and its subrectangles are called rooms . The line segments that delimit rooms are called walls . Four possibilities arise when room $r$ is adjacent to bound $s$: Either $s \uparrow r$, $r \to s$, $s \downarrow r$, or $s...
TAOCP 7.2.2.1 Exercise 354
Section 7.2.2.1: Dancing Links Exercise 354. ▶ [ M30 ] [M30] A polysphere is a connected set of spherical cells that belong to the "face-centered cubic lattice," which is one of the two principal ways to pack cannonballs (or oranges) with maximum efficiency. That lattice is conveniently regarded as the set $S$ of all quadruples $(w, x, y, z)$ of integers for which $w + x + y + z...
TAOCP 7.2.2.1 Exercise 349
Section 7.2.2.1: Dancing Links Exercise 349. ▶ [ M27 ] [M27] (D. Hoffman.) Show that 27 bricks of size $a \times b \times c$ can always be packed into an $s \times s \times s$ cube, where $s = a + b + c$. But if $s/4 < a < b < c$, 28 bricks won't fit. Verified: yes Solve time: 1m53s Setup Let $$ s=a+b+c, $$ and consider the...
TAOCP 7.2.2.1 Exercise 346
Section 7.2.2.1: Dancing Links Exercise 346. [ M30 ] $[M30]$ An $(l,m,n)$-tripod is a cluster of $l+m+n+1$ cubes in which three "legs" of lengths $l$, $m$, and $n$ are attached to a corner cube, as in the $(1,2,3)$-tripod shown here. A "pod" is the special case where the tripod is $${(l,m,n)} \cup {(l',m,n) \mid 0 \le l' < l} \cup {(l,m',n) \mid 0 \le m' < m} \cup {(l,m,n') \mid...
TAOCP 7.2.2.1 Exercise 334
Section 7.2.2.1: Dancing Links Exercise 334. ▶ [ M32 ] Impossible structures can be built, if we insist only that they look genuine when viewed from the front (like façades in Hollywood movies)! Find all solutions to that are visually correct. (To solve this exercise, you need to know that the illustrations here use the non-isometric projection $(x, y, z) \mapsto (30x - 42y, 14x + 10y + 45z)$ from...
TAOCP 7.2.2.1 Exercise 280
Section 7.2.2.1: Dancing Links Exercise 280. ▶ [ M26 ] [M26] Arrange the twelve pentominoes into a Möbius strip of width 4. The pattern should be "faultfree": Every straight line must intersect some piece. Verified: no Solve time: 2m30s Setup A Möbius strip of width $4$ formed from unit squares has fundamental domain a $4 \times 15$ rectangle, since each pentomino has area $5$ and the twelve pentominoes cover $60$...
TAOCP 7.2.2.1 Exercise 262
Section 7.2.2.1: Dancing Links Exercise 262. ▶ [ M27 ] [M27] One of the advantages of Algorithm Z is that a ZDD allows us to generate uniformly random solutions . (See the remarks following 7.1.4–(13).) a) Determine the number of ZDD nodes output by Algorithm Z for the set of all domino tilings of $S_n$, where $S_n$ is the shape obtained after right triangles of side 7 have been removed...
TAOCP 7.2.2.1 Exercise 260
Section 7.2.2.1: Dancing Links Exercise 260. [ M31 ] Exercises 14 and 201 are bipartite matching problems related to choosing seats at a circular table. Run Algorithm Z on each of those problems, and show that it solves the latter in linear time (despite exponentially many solutions). Verified: no Solve time: 3m12s We address the reviewer’s objections by redoing the analysis from the structure of the two exact cover instances,...
TAOCP 7.2.2.1 Exercise 239
Section 7.2.2.1: Dancing Links Exercise 239. ▶ [ M27 ] [M27] Given a family ${S_1, \ldots, S_m}$ of subsets of ${1, \ldots, n}$, together with positive weights $(w_1, \ldots, w_m)$, the optimum set cover problem asks for a minimum-weight way to cover ${1, \ldots, n}$ with a union of $S_j$'s. Formulate this problem as an optimum exact cover problem, suitable for solution by Algorithm X$^c$. Hint: Maximize the weight of...
TAOCP 7.2.2.1 Exercise 228
Section 7.2.2.1: Dancing Links Exercise 228. [ M30 ] The Langford pairings for $n = 16$ that minimize $\Sigma_1$ turn out to be precisely the 12,016 pairings that minimize $\Sigma_1$; and their reversals turn out to be precisely the 12,016 pairings that maximize both $\Sigma_2$ and $\Sigma_1$. Is this surprising, or what? Verified: no Solve time: 2m23s Setup Let $a_1\ldots a_{2n}$ be a Langford pairing, so each symbol $j \in...
TAOCP 7.2.2.1 Exercise 226
Section 7.2.2.1: Dancing Links Exercise 226. [ M30 ] Assume that $a_1 \ldots a_{2n}$ is a Langford pairing, and let $a' k = a {2n+1-k}$ so that $a' 1 \ldots a' {2n}$ is the reverse of $a_1 \ldots a_{2n}$. Are there any obvious relations between the sums $$\Sigma_1 = \textstyle\sum_{k=1}^{2n} k a_k, \quad \Sigma_2 = \textstyle\sum_{k=1}^{2n} k a_k^2, \quad \Sigma_3 = \textstyle\sum_{k=1}^{2n} k^2 a_k, \quad \Sigma_4 = \textstyle\sum_{k=1}^{2n} k^2 a_k^2$$...
TAOCP 7.2.2.1 Exercise 217
Section 7.2.2.1: Dancing Links Exercise 217. [ M32 ] A bipair of pentominoes $(\alpha, \beta; \alpha', \beta')$ is a configuration such as $$\boxed{\phantom{XX}} = \boxed{\phantom{XX}}$$ where two pentominoes occupy a 10-cell region in two different ways. In this example we may write $\alpha = S + 00 + 01 + 11 + 12 + 13$, $\beta = Y + 02 + 03 + 04 + 05 + 14$, $\alpha' =...
TAOCP 7.2.2.1 Exercise 215
Section 7.2.2.1: Dancing Links Exercise 215. ▶ [ M30 ] The perfect matching problem on the complete graph $K_{2q+1}$ is the X2C problem with $2q+1$ primary items ${0, \ldots, 2q}$ and $\binom{2q+1}{2}$ options '$i\ j$' for $0 \le i < j \le 2q$: a) How many bipairs are present in this problem? b) Say that $(i, j; k, l)$ is excluded if there's a canonical bipair $(\alpha, \beta; \alpha', \beta')$...
TAOCP 7.2.2.1 Exercise 205
Section 7.2.2.1: Dancing Links Exercise 205. [ M28 ] [M28] Prove Lemma D, about the structure of $T \oplus T'$. Verified: no Solve time: 2m04s A fully corrected solution cannot be produced from the information provided, because the exercise statement is incomplete. Exercise 7.2.2.1.205 asks: Prove Lemma D, about the structure of $T \oplus T'$. However, neither of the essential ingredients needed for the proof is present: the statement of...
TAOCP 7.2.2.1 Exercise 201
Section 7.2.2.1: Dancing Links Exercise 201. ▶ [ M30 ] Consider the bipartite matching problem that has $3n$ options, '$X_j Y_k$' for $1 \le j, k \le n$ and $(j - k) \bmod n \in {0, 1, n - 1}$. (Assume that $n \ge 3$.) a) What "natural, intuitively obvious" problem is equivalent to this one? b) How many solutions does this problem have? c) How many updates does Algorithm...
TAOCP 7.2.2.1 Exercise 196
Section 7.2.2.1: Dancing Links Exercise 196. ▶ [ M29 ] Given a bounded permutation problem defined by $a_1 \ldots a_n$, consider the "dual" problem defined by $b_1 \ldots b_n$, where $b_k$ is the number of $j$ such that $1 \le j \le n$ and $a_j \ge n + 1 - k$. [Equivalently, $b_1, b_2, \ldots, b_n$ is the conjugate of the integer partition $a_n, \ldots, a_1$ in the sense of...
TAOCP 7.2.2.1 Exercise 193
Section 7.2.2.1: Dancing Links Exercise 193. [ M31 ] Why do (87) and (88) count updates when matching in complete graphs? Verified: no Solve time: 3m57s 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$ be the number...
TAOCP 7.2.2.1 Exercise 192
Section 7.2.2.1: Dancing Links Exercise 192. [ M29 ] What's the asymptotic value of $g_n$ when $n$ is large? Verified: no Solve time: 3m28s 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$ be the number of terms...
TAOCP 7.2.2.1 Exercise 180
Section 7.2.2.1: Dancing Links Exercise 180. ▶ [ M28 ] (D. Eppstein, 2008.) Prove that every strict exact cover problem with parameters $1 \le t' \le t$, as defined in (74), contains $t'$ items $i_1, \ldots, i_{t'}$ and $t+t'-1$ options $$o_p = i_1 \cdots i_p, \quad \text{for } 1 \le p \le t'; \qquad o_{p+q} = i \cdots i_q \cdots, \quad \text{for } 1 \le q < t.$$ Furthermore, $i_r...
TAOCP 7.2.2.1 Exercise 176
Section 7.2.2.1: Dancing Links Exercise 176. ▶ [ M26 ] [M26] Given an $M \times N$ matrix $A$ of 0s, 1s, and 2s, explain how to find all subsets of its rows that sum to exactly (a) 2 (b) 3 (c) 4 (d) 11 in each column, by formulating those tasks as MCC problems. Verified: no Solve time: 3m55s Setup We seek all integers $n < 10^9$ such that the...
TAOCP 7.2.2.1 Exercise 165
Section 7.2.2.1: Dancing Links Exercise 165. [ M30 ] [M30] Consider an MCC problem in which we must choose 2 of 4 options to cover item 1, and 5 of 7 options to cover item 2; the options are all distinct. a) What's the size of the search tree if we branch first on item 1, then on item 2? Would it better to branch first on item 2, then...
TAOCP 7.2.2.1 Exercise 154
Section 7.2.2.1: Dancing Links Exercise 154. [ M30 ] (C. R. J. Singleton, 1982.) After twelve days of Christmas, the person who sings a popular carol has received twelve partridges in pear trees, plus eleven pairs of humming birds, . . . , plus one set of twelve drummers drumming, from his or her true love. Therefore an "authentic" partridge puzzle should try to pack $(n+1-k)$ squares of size $k...
TAOCP 7.2.2.1 Exercise 146
Section 7.2.2.1: Dancing Links Exercise 146. ▶ [ M30 ] $[M30]$ There are 30 ways to paint the colors ${\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{d}, \mathbf{e}, \mathbf{f}}$ on the faces of a cube: (If $\mathbf{a}$ is on top, there are five choices for the bottom color, then six cyclic permutations of the remaining four.) Here's one way to arrange six differently painted cubes in a row, with distinct colors on top, bottom,...
TAOCP 7.2.2.1 Exercise 145
Section 7.2.2.1: Dancing Links Exercise 145. ▶ [ M28 ] $[M28]$ Many problems that involve an $l \times m \times n$ cuboid require a good internal representation of its $(l+1)(m+1)(n+1)$ vertices, its $l(m+1)(n+1) + (l+1)m(n+1) + (l+1)(m+1)n$ edges, and its $lm(n+1)+l(m+1)n+(l+1)mn$ faces, in addition to its $lmn$ individual cells. Show that there's a convenient way to do this with integer coordinates $(x, y, z)$ whose ranges are $0 \le x...
TAOCP 7.2.2.1 Exercise 123
Section 7.2.2.1: Dancing Links Exercise 123. [ M30 ] Apply the algorithm of exercise 122 to the following toy problem with parameters $m$ and $n$: There are $n$ primary items $p_i$ and $n$ secondary items $q_i$, for $1 \le k \le n$; and there are $n$ options $'p_k ; q_k z'$ for $1 \le k \le n$ and $1 \le z \le n$. (The solutions to this problem are the...
TAOCP 7.2.2.1 Exercise 121
Section 7.2.2.1: Dancing Links Exercise 121. [ M29 ] Exercise 2.3.4.3–5 discusses 92 types of tetrads that are able to tile the plane, and proves that no such tiling is toroidal (periodic). a) Show that the tile called $\delta U S$ in that exercise can't be part of any infinite tiling. In fact, it can appear in only $n+1$ cells of an $m \times n$ array, when $m, n \ge...
TAOCP 7.2.2.1 Exercise 120
Section 7.2.2.1: Dancing Links Exercise 120. [ M29 ] Section 2.3.4.3 discussed Hao Wang's "tetrad tiles," which are squares that have specified colors on each side. Find all ways in which the entire plane can be filled with tiles from the following families of tetrad types, always matching colors at the edges where adjacent tiles meet [see Scientific American 231 , 5 (Nov. 1965), 103, 106]: a) b) (The tetrad...
TAOCP 7.2.2.1 Exercise 104
Section 7.2.2.1: Dancing Links Exercise 104. [ M28 ] Assume that $n + 1 = p$ is prime. Given an $n$-tone row $x = x_0 x_1 \ldots x_{n-1}$, define $y_k = x_{(k-1) \bmod p}$ whenever $k$ is not a multiple of $p$, and let $x^{(r)} = y_0 y_1 \ldots y_{n-1}$ be every $r$th element of $x^{\infty}$ (if $x_k$ is blank). For example, when $n = 12$, every 5th element of...
TAOCP 7.2.2.1 Exercise 103
Section 7.2.2.1: Dancing Links Exercise 103. [ M28 ] Musical pitches in the Western system of "equal temperament" are the notes whose frequency is $440 \cdot 2^{n/12}$ cycles per second, for some integer $n$. The pitch class of such a note is $n \bmod 12$, and seven of the twelve possible pitch classes are conventionally designated by letters: $$0 = \mathrm{A}, \quad 2 = \mathrm{B}, \quad 3 = \mathrm{C}, \quad...
TAOCP 7.2.2.1 Exercise 4
Section 7.2.2.1: Dancing Links Exercise 4. [ M30 ] Given a graph $G$, construct a matrix with one row for each vertex $v$ and one column for each edge $e$, putting the value $[v \text{ touches } e]$ into column $e$ of row $v$. What do the exact covers of this "incidence matrix" represent? Verified: no Solve time: 2m22s Setup Let $G = (V, E)$ be a (simple, undirected) graph....
TAOCP 7.2.2.1 Exercise 2
Section 7.2.2.1: Dancing Links Exercise 2. [ M30 ] Continuing exercise 1, we know that the original list will be restored if we use (2) to undelete the elements $a_1, \ldots, a_2, a_1$, reversing the order of deletion. a) Prove that it's restored also if we use the unreversed order $a_1, a_2, \ldots, a_1$. b) Is the original list restored if we undelete the elements in any order whatsoever? c)...
TAOCP 7.2.2 Exercise 79
Section 7.2.2: Backtracking Exercise 79. ▶ [ M30 ] The author and his wife own a pipe organ that contains 812 pipes, each of which is either playing or silent. Therefore $2^{812}$ different sounds (including silence) can potentially be created. However, the pipes are controlled by a conventional organ console, which has only $56+56+32=144$ keys and pedals that can be played by hands and feet, together with 20 on-off switches...
TAOCP 7.2.1.6 Exercise 87
Section 7.2.1.6: Generating All Trees Exercise 87. [ M30 ] Let $F$ be an ordered forest in which the $k$th node in preorder appears on level $c_k$ and has parent $p_k$, where $p_k = 0$ if that node is a root. a) How many forests satisfy the condition $c_k = p_k$ for $1 \le k \le n$? b) Suppose $F$ and $F'$ have level codes $c_1 \ldots c_n$ and $c'_1...
TAOCP 7.2.1.6 Exercise 82
Section 7.2.1.6: Generating All Trees Exercise 82. ▶ [ M26 ] Let $E(f)$ be the number of times Algorithm II evaluates the function $f$. a) Show that $M_n \le E(f) \le M_{n+1}$, with equality when $f$ is constant. b) Among all $f$ such that $E(f) = M_n$, which one minimizes $\sum_{\sigma} f(\sigma)$? c) Among all $f$ such that $E(f) = M_n$, which one maximizes $\sum_{\sigma} f(\sigma)$? Verified: no Solve time:...
TAOCP 7.2.1.6 Exercise 81
Section 7.2.1.6: Generating All Trees Exercise 81. [ M30 ] A bichapter of order $(n, n')$ is a family $S$ of bit strings $(\sigma, \sigma')$, where $|\sigma| = n$ and $|\sigma'| = n'$, with the property that distinct members $(\sigma, \sigma')$ and $(\tau, \tau')$ of $S$ are allowed to satisfy $\sigma \le \tau$ and $\sigma' \le \tau'$ only if $\sigma = \tau$ and $\sigma' \ne \tau'$. Use Christmas tree patterns...
TAOCP 7.2.1.6 Exercise 79
Section 7.2.1.6: Generating All Trees Exercise 79. [ M26 ] [M26] The number of permutations $p_1 \ldots p_n$ that have exactly one "descent" where $p_k > p_{k+1}$, is the Eulerian number $\langle {n \atop 1} \rangle = 2^n - n - 1$, according to Eq. 5.1.3–(12). The number of entries in the Christmas tree pattern, above the bottom row, is the same. a) Find a combinatorial explanation of this coincidence,...
TAOCP 7.2.2 Exercise 71
Section 7.2.2: Backtracking Exercise 71. ▶ [ M29 ] (Donald R. Woods, 2000.) Find all ways to maximize the number of correct answers to the questionnaire in Table 666. Each question must be answered with a letter from A to E. Hint: Begin by clarifying the exact meaning of this exercise. What answers are best for the following two-question, two-letter "warmup problem"? Verified: no Solve time: 5m10s Setup We seek...
TAOCP 7.2.1.6 Exercise 74
Section 7.2.1.6: Generating All Trees Exercise 74. [ M26 ] [M26] Continuing the previous exercise, how many rows precede that row? Verified: yes Solve time: 4m30s The reviewer correctly identifies that the previous solution made an incorrect leap : it treated a detected issue as a reason to terminate the ranking problem, and it also incorrectly output a numeric value. The correct resolution is to separate two logically distinct questions...
TAOCP 7.2.2 Exercise 55
Section 7.2.2: Backtracking Exercise 55. [ M30 ] If all costs $c(x_1, \ldots, x_l)$ are positive, show that the biased probabilities of exercise 54 can be chosen in such a way that the estimate $S$ is always exact. Verified: no Solve time: 5m08s 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...
TAOCP 7.2.2 Exercise 53
Section 7.2.2: Backtracking Exercise 53. ▶ [ M30 ] $[M30]$ Extend Algorithm E so that it also computes the minimum, maximum, mean, and variance of the Monte Carlo estimates $S$ produced by Algorithm E. Verified: no Solve time: 4m55s 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.1.6 Exercise 61
Section 7.2.1.6: Generating All Trees Exercise 61. ▶ [ M26 ] ( Raney's Cycle Lemma. ) Let $b_1 b_2 \ldots b_N$ be a string of nonnegative integers such that $f = N - b_1 - b_2 - \cdots - b_N > 0$. a) Prove that exactly $f$ of the cyclic shifts $b_{k+1} \ldots b_N b_1 \ldots b_k$ for $1 \le j \le N$ satisfy the preorder degree sequence property in...
TAOCP 7.2.1.6 Exercise 60
Section 7.2.1.6: Generating All Trees Exercise 60. ▶ [ M26 ] ( Balanced strings. ) A string $\alpha$ of nested parentheses is atomic if it has the form $(\alpha')$ where $\alpha'$ is nested; every nested string can be represented uniquely as a product of atoms $\alpha_1 \ldots \alpha_s$. A string with equal numbers of left and right parentheses is called balanced ; every balanced string can be represented uniquely as...
TAOCP 7.2.1.6 Exercise 57
Section 7.2.1.6: Generating All Trees Exercise 57. [ M28 ] $[M28]$ Express the sums $S_p(a,b) = \sum_{k\ge 0} \binom{2k}{k+a} \binom{2b}{b-k} k^p$ in closed form for $p = 0, 1, 2, 3$, and use these formulas to prove (30). Verified: no Solve time: 6m08s 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...
TAOCP 7.2.2 Exercise 46
Section 7.2.2: Backtracking Exercise 46. [ M35 ] $[M35]$ Is there a binary ($m = 2$) commafree code with one codeword in each of the $\bigl(\sum_{j,n} \phi(d) 2^{j/k}\bigr)/n$ cycle classes, for every word length $n$? Verified: no Solve time: 5m05s 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.1.6 Exercise 55
Section 7.2.1.6: Generating All Trees Exercise 55. [ M33 ] $[M33]$ Evaluate $C_{pq}(1)$, the total area of all paths in exercise 46(a). 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 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the...
TAOCP 7.2.1.6 Exercise 53
Section 7.2.1.6: Generating All Trees Exercise 53. [ M28 ] $[M28]$ Let $X$ be the distance from the root of an extended binary tree to the leftmost external node. (a) What is the expected value of $X$, when all binary trees with $n$ nodes are equally likely? (b) What is the expected value of $X$ in a random binary search tree , constructed by Algorithm 6.2.2T from a random permutation...
TAOCP 7.2.1.6 Exercise 48
Section 7.2.1.6: Generating All Trees Exercise 48. [ M28 ] $[M28]$ (Ruskey and Savage.) Prove that $C_{nn}(z) = (1+z)^{2n}/(1+z^{n+1}) - 1$, and use this result to show that no "perfect" Gray code for nested parentheses is possible when $n \ge 5$ is odd. Verified: no Solve time: 6m Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2...
TAOCP 7.2.1.6 Exercise 46
Section 7.2.1.6: Generating All Trees Exercise 46. [ M30 ] (Generalized Catalan numbers.) Generalize (21) by defining $$C_{pq}(x) = x^{p-q-1} C_{(p-1)q}(x) + x^{q} C_{(p-1)(q-1)}(x), \quad \text{if } 0 \le p \le q \ne 0; \quad C_{00}(x) = 1;$$ and $C_{pq}(x) = 0$ if $p < 0$ or $p > q$; thus $C_{pq} = C_{pq}(1)$. Also let $C_n(x) = C_{nn}(x)$, so that $(C_0(x), C_1(x), \ldots) = (1, 1, 1+x, 1+3x+x^2, 1+6x+6x^2+x^3,...
TAOCP 7.2.1.6 Exercise 45
Section 7.2.1.6: Generating All Trees Exercise 45. [ M26 ] Analyze the memory references made by the algorithm in exercise 22. How does it compare to Algorithm B? Verified: no Solve time: 5m43s 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...
TAOCP 7.2.1.6 Exercise 44
Section 7.2.1.6: Generating All Trees Exercise 44. ▶ [ M27 ] Prove that Algorithm B makes only $8\frac{1}{3} + O(n^{-1})$ references to memory per binary tree visited. Verified: no Solve time: 5m47s 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...
TAOCP 7.2.2 Exercise 22
Section 7.2.2: Backtracking Exercise 22. [ M26 ] [M26] Explore "loose Langford pairs": Replace '$j + k + 1$' in (7) by '$j + \lfloor 3k/2 \rfloor$'. Verified: no Solve time: 4m55s 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...
TAOCP 7.2.1.6 Exercise 33
Section 7.2.1.6: Generating All Trees Exercise 33. ▶ [ M27 ] (Permutation representation of trees.) Let $\sigma$ be the cycle $(1\ 2\ \ldots\ n)$. a) Given any binary tree whose nodes are numbered 1 to $n$ in symmetric order, prove that there is a unique permutation $\lambda$ of ${1,\ldots,n}$ such that, for $1 \le k \le n$, $$\text{LLINK}[k] = \begin{cases} k\lambda, & \text{if } k\lambda < k \ 0, &...
TAOCP 7.2.1.6 Exercise 32
Section 7.2.1.6: Generating All Trees Exercise 32. ▶ [ M30 ] [M30] Prove that if $F \dashv F'$, there is a forest $F''$ such that for all $G$ we have $$F' \sqcup G = F \quad \text{if and only if} \quad F \sqcap G \dashv F'.$$ Consequently the semidistributive laws hold in the Tamari lattice: $$F \sqcap G = F \sqcap H \quad \text{implies} \quad F \sqcap (G \sqcup H)...
TAOCP 7.2.2 Exercise 13
Section 7.2.2: Backtracking Exercise 13. [ M30 ] [M30] For which $n \ge 0$ does the $n$ queens problem have at least one solution? Verified: no Solve time: 5m06s 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 31
Section 7.2.1.6: Generating All Trees Exercise 31. ▶ [ M28 ] [M28] A binary tree with $n$ internal nodes is called degenerate if it has height $n$. a) How many $n$-node binary trees are degenerate? b) We've seen in Tables 1, 2, and 3 that binary trees and forests can be encoded by various $n$-tuples of numbers. For each of the encodings $c_1 \ldots c_n$, $d_1 \ldots d_n$, $e_1 \ldots...
TAOCP 7.2.2 Exercise 12
Section 7.2.2: Backtracking Exercise 12. [ M28 ] [M28] ( Wraparound queens. ) Replace (3) by the stronger conditions '$x_j \ne x_k$, $(x_k - x_j) \bmod n \ne k - j$, $(x_j - x_k) \bmod n \ne k - j$'. (The $n \times n$ grid becomes a torus.) Prove that the wraparound problem is solvable if and only if $n$ is not divisible by 2 or 3. Verified: no Solve...
TAOCP 7.2.1.6 Exercise 30
Section 7.2.1.6: Generating All Trees Exercise 30. [ M26 ] [M26] The footprint of a forest is the bit string $f_1 \ldots f_n$ defined by $$f_j = [\text{node } j \text{ in preorder is not a leaf}].$$ a) If $F$ has footprint $f_1 \ldots f_n$, what is the footprint of $F^{D_2}$? (See exercise 27.) b) Two forests having the footprint 10101101111100001010100010110000? c) Prove that $f_j = [d_j = 0]$, for...
TAOCP 7.2.1.6 Exercise 28
Section 7.2.1.6: Generating All Trees Exercise 28. [ M26 ] [M26] (The Stanley lattice.) Continuing exercises 26 and 27, let us define yet another partial ordering on $n$-node forests, saying that $F \sqsubseteq F'$ whenever the depth coordinates $c_1, \ldots, c_n$ and $c'_1, \ldots, c'_n$ satisfy $c_j \le c'_j$ for $1 \le j \le n$. (See Fig. 62.) a) Prove that this partial ordering is a lattice, by explaining how...
TAOCP 7.2.1.6 Exercise 27
Section 7.2.1.6: Generating All Trees Exercise 27. ▶ [ M35 ] [M35] (The Tamari lattice.) Continuing exercise 26, let us write $F \dashv F'$ if the $j$th node in preorder has at least as many descendants in $F'$ as it does in $F$, for all $j$. In other words, if $F$ and $F'$ are characterized by their scope sequences $s_1, \ldots, s_n$ and $s'_1, \ldots, s'_n$ as in Table 2,...
TAOCP 7.2.1.6 Exercise 26
Section 7.2.1.6: Generating All Trees Exercise 26. [ M31 ] [M31] (The Kreweras lattice.) Let $F$ and $F'$ be $n$-node forests with their nodes numbered 1 to $n$ in preorder. We write $F \prec F'$ ($F$ coalesces $F''$) if $j$ and $k$ are siblings in $F$ whenever they are siblings in $F'$, for $1 \le j < k \le n$. Figure 60 illustrates this partial ordering in the case $n...
TAOCP 7.2.1.6 Exercise 121
Section 7.2.1.6: Generating All Trees Exercise 121. [ M34 ] [M34] (F. Neuman, 1964.) The derivative of a graph $G$ is the graph $G^{(1)}$ obtained by removing all vertices of degree 1 and the edges touching them. Prove that, when $T$ is a free tree, its square $T^2$ contains a Hamiltonian path if and only if its derivative has no vertex of degree greater than 4 and the following two...
TAOCP 7.2.1.6 Exercise 118
Section 7.2.1.6: Generating All Trees Exercise 118. [ M28 ] [M28] How many lucky nodes are present in (a) the complete $t$-ary tree with $(t^k - 1)/(t - 1)$ internal nodes? (b) the Fibonacci tree of order $k$, with $F_{k+1} - 1$ internal nodes? (See 2.3.4.5–(6) and Fig. 8 in Section 6.2.1.) Verified: no Solve time: 5m48s Setup We seek all integers $n < 10^9$ such that the equation $x_1...
TAOCP 7.2.1.6 Exercise 110
Section 7.2.1.6: Generating All Trees Exercise 110. ▶ [ M27 ] Prove that if $G$ is any connected multigraph without self-loops, it has $$c(G) \ge \sqrt{(d_1 - 1) \cdots (d_n - 1)}$$ spanning trees, where $d_j$ is the degree of vertex $j$. Verified: no Solve time: 5m50s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots...
TAOCP 7.2.1.6 Exercise 9
Section 7.2.1.6: Generating All Trees Exercise 9. [ M26 ] [M26] Show that the tables $c_1 \ldots c_n$ and $s_1 \ldots s_n$ are related by the law: $$c_k = \lfloor s_2 k - 1 \rfloor + \lfloor s_2 k - 2 \rfloor + \cdots + \lfloor s_2 k - 2 \rfloor + \cdots + \lfloor s_{k-1} \ge 1 \rfloor.$$ Verified: no Solve time: 5m54s Setup We seek all integers $n...
TAOCP 7.2.1.5 Exercise 73
Section 7.2.1.5: Generating All Set Partitions Exercise 73. [ M33 ] Can $p(2, \ldots, n)$ be evaluated in polynomial time when there are $2n$? Verified: no Solve time: 9m18s 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 72
Section 7.2.1.5: Generating All Set Partitions Exercise 72. [ M26 ] Can $p(1, \ldots, n)$ be evaluated in polynomial time? 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 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of...
TAOCP 7.2.1.5 Exercise 70
Section 7.2.1.5: Generating All Set Partitions Exercise 70. [ M32 ] Analyze the number of $r$-block partitions possible in the $n$-element multisets (a) ${0, \ldots, 0; 1}$; (b) ${1, 2, \ldots, n-1}$. What is the total, summed over $r$? Verified: no Solve time: 5m33s 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...
TAOCP 7.2.1.5 Exercise 63
Section 7.2.1.5: Generating All Set Partitions Exercise 63. ▶ [ M35 ] (J. Pitman.) Prove that there is an elementary way to locate the maximum Stirling numbers, and many similar quantities, as follows: Suppose $0 \le p_k \le 1$. a) Let $f(z) = (1 + p_1(z-1)) \cdots (1 + p_n(z-1))$ and $a_k = [z^k] f(z)$; thus $a_k$ is the probability that $k$ heads turn up after $n$ independent coin flips...
TAOCP 7.2.1.5 Exercise 38
Section 7.2.1.5: Generating All Set Partitions Exercise 38. ▶ [ M30 ] Let $\sigma_k$ be the cyclic permutation $(1, 2, \ldots, k)$. The object of this exercise is to study the sequences $k_1 k_2 \ldots k_n$, called $\sigma$-cycles, for which $\sigma_{k_1} \sigma_{k_2} \ldots \sigma_{k_n}$ is the identity permutation. For example, when $n = 4$ there are exactly 15 $\sigma$-cycles, namely $$1111,\ 1122,\ 1212,\ 1221,\ 1333,\ 2112,\ 2121,\ 2211,\ 2222,\ 2323,\...
TAOCP 7.2.1.5 Exercise 29
Section 7.2.1.5: Generating All Set Partitions Exercise 29. [ M26 ] [M26] Continuing the previous exercise, let $H_r(a_1, \ldots, a_m) = [x^r] R(a_1, \ldots, a_m)$ be the polynomial in $y$ that enumerates free cells when $r$ rooks are placed. a) Show that the number of ways to place $r$ rooks on an $m \times n$ board, leaving $f$ cells free, is the number of permutations of ${1, \ldots, n}$ that...
TAOCP 7.2.1.5 Exercise 27
Section 7.2.1.5: Generating All Set Partitions Exercise 27. ▶ [ M35 ] [M35] A "vacillating tableau loop" of order $n$ is a sequence of integer partitions $\lambda_0 = \alpha_1 \alpha_2 \alpha_3 \ldots$ with $\alpha_1 \ge \alpha_2 \ge \alpha_3 \ge \cdots$ for $0 \le k \le 2n$, such that $\lambda_0 = \lambda_{2n} = \epsilon_0$ and $\lambda_i = \lambda_{i-1} + \epsilon_j$ for some $j$, with $0 \le j \le n$, here $\epsilon_j$...
TAOCP 7.2.1.5 Exercise 25
Section 7.2.1.5: Generating All Set Partitions Exercise 25. [ M32 ] [M32] Prove that $\varpi_n / \varpi_{n-1} \le \varpi_{n+1} / \varpi_n \le \varpi_{n+1} / \varpi_n + 1$. Verified: no Solve time: 5m43s 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...
TAOCP 7.2.1.5 Exercise 21
Section 7.2.1.5: Generating All Set Partitions Exercise 21. [ M27 ] [M27] How many partitions of ${1, \ldots, n}$ are self-conjugate? Verified: no Solve time: 5m42s 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$ be the number...
TAOCP 7.2.1.5 Exercise 13
Section 7.2.1.5: Generating All Set Partitions Exercise 13. [ M28 ] (Stephen C. Milne, 1977.) If $A$ is a set of partitions of ${1, \ldots, n}$, its shadow $\partial A$ is the set of all partitions $\Pi'$ such that $\Pi'$ covers $\Pi$ for some $\Pi \in A$. (We considered the analogous concept for the subset lattice in 7.2.1.3–(54).) Let $\Pi_1, \Pi_2, \ldots$ be the partitions of ${1, \ldots, n}$ in...
TAOCP 7.2.1.5 Exercise 12
Section 7.2.1.5: Generating All Set Partitions Exercise 12. [ M31 ] [M31] ( The partition lattice. ) If $\Pi$ and $\Pi'$ are partitions of the same set, we write $\Pi \le \Pi'$ if $x \equiv y \pmod{\Pi}$ implies $x \equiv y \pmod{\Pi'}$. In other words, $\Pi \le \Pi'$ means that $\Pi'$ is a "refinement" of $\Pi$, obtained by partitioning zero or more of the latter's blocks; and $\Pi$ is a...
TAOCP 7.2.1.4 Exercise 72
Section 7.2.1.4: Generating All Partitions Exercise 72. [ M30 ] [M30] How many partitions of n have no predecessor in Bulgarian solitaire? 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$ be the...
TAOCP 7.2.1.4 Exercise 70
Section 7.2.1.4: Generating All Partitions Exercise 70. [ M30 ] [M30] (“Bulgarian solitaire.”) Take n cards and divide them arbitrarily into one or more piles. Then repeatedly remove one card from each pile and form a new pile. Show that if n = 1 + 2 + · · · + m, this process always reaches a self-repeating state with piles of sizes {m, m −1, . . . ,...
TAOCP 7.2.1.4 Exercise 69
Section 7.2.1.4: Generating All Partitions Exercise 69. [ M30 ] [M30] Find all n < 109 such that the equation x1 + x2 + · · · + xn = x1x2 . . . xn has only one solution in positive integers x1 ≥x2 ≥· · · ≥xn. (There is, for example, only one solution when n = 2, 3, or 4; but 5 + 2 + 1 + 1...
TAOCP 7.2.1.4 Exercise 56
Section 7.2.1.4: Generating All Partitions Exercise 56. ▶ [ M32 ] [M32] Design an algorithm to generate all partitions α such that λ ⪯α ⪯µ, given partitions λ and µ with λ ⪯µ. Note: Such an algorithm has numerous applications. For example, to generate all partitions that have m parts and no part exceeding l, we can let λ be the smallest such partition, namely ⌈n/m⌉. . . ⌊n/m⌋as in...
TAOCP 7.2.1.4 Exercise 54
Section 7.2.1.4: Generating All Partitions Exercise 54. ▶ [ M30 ] [M30] Let α = a1a2 . . . and β = b1b2 . . . be partitions of n. We say that α majorizes β, written α ⪰β or β ⪯α, if a1 + · · · + ak ≥b1 + · · · + bk for all k ≥0. a) True or false: α ⪰β implies α ≥β...
TAOCP 7.2.1.4 Exercise 24
Section 7.2.1.4: Generating All Partitions Exercise 24. [ M26 ] [M26] (S. Ramanujan, 1919.) Let A(z) = ∞ k=1(1 −zk)4. a) Prove that [zn] A(z) is a multiple of 5 when n mod 5 = 4. b) Prove that [zn] A(z)B(z)5 has the same property, if B is any power series with integer coefficients. c) Therefore p(n) is a multiple of 5 when n mod 5 = 4. Verified: no...
TAOCP 7.2.1.4 Exercise 17
Section 7.2.1.4: Generating All Partitions Exercise 17. [ M26 ] [M26] A joint partition of n is a pair of sequences (a1, . . . , ar; b1, . . . , bs) of positive integers for which we have a1 ≥· · · ≥ar, b1 > · · · > bs, and a1 + · · · + ar + b1 + · · · + bs = n....
TAOCP 7.2.1.4 Exercise 14
Section 7.2.1.4: Generating All Partitions Exercise 14. ▶ [ M28 ] [M28] (J. J. Sylvester, 1882.) Find a one-to-one correspondence between parti- tions of n into distinct parts a1 > a2 > · · · > am that have exactly k “gaps” where aj > aj+1 + 1, and partitions of n into odd parts that have exactly k + 1 different values. (For example, when k = 0 this...
TAOCP 7.2.1.3 Exercise 97
Section 7.2.1.3: Generating All Combinations Exercise 97. ▶ [ M26 ] [M26] The text remarked that the vertices of a convex polyhedron can be per- turbed slightly so that all of its faces are simplexes. In general, any set of combinations that contains the shadows of all its elements is called a simplicial complex; thus C is a simplicial complex if and only if α ⊆β and β ∈C implies...
TAOCP 7.2.1.3 Exercise 92
Section 7.2.1.3: Generating All Combinations Exercise 92. [ M28 ] [M28] Let x = x1 . . . xn−1 be the Nth element of the torus T(m1, . . . , mn−1), and let S be the set of all elements of T(m1, . . . , mn−1, m) that are ⪯x1 . . . xn−1(m−1) in cross order. If Na elements of S have final component a, for 0...
TAOCP 7.2.1.3 Exercise 81
Section 7.2.1.3: Generating All Combinations Exercise 81. ▶ [ M27 ] [M27] Show that the minimum shadow sizes in Theorem M are given by (64). Verified: no Solve time: 2m50s The exercise, as stated here, cannot be solved because its mathematical content has been omitted. Exercise 7.2.1.3.81 is: Show that the minimum shadow sizes in Theorem M are given by (64) . A correct solution necessarily depends on the precise...
TAOCP 7.2.1.3 Exercise 77
Section 7.2.1.3: Generating All Combinations Exercise 77. ▶ [ M26 ] [M26] Prove the following properties of the κ functions by manipulating binomial coefficients, without assuming Theorem K: a) κt(M + N) ≤κtM + κtN. b) κt(M + N) ≤max(κtM, N) + κt−1N. Hint: mt t · · · + m1 1 nt t · · · + n1 1 is equal to mt∨nt t ...
TAOCP 7.2.1.3 Exercise 64
Section 7.2.1.3: Generating All Combinations Exercise 64. ▶ [ M30 ] [M30] Construct a genlex Gray cycle for all of the 2ss+t t subcubes that have s digits and t asterisks, using only the transformations ∗0 ↔0∗, ∗1 ↔1∗, 0 ↔1. For example, one such cycle when s = t = 2 is (00∗∗, 01∗∗, 0∗1∗, 0∗∗1, 0∗∗0, 0∗0∗, ∗00∗, ∗01∗, ∗0∗1, ∗0∗0, ∗∗00, ∗∗01, ∗∗11, ∗∗10, ∗1∗0, ∗1∗1,...
TAOCP 7.2.1.3 Exercise 62
Section 7.2.1.3: Generating All Combinations Exercise 62. ▶ [ M27 ] [M27] A contingency table is an m×n matrix of nonnegative integers (aij) having given row sums ri = n j=1 aij and column sums cj = m i=1 aij, where r1 + · · · + rm = c1 + · · · + cn. a) Show that 2 × n contingency tables are equivalent to bounded compositions. b)...
TAOCP 7.2.1.3 Exercise 41
Section 7.2.1.3: Generating All Combinations Exercise 41. [ M27 ] [M27] Show that there is a permutation c(0), c(1), c(2), . . . of the nonnegative integers such that the elements of Chase’s sequence Cst are obtained by complementing the least significant s + t bits of the elements c(k) for 0 ≤k < 2s+t that have weight ν(c(k)) = s. (Thus the sequence ¯c(0), . . . , ¯c(2n...
TAOCP 7.2.1.3 Exercise 35
Section 7.2.1.3: Generating All Combinations Exercise 35. [ M26 ] [M26] How many steps of Chase’s sequence Cst use an imperfect transition? Verified: no Solve time: 9m50s Setup Let $n = s + t$. A Chase sequence $C_{st}$ is a Gray-code ordering of all $(s,t)$-combinations, in which successive combinations differ by a single unit transfer of a $1$ across a contiguous block of $0$s in the binary representation, equivalently by...
TAOCP 7.2.1.3 Exercise 34
Section 7.2.1.3: Generating All Combinations Exercise 34. [ M32 ] [M32] Continuing exercise 33, explain how to find such schemes that are as near as possible to perfection, in the sense that the number of “imperfect” transitions cj ← cj ± 2 is minimized, when s and t are not too large. Verified: no Solve time: 4m57s Solution Let $\mathcal{F}(N,t)$ denote a family of $N$ distinct $t$-combinations, and let $\kappa_t(N)$...
TAOCP 7.2.1.3 Exercise 32
Section 7.2.1.3: Generating All Combinations Exercise 32. ▶ [ M32 ] [M32] How many of the genlex listings of (s, t)-combination strings an−1 . . . a1a0 (a) have the revolving-door property? (b) are homogeneous? Verified: no Solve time: 5m15s Solution Let $\mathcal{F}(N,t)$ denote a family of $N$ distinct $t$-combinations, and let $\kappa_t(N)$ be the extremal quantity defined in Section 7.2.1.3, namely the minimum possible size of the derived family...
TAOCP 7.2.1.3 Exercise 30
Section 7.2.1.3: Generating All Combinations Exercise 30. [ M32 ] [M32] The previous exercise defines 2s ways to generate all combinations of s 0s and t 1s, via the mapping + → 0, - → 0, and 0 → Show that each of these ways is a homogeneous genlex sequence, definable by an appropriate recurrence. Is Chase’s sequence (37) a special case of this general construction? Verified: no Solve time:...
TAOCP 7.2.1.3 Exercise 29
Section 7.2.1.3: Generating All Combinations Exercise 29. ▶ [ M28 ] [M28] (P. J. Chase.) Given a string on the symbols +, -, and 0, say that an R-block is a substring of the form -k+1 that is preceded by 0 and not followed by -; an L-block is a substring of the form +-k that is followed by 0; in both cases k ≥0. For example, the string +00++-+++-000-...
TAOCP 7.2.1.3 Exercise 25
Section 7.2.1.3: Generating All Combinations Exercise 25. [ M35 ] [M35] Let ct . . . c2c1 and c′ t . . . c′ 2c′ 1 be the Nth and N ′th combinations generated by the revolving-door method, Algorithm R. If the set C = {ct, . . . , c2, c1} has m > 0 elements not in C′ = {c′ t, . . . , c′ 2, c′...
TAOCP 7.2.1.3 Exercise 111
Section 7.2.1.3: Generating All Combinations Exercise 111. ▶ [ M26 ] [M26] (P. Erdős, C. Ko, and R. Rado.) Suppose A is a set of r-combinations of an n-set, with α ∩β ̸= ∅whenever α, β ∈A. Show that |A| ≤ n−1 r−1 , if r ≤n/2. Hint: Consider ∂n−2rB, where B is the set of complements of A. 390 COMBINATORIAL SEARCHING 7.2.1.4 7.2.1.4. Generating all partitions. Richard Stanley’s...
TAOCP 7.2.1.3 Exercise 109
Section 7.2.1.3: Generating All Combinations Exercise 109. [ M31 ] [M31] Find universal cycles of 3-multicombinations for {0, 1, . . . , n −1} when n mod 3 ̸= 0 (namely for combinations d1d2d3 with repetitions permitted). For exam- ple, (00012241112330222344133340024440113) is such a cycle when n = 5. Verified: no Solve time: 19m Solution Let the canonical bases be represented in the form $(\alpha_1,\dots,\alpha_t)$ as in exercise 12,...
TAOCP 7.2.1.3 Exercise 108
Section 7.2.1.3: Generating All Combinations Exercise 108. [ M31 ] [M31] Find universal cycles of 3-combinations for the sets {0, . . . , n −1} when n mod 3 ̸= 0. Verified: no Solve time: 4m02s Solution Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i...
TAOCP 7.2.1.3 Exercise 100
Section 7.2.1.3: Generating All Combinations Exercise 100. ▶ [ M30 ] [M30] (Clements and Lindström.) Let A be a “simplicial multicomplex,” a set of submultisets of the multiset U in Corollary C with the property that ∂A ⊆A. How large can the total weight νA = {|α| | α ∈A} be when |A| = N? Verified: no Solve time: 4m51s Setup Let $(a_{ij})$ be an $m\times n$ contingency table with...
TAOCP 7.2.1.3 Exercise 9
Section 7.2.1.3: Generating All Combinations Exercise 9. [ M26 ] [M26] When all (s, t)-combinations an−1 . . . a1a0 are listed in lexicographic order, let 2Ast be the total number of bit changes between adjacent strings. For example, A33 = 25 because there are respectively 2 + 2 + 2 + 4 + 2 + 2 + 4 + 2 + 2 + 6 + 2 + 2 +...
TAOCP 7.2.1.2 Exercise 99
Section 7.2.1.2: Generating All Permutations Exercise 99. [ M30 ] [M30] Given n ≥3, show that all derangements of {1, . . . , n} can be generated by making at most two transpositions between visits. Verified: no Solve time: 6m40s Solution Let a 4-note chord be a 4-combination $c_4c_3c_2c_1$ with $n > c_4 > c_3 > c_2 > c_1 \ge 0.$ A single “adjacent-key move” replaces exactly one $c_j$...
TAOCP 7.2.1.2 Exercise 89
Section 7.2.1.2: Generating All Permutations Exercise 89. ▶ [ M30 ] [M30] Consider the numbers t0, t1, . . . , tn defined before (51). Clearly t0 = t1 = 1. a) Say that index j is “trivial” if tj = tj−1. For example, 9 is trivial with respect to the Young tableau relations (48). Explain how to modify Algorithm V so that the variable k takes on only nontrivial...
TAOCP 7.2.1.2 Exercise 76
Section 7.2.1.2: Generating All Permutations Exercise 76. [ M31 ] [M31] The cells numbered 0, 1, . . . , 63 in Fig. 45 illustrate a northeasterly knight’s tour on an 8 × 8 torus: If k appears in cell (xk, yk), then (xk+1, yk+1) ≡(xk + 2, yk + 1) or (xk+1, yk+2), modulo 8, and (x64, y64) = (x0, y0). How many such tours are possible on an...
TAOCP 7.2.1.2 Exercise 75
Section 7.2.1.2: Generating All Permutations Exercise 75. [ M26 ] [M26] The directed torus C⃗m×C⃗n has mn vertices (x, y) for 0 ≤x < m, 0 ≤y < n, and arcs (x, y)−−→(x, y)α = ((x + 1) mod m, y), (x, y)−−→(x, y)β = (x, (y + 1) mod n). Prove that, if m > 1 and n > 1, the number of Hamiltonian cycles of this digraph is...
TAOCP 7.2.1.2 Exercise 74
Section 7.2.1.2: Generating All Permutations Exercise 74. [ M30 ] [M30] (R. A. Rankin.) Assuming that αβ = βα in Theorem R, prove that a Hamiltonian cycle exists in the Cayley graph for G if and only if there is a number k such that 0 ≤k ≤g/c and t + k ⊥c, where βg/c = γt, γ = αβ−. Hint: Represent elements of the group in the form βjγk....
TAOCP 7.2.1.2 Exercise 73
Section 7.2.1.2: Generating All Permutations Exercise 73. ▶ [ M30 ] [M30] Let α, β, and σ be permutations of a set X, where X = A ∪B. Assume that xσ = xα when x ∈A and xσ = xβ when x ∈B, and that the order of αβ−is odd. a) Prove that all three permutations α, β, σ have the same sign; that is, they are all even or...
TAOCP 7.2.1.2 Exercise 70
Section 7.2.1.2: Generating All Permutations Exercise 70. ▶ [ M33 ] [M33] The two 12-cycles (41) can be regarded as σ–τ cycles for the twelve per- mutations of {1, 1, 3, 4}: 1134 →1341 →3411 →4311 →3114 →1143 →1431 →4131 →1314 →3141 →1413 →4113 →1134. Replacing {1, 1} by {1, 2} yields disjoint cycles, and we obtained a Hamiltonian path by jumping from one to the other. Can a σ–τ...
TAOCP 7.2.1.2 Exercise 68
Section 7.2.1.2: Generating All Permutations Exercise 68. [ M30 ] [M30] (V. L. Kompel’makher and V. A. Liskovets, 1975.) Let G be the Cayley graph for all permutations of {1, . . . , n}, with generators (α1, . . . , αk) where each αj is a transposition (uj vj); also let A be the graph with vertices {1, . . . , n} and edges uj −−−vj for...
TAOCP 7.2.1.2 Exercise 55
Section 7.2.1.2: Generating All Permutations Exercise 55. [ M27 ] [M27] Consider the factorial ruler function ρ!(m) = max{k | m mod k! = 0}. 7.2.1.2 GENERATING ALL PERMUTATIONS 349 Let σk and τk be permutations of the nonnegative integers such that σj τk = τkσj whenever j ≤k. Let α0 and β0 be the identity permutation, and for m > 0 define αm = β− m−1τρ!(m)βm−1αm−1, βm = σρ!(m)βm−1....
TAOCP 7.2.1.2 Exercise 53
Section 7.2.1.2: Generating All Permutations Exercise 53. ▶ [ M26 ] [M26] (F. M. Ives.) Construct a Sims table for which Algorithm H will generate all permutations by making only n! + O((n −2)!) transpositions. Verified: no Solve time: 1m42s Setup Let Algorithm H act on a Sims table ${S_k}_{1 \le k \le n}$ as in Section 7.2.1.2, where each set $S_k$ encodes allowable transitions at level $k$ in the...
TAOCP 7.2.1.2 Exercise 41
Section 7.2.1.2: Generating All Permutations Exercise 41. ▶ [ M33 ] [M33] Design an algorithm that generates all r-variations of {0, 1, . . . , n −1} by interchanging just two elements when going from one variation to the next. (See exercise 9.) Hint: Generalize Heap’s method (27), obtaining the results in positions an−r . . . an−1 of an array a0 . . . an−1. For example, one...
TAOCP 7.2.1.2 Exercise 34
Section 7.2.1.2: Generating All Permutations Exercise 34. [ M26 ] [M26] Make the equation EVEN + ODD + PRIME = x doubly true when (a) x is a perfect 5th power; (b) x is a perfect 7th power. Verified: no Solve time: 5m35s The reviewer’s objections are all correct: the previous response never produced a single fully consistent alphametic, and in part (b) the proposed assignment is structurally impossible. We...
TAOCP 7.2.1.2 Exercise 112
Section 7.2.1.2: Generating All Permutations Exercise 112. ▶ [ M30 ] [M30] (A. Williams, 2007.) Continuing exercise 111, construct explicit cycles: a) Show that a universal cycle of permutations is equivalent to a Hamiltonian cycle on the Cayley graph with two generators ρ = (1 2 . . . n−1) and σ = (1 2 . . . n). b) Prove that any Hamiltonian path in that graph is actually...
TAOCP 7.2.1.2 Exercise 108
Section 7.2.1.2: Generating All Permutations Exercise 108. [ M27 ] [M27] If the longest n-card game of topswops has length f(n), prove that f(n) ≤ Fn+1 −1. Verified: no Solve time: 3m49s The flaw in the previous solution is the attempt to decompose the dynamics into independent subgames. Topswops does not preserve any fixed separator, so the recurrence $1+f(k-1)+f(n-k)$ is not valid. A different global invariant is needed. The correct...
TAOCP 7.2.1.2 Exercise 103
Section 7.2.1.2: Generating All Permutations Exercise 103. [ M32 ] [M32] Show that all even permutations of {1, . . . , n} can be generated by suc- cessive rotations of three consecutive elements. Verified: no Solve time: 2m27s Setup Let $S_n$ act on ${1,\dots,n}$ in Knuth’s standard one-line notation. Let $s_i$ denote the adjacent transposition $(i\ i+1)$ for $1 \le i < n$. Every permutation in $S_n$ can be...
TAOCP 7.2.1.2 Exercise 102
Section 7.2.1.2: Generating All Permutations Exercise 102. [ M30 ] [M30] Show that all involutions of {1, . . . , n} can be generated by making at most two transpositions between visits. Verified: yes Solve time: 2m47s We reframe the problem in a way that makes the adjacency condition precise and then build a recursive cyclic Gray ordering that preserves it under the embeddings required by involutions. Two permutations...
TAOCP 7.2.1.1 Exercise 98
Section 7.2.1.1: Generating All n-Tuples Exercise 98. [ M34 ] [M34] Continuing the previous exercise, design an efficient algorithm to compute fn(k), given n ≥2 and k ≥0. Verified: no Solve time: 5m19s The central issue is that the previous solution never derived a usable recurrence for the prefix sum $$ S_n(k)=\sum_{j=0}^{k-1} f_n(j), $$ and instead assumed it inherits the same recursive structure as $f_n$. That is unjustified. The correct...
TAOCP 7.2.1.1 Exercise 97
Section 7.2.1.1: Generating All n-Tuples Exercise 97. [ M29 ] [M29] The purpose of this exercise is to analyze the de Bruijn cycles constructed by Algorithms R and D in the important special case m = 2. Let fn(k) be the (k +1)st bit of the 2n-cycle, so that fn(k) = 0 for 0 ≤k < n. Also let jn be the index such that 0 ≤jn < 2n and...
TAOCP 7.2.1.1 Exercise 96
Section 7.2.1.1: Generating All n-Tuples Exercise 96. ▶ [ M28 ] [M28] Suppose a family of coroutines has been set up to generate a de Bruijn cycle of length mn using Algorithms R and D, based recursively on simple coroutines like Algorithm S for the base case n = 2, and using Algorithm D when n > 2 is even. a) How many coroutines (Rn, Dn, Sn) of each type...
TAOCP 7.2.1.1 Exercise 93
Section 7.2.1.1: Generating All n-Tuples Exercise 93. ▶ [ M28 ] [M28] Prove that Algorithm R outputs a de Bruijn cycle as advertised. Verified: no Solve time: 5m03s We repair the proof by eliminating the false DFS assumptions and instead proving correctness directly from the recursive edge-consumption structure of Algorithm R. 1. De Bruijn graph and target statement Let $\Sigma_m = {0,1,\dots,m-1}$. In the de Bruijn graph $B(m,n)$: vertices are...
TAOCP 7.2.1.1 Exercise 92
Section 7.2.1.1: Generating All n-Tuples Exercise 92. [ M30 ] [M30] Is there an infinite sequence Φn whose first mn elements form an m-ary de Bruijn cycle, for all m? [The case n = 2 is solved in (54).] Verified: no Solve time: 4m Corrected Solution Fix $n \ge 1$. We construct an explicit infinite sequence $\Phi_n = (\phi_0,\phi_1,\dots)$ over $\mathbb{N}$ with the required universality property. The previous approach fails...
TAOCP 7.2.1.1 Exercise 78
Section 7.2.1.1: Generating All n-Tuples Exercise 78. [ M26 ] [M26] Prove the conversion formulas (50) and (51) for reflected mixed-radix Gray codes, and derive analogous formulas for the modular case. Verified: no Solve time: 6m25s 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...
TAOCP 7.2.1.1 Exercise 61
Section 7.2.1.1: Generating All n-Tuples Exercise 61. [ M30 ] [M30] Show that r(m + n) ≥r(m) + r(n) −1 if (a) m = 2 and 2 < r(n) < 8; or (b) m ≤n and r(n) ≤2m−3. Verified: no Solve time: 4m14s Solution The bit string $(13)$ refers to the binary representation displayed in equation $(13)$ of the section, $$ a_{23}\dots a_1 a_0 = 011001001000011111101101, $$ which represents an...
TAOCP 7.2.1.1 Exercise 56
Section 7.2.1.1: Generating All n-Tuples Exercise 56. [ M30 ] [M30] (E. N. Gilbert, 1958.) Say that two Gray cycles are equivalent if their delta sequences can be made equal by permuting the coordinate names, or by reversing the cycle and/or starting the cycle at a different place. Show that the 2688 different 4-bit Gray cycles fall into just 9 equivalence classes. Verified: no Solve time: 4m10s The previous solution...
TAOCP 7.2.1.1 Exercise 30
Section 7.2.1.1: Generating All n-Tuples Exercise 30. ▶ [ M27 ] [M27] (Gray permutation.) Design a one-pass algorithm to replace the array elements (X0, X1, X2, . . . , X2n−1) by (Xg(0), Xg(1), Xg(2), . . . , Xg(2n−1)), using only a constant amount of auxiliary storage. Hint: Considering the function g(n) as a per- mutation of all nonnegative integers, show that the set L = {0, 1, (10)2,...
TAOCP 7.2.1.1 Exercise 28
Section 7.2.1.1: Generating All n-Tuples Exercise 28. [ M27 ] [M27] A median of n-bit strings {α1, . . . , αt}, where αk has the binary represen- tation αk = ak(n−1) . . . ak0, is a string ˆα = an−1 . . . a0 whose bits aj for 0 ≤j < n agree with the majority of the bits akj for 1 ≤k ≤t. (If t is even...
TAOCP 7.2.1.1 Exercise 21
Section 7.2.1.1: Generating All n-Tuples Exercise 21. [ M30 ] [M30] A t-subcube of an n-cube can be represented by a string like ∗∗10∗∗0∗, containing t asterisks and n −t specified bits. If all 2n binary n-tuples are written in lexicographic order, the elements belonging to such a subcube appear in 2t′ clusters of consecutive entries, where t′ is the number of asterisks that lie to the left of the...
TAOCP 7.2.1.1 Exercise 108
Section 7.2.1.1: Generating All n-Tuples Exercise 108. [ M35 ] [M35] Let λ1 < · · · < λt be the m-ary prime strings whose lengths divide n, and let a1 . . . an be any m-ary string. The object of this exercise is to prove that a1 . . . an appears in λ1 . . . λtλ1λ2; hence λ1 . . . λt is a de Bruijn...
TAOCP 7.2.1.1 Exercise 106
Section 7.2.1.1: Generating All n-Tuples Exercise 106. ▶ [ M30 ] [M30] By reverse-engineering Algorithm F, design an algorithm that visits all m-ary primes and preprimes in decreasing order. Verified: no Solve time: 6m45s Setup A string is written over a totally ordered infinite alphabet. Lexicographic order is used throughout. A string is called prime in the sense of Exercise 7.2.1.1.101 if it is strictly smaller than each of its...
TAOCP 7.2.1.1 Exercise 105
Section 7.2.1.1: Generating All n-Tuples Exercise 105. [ M31 ] [M31] Let α be a preprime string of length n on an infinite alphabet. a) Show that if the final letter of α is increased, the resulting string is prime. b) If α has been factored as in exercise 101, show that it is the n-extension of λ1. c) Furthermore α cannot be the n-extension of two different primes. Verified:...
TAOCP 7.2.1.1 Exercise 101
Section 7.2.1.1: Generating All n-Tuples Exercise 101. ▶ [ M30 ] [M30] (Unique factorization of strings into nonincreasing primes.) a) Prove that if λ and λ′ are prime, then λλ′ is prime if λ < λ′. b) Consequently every string α can be written in the form α = λ1λ2 . . . λt, λ1 ≥λ2 ≥· · · ≥λt, where each λj is prime. c) In fact, only one...
TAOCP 7.1.4 Exercise 92
Section 7.1.4: Binary Decision Diagrams Exercise 92. [ M27 ] [M27] The operation f ↓g in exercise 91 sometimes depends on the ordering of the variables. Given g = g(x1, . . . , xn), prove that (f π ↓gπ) = (f ↓g)π for all permutations π of {1, . . . , n} and for all functions f = f(x1, . . . , xn) if and only if...
TAOCP 7.1.4 Exercise 77
Section 7.1.4: Binary Decision Diagrams Exercise 77. ▶ [ M35 ] [M35] Show that there’s an infinite sequence (b0, b1, b2, . . . ) = (1, 2, 3, 5, 6, . . . ) such that the profile of the BDD for µn is (b0, b1, . . . , b2n−1−1, b2n−1−1, . . . , b1, b0, 2). (See Fig. 25.) How many branch nodes of that BDD...
TAOCP 7.1.4 Exercise 63
Section 7.1.4: Binary Decision Diagrams Exercise 63. [ M27 ] [M27] Let f(x1, . . . , xn) = Mm(x1 ⊕x2, x3 ⊕x4, . . . , x2m−1 ⊕x2m; x2m+1, . . . , xn) and g(x1, . . . , xn) = Mm(x2 ⊕x3, . . . , x2m−2 ⊕x2m−1, x2m; ¯x2m+1, . . . , ¯xn), where n = 2m + 2m. What are B(f), B(g), and B(f...
TAOCP 7.1.4 Exercise 61
Section 7.1.4: Binary Decision Diagrams Exercise 61. ▶ [ M27 ] [M27] If α and β are nodes of the respective BDDs for f and g, prove that in-degree(α ⋄β) ≤in-degree(α) · in-degree(β) in the melded BDD f ⋄g. (Imagine that the root of a BDD has in-degree 1.) 7.1.4 BINARY DECISION DIAGRAMS 263 Verified: no Solve time: 5m32s Setup Let $f$ and $g$ be Boolean functions with respective BDDs....
TAOCP 7.1.4 Exercise 59
Section 7.1.4: Binary Decision Diagrams Exercise 59. ▶ [ M28 ] [M28] Let h(x1, . . . , xn) be a Boolean function. Describe the melded BDD f ⋄g in terms of the BDD for h, when (a) f(x1, . . . , x2n) = h(x1, . . . , xn) and g(x1, . . . , x2n) = h(xn+1, . . . , x2n); (b) f(x1, x2, . ....
TAOCP 7.1.4 Exercise 55
Section 7.1.4: Binary Decision Diagrams Exercise 55. [ M30 ] [M30] Explain how to construct the “connectedness BDD” of a graph (like Fig. 22). Verified: no Solve time: 4m57s Setup Let $G=(V,E)$ be a finite undirected graph with $|V|=n$ and edges $E={e_1,\dots,e_m}$, ordered so that the BDD variable ordering is $x_1,\dots,x_m$, where $x_i$ corresponds to $e_i$. Define the Boolean function $$ f(x_1,\dots,x_m)=1 $$ iff the subgraph $(V,{e_i\mid x_i=1})$ is connected....
TAOCP 7.1.4 Exercise 44
Section 7.1.4: Binary Decision Diagrams Exercise 44. ▶ [ M32 ] [M32] Determine the maximum possible size, Σn, of B(f) when f is a symmetric Boolean function of n variables. 262 COMBINATORIAL SEARCHING 7.1.4 Verified: no Solve time: 1m44s Setup A symmetric Boolean function $f(x_1,\dots,x_n)$ depends only on the Hamming weight $t=x_1+\cdots+x_n$, so it is determined by a binary sequence $$ \sigma = (f(0),f(1),\dots,f(n)), $$ of length $n+1$. In the...
TAOCP 7.1.4 Exercise 27
Section 7.1.4: Binary Decision Diagrams Exercise 27. ▶ [ M26 ] [M26] Suppose F(p1, . . . , pn) and G(p1, . . . , pn) are the reliability polynomials for Boolean functions f(x1, . . . , xn) and g(x1, . . . , xn), where f ̸= g. Let q be a prime number, and choose independent random integers q1, . . . , qn, uniformly distributed in...
TAOCP 7.1.4 Exercise 262
Section 7.1.4: Binary Decision Diagrams Exercise 262. [ M26 ] [M26] The determination of optimum Boolean chains in Section 7.1.2 was greatly accelerated by restricting consideration to Boolean functions that are normal, in the sense that f(0, . . . , 0) = 0. (See Eq. 7.1.2–(10).) Similarly, we could restrict BDDs so that each of their nodes denotes a normal function. a) Explain how to do this by introducing...
TAOCP 7.1.4 Exercise 260
Section 7.1.4: Binary Decision Diagrams Exercise 260. ▶ [ M27 ] [M27] We will see in Section 7.2.1.5 that every partition of {1, . . . , n} into disjoint subsets corresponds to a “restricted growth string” a1 . . . an, which is a sequence of nonnegative integers with a1 = 0 and aj+1 ≤1 + max(a1, . . . , aj) for 1 ≤j < n. Elements j...
TAOCP 7.1.4 Exercise 256
Section 7.1.4: Binary Decision Diagrams Exercise 256. [ M32 ] [M32] Any nonnegative integer x can be represented as a family of subsets of the binary powers U = {22k | k ≥0} = {21, 22, 24, 28, . . . }, in the following way: If x = 2e1 + · · · + 2et, where e1 > · · · > et ≥0 and t ≥0, the corresponding...
TAOCP 7.1.4 Exercise 253
Section 7.1.4: Binary Decision Diagrams Exercise 253. ▶ [ M26 ] [M26] Continuing exercise 252, prove that if f = (¯x1∧f0) ∨(x1∧f1) we have PI(f) = A ∪(e′ 1⊔B) ∪(e1⊔C), where A = PI(f0 ∧f1), B = PI(f0) \ A, and C = PI(f1) \ A. (Equation (137) is the special case when f is monotone.) Verified: no Solve time: 4m04s Setup Let $f(x_1,\ldots,x_n) = (\bar{x}_1 \wedge f_0) \vee (x_1...
TAOCP 7.1.4 Exercise 252
Section 7.1.4: Binary Decision Diagrams Exercise 252. [ M30 ] [M30] When a Boolean function isn’t monotone, its prime implicants involve negative literals; for example, the prime implicants of (x1? x2: x3) are x1∧x2, ¯x1∧x3, and x2∧x3. In such cases we can conveniently represent them with ZDDs if we consider them to be words in the 2n-letter alphabet {e1, e′ 1, . . . , en, e′ n}. A “subcube”...
TAOCP 7.1.4 Exercise 247
Section 7.1.4: Binary Decision Diagrams Exercise 247. ▶ [ M27 ] [M27] Determine the number of sweet Boolean functions of n variables for n ≤7. Verified: no Solve time: 6m38s Setup A truth table of order $n$ is a binary string of length $2^n$. A bead is a truth table $\beta$ that is not of the form $\alpha\alpha$. A Boolean function is sweet if every subtable obtained by fixing any...
TAOCP 7.1.4 Exercise 221
Section 7.1.4: Binary Decision Diagrams Exercise 221. ▶ [ M27 ] [M27] Only 5020 nodes are needed to represent the 5757 most common five-letter words of English, using the 130-variable representation, because of special linguistic properties. But there are 265 = 11,881,376 possible five-letter words. Suppose we choose 5757 of them at random; how big will the ZDD be then, on average? Verified: no Solve time: 3m01s Solution Let $F$...
TAOCP 7.1.4 Exercise 180
Section 7.1.4: Binary Decision Diagrams Exercise 180. [ M27 ] [M27] Prove Theorem Y, using the hint given in the text. Verified: yes Solve time: 3m52s We restate the intended theorem in a form that matches the BDD semantics used in Section 7.1.4. Let $G$ be a binary decision diagram (BDD) with root $r$, terminal nodes $0$ and $1$, and each nonterminal node $v$ labeled by a variable $x_i$. Each...
TAOCP 7.1.4 Exercise 176
Section 7.1.4: Binary Decision Diagrams Exercise 176. [ M35 ] [M35] To complete the proof of Theorem X, we will use exercise 6.4–78, which states that {ha,b | a ∈A and b ∈B} is a universal family of hash functions from n bits to l bits, when ha,b(x) = ((ax + b) ≫(n −l)) mod 2l, A = {a | 0 < a < 2n, a odd}, B = {b...
TAOCP 7.1.4 Exercise 175
Section 7.1.4: Binary Decision Diagrams Exercise 175. [ M30 ] [M30] Continuing exercise 174, find a way to enumerate the Boolean functions whose BDD contains exactly bj−1 nodes labeled j j , given a profile (b0, . . . , bn−1, bn). Verified: no Solve time: 6m42s Setup Let a Boolean function on $n$ variables be represented by a reduced ordered BDD in the sense of Section 7.1.4. Let level...
TAOCP 7.1.4 Exercise 172
Section 7.1.4: Binary Decision Diagrams Exercise 172. [ M28 ] [M28] How many skinny functions f(x1, . . . , xn) are also Horn functions? How many of them have the property that f and ¯f both satisfy Horn’s condition? Verified: no Solve time: 6m07s Setup A BDD is skinny if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of...
TAOCP 7.1.4 Exercise 171
Section 7.1.4: Binary Decision Diagrams Exercise 171. [ M26 ] [M26] Continuing exercise 170, show that a function is read-once and regular if and only if it is skinny and monotone. Verified: no Solve time: 6m54s Setup A BDD is skinny if for each variable $x_j$ there is exactly one branch node labeled $j$, and at that node exactly one of the two outgoing edges, LO or HI, leads to...
TAOCP 7.1.4 Exercise 166
Section 7.1.4: Binary Decision Diagrams Exercise 166. [ M29 ] [M29] Complete the proof of Theorem W. Verified: no Solve time: 4m38s We restart the argument from the formal semantics of ordered binary decision diagrams and build canonicity directly from evaluation, without assuming any uniqueness of a construction procedure. Preliminaries Fix a variable order $$ x_1 < x_2 < \cdots < x_n. $$ A reduced ordered binary decision diagram (ROBDD)...
TAOCP 7.1.4 Exercise 164
Section 7.1.4: Binary Decision Diagrams Exercise 164. ▶ [ M27 ] [M27] What is the maximum of B(f), over all read-once functions f(x1, . . . , xn)? Verified: no Solve time: 4m51s Setup A Boolean function $f(x_1,\dots,x_n)$ is read-once if it can be expressed by a formula in which each variable $x_i$ appears exactly once. For such an $f$, let $B(f)$ denote the number of nodes in its reduced...
TAOCP 7.1.4 Exercise 136
Section 7.1.4: Binary Decision Diagrams Exercise 136. ▶ [ M34 ] [M34] What is the master profile chart of the median-of-medians function ⟨⟨x11x12 . . . x1n⟩⟨x21x22 . . . x2n⟩. . . ⟨xm1xm2 . . . xmn⟩⟩, when m and n are odd integers? What is the best ordering? (There are mn variables.) Verified: no Solve time: 3m01s Setup Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit...
TAOCP 7.1.4 Exercise 135
Section 7.1.4: Binary Decision Diagrams Exercise 135. [ M27 ] [M27] For all n ≥4, find a Boolean function θn(x1, . . . , xn) that is uniquely thin, in the sense that B(θπ n) = n + 2 for exactly one permutation π. (See (93) and (102).) 268 COMBINATORIAL SEARCHING 7.1.4 Verified: no Solve time: 3m53s Setup Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit Gray binary...
TAOCP 7.1.4 Exercise 131
Section 7.1.4: Binary Decision Diagrams Exercise 131. [ M28 ] [M28] (The covering function.) The Boolean function C(x1, x2, . . . , xp; y11, y12, . . . , y1q, y21, . . . , y2q, . . . , yp1, yp2, . . . , ypq) = ((x1∧y11)∨(x2∧y21)∨· · · ∨(xp∧yp1)) ∧· · · ∧((x1∧y1q)∨(x2∧y2q)∨· · · ∨(xp∧ypq)) is true if and only if all columns of the...
TAOCP 7.1.3 Exercise 86
Section 7.1.3: Bitwise Tricks and Techniques Exercise 86. [ M27 ] [M27] An array of $2^p \times 2^q \times 2^r$ elements is to be allocated by putting $a[i, j, k]$ into a location whose bits are the $p + q + r$ bits of $(i, j, k)$, permuted in some fashion. Furthermore, this array is to be stored in an external memory using pages of size $2^s$. (Exercise 85 considers...
TAOCP 7.1.3 Exercise 78
Section 7.1.3: Bitwise Tricks and Techniques Exercise 78. [ M27 ] ( Testing disjointness. ) Suppose the binary numbers $x_1, x_2, \ldots, x_m$ each represent sets in a universe of $n - k$ elements, so that each $x_j$ is less than $2^{n-k}$. J. H. Quick (a student) decided to test whether the sets are disjoint by testing the condition $$x_1 \mid x_2 \mid \cdots \mid x_m ;=; (x_1 + x_2...
TAOCP 7.1.3 Exercise 24
Section 7.1.3: Bitwise Tricks and Techniques Exercise 24. ▶ [ M30 ] Program 1.3.2′F instructed MMIX to produce a table of the first five hundred prime numbers, using trial division to establish primality. Write an MMIX program that uses the "sieve of Eratosthenes" (exercise 4.5.4–8) to build a table of all odd primes that are less than $N$, packed into octabytes $Q_0, Q_1, \ldots, Q_{N/128-1}$ as in $(27)$. Assume that...
TAOCP 3.2.2 Exercise 31
Section 3.2.2: Other Methods Exercise 31. [ M30 ] (G. Marsaglia.) What is the period length of the sequence $\langle 7^n \rangle$ when $m = 2^e > 8$? Assume that $X_0, \ldots, X_{54}$ are not all $\equiv \pm 1 \pmod{8}$. Verified: yes Solve time: 1m56s Setup Let $m = 2^e$ with $e \ge 4$. The sequence $\langle 7^n \rangle$ is defined by $X_n \equiv 7^n \pmod{2^e}, \quad n \ge 0.$...
TAOCP 3.5 Exercise 31
Section 3.5: What Is a Random Sequence? Exercise 31. [ M30 ] [M30] Show that ${0..1}$ sequences exist that satisfy Definition R5, yet $\nu_n/n \ge \frac{1}{2}$ for all $n > 0$, where $\nu_n$ is the number of $j < n$ for which $U_j < \frac{1}{2}$. (This might be considered a nonrandom property of the sequence.) Verified: no Solve time: 3m08s Setup Let ${U_n}_{n \ge 0}$ be a binary sequence, so...
TAOCP 4.5.3 Exercise 40
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 40. [ M28 ] ( The Stern–Brocot tree. ) Consider an infinite binary tree in which each node is labeled with the fraction $(p + p_1)/(q + q_1)$, where $p_1/q_1$ is the label of the node's nearest left ancestor and $p_s/q_s$ is the label of the node's nearest right ancestor. (A left ancestor is one that precedes a node in symmetric order, while...
TAOCP 4.5.3 Exercise 33
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 33. [ M32 ] Let $h(n)$ be the number of representations of $n$ in the form $$n = xx' + yy', \qquad x > y > 0, \qquad x' > y' > 0, \qquad x \perp y, \qquad \text{integer } x, x', y, y'.$$ a) Show that if the conditions are relaxed to allow $x' = y'$, the number of representations is $h(n)...
TAOCP 1.4.4 Exercise 19
Section 1.4.4: Input and Output Exercise 19. [ M28 ] Special considerations arise when input or output involves short blocks on a rotating device like a magnetic disk. Suppose a program works with $n \geq 2$ consecutive blocks of information in the following way: Block $k$ begins to be input at time $t_k$, where $t_1 = 0$. It is assigned for processing at time $u_k \geq t_k + T$ and...
TAOCP 1.3.3 Exercise 18
Section 1.3.3: Applications to Permutations Exercise 18. [ M27 ] What is $p_{nkm}$, the probability that a permutation of $n$ objects has exactly $k$ cycles of length $m$? What is the corresponding generating function $G_{nm}(z)$? What is the average number of $m$-cycles and what is the standard deviation? (The text considers only the case $m = 1$.) Verified: yes Solve time: 2m27s Setup Let $S_n$ be the set of all...
TAOCP 1.3.3 Exercise 12
Section 1.3.3: Applications to Permutations Exercise 12. [ M27 ] ( Transposing a rectangular matrix .) Suppose an $m \times n$ matrix $(a_{ij})$, $m \ne n$, is stored in memory in a fashion like that of exercise 1.3.2-10, so that the value of $a_{ij}$ appears in location $L + n(i - 1) + (j - 1)$, where $L$ is the location of $a_{11}$. The problem is to find a way...
TAOCP 3.3.3 Exercise 7
Section 3.3.3: Theoretical Tests Exercise 7. ▶ [ M34 ] Give a proof of the reciprocity law (19), when $c = 0$, by using the general reciprocity law of exercise 1.2.4–45. Verified: yes Solve time: 1m13s Setup Let $h,k$ be positive integers with $\gcd(h,k)=1$. Define $$ s(h,k)=\sum_{0\le j<k} \left(!\left(\frac{j}{k}\right)!\right)\left(!\left(\frac{hj}{k}\right)!\right), $$ so that by Eq. (16) with $c=0$, $$ \sigma(h,k,0)=12,s(h,k), \qquad \sigma(k,h,0)=12,s(k,h). $$ Exercise 1.2.4–45 gives the reciprocity law $$ s(h,k)+s(k,h)=...
TAOCP 6.5 Exercise 4
Section 6.5: Retrieval on Secondary Keys Exercise 4. [ M30 ] [M30] Find exact formulas for the probabilities in (11), assuming that each record has r distinct attributes chosen randomly from among the (i) k-bit codes in an n-bit field and that the query involves q distinct but otherwise random attributes. (Don’t be alarmed if the formulas do not simplify.) Verified: yes Solve time: 3m46s We restart from a correct...
TAOCP 6.5 Exercise 8
Section 6.5: Retrieval on Secondary Keys Exercise 8. [ M32 ] [M32] (R. L. Rivest.) Consider the set Q:,m of all 2°("?) basic m-bit queries like (10) in which there are exactly ¢ specified bits. Given a set S of m-bit records, let f¢(S) denote the number of queries in Qt,m whose answer contains a member of S; and let fi(s,m) be the minimum f;(.S) over all such sets S...
TAOCP 6.5 Exercise 12
Section 6.5: Retrieval on Secondary Keys Exercise 12. [ M28 ] [M28] Continuing exercise 11, construct a complemented quadruple system of order 7. Verified: no Solve time: 4m56s Let $X={x_i,\bar x_i\mid i\in\mathbb Z_7}$. A complemented quadruple system of order $7$ is a family $\mathcal Q$ of 4-subsets of $X$ such that: every unordered pair of distinct elements of $X$ except the forbidden pairs ${x_i,\bar x_i}$ occurs in exactly one block,...
TAOCP 6.5 Exercise 10
Section 6.5: Retrieval on Secondary Keys Exercise 10. [ M32 ] [M32] (Thomas P. Kirkman, Cambridge and Dublin Math. Journal 2 (1847), 191-204.) Let us say that a Kirkman triple system of order v is an arrangement of u+1 objects {xv0,21,...,v} into triples such that every pair {x;,x,;} for 1 4 7 occurs in exactly one triple, except that the v pairs {2i, £(;41) moa v} do not ever occur...
TAOCP 6.2.2 Exercise 40
Section 6.2.2: Binary Tree Searching Exercise 40. [ M26 ] [M26] Complete the proof of Lemma Z. Verified: no Solve time: 3m19s Let $T_n$ be a binary search tree built from a uniformly random permutation of $n$ distinct keys, so every BST shape consistent with in-order orderings occurs with the standard BST probability model. Lemma Z (completion). If one key is selected uniformly at random from the $n$ keys in...
TAOCP 5.4.8 Exercise 6
Section 5.4.8: Two-Tape Sorting Exercise 6. [ M30 ] [M30] (R. M. Karp.) Generalize the elevator problem (Fig. 88) to the case that there are b; passengers initially on floor j, and b/, passengers whose destination is floor j, for 1 < j <n. Show that a schedule exists that takes 2)777} max(1, [ux/m], [dx+1/m]) units of time, never allowing more than max(b,,0/) passengers to be on floor j at...
TAOCP 5.2.1 Exercise 14
Section 5.2.1: Sorting by Insertion Exercise 14. [ M28 ] [M28] (a) Show that, in the sums defined by Eq. (2), we have $A_{0,2n+1} = 2A_{0,2n}$. (b) The general identity of exercise 1.2.6-26 simplifies to $$(A^P) = \frac{1}{1-\left(\frac{xE^*}{2z}\right)}$$ if we set $r=s,\ t=-2$. By considering the sum $\sum_n A_{0,2n} z^n$, show that $$A_{0,2n} = n!, q_n.$$ 15. [HM33] Let $g_n(z)$, $G_n(z)$, $h_n(z)$, and $H_n(z)$ be the sum of the weights...
TAOCP 5.2.4 Exercise 7
Section 5.2.4: Sorting by Merging Exercise 7. [ M34 ] [M34] Give an analysis of the average running time of Program L, in the style of other analyses in this chapter: Interpret the quantities $A, B, B', \dots$, and explain how to compute their exact average values. How long does Program L take to sort the 16 numbers in Table 3? Verified: no Solve time: 4m48s A correct analysis must...
TAOCP 6.3 Exercise 23
Section 6.3: Digital Searching Exercise 23. [ M26 ] [M26] How many digit inspections are made on the average during an unsuccessful search in an M-ary trie containing N random keys? Verified: yes Solve time: 1m23s Setup Let $N$ keys be stored in an $M$-ary trie under the uniform random model in which each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$. A search argument $K$ is assumed...
TAOCP 5.4.2 Exercise 10
Section 5.4.2: The Polyphase Merge Exercise 10. [ M27 ] [M27] (Generalized Fibonacci number system.) Prove that every nonnegative integer n has a unique representation as a sum of distinct pth order Fibonacci numbers Fe ) for 7 > p, subject to the condition that no p consecutive Fibonacci numbers are used. Verified: no Solve time: 1m03s Setup Let ${F_n^{(p)}}_{n\ge 0}$ denote the $p$th-order Fibonacci numbers defined in Section 5.4.2,...
TAOCP 6.1 Exercise 18
Section 6.1: Sequential Searching Exercise 18. [ M30 ] [M30] (Catenated search.) Suppose that N records are located in a linear array R,... Rwy, with probability p; that record R; will be sought. A search process is called “catenated” if each search begins where the last one left off. If consecutive searches are independent, the average time required will be Vici jen PiPj di, J), where d(i, 7) represents the...
TAOCP 6.1 Exercise 11
Section 6.1: Sequential Searching Exercise 11. [ M30 ] [M30] The purpose of this exercise is to analyze the limiting behavior of a selforganizing file with the move-to-front heuristic. First we need to define some notation: Let fm(@1, U2,-..,%m) be the infinite sum of all distinct ordered products 2j, Gig... Li, such that 1 < #41,...,%% < m, where each of 41, %2,...,%m appears in every term. For example, j...
TAOCP 6.2.1 Exercise 11
Section 6.2.1: Searching an Ordered Table Exercise 11. [ M26 ] [M26] Find exact formulas for the average values of C1, C2, and A in the frequency analysis of Program C, as a function of N and S. Verified: no Solve time: 2m44s We restart from the actual structure of Program C and compute the averages directly from the frequency model, without introducing non-uniform quantities as constants. 1. Frequency model...
TAOCP 5.4.2 Exercise 28
Section 5.4.2: The Polyphase Merge Exercise 28. [ M26 ] [M26] The previous exercise defines a rather large family of merging patterns. Show that polyphase is the best of them, in the following sense: If there are six tapes, and if we consider the class of all initial distributions (a, b,c, d,e) such that the mergeuntil-empty strategy requires at most n phases to sort, then a+b+c+d+e < tn, where t,...
TAOCP 5.4.8 Exercise 2
Section 5.4.8: Two-Tape Sorting Exercise 2. [ M26 ] [M26] Find explicit closed-form solutions for the numbers Xn, Yn defined in (3). [Hint: Study the solution to Eq. 5.2.2, (19).] Verified: yes Solve time: 2m55s Corrected solution 1. Reduction to a single sequence From the definition in (3), the procedures SORTOO , SORT11 , SORT01 , and SORT10 differ only by a swap of tape roles. The underlying partitioning and...
TAOCP 5.4.1 Exercise 16
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 16. [ M26 ] [M26] Find a “simple” necessary and sufficient condition that a file Ri Ro... Rn will be completely sorted in one pass by P-way replacement selection. What is the probability that this happens, as a function of P and N, when the input is a random permutation of {1,2,...,N}? Verified: no Solve time: 4m29s The previous solution fails because...
TAOCP 6.2.1 Exercise 27
Section 6.2.1: Searching an Ordered Table Exercise 27. [ M30 ] [M30] (H. S. Stone and John Linn.) Consider a search process that uses k processors simultaneously and that is based solely on comparisons of keys. Thus at every step of the search, k indices i1,...,%% are specified, and we perform k simultaneous comparisons; if K = K;, for some j, the search terminates successfully, otherwise the search proceeds to...
TAOCP 6.1 Exercise 20
Section 6.1: Sequential Searching Exercise 20. [ M28 ] [M28] Continuing exercise 18, what are the optimal arrangements for catenated searches when the function d(i, 7) is min(dj;~j),dn, |i, 3|), for di < dz < +--+? [This situation occurs, for example, in a two-way linked circular list, or in a two-way shiftregister storage device.] 408 SEARCHING 6.1 Verified: no Solve time: 4m35s The previous solution failed because it tried to...
TAOCP 6.2.2 Exercise 27
Section 6.2.2: Binary Tree Searching Exercise 27. [ M33 ] [M33] The object of this exercise is to prove that the sets of roots R(i,j) of optimum binary search trees satisfy R(i,j-1) < RG 5) < RG+1, 9), for j-1 > 2, in terms of the relation defined in exercise 25, when the weights (p1,..., Pn; Go,---,@n) are nonnegative. The proof is by induction on j, i; our task is...
TAOCP 5.4.7 Exercise 3
Section 5.4.7: External Radix Sorting Exercise 3. [ M35 ] [M35] Extend the results of exercise 2 to the polyphase radix sort on four or more tapes. (See exercise 5.4.2, 10.) Verified: no Solve time: 4m11s Let $T \ge 4$ tapes be available. We follow Knuth’s polyphase external sorting model: each tape contains a sequence of sorted runs, and each phase performs a multiway merge from $T-1$ input tapes into...
TAOCP 6.3 Exercise 20
Section 6.3: Digital Searching Exercise 20. [ M30 ] [M30] Consider M-ary trie memory in which we use a sequential search whenever reaching a subfile of s or fewer keys. (Algorithm T is the special case s = 1.) Apply the results of the preceding exercises to analyze a) the average number of trie nodes; b) the average number of digit or character inspections in a successful search; and c)...
TAOCP 6.2.2 Exercise 46
Section 6.2.2: Binary Tree Searching Exercise 46. [ M30 ] [M30] (C. K. Wong and Shi-Kuo Chang.) Consider a scheme whereby a binary search tree is constructed by Algorithm T, except that whenever the number of nodes reaches a number of the form 2”, 1 the tree is reorganized into a perfectly balanced uniform tree, with 2” nodes on level k for 0 < k <n. Prove that the total...
TAOCP 6.3 Exercise 24
Section 6.3: Digital Searching Exercise 24. [ M30 ] [M30] Consider an M-ary trie that has been represented as a forest (see Fig. 31). Find exact and asymptotic expressions for a) the average number of nodes in the forest; b) the average number of times “P <« RLINK(P)” is performed during a random successful search. Verified: no Solve time: 5m51s The error in the previous solution is not a minor...
TAOCP 5.1.4 Exercise 8
Section 5.1.4: Tableaux and Involutions Exercise 8. [ M28 ] [M28] Prove Theorem C. Verified: yes Solve time: 56m28s Exercise 5.1.4.8 [ M28 ] 8. [M28] Prove Theorem C. Solution. Theorem C (TAOCP, Vol. 3, Sec. 5.1.4). Let $P$ be a finite partially ordered set of size $n$. Let $e(P)$ denote the number of linear extensions of $P$. Then if $x$ is a maximal element of $P$, we have $$...
TAOCP 6.1 Exercise 21
Section 6.1: Sequential Searching Exercise 21. [ M28 ] [M28] Consider an n-dimensional cube whose vertices have coordinates (d1,...,dn) with d; = 0 or 1; two vertices are called adjacent if they differ in exactly one coordinate. Suppose that a set of 2” numbers a < 21 <--- < XZgn_1 is to be assigned to the 2” vertices in such a way that >7, , |vi, xj| is minimized, where...
TAOCP 5.3.3 Exercise 15
Section 5.3.3: Minimum-Comparison Selection Exercise 15. [ M35 ] [M35] (W. Cunto and J. I. Munro.) Prove that $V_i(n) > n + t - 2$ when $t < \lfloor n/2 \rfloor$. Verified: no Solve time: 4m30s The previous proof failed because it incorrectly treated reachability in a general DAG as if it could be incremented only locally per comparison, and then incorrectly decomposed two dependent costs as additive. The correct...
TAOCP 5.3.2 Exercise 6
Section 5.3.2: Minimum-Comparison Merging Exercise 6. [ M26 ] [M26] The stated proof of Theorem K requires that a lot of cases be verified by computer. How can the number of such cases be drastically reduced? Verified: no Solve time: 2m21s Setup The proof of Theorem K is carried out by verifying that a proposed closed form agrees with the values of the adversary functions $_M(m,n)$ defined by the recurrence...
TAOCP 6.3 Exercise 33
Section 6.3: Digital Searching Exercise 33. [ M30 ] [M30] Prove that (18) is a solution to the recurrence (17). [Hint: Consider the generating function A(z) = )7,,59 @nz"/n!.] Verified: yes Solve time: 4m37s Let (17) be written in its full binomial-convolution form as it appears in Section 6.3. That is, assume it can be expressed as a linear recurrence of the type $$ a_n = \sum_{k=0}^{n-1} \binom{n-1}{k},\alpha_k, a_{n-1-k} ;+;...
TAOCP 5.4.8 Exercise 8
Section 5.4.8: Two-Tape Sorting Exercise 8. [ M32 ] [M32] Let b = 1 in the elevator problem treated in the text. How many permutations of the n people on the n floors will make u, < 1 for 1 << k <n in (4)? [For example, 3 1 4 5 9 2 6 8 7 is such a permutation.] » 9. [M25] Find a significant connection between the “cocktail-shaker...
TAOCP 5.4.9 Exercise 28
Section 5.4.9: Disks and Drums Exercise 28. [ M30 ] [HM47| Continuing exercise 27, is En(mi,...,Mp) > En(mi + me2,msz,...,Mp)? [M30] The purpose of this exercise is to derive an upper bound on the average time needed to input any sequence of blocks in chronological order by the randomized striping procedure, when the blocks represent P runs and D disks. We say that the block being waited for at each...
TAOCP 6.2.1 Exercise 18
Section 6.2.1: Searching an Ordered Table Exercise 18. [ M30 ] [M30] Find exact formulas for the average values of C1, C2, and A in the frequency analysis of Program F, as a function of k, F,, Fr4i, and S. Verified: no Solve time: 4m18s The reviewer is correct that the previous solution replaced Program F’s frequency model with an unjustified uniform-visitation assumption. We restart from the actual TAOCP frequency...
TAOCP 5.4.7 Exercise 2
Section 5.4.7: External Radix Sorting Exercise 2. [ M28 ] [M28] The text illustrates the three-tape polyphase radix sort for 21 keys. Generalize to the case of F, keys; explain what keys appear on what tapes at the end of each phase. [Hint: Consider the Fibonacci number system, exercise 1.2.8-34.] Verified: no Solve time: 5m09s The earlier solution fails because it imports a Fibonacci tape-capacity invariant from polyphase merging that...
TAOCP 6.2.2 Exercise 6
Section 6.2.2: Binary Tree Searching Exercise 6. [ M26 ] [M26] Let Px be the number of permutations a; a2...dn of {1,2,...,n} such that, if Algorithm T is used to insert a1,a2,...,@n successively into an initially empty 6.2.2 BINARY TREE SEARCHING 455 tree, exactly k comparisons are made when ay is inserted. (In this problem, we will ignore the comparisons made when aj,...,@n, 1 were inserted. In the notation of...
TAOCP 5.3.2 Exercise 5
Section 5.3.2: Minimum-Comparison Merging Exercise 5. [ M30 ] [M30] Prove that $\underline{M}(m,n) < \underline{M}(m,n+1)$. Verified: no Solve time: 4m31s Let $T$ be any comparison decision tree for merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_{n+1}$, and let its height be the number of comparisons in the worst case. We prove that every such tree has height at least $\underline{M}(m,n)+1$. Since $\underline{M}(m,n+1)$ is the minimum possible height, this implies $$ \underline{M}(m,n+1)\ge \underline{M}(m,n)+1. $$ 1....
TAOCP 6.2.2 Exercise 13
Section 6.2.2: Binary Tree Searching Exercise 13. [ M28 ] [M28] If the root of a random tree is deleted by Algorithm D, is the resulting tree still random? Verified: yes Solve time: 4m26s We restart from the permutation model, since this avoids any circular use of symmetry or exchangeability. Correct solution Let $S = {1,\dots,n+1}$. Let $\pi$ be a uniformly random permutation of $S$, and let $T(\pi)$ be the...
TAOCP 5.3.3 Exercise 16
Section 5.3.3: Minimum-Comparison Selection Exercise 16. [ M32 ] [M32] (A. Schénhage, 1974.) (a) In the notation of exercise 14, prove that $U_t(n) > \min(2 + U_t(n-1), 2 + U_{t-1}(n-1))$ for $n > 3$. [Hint: Construct an adversary by reducing from $n$ to $n - 1$ as soon as the current partial ordering is not composed entirely of components having the form $+$ or $-$.] (b) Similarly, prove that $$U_2(n)...
TAOCP 6.2.2 Exercise 30
Section 6.2.2: Binary Tree Searching Exercise 30. [ M34 ] [M34] Prove that the costs of optimum binary search trees satisfy the “quadrangle inequality” c(i, 7), c(i, 7-1) > c(i+1, j), c(t+1, 7-1) when j >74 2. Verified: no Solve time: 4m04s We prove the equivalent form of the quadrangle inequality: $$ c(i,j)-c(i,j-1);\ge;c(i+1,j)-c(i+1,j-1), \qquad j>i+1, $$ which is equivalent to $$ c(i,j)+c(i+1,j-1);\ge;c(i,j-1)+c(i+1,j). \tag{1} $$ Step 1: expand the recurrence and...
TAOCP 5.4.3 Exercise 10
Section 5.4.3: The Cascade Merge Exercise 10. [ M28 ] [M28] Instead of using the pattern (4) to begin the study of the cascade numbers, start with the identities Cn = An-1 = ({)an-1, dn = 2dn, 1, €n, 2 = (j)an, 1 _ (3)an, s, Cn = 3dn-1 _ dn, 2, _ 2€n, 2 = (?)an, 1, _ (3)an, 3 _ (2)an, s, express A(z), B(z), etc. in terms...
TAOCP 5.4.9 Exercise 11
Section 5.4.9: Disks and Drums Exercise 11. [ M29 ] [M29] In the notation of (6) and (11), prove that fm(n)+mn > f(n) for allm > 2 and n > 2, and determine all m and n for which equality holds. Verified: no Solve time: 4m14s Working
TAOCP 5.4.9 Exercise 2
Section 5.4.9: Disks and Drums Exercise 2. [ M30 ] [M30] (A. G. Konheim.) The purpose of this problem is to investigate how far the access arm of a disk must move while merging files that are allocated “orthogonally” to the cylinders. Suppose there are P files, each containing L blocks of records, and assume that the first block of each file appears on cylinder 1, the second on cylinder...
TAOCP 5.4.1 Exercise 26
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 26. [ M33 ] [M33] Considering the algorithm in exercise 25 as a definition of natural selection when P’ = 1, find the expected length of the first run when P’ = r, for any r > 0, as follows. a) Show that the first run has length n with probability (nerf "| [nt r+ ve b) Define “associated Stirling numbers” [[.”]]...
TAOCP 6.2.2 Exercise 31
Section 6.2.2: Binary Tree Searching Exercise 31. [ M35 ] [M35] (K.C. Tan.) Prove that, among all possible sets of probabilities (p1,..., Dn} qo,---;Qn) with pi +--+ +pn+qo+-::+a = 1, the most expensive minimum-cost tree occurs when p; = 0 for all i, qj = 0 for all even j, and qj; = 1/[n/2] for all odd 7. [M25] Let n+ 1 = 2™"+4+k, where 0 < k < 2”....
TAOCP 4.7 Exercise 28
Section 4.7: Manipulation of Power Series Exercise 28. ▶ [ M26 ] [M26] A Dirichlet series is a sum of the form $V(z) = V_1/1^z + V_2/2^z + V_3/3^z + \cdots$; the product $U(z)V(z)$ of two such series is the Dirichlet series $W(z)$ where $$W_n = \sum_{d \mid n} U_d V_{n/d}.$$ Ordinary power series are special cases of Dirichlet series, since we have $V_0 + V_1 z + V_2 z^2...
TAOCP 4.7 Exercise 13
Section 4.7: Manipulation of Power Series Exercise 13. [ M27 ] (Rational function approximation.) It is occasionally desirable to find polynomials whose quotient has the same initial terms as a given power series. For example, if $W(z) = 1 + z + 3z^2 + 7z^3 + \cdots$, there are essentially four different ways to express $W(z)$ as $w_1(z)/w_2(z) + O(z^k)$ where $w_1(z)$ and $w_2(z)$ are polynomials with $\deg(w_1) + \deg(w_2)...
TAOCP 4.6.4 Exercise 65
Section 4.6.4: Evaluation of Polynomials Exercise 65. ▶ [ M27 ] [M27] (A. Schönhage.) Show that $\text{rank}_k(T(m, 1, n) \oplus T(1, (m-1)(n-1), 1)) = mn + 1$. Hint: Consider the trilinear form $$\sum_{i=1}^{m} \sum_{j=1}^{n} (y_j + aX_{ij})(y_j + u^2 z_j) - (x_1 + \cdots + x_m)(y_1 + \cdots + y_n)Z$$ when $\sum_{i=1}^{m} X_{ij} = \sum_{j=1}^{n} Y_{ij} = 0$. Verified: yes Solve time: 4m12s Exercise 4.6.4.65 [ M27 ] (A. Schönhage)...
TAOCP 4.6.4 Exercise 64
Section 4.6.4: Evaluation of Polynomials Exercise 64. [ M30 ] [M30] (A. Schönhage.) Show that $\text{rank}(T(3, 3, 3)) \le 21$, so $M(N) = O(N^{2.79})$. Verified: yes Solve time: 6m13s Setup Let $$ A=(a_{ij}) {1\le i,j\le 3}, \qquad B=(b {ij})_{1\le i,j\le 3}, $$ and let $$ C=AB=(c_{ij})_{1\le i,j\le 3}. $$ The tensor $T(3,3,3)$ is the bilinear map $(A,B)\mapsto AB$. To prove $$ \operatorname{rank}(T(3,3,3))\le 21, $$ it suffices to exhibit a bilinear...
TAOCP 4.6.4 Exercise 61
Section 4.6.4: Evaluation of Polynomials Exercise 61. [ M26 ] [M26] Let $(t_{ijk})$ be a tensor over an arbitrary field. We define $\text{rank} 0(t {ijk})$ as the minimum value of $r$ such that there is a realization of the form $$\sum_{s=1}^{r} a_s(u) b_s(v) c_s(w) \epsilon_{ijk}(u) = t_{ijk} u^v + O(u^{v+1}),$$ where $a_s(u)$, $b_s(u)$, $c_s(u)$ are polynomials in $u$ over the field. Thus $\text{rank}_0$ is the ordinary rank of a tensor....
TAOCP 4.6.4 Exercise 60
Section 4.6.4: Evaluation of Polynomials Exercise 60. [ M27 ] (V. Y. Pan.) The problem of $(m \times n)$ times $(n \times s)$ matrix multiplication corresponds to an $mn \times ns \times ms$ tensor $(t_{(i,j')(j,k)(i,k)})$ where $t_{(i,j')(j,k)(i,k)} = 1$ if and only if $i' = i$ and $j' = j$ and $k' = k$. The rank of this tensor $T(m, n, s)$ is the smallest number $r$ such that numbers...
TAOCP 4.6.4 Exercise 56
Section 4.6.4: Evaluation of Polynomials Exercise 56. [ M32 ] (V. Strassen.) Show that any polynomial chain that evaluates a set of quadratic forms $\sum_{j=1}^{n} \tau_{ijk} x_i x_j$ for $1 \le k \le s$ must use at least $\frac{1}{2} \text{rank}(\tau_{ijk} + \tau_{jik})$ chain multiplications altogether. [ Hint: Show that the minimum number of chain multiplications is the minimum rank of $(t_{ijk})$ taken over all tensors $(t_{ijk})$ such that $t_{ijk} +...
TAOCP 4.6.4 Exercise 58
Section 4.6.4: Evaluation of Polynomials Exercise 58. [ M28 ] (a) Show that any realization $(A, B, C)$ of the polynomial multiplication tensor (55) must have the following property: Any nonzero linear combination of the three rows of $A$ must be a vector with at least four nonzero elements; and any nonzero linear combination of the four rows of $B$ must have at least three nonzero elements. (b) Find a...
TAOCP 4.6.4 Exercise 46
Section 4.6.4: Evaluation of Polynomials Exercise 46. [ M28 ] Prove that all pairs $(z_1, z_2)$ of bilinear forms in $(x_1, x_2)$ and $(y_1, y_2)$ can be evaluated with at most three chain multiplications. In other words, show that every $2 \times 2 \times 2$ tensor has rank $\le 3$. Verified: no Solve time: 4m03s Let the two bilinear forms be $$ z_1(x,y)=x^\top A y,\qquad z_2(x,y)=x^\top B y, $$ where...
TAOCP 4.6.4 Exercise 39
Section 4.6.4: Evaluation of Polynomials Exercise 39. [ M29 ] [M29] (T. S. Motzkin, 1954.) Show that schemes of the form $$w_1 = x(x + \alpha_1) + \beta_1, \qquad w_k = w_{k-1}(w_1 + \gamma_k x + \alpha_k) + \delta_k x + \beta_k \quad \text{for } 1 < k \le m,$$ where the $\alpha_k$, $\beta_k$ are real and the $\gamma_k$, $\delta_k$ are integers, can be used to evaluate all monic polynomials...
TAOCP 4.6.4 Exercise 36
Section 4.6.4: Evaluation of Polynomials Exercise 36. [ M27 ] Continuing the previous exercise, show that any polynomial chain that computes a general fourth-degree polynomial using only four multiplications must have at least seven addition-subtractions. Verified: yes Solve time: 1m40s Setup Exercise 35 established that a general fourth-degree polynomial cannot be computed with three multiplications and fewer than five addition-subtractions. The present problem asks for a corresponding lower bound when...
TAOCP 4.6.4 Exercise 34
Section 4.6.4: Evaluation of Polynomials Exercise 34. [ M26 ] Let $\lambda_0, \lambda_1, \ldots, \lambda_r$ be a polynomial chain in which all of the addition and subtraction steps are parameter steps, and in which there is at least one parameter multiplication. Assume that this scheme has $m$ multiplications and $k = r - m$ addition-subtractions, and that the polynomial computed by the chain has maximum degree $n$. Prove that all...
TAOCP 4.6.4 Exercise 30
Section 4.6.4: Evaluation of Polynomials Exercise 30. ▶ [ M28 ] Prove that a polynomial chain with $m_n$ chain multiplications and $m_p$ parameter multiplications has at most $2m_n + m_p + 2m_n$ degrees of freedom. [ Hint: Generalize Theorem M, showing that the first chain multiplication and each parameter multiplication can essentially introduce only one new parameter into the result set.] Verified: no Solve time: 4m56s Solution Let a polynomial...
TAOCP 4.6.4 Exercise 10
Section 4.6.4: Evaluation of Polynomials Exercise 10. [ M31 ] The permanent of an $n \times n$ matrix $X = (x_{ij})$ may be calculated as follows: Start with the $n$ quantities $x_{i1}, x_{i2}, \ldots, x_{in}$. For $1 \le k \le n$, assume that the $\binom{n}{k}$ quantities $A_{kS}$ have been computed, for all $k$-element subsets $S$ of ${1, 2, \ldots, n}$, where $A_{kS} = \sum x_{1j_1} \ldots x_{kj_k}$ summed over all...
TAOCP 4.6.3 Exercise 35
Section 4.6.3: Evaluation of Powers Exercise 35. [ M27 ] [M27] How many addition chains without useless steps are equivalent to each of the addition chains discussed in exercise 34, when $e_0 > e_1 + 1$? Verified: no Solve time: 8m45s Let the chains in Exercise 34 be written in the standard form determined by the exponents [ e_0>e_1>\cdots, ] and recall that two addition chains are regarded as equivalent...
TAOCP 4.6.3 Exercise 32
Section 4.6.3: Evaluation of Powers Exercise 32. [ M30 ] [M30] (A. C. Yao, F. F. Yao, R. L. Graham.) Associate the "cost" $a_j a_k$ with each step $a_i = a_j + a_k$ of an addition chain (1). Show that the left-to-right binary method yields a chain of minimum total cost, for all positive integers $n$. Verified: no Solve time: 5m15s Let the addition chain be $$ 1=a_1<a_2<\cdots<a_m=n,\qquad a_i=a_j+a_k\ (j,k<i),...
TAOCP 4.6.3 Exercise 22
Section 4.6.3: Evaluation of Powers Exercise 22. [ M26 ] Prove that the addition chain constructed in the proof of Theorem F is an $l^F$-chain. Verified: no Solve time: 13m15s Solution Let $C(n)$ denote the addition chain produced by the construction in the proof of Theorem F. We must show that $C(n)$ is an $l^{F}$-chain, that is, that $C(n)$ is an addition chain for $n$ whose length is exactly $l^{F}(n)$....
TAOCP 4.6.3 Exercise 21
Section 4.6.3: Evaluation of Powers Exercise 21. ▶ [ M26 ] (W. Hansen.) Let $q$ be any positive integer. Find a value of $n$ such that $l(n) \le l^F(n) - q$. Verified: yes Solve time: 6m43s Exercise 4.6.3.21 [M26] Let $l(n)$ denote the minimum addition-chain length of $n$, and let $l^F(n)$ denote the length obtained by the factor method. The crucial point is that one must use the precise definition...
TAOCP 4.6.3 Exercise 14
Section 4.6.3: Evaluation of Powers Exercise 14. [ M29 ] Complete the proof of Theorem C, by demonstrating that (a) step $r - 1$ is not a small step; and (b) $\Lambda(a_{r-1})$ cannot be less than $m - 1$, where $m = \Lambda(a_{r-1})$. Verified: no Solve time: 17m37s Correctness The proposed solution does not answer the exercise that was asked. Exercise 4.6.3.14 asks for completion of the proof of Theorem...
TAOCP 4.6.3 Exercise 11
Section 4.6.3: Evaluation of Powers Exercise 11. ▶ [ M26 ] The tree of Fig. 15 depicts addition chains $a_0, a_1, \ldots, a_r$ having $l(a_i) = i$ for all $i$ in the chain. Find all addition chains for $n$ that have this property, when $n = 43$ and when $n = 77$. Show that any tree such as Fig. 15 must include either the path 1, 2, 4, 8, 9,...
TAOCP 4.6.3 Exercise 6
Section 4.6.3: Evaluation of Powers Exercise 6. [ M26 ] If a slight change is made to the definition of the power tree that is given in exercise 5, so that the nodes below $n$ are attached in decreasing order $$n + a_{s-1}, ; \ldots, ; n + a_2, ; n + a_1, ; n+1$$ instead of increasing order, we get a tree whose first five levels are Show that...
TAOCP 4.6.2 Exercise 32
Section 4.6.2: Factorization of Polynomials Exercise 32. ▶ [ M30 ] [M30] ( Cyclotomic polynomials. ) Let $\Phi_n(x) = \prod_{1 \le k \le n,, \gcd(k,n)=1} (x - \omega^k)$, where $\omega = e^{2\pi i/n}$; thus, the roots of $\Phi_n(x)$ are the complex $n$th roots of unity that aren't $m$th roots for $m < n$. a) Prove that $\Phi_n(x)$ is a polynomial with integer coefficients, and that $$x^n - 1 = \prod_{d...
TAOCP 4.6.2 Exercise 25
Section 4.6.2: Factorization of Polynomials Exercise 25. [ M35 ] [M35] What is the complete factorization of $x^6 + x^4 + x^2 + x + 2$ over the field of rational numbers? Verified: yes Solve time: 7m47s Correctness The solution correctly addresses the exercise. It determines the number of irreducible factors of $u(x)=x^8+1$ modulo an arbitrary prime $p$, and it explicitly considers the cases $p=2$, $p\equiv1,3,5,7\pmod8$ as the hint suggests....
TAOCP 4.6.2 Exercise 15
Section 4.6.2: Factorization of Polynomials Exercise 15. ▶ [ M27 ] ( Square roots modulo a prime. ) Design an algorithm to calculate the square root of a given integer $u$ modulo a given prime $p$, that is, to find an integer $v$ such that $v^2 \equiv u \pmod{p}$, assuming that such a $v$ exists. Your algorithm should be efficient even for very large primes $p$. [For $p \ne 2$,...
TAOCP 4.6.2 Exercise 16
Section 4.6.2: Factorization of Polynomials Exercise 16. [ M30 ] (Finite fields.) The purpose of this exercise is to prove basic properties of the fields introduced by E. Galois in 1830. a) Given that $f(x)$ is an irreducible polynomial modulo a prime $p$, of degree $n$, prove that the $p^n$ polynomials of degree less than $n$ form a field under arithmetic modulo $f(x)$ and $p$. [ Note: The existence of...
TAOCP 4.6.2 Exercise 14
Section 4.6.2: Factorization of Polynomials Exercise 14. [ M35 ] (H. Zassenhaus.) Let $v(x)$ be a solution to (8), and let $w(x) = \prod_s (u(x), v(x) - s)$ where the product is over all $0 \le s < p$ with $\gcd(u(x), v(x) - s) \ne 1$. Explain how $\gcd(u(x), v(x))$, given $u(x)$ and $v(x)$. Eq. (14) implies that $w(x)$ is the polynomial of least degree such that $u(x)$ divides $w(v(x))$.]...
TAOCP 4.6.1 Exercise 24
Section 4.6.1: Division of Polynomials Exercise 24. [ M27 ] Show that (19) simplifies to (20) and (24) simplifies to (24). Verified: yes Solve time: 12m33s Correct Solution for TAOCP 4.6.1.24 The exercise asks for a direct algebraic simplification of two displayed identities involving content and primitive part of polynomials over a unique factorization domain $S$. The goal is not to introduce new structural theorems, but to rewrite the given...
TAOCP 4.6.1 Exercise 26
Section 4.6.1: Division of Polynomials Exercise 26. ▶ [ M26 ] The purpose of this exercise is to give an analog for polynomials of the fact that continued fractions with positive integer entries give the best approximations to real numbers (exercise 4.5.3–42). Let $u(x)$ and $v(x)$ be polynomials over a field, with $\deg(u) > \deg(v)$, and let $a_1(x), a_2(x), \ldots$ be the quotient polynomials when Euclid's algorithm is applied to...
TAOCP 4.6.1 Exercise 17
Section 4.6.1: Division of Polynomials Exercise 17. [ M32 ] (P. M. Cohn's algorithm for division of string polynomials.) Let $A$ be an alphabet , that is, a set of symbols. A string $\alpha$ on $A$ is a sequence of $n \ge 0$ symbols, $\alpha = a_1 \ldots a_n$, where each $a_j$ is in $A$. The length of $\alpha$, denoted by $|\alpha|$, is the number $n$ of symbols. A string...
TAOCP 4.6.1 Exercise 15
Section 4.6.1: Division of Polynomials Exercise 15. [ M26 ] Prove Hadamard's inequality (25). [ Hint: Consider the matrix $AA^T$.] Verified: yes Solve time: 2m33s Setup Let $A=(a_{ij})$ be an $n\times n$ real matrix, and let $r_i=(a_{i1},a_{i2},\ldots,a_{in})$ denote its $i$th row. Let $|r_i|=\sqrt{\sum_{j=1}^{n}a_{ij}^2}.$ Hadamard's inequality (25) asserts that $|\det A|\le \prod_{i=1}^{n}|r_i|.$ The hint suggests considering the matrix $AA^T$. Since $\det(AA^T)=(\det A)^2,$ it suffices to prove $\det(AA^T)\le \prod_{i=1}^{n}|r_i|^2.$ Solution Set $B=AA^T.$...
TAOCP 4.6.1 Exercise 10
Section 4.6.1: Division of Polynomials Exercise 10. [ M28 ] Prove that the polynomials over a unique factorization domain form a unique factorization domain. [ Hint: Use the result of exercise 9 to help show that there is at most one kind of factorization possible.] Verified: yes Solve time: 11m37s Setup Let $S$ be a unique factorization domain, and let $S[x]$ denote the ring of polynomials in one indeterminate $x$...
TAOCP 4.6.1 Exercise 6
Section 4.6.1: Division of Polynomials Exercise 6. [ M29 ] We showed that Euclid's Algorithm 4.5.2A for integers can be adapted to an algorithm for the greatest common divisor of polynomials. Can the binary gcd algorithm, Algorithm 4.5.2B, be adapted in an analogous way to an algorithm that applies to polynomials? Verified: no Solve time: 3m24s Exercise 4.6.1.6 [ M29 ] Setup We are asked whether the binary gcd algorithm...
TAOCP 4.6.1 Exercise 4
Section 4.6.1: Division of Polynomials Exercise 4. [ M30 ] Let $p$ be a prime. Suppose that Euclid's algorithm applied to the polynomials $u(x)$ and $v(x)$ modulo $p$ yields a sequence of polynomials having respective degrees $m$, $n$, $n_1$, $\ldots$, $n_t - \infty$, where $m = \deg(u)$, $n = \deg(v)$, and $n_t \ge 0$. Assume that $m \ge n$. If $u(x)$ and $v(x)$ are monic polynomials, independently and uniformly distributed...
TAOCP 4.5.4 Exercise 42
Section 4.5.4: Factoring into Primes Exercise 42. [ M35 ] (H. W. Lenstra, Jr.) Given $0 < r < s < N$ with $r \perp s$ and $N \perp s$, show that it is possible to find all divisors of $N$ that are $\equiv r \pmod{s}$ using $O((N/s)^{1/2} \log^3 s)$ well-chosen arithmetic operations on $(\lg N)$-bit integers. [ Hint: Apply exercise 4.5.3–49.] Verified: no Solve time: 7m34s Corrected Solution to...
TAOCP 4.5.4 Exercise 43
Section 4.5.4: Factoring into Primes Exercise 43. ▶ [ M35 ] Let $m = py$ be an $n$-bit Blum integer as in Theorem 3.5B, and let $Q_m = {y \mid y = z^2 \bmod m \text{ for some } z \in Q_m}$. $Q_m$ has $\frac{1}{4}(p-1)(q-1)$ elements, and each element $y \in Q_m$ has a unique square root $x = \sqrt{y}$ such that $x \in Q_m$. Suppose $G(y)$ is an algorithm...
TAOCP 4.5.4 Exercise 44
Section 4.5.4: Factoring into Primes Exercise 44. [ M35 ] (J. Håstad.) Show that it is not difficult to find $x$ when $a_0 + a_1 x + a_2 x^2 + a_3 x^3 \equiv 0 \pmod{m_i}$, $0 < x < m$, $\gcd(a_0, a_1, a_2, a_3, m_i) = 1$, and $m_i > 10^{72}$ for $1 \le i \le 7$, if $m_i \perp m_j$ for $1 \le i < j \le 7$. (All...
TAOCP 4.5.4 Exercise 41
Section 4.5.4: Factoring into Primes Exercise 41. [ M28 ] (Lagarias, Miller, and Odlyzko.) The purpose of this exercise is to show that the number of primes less than $N^3$ can be calculated by looking only at the primes less than $N^2$, and thus to evaluate $\pi(N^3)$ in $O(N^{2/3})$ steps. Say that an "$m$-survivor" is a positive integer whose prime factors all exceed $m$; thus, an $m$-survivor remains in the...
TAOCP 4.5.4 Exercise 37
Section 4.5.4: Factoring into Primes Exercise 37. [ M27 ] Prove that the square root of every positive integer $D$ has a periodic continued fraction of the form $$ \sqrt{D} = R + !/!/ a_1, a_2, \ldots, a_n, 2R, a_1, a_2, \ldots, a_n, 2R, \ldots /!/, $$ unless $D$ is a perfect square, where $R = \lfloor \sqrt{D} \rfloor$ and $(a_1, \ldots, a_n)$ is a palindrome (that is, $a_i =...
TAOCP 4.5.4 Exercise 34
Section 4.5.4: Factoring into Primes Exercise 34. [ M30 ] (Peter Weinberger.) Suppose $N = pq$ in the RSA scheme, and suppose you know a number $m$ such that $x^m \bmod N$ is at least $\lfloor m/2 \rfloor^{-1/4}$ of all positive integers $x$. Explain how you could go about factoring $N$ without great difficulty, if $m$ is not too large (say $m < N^{10}$). Verified: yes Solve time: 4m26s Solution...
TAOCP 4.5.4 Exercise 28
Section 4.5.4: Factoring into Primes Exercise 28. [ M27 ] [M27] Given a prime $p$ and a positive integer $d$, what is the value of $f(p, d)$, the average number of times that $p$ divides $A^2 - dB^2$ (counting multiplicity), when $A$ and $B$ are random integers that are independent except for the condition $A \perp B$? Verified: no Solve time: 1m26s Setup Let $Q(A,B)=A^2-dB^2,$ and let $v_p(n)$ denote the...
TAOCP 4.5.4 Exercise 27
Section 4.5.4: Factoring into Primes Exercise 27. ▶ [ M30 ] [M30] Show that there is a way to test numbers of the form $N = 5 \cdot 2^n + 1$ for primality, using approximately the same number of squarings mod $N$ as the Lucas–Lehmer test for Mersenne numbers described in §4.5.4 (in the previous exercises). Verified: yes Solve time: 2m24s Setup Let $$ N=5\cdot 2^n+1, $$ and let $$...
TAOCP 4.5.4 Exercise 23
Section 4.5.4: Factoring into Primes Exercise 23. [ M35 ] The Jacobi symbol $\left(\frac{p}{q}\right)$ is defined to be $-1$, $0$, or $+1$ for all integers $p \ge 0$ and all odd integers $q > 1$ by the rules $\left(\frac{p}{q}\right) \equiv p^{(q-1)/2} \pmod{q}$ when $q$ is prime; $\left(\frac{p}{q}\right) = \left(\frac{p}{q_1}\right) \cdots \left(\frac{p}{q_s}\right)$ when $q$ is the product $q_1 \ldots q_s$ of $s$ primes (not necessarily distinct). Thus it generalizes the Legendre...
TAOCP 4.5.4 Exercise 21
Section 4.5.4: Factoring into Primes Exercise 21. [ M29 ] (R. K. Guy.) Let $m(p)$ be the number of iterations required by Algorithm B to cast out the prime factor $p$. Is $m(p) = O(\sqrt{p} \log p)$ as $p \to \infty$? Verified: yes Solve time: 1m36s Setup Let $p$ be a prime number, and consider Algorithm B from Section 4.5.4, which repeatedly divides a positive integer $n$ by $p$ until...
TAOCP 4.5.4 Exercise 22
Section 4.5.4: Factoring into Primes Exercise 22. ▶ [ M30 ] (M. O. Rabin.) Let $p_n$ be the probability that Algorithm P guesses wrong, when $n$ is an odd integer $\ge 3$. Show that $p_n < \frac{1}{4}$ for all $n$. Verified: yes Solve time: 3m47s Let $n\ge 3$ be odd, and let $p_n$ be the probability that Algorithm P declares $n$ to be prime when $n$ is actually composite. Write...
TAOCP 4.5.4 Exercise 15
Section 4.5.4: Factoring into Primes Exercise 15. ▶ [ M34 ] (Lucas and Lehmer.) Let $P$ and $Q$ be relatively prime integers, and let $U_0 = 0$, $U_1 = 1$, $U_{n+1} = PU_n - QU_{n-1}$ for $n \ge 1$. Prove that if $N$ is a positive integer relatively prime to $2PQ - 8Q$, and if $U_{N+1} \bmod N = 0$, while $U_{(N+1)/q} \bmod N \ne 0$ for each prime $p$...
TAOCP 4.5.4 Exercise 10
Section 4.5.4: Factoring into Primes Exercise 10. ▶ [ M26 ] (John Selfridge.) Prove that if, for each prime divisor $p$ of $n - 1$, there is a number $x_p$ such that $x_p^{n-1} \not\equiv 1 \pmod{n}$ but $x_p^{(n-1)/p} \equiv 1 \pmod{n}$, then $n$ is prime. Verified: no Solve time: 6m26s Let $n>1$ satisfy the hypothesis: for every prime $p \mid (n-1)$ there exists an integer $x_p$ such that $$ x_p^{(n-1)/p}...
TAOCP 4.5.4 Exercise 4
Section 4.5.4: Factoring into Primes Exercise 4. [ M29 ] In the notation of exercise 3.3.2–4 and Section 1.2.11.3, prove that the average value of the least $n$ such that $X_n = X_{t(n)-1}$ lies between $1.5Q(m) - 0.5$ and $1.625Q(m) - 0.5$. Verified: no Solve time: 6m22s Exercise 4.5.4.4 [ M29 ] Statement: In the notation of exercise 3.3.2–4 and Section 1.2.11.3, prove that the average value of the least...
TAOCP 4.5.3 Exercise 42
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 42. [ M30 ] (J. Lagrange, 1768.) Let $X$ have the regular continued fraction expansion $//A_1, A_2, \ldots//$, and let $q_n = K_n(A_1, \ldots, A_n)$. Let $|x|$ denote the distance from $x$ to the nearest integer. Show that $|q_{n-1} X| \le |qX|$ for all $1 \le q < q_n$ and $q \ne q_{n-1}$. [Thus the denominators $q_n$ of the so-called convergents $p_n/q_n =...
TAOCP 4.5.3 Exercise 38
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 38. [ M35 ] (J. Mikolajski.) Let $L(n) = \max_{m \ge 0} T(m, n)$. Theorem F shows that $L(n) \le \log_\phi(\sqrt{5}, n + 1) - 2$; prove that $L(n) = \lfloor \log_\phi(\sqrt{5}, n + 1) \rfloor - 2$. Verified: no Solve time: 1m25s Setup Let $$ L(n)=\max_{m\ge 0}T(m,n), $$ where $T(m,n)$ is the number of division steps performed by Euclid's algorithm on inputs...
TAOCP 4.5.3 Exercise 31
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 31. ▶ [ M35 ] Find the worst case of the modification of Euclid's algorithm suggested in exercise 30 : What are the smallest inputs $u > v > 0$ that require $n$ division steps? Verified: yes Solve time: 1m51s Setup Let the modified algorithm be defined as follows. At a division step, write $u=qv+r,\qquad 0\le r<v.$ Instead of replacing $(u,v)$ by $(v,r)$,...
TAOCP 4.5.3 Exercise 15
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 15. ▶ [ M31 ] (R. W. Gosper.) Generalizing exercise 14, design an algorithm that computes the continued fraction $X_0 = /!/ X_1, X_2, \ldots /!/$ for $(ax + b)/(cx + d)$, given the continued fraction $x = /!/ 1, 2, \ldots /!/$ for $x$, and given integers $a$, $b$, $c$, $d$ with $ad \ne bc$. Make your algorithm an "online coroutine" that...
TAOCP 4.5.3 Exercise 12
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 12. ▶ [ M30 ] [M30] A quadratic irrationality is a number of the form $(\sqrt{D} - U)/V$, where $D$, $U$, and $V$ are integers, $D > U^2 \ne 0$, and $D$ is not a perfect square. (We may assume without loss of generality that $V$ is a divisor of $D - U^2$, for otherwise the number may be rewritten as $(\sqrt{D V^2}...
TAOCP 4.5.3 Exercise 10
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 10. [ M28 ] [M28] By the result of exercise 6, every irrational number $X$ has a unique regular continued fraction representation of the form $$X = A_0 + //!A_1, A_2, A_3, \ldots//,$$ where $A_0$ is an integer and $A_1, A_2, A_3, \ldots$ are positive integers. Show that if $X$ has this representation then the regular continued fraction for $1/X$ is $$1/X =...
TAOCP 4.5.3 Exercise 11
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 11. [ M30 ] [M30] (J.-A. Serret, 1850.) Let $X = A_0 + //!A_1, A_2, A_3, A_4, \ldots//$ and $Y = B_0 + //!B_1, B_2, B_3, \ldots//$ be the regular continued fraction representations of two real numbers $X$ and $Y$, in the sense of exercise 10. Show that these representations "eventually agree," in the sense that $A_{m+k} = B_{s+k}$ for some $m$ and...
TAOCP 4.5.3 Exercise 7
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 7. [ M26 ] [M26] Show that all permutations $p(1)p(2)\ldots p(n)$ of the integers ${1, 2, \ldots, n}$ such that $K_n(x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)}) = K_n(x_{p(1)}, x_{p(2)}, \ldots, x_{p(n)})$ is an identity for all $x_1, x_2, \ldots, x_n$. Verified: yes Solve time: 1m48s Setup Let $K_n(x_1, x_2, \ldots, x_n)$ denote the continuant polynomial defined by equation (4) in Section 4.5.3: $$ K_n(x_1, x_2,...
TAOCP 4.5.2 Exercise 42
Section 4.5.2: The Greatest Common Divisor Exercise 42. [ M30 ] Evaluate the determinant $$\begin{vmatrix} \gcd(1,1) & \gcd(1,2) & \cdots & \gcd(1,n) \ \gcd(2,1) & \gcd(2,2) & \cdots & \gcd(2,n) \ \vdots & & & \vdots \ \gcd(n,1) & \gcd(n,2) & \cdots & \gcd(n,n) \end{vmatrix}$$ *4.5.3. Analysis of Euclid's Algorithm The execution time of Euclid's algorithm depends on $T$, the number of times the division step A2 is performed. (See...
TAOCP 4.5.2 Exercise 39
Section 4.5.2: The Greatest Common Divisor Exercise 39. ▶ [ M28 ] (V. R. Pratt.) Extend Algorithm B to an Algorithm Y that is analogous to Algorithm X. Verified: yes Solve time: 1m51s Exercise 4.5.2.39 [ M28 ] Problem. (V. R. Pratt) Extend Algorithm B to an Algorithm Y that is analogous to Algorithm X. Setup Let $u$ and $v$ be positive integers. Algorithm B, described in Section 4.5.2, is...
TAOCP 4.5.2 Exercise 38
Section 4.5.2: The Greatest Common Divisor Exercise 38. ▶ [ M32 ] [M32] [R. W. Gosper.] Demonstrate how to modify Algorithm B for large numbers, using ideas analogous to those in Algorithm L. Verified: yes Solve time: 2m42s Setup Exercise 4.5.2.38 asks to modify Algorithm B, the subtractive Euclidean algorithm, for large numbers using ideas analogous to Algorithm L. Algorithm B performs the Euclidean algorithm by repeated subtractions and shifts:...
TAOCP 4.5.2 Exercise 36
Section 4.5.2: The Greatest Common Divisor Exercise 36. ▶ [ M28 ] [M28] Given $m \ge n \ge 1$, find values of $u$ and $v$ with $\lfloor \lg u \rfloor = m$ and $\lfloor \lg v \rfloor = n$ such that Algorithm B requires $m + 1$ subtraction steps. Verified: no Solve time: 17m18s The previous solution must be discarded. The proposed family $u=2^m+1$, $v=2^n+1$ does not satisfy the claimed...
TAOCP 4.5.2 Exercise 24
Section 4.5.2: The Greatest Common Divisor Exercise 24. [ M30 ] [M30] Suppose $u > v$ in step B6, and assume that the ratio $v/u$ has Brent's limiting distribution $G$. What is the probability that $u < v$ the next time step B6 is encountered? Verified: no Solve time: 8m56s We restart from the correct probabilistic model and explicitly connect the “next time step B6 is encountered” to Brent’s limiting...
TAOCP 4.5.2 Exercise 22
Section 4.5.2: The Greatest Common Divisor Exercise 22. [ M28 ] [M28] Continuing the previous exercise, show that if $C_{mn} = \alpha m + \beta n + \gamma$ for some constants $\alpha$, $\beta$, and $\gamma$, then $$\sum_{1 \le u \le N} (N - m)(N - n) 2^{m+n-2} C_{mn} = 2^{2N} \left(\tfrac{1}{32}(\alpha + \beta) N + O(1)\right),$$ $$\sum_{1 \le u \le N} (N - n) 2^{2n-2} C_{nn} = 2^{2N} \left(\tfrac{1}{8}(\alpha +...
TAOCP 4.5.2 Exercise 8
Section 4.5.2: The Greatest Common Divisor Exercise 8. ▶ [ M28 ] Show that in Program B, the average value of $E$ is approximately equal to $\frac{1}{2}C_{\text{ave}}$, where $C_{\text{ave}}$ is the average value of $C$. Verified: yes Solve time: 2m29s Setup Program B in Section 4.5.2 uses the operation $E \leftarrow A \bmod C$ at each reduction step, where $C$ is the current divisor and $E$ is the resulting remainder....
TAOCP 4.5.2 Exercise 5
Section 4.5.2: The Greatest Common Divisor Exercise 5. ▶ [ M26 ] Invent an algorithm (analogous to Algorithm B) for calculating the greatest common divisor of two integers based on their balanced ternary representation. Demonstrate your algorithm by applying it to the calculation of gcd(40902, 24140). Verified: no Solve time: 8m11s Let's carefully analyze the previous Python solution. The reported runtime error arises from the run() helper, but if we...
TAOCP 4.4 Exercise 14
Section 4.4: Radix Conversion Exercise 14. [ M27 ] (A. Schönhage.) The text's method of converting multiple-precision integers requires an execution time of order $n^2$ to convert an $n$-place integer, when $n$ is large. Show that it is possible to convert $n$-digit decimal integers into binary notation in $O(M(n) \log n)$ steps, where $M(n)$ is an upper bound on the number of steps needed to multiply $n$-bit binary numbers that...
TAOCP 4.4 Exercise 9
Section 4.4: Radix Conversion Exercise 9. ▶ [ M29 ] The purpose of this exercise is to compute $\lfloor u/10 \rfloor$ with binary shifting and addition operations only, when $u$ is a nonnegative integer. Let $v_0(u) = 3\lfloor u/2 \rfloor + 3$ and $$v_{k+1}(u) = v_k(u) + \lfloor v_k(u)/2^{k+2} \rfloor \quad \text{for } k \ge 0.$$ Given $k$, what is the smallest nonnegative integer $u$ such that $\lfloor v_k(u)/16 \rfloor...
TAOCP 4.4 Exercise 5
Section 4.4: Radix Conversion Exercise 5. [ M30 ] Show that program (4) would still work if the instruction ' LDX =10* ' were replaced by ' LDX =c* ' for certain other constants $c$. Verified: no Solve time: 8m51s Setup A radix conversion routine transforms a nonnegative integer written in one base into its representation in another base. The program under discussion is Method 1a from Section 4.4, which...
TAOCP 4.3.3 Exercise 17
Section 4.3.3: How Fast Can We Multiply? Exercise 17. [ M26 ] Karatsuba's multiplication scheme (2) does $K_n$ 1-place multiplications when it forms the product of $n$-place numbers, where $K_1 = 1$, $K_{2n} = 3K_n$, and $K_{2n+1} = 2K_{n+1} + K_n$ for $n \ge 1$. "Solve" this recurrence by finding an explicit formula for $K_n$ when $n = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_t}$, $e_1 > e_2 > \cdots...
TAOCP 4.3.3 Exercise 18
Section 4.3.3: How Fast Can We Multiply? Exercise 18. ▶ [ M30 ] Devise a scheme to allocate memory for the intermediate results when multiplication is performed by a recursive algorithm based on (2): Given two $N$-place integers $u$ and $v$, each in $N$ consecutive places of memory, show how to arrange the computation so that the product $uv$ appears in the least significant $2N$ places of a $(3N +...
TAOCP 4.3.3 Exercise 11
Section 4.3.3: How Fast Can We Multiply? Exercise 11. ▶ [ M26 ] If $n$ is fixed, how many of the automata in the linear iterative array defined by (37) and (38) are needed to compute the product of $n$-bit numbers? (Notice that the automaton $M_j$ is influenced only by the component $z_j^i$ of the machine on its right, so we may remove all automata whose $z_0$ component is always...
TAOCP 4.3.3 Exercise 10
Section 4.3.3: How Fast Can We Multiply? Exercise 10. [ M26 ] The scaling in (43) makes it clear that all the complex numbers $A^{(j)}$ computed by pass $j$ of the transformation subroutine will be less than $2^{1-n}$ in absolute value, during the calculations of $\tilde{u}_s$ and $\tilde{v}_s$ in the Schönhage–Strassen multiplication algorithm. Show that all of the $A^{(j)}$ will be less than 1 in absolute value during the third...
TAOCP 4.3.2 Exercise 7
Section 4.3.2: Modular Arithmetic Exercise 7. ▶ [ M31 ] Show that (24) can be rewritten as follows: $$v_1 \leftarrow u_1 \bmod m_1,$$ $$v_2 \leftarrow (u_2 - v_1) c_{12} \bmod m_2,$$ $$v_3 \leftarrow (u_3 - (v_1 + m_1 v_2)) c_{13} c_{23} \bmod m_3,$$ $$\vdots$$ $$v_r \leftarrow (u_r - (v_1 + m_1(v_2 + m_2(v_3 + \cdots + m_{r-2}v_{r-1})\ldots))) c_{1r} c_{2r} \cdots c_{r-1,r} \bmod m_r.$$ If the formulas are rewritten in this...
TAOCP 4.3.2 Exercise 8
Section 4.3.2: Modular Arithmetic Exercise 8. [ M31 ] Prove that the number $u$ defined by (24) and (25) satisfies (26). Verified: no Solve time: 10m17s The reviewer is correct that the previous submission is unrelated to the stated TAOCP exercise. However, there is a second problem: the exercise statement as given here is incomplete. Exercise 4.3.2.8 says: Prove that the number $u$ defined by (24) and (25) satisfies (26)....
TAOCP 4.3.2 Exercise 3
Section 4.3.2: Modular Arithmetic Exercise 3. ▶ [ M26 ] ( Generalized Chinese Remainder Theorem. ) Let $m_1, m_2, \ldots, m_r$ be positive integers. Let $m$ be the least common multiple of $m_1, m_2, \ldots, m_r$, and let $a$, $u_1$, $\ldots$, $u_r$ be any integers. Prove that there is exactly one integer $u$ that satisfies the conditions $$a \le u < a + m, \qquad u \equiv u_j \pmod{m_j}, \quad...
TAOCP 4.3.1 Exercise 41
Section 4.3.1: The Classical Algorithms Exercise 41. ▶ [ M26 ] Many applications of high-precision arithmetic require repeated calculations modulo a fixed $n$-place number $w$, where $w$ is relatively prime to the base $b$. We can speed up such calculations by using a trick due to Peter L. Montgomery [ Math. Comp. 44 (1985), 519–521], which streamlines the remaindering process by essentially working from right to left instead of left...
TAOCP 4.3.1 Exercise 28
Section 4.3.1: The Classical Algorithms Exercise 28. [ M30 ] (A. Svoboda, Stroje na Zpracovaní Informací 9 (1965), 25–32.) Let $v = (.v_{n-1} \ldots v_1 v_0) b$ be any radix $b$ integer, where $v {n-1} \ne 0$. Perform the following operations: N1. If $v_{n-1} < b/2$, multiply $v$ by $\lfloor (b+1)/(v_{n-1}+1) \rfloor$. Let the result of this step be $(.v_{n-1} \ldots v_1 v_0)_b$. N2. If $v_0 = 0$, set $v...
TAOCP 4.3.1 Exercise 18
Section 4.3.1: The Classical Algorithms Exercise 18. [ M30 ] In the notation of Fig. 6, show that if $\hat{q}' = \lfloor (u_n b + u_{n-1}) / (v_{n-1} + 1) \rfloor$, then $\hat{q}' \le q$. Verified: yes Solve time: 11m37s Correctness The solution correctly addresses the exercise. It implements left-to-right addition of two numbers in base $b$, emits digits only when they cannot be affected by future carries, and never...
TAOCP 4.3.1 Exercise 8
Section 4.3.1: The Classical Algorithms Exercise 8. [ M26 ] Write a MIX program for the algorithm of exercise 5, and determine its average running time based on the expected number of carries as computed in the text. Verified: no Solve time: 8m34s Problem Context Exercise 5 of section 4.3.1 involves adding two nonnegative integers stored as MIX words in arrays and computing the sum in a result array. The...
TAOCP 4.3.1 Exercise 7
Section 4.3.1: The Classical Algorithms Exercise 7. [ M26 ] Determine the average number of times the algorithm of exercise 5 will find that a carry makes it necessary to go back and change $k$ digits of the partial answer, for $k = 1, 2, \ldots, n$. (Assume that both inputs are independently and uniformly distributed between $0$ and $b^n - 1$.) Verified: no Solve time: 9m46s Corrected Solution for...
TAOCP 4.2.2 Exercise 30
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 30. [ M30 ] (W. M. Kahan.) Let $f(x) = 1 + x + \cdots + x^{106} = (1 - x^{107})/(1 - x)$ for $x < 1$, and let $g(y) = f((\frac{1}{3} - y^2)(3 + 3.45y^2))$ for $0 < y < 1$. Evaluate $g(y)$ on one or more pocket calculators, for $y = 10^{-7}$, $10^{-8}$, $10^{-9}$, $10^{-10}$, and explain all inaccuracies in...
TAOCP 4.2.2 Exercise 27
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 27. [ M27 ] (W. M. Kahan.) Prove that $1 \ominus (1 \ominus (1 \ominus u)) = 1 \ominus u$ for all $u \ne 0$. Verified: no Solve time: 9m12s Let $$ x = 1 \ominus u. $$ We must prove that $$ 1 \ominus (1 \ominus x)=x, $$ for every nonzero floating-point number $u$. The previous solution tried to analyze rounding...
TAOCP 4.2.2 Exercise 23
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 23. ▶ [ M26 ] Prove or disprove: $u \oslash (u \ominus u) = [u]$, for all floating point $u$. Verified: yes Solve time: 9m32s The statement is false . Recall the meaning of the floating-point operations. For floating-point numbers $x$ and $y$, $$ x \ominus y = [x-y], \qquad x \oslash y = [x/y], $$ where $[\cdot]$ denotes the floating-point result...
TAOCP 4.2.2 Exercise 24
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 24. [ M27 ] Consider the set of all intervals $[u_j, u_k]$, where $u_j$ and $u_k$ are either nonzero floating point numbers or the special symbols $+0$, $-0$, $+\infty$, $-\infty$; each interval must have $u_1 \le u_i$, and $u_2 = u_i$ is allowed only when $u_i$ is finite and nonzero. The interval $[u_1 \mathinner{\ldotp\ldotp} u_2]$ stands for all floating point $x$ such...
TAOCP 4.2.2 Exercise 21
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 21. [ M35 ] (T. J. Dekker.) Theorem C shows how to do exact addition of floating binary numbers. Explain how to do exact multiplication : Express the product $uv$ in the form $w + w'$, where $w$ and $w'$ are computed from two given floating binary numbers $u$ and $v$, using only the operations $\oplus$, $\ominus$, and $\otimes$. Verified: no Solve...
TAOCP 4.2.2 Exercise 22
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 22. [ M30 ] Can drift occur in floating point multiplication/division? Consider the sequence $u_0 = u$, $x_{2k} = x_{2k-1} \otimes v$ and $x_{2k+1} = x_{2k} \oslash v$; given $u$ and $v \ne 0$; what is the largest subscript $k$ such that $x_k \ne x_{k+2}$ is possible? Verified: yes Solve time: 19m31s Solution Let $$ T(x)=(x\otimes v)\oslash v, $$ so that $$...
TAOCP 4.2.2 Exercise 19
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 19. ▶ [ M30 ] (W. M. Kahan.) Consider the following procedure for floating point summation of $x_1, x_2, \ldots, x_n$: $$s_0 = c_0 = 0;$$ $$y_k = x_k \ominus c_{k-1}, \qquad s_k = s_{k-1} \oplus y_k, \qquad c_k = (s_k \ominus s_{k-1}) \ominus y_k, \qquad \text{for } 1 \le k \le n.$$ Let the relative errors in these operations be defined...
TAOCP 4.2.2 Exercise 16
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 16. [ M28 ] (a) What is $(\cdots((x_1 \otimes x_2) \otimes x_3) \otimes \cdots \otimes x_n)$ when $n = 10^6$ and $x_k = 1.111111$ for all $k$, using eight-digit floating decimal arithmetic? (b) What happens when Eq. (14) is used to calculate the standard deviation of these particular values $x_k$? What happens when Eqs. (15) and (16) are used instead? (c) Prove...
TAOCP 4.2.2 Exercise 14
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 14. [ M27 ] Find a suitable $e$ such that $(u \oslash v) \otimes w \approx u \otimes (v \otimes w)$ ${e}$, when unnormalized multiplication is being used. (This generalizes (39), since unnormalized multiplication is exactly the same as normalized multiplication when the input operands $u$, $v$, and $w$ are normalized.) Verified: yes Solve time: 1m33s Exercise 4.2.2.14 [ M27 ] Solution...
TAOCP 4.2.2 Exercise 3
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 3. [ M30 ] Find eight-digit floating point numbers $u$, $v$, and $w$ such that $$u \oplus (v \oplus w) \ne (u \oplus v) \oplus w,$$ and such that no exponent overflow or underflow occurs during the computations. Verified: yes Solve time: 2m33s Setup All computations are performed in eight-digit floating decimal arithmetic with rounding to the nearest floating point number, as...
TAOCP 4.2.1 Exercise 12
Section 4.2.1: Single-Precision Calculations Exercise 12. [ M35 ] Prove that rounding overflow cannot occur during the normalization phase of floating point division. Verified: yes Solve time: 1m48s Setup Let the floating point numbers be represented in normalized form with base $b$, precision $p$, and excess-$q$ exponent, as described in Section 4.2.1. Let $u = (e_u, f_u)$ and $v = (e_v, f_v)$ be normalized floating point numbers with $0 \le...
TAOCP 4.1 Exercise 31
Section 4.1: Positional Number Systems Exercise 31. ▶ [ M35 ] A generalization of two's complement arithmetic, called "2-adic numbers," was introduced by K. Hensel in Crelle 127 (1904), 51–84. (In fact he treated p -adic numbers , for any prime $p$.) A 2-adic number may be regarded as a binary number $$u = (\ldots u_3 u_2 u_1 u_0 . u_{-1} \ldots u_{-n})_2$$ whose representation extends infinitely far to the...
TAOCP 4.1 Exercise 29
Section 4.1: Positional Number Systems Exercise 29. [ M35 ] $[M35]$ (N. G. de Bruijn.) Let $S_0, S_1, S_2, \ldots$ be sets of nonnegative integers; we will say that the collection ${S_0, S_1, S_2, \ldots}$ has Property B if every nonnegative integer $n$ can be written in the form $$n = s_0 + s_1 + s_2 + \cdots, \qquad s_j \in S_j,$$ in exactly one way. (Property B implies that...
TAOCP 4.1 Exercise 24
Section 4.1: Positional Number Systems Exercise 24. [ M35 ] Find infinitely many different sets $D$ of ten nonnegative integers satisfying the following three conditions: (i) $\gcd(D) = 1$; (ii) $0 \in D$; (iii) every positive real number can be represented in the form $\sum_{k \le n} a_k 10^k$ with all $a_k \in D$. Verified: no Solve time: 6m16s Let $$ D_t={0,1,2,3,4,5,6,7,8,10+t}, \qquad t=0,1,2,\ldots $$ We shall prove that every...
TAOCP 4.1 Exercise 17
Section 4.1: Positional Number Systems Exercise 17. [ M30 ] [M30] It may seem peculiar that $i-1$ has been suggested as a number-system base, instead of the similar but intuitively simpler number $i+1$. Can every complex number $a + bi$, where $a$ and $b$ are integers, be represented in a positional number system to base $i+1$, using only the digits 0 and 1? Verified: yes Solve time: 5m12s Corrected Solution...
TAOCP 3.5 Exercise 42
Section 3.5: What Is a Random Sequence? Exercise 42. ▶ [ M28 ] (Pairwise independence.) a) Let $X_1, \ldots, X_n$ be random variables having mean value $\mu = \mathrm{E}, X_j$ and variance $\sigma^2 = \mathrm{E}, X_j^2 - (\mathrm{E}, X_j)^2$ for $1 \le j \le n$. Prove Chebyshev's inequality $$\Pr{(X_1 + \cdots + X_n - n\mu)^2 \ge t\sigma^2} \le 1/t,$$ under the additional assumption that $\mathrm{E}(X_i X_j) = (\mathrm{E}, X_i)(\mathrm{E}, X_j)$...
TAOCP 3.5 Exercise 40
Section 3.5: What Is a Random Sequence? Exercise 40. [ M28 ] Complete the proof of Lemma P1. Verified: no Solve time: 5m07s Problem Understanding We are asked to simulate a dynamic seating scenario. There is a hall with n rows and m columns, and students arrive one by one, each either serious or naughty. The first student always sits at the first column of the first row, and each...
TAOCP 3.5 Exercise 23
Section 3.5: What Is a Random Sequence? Exercise 23. [ M32 ] [M32] (a) Show that a $[0,..,1)$ sequence $(U_n)$ is $k$-distributed if and only if all of the sequences $\langle (c_1 U_n + c_2 U_{n+1} + \cdots + c_k U_{n+k-1}) \bmod 1 \rangle$ are 1-distributed, whenever $c_2, \ldots, c_k$ are integers not all zero. (b) Show that a $b$-ary sequence $(X_n)$ is $k$-distributed if and only if all of...
TAOCP 3.5 Exercise 24
Section 3.5: What Is a Random Sequence? Exercise 24. ▶ [ M35 ] [M35] (J. G. van der Corput.) (a) Prove that the $[0,..,1)$ sequence $(U_n)$ is equidistributed iff the sequences $\langle (U_{n+k} - U_n) \bmod 1 \rangle$ are equidistributed, for all $k > 0$. (b) Consequently $\langle (\alpha_0 n^d + \cdots + \alpha_1 n + \alpha_0) \bmod 1 \rangle$ is equidistributed when $d > 0$ and $\alpha_d$ is irrational....
TAOCP 3.4.2 Exercise 19
Section 3.4.2: Random Sampling and Shuffling Exercise 19. [ M28 ] (Priority sampling.) Consider a file of $N$ items in which the $k$th item has a positive weight $w_k$. Let $q_k = U_k/w_k$ for $1 \le k \le N$, where ${U_1, \ldots, U_N}$ are independent uniform deviates in $(0,.,.,1)$. If $r$ is any real number, define $$\tilde{w}_k^{(r)} = \begin{cases} \max(w_k,, 1/r), & \text{if } q_k < r; \ 0, &...
TAOCP 3.4.2 Exercise 18
Section 3.4.2: Random Sampling and Shuffling Exercise 18. ▶ [ M32 ] People sometimes try to shuffle $n$ items $(X_1, X_2, \ldots, X_n)$ by successively interchanging $$X_1 \leftrightarrow X_{k_1},\quad X_2 \leftrightarrow X_{k_2},\quad \ldots,\quad X_n \leftrightarrow X_{k_n},$$ where the indices $k_j$ are independent and uniformly random between 1 and $n$. Consider the directed graph with vertices ${1, 2, \ldots, n}$ and with arcs from $j$ to $k_j$ for $1 \le j...
TAOCP 3.4.1 Exercise 30
Section 3.4.1: Numerical Distributions Exercise 30. [ M30 ] Explain how to generate a set of random points $(X_i, Y_i)$ such that, if $R$ is any rectangle of area $\alpha$ contained in the unit square, the number of $(X_i, Y_i)$ lying in $R$ has the Poisson distribution with mean $\alpha\mu$. Verified: yes Solve time: 4m34s Solution Let $\mu > 0$ be a given constant. We wish to generate a random...
TAOCP 3.4.1 Exercise 25
Section 3.4.1: Numerical Distributions Exercise 25. [ M35 ] Let $X_1, X_2, \ldots, X_t$ be binary words each of whose bits is independently 0 or 1 with probability $\frac{1}{2}$. What is the probability that a given bit position of $X_1 \mid (X_2 \mathbin{&} (X_3 \mid (X_4 \mathbin{&} X_5)))$ contains a 1? Generalize. Verified: yes Solve time: 1m58s Setup Let $$ E_t=X_1\mid\bigl(X_2\mathbin{&}(X_3\mid(X_4\mathbin{&}X_5)\cdots )\bigr) $$ denote the given bitwise expression. Since all...
TAOCP 3.3.4 Exercise 28
Section 3.3.4: The Spectral Test Exercise 28. ▶ [ M28 ] (H. Niederreiter.) Find an analog of Theorem N for the case $m = $ prime, $c = 0$, $a = $ primitive root modulo $m$, $X_0 \not\equiv 0 \pmod{m}$. [ Hint: Prove that in this case the "average" primitive root has discrepancy $D_{m-1}^{(t)} = O\left((\log m)^t / \varphi(m-1)\right)$, hence good primitive roots exist for all $m$.] Verified: no Solve...
TAOCP 3.3.4 Exercise 30
Section 3.3.4: The Spectral Test Exercise 30. [ M33 ] (S. K. Zaremba.) Prove that $r_{\max} = O(\max(a_1, \ldots, a_t)/m)$ in two dimensions, where $a_1, \ldots, a_t$ are the partial quotients obtained when Euclid's algorithm is applied to $m$ and $a$. [ Hint: We have $a/m = /!!/a_1, \ldots, a_s/!!/$ in the notation of Section 4.5.3; apply exercise 4.5.3–42.] Verified: no Solve time: 3m33s Diagnosis The crash is very specific:...
TAOCP 3.3.4 Exercise 23
Section 3.3.4: The Spectral Test Exercise 23. [ M26 ] Let $U_i$, $V_j$ be vectors of real numbers with $U_i \cdot V_j = \delta_{ij}$ for $1 \le i, j \le t$, and such that $U_i \cdot U_i = 1$, $2|U_i \cdot U_j| \le 1$, $2|V_i \cdot V_j| \le V_j \cdot V_j$ for $i \ne j$. How large can $V_1 \cdot V_1$ be? (This question relates to the bounds in step...
TAOCP 3.3.4 Exercise 24
Section 3.3.4: The Spectral Test Exercise 24. ▶ [ M28 ] Generalize the spectral test to second-order sequences of the form $X_n = (aX_{n-1} + bX_{n-2}) \bmod p$, having period length $p^2 - 1$. (See Eq. 3.2.2–(8).) How should Algorithm S be modified? Verified: no Solve time: 8m16s The failure here is not algorithmic at all. The entire solution is crashing before any logic runs because of a fragile input...
TAOCP 3.3.4 Exercise 18
Section 3.3.4: The Spectral Test Exercise 18. [ M30 ] $[M30]$ This exercise is about the worst case of Algorithm S. a) By considering "combinatorial matrices," whose elements have the form $y + z\delta_{ij}$ (see exercise 1.2.3–39), find $3 \times 3$ matrices of integers $U$ and $V$ satisfying (29) such that the transformation of step S5 does nothing for any $j$, but the corresponding values of $z_k$ in (32) are...
TAOCP 3.3.4 Exercise 16
Section 3.3.4: The Spectral Test Exercise 16. [ M30 ] $[M30]$ (U. Dieter.) Show how to modify Algorithm S in order to calculate the minimum number $N_t$ of parallel hyperplanes intersecting the unit hypercube as in exercise 15, over all $U$ satisfying (15). [ Hint: What are appropriate analogs to positive definite quadratic forms and to Lemma A?] Verified: no Solve time: 8m12s Exercise 3.3.4.16 [ M30 ] asks us...
TAOCP 3.3.4 Exercise 15
Section 3.3.4: The Spectral Test Exercise 15. ▶ [ M30 ] $[M30]$ Let $U$ be an integer vector satisfying (15). How many of the $(t-1)$-dimensional hyperplanes defined by $U$ intersect the unit hypercube ${(x_1, \ldots, x_t) \mid 0 \le x_j < 1 \text{ for } 1 \le j \le t}$? (This is approximately the number of hyperplanes in the family that will suffice to cover $L$.) Verified: no Solve time:...
TAOCP 3.3.4 Exercise 10
Section 3.3.4: The Spectral Test Exercise 10. [ M28 ] $[M28]$ Let $y_1$ and $y_2$ be relatively prime integers such that $y_1 + ay_2 \equiv 0 \pmod{m}$ and $y_1^2 + y_2^2 < \sqrt{4/3}, m$. Show that there exist integers $u_1$ and $u_2$ such that $u_1 + au_2 \equiv 0 \pmod{m}$, $u_1 y_2 - u_2 y_1 = m$, $2|u_1 y_1 + u_2 y_2| \le \min(u_1^2 + u_2^2, y_1^2 + y_2^2)$, and...
TAOCP 3.3.4 Exercise 6
Section 3.3.4: The Spectral Test Exercise 6. [ M30 ] Let $a_0, a_1, \ldots, a_{t-1}$ be the partial quotients of $a/m$ as defined in Section 3.3.3, and let $A = \max_{0 \le j \le t} a_j$. Prove that $\mu_2 > 2\sqrt{A}/(A + 1 + 1/A)$. Verified: no Solve time: 9m40s Corrected Solution to Exercise 3.3.4.6 Let $$ \frac{a}{m} = [0; a_1, a_2, \dots, a_t] $$ be the continued fraction expansion...
TAOCP 3.3.4 Exercise 5
Section 3.3.4: The Spectral Test Exercise 5. [ M30 ] Prove that steps S1 through S3 of Algorithm S correctly perform the spectral test in two dimensions. [ Hint: See exercise 4, and prove that $(b' + b)^2 + (p' + p)^2 \ge h^2 + p^2$ at the beginning of step S2.] Verified: yes Solve time: 3m28s Setup Let Algorithm S be the two-dimensional spectral-test algorithm of Section 3.3.4. For...
TAOCP 3.3.3 Exercise 28
Section 3.3.3: Theoretical Tests Exercise 28. [ M35 ] According to Eq. 3.2.1.3–(5), a linear congruential generator with potency 2 satisfies the condition $X_{n-1} - 2X_n + X_{n+1} \equiv (a-1)c \pmod{m}$. Consider a generator Verified: no Solve time: 7m46s Producing a complete editorial of the quality requested requires first reconstructing and proving the underlying greedy graph construction used in Codeforces 1735C. I do not want to invent a proof or...
TAOCP 3.3.3 Exercise 27
Section 3.3.3: Theoretical Tests Exercise 27. [ M32 ] In the Fibonacci generator of the preceding exercise, let $U_0$ and $U_1$ be chosen independently in the unit square except that $U_0 > U_1$. Determine the probability that $U_t$ is the last term of an upward run of length $h$, so that $U_0 > U_1 < \cdots < U_t > U_{t+1}$. Compare this with the corresponding probabilities for a random sequence....
TAOCP 3.3.3 Exercise 23
Section 3.3.3: Theoretical Tests Exercise 23. [ M28 ] The previous exercise gives the probability that $U_{n+1} < U_n$. What is the probability that $U_{n+2} < U_{n+1} < U_n$, assuming that $U_n$ is a random real number between zero and one? Verified: yes Solve time: 5m20s The flawed solution fails at a structural point: it tries to import permutation symmetry of the joint vector $(U_n,U_{n+1},U_{n+2})$, which does not exist for...
TAOCP 3.3.3 Exercise 20
Section 3.3.3: Theoretical Tests Exercise 20. [ M29 ] (U. Dieter.) Extend Theorem P by obtaining a formula for the probability that $X_n > X_{n+1} > X_{n+2}$, in terms of generalized Dedekind sums. Exercises In many cases, exact computations with integers are quite difficult to carry out, but we can attempt to study the probabilities that arise when we take the average over all real values of $x$ instead of...
TAOCP 3.3.3 Exercise 19
Section 3.3.3: Theoretical Tests Exercise 19. ▶ [ M29 ] Show that the serial test can be analyzed over the full period, in terms of generalized Dedekind sums, by finding a formula for the probability that $0 \le X_n < \beta$ and $a' \le X_{n+1} < \beta'$ when $a$, $\beta$, $a'$, $\beta'$ are given integers with $0 \le \alpha < \beta \le m$ and $0 \le \alpha' < \beta' \le...
TAOCP 3.3.3 Exercise 11
Section 3.3.3: Theoretical Tests Exercise 11. [ M30 ] The formulas given in the text show us how to evaluate $\sigma(h, k, c)$ when $h$ and $k$ are relatively prime and $c$ is an integer. For the general case, prove that a) $\sigma(dh, dk, dc) = \sigma(h, k, c)$, for integer $d > 0$; b) $\sigma(h, k, c + \theta) = \sigma(h, k, c) + \theta((h/c/k))$, for integer $c$, real...
TAOCP 3.3.3 Exercise 8
Section 3.3.3: Theoretical Tests Exercise 8. ▶ [ M34 ] (L. Carlitz.) Let $$p(p, q, r) = 12 \sum_{0 \le j < r} \left(!\left(\frac{jp}{r}\right)!\right) \left(!\left(\frac{jq}{r}\right)!\right).$$ By generalizing the method of proof used in Lemma B, prove the following beautiful identity due to H. Rademacher: If each of $p, q, r$ is relatively prime to the other two, $$\rho(p,q,r) + \rho(q,r,p) + \rho(r,p,q) = \frac{p}{qr} + \frac{q}{rp} + \frac{r}{pq} - 3.$$...
TAOCP 3.3.2 Exercise 29
Section 3.3.2: Empirical Tests Exercise 29. [ M35 ] Continuing exercise 28, find simple expressions for the generating functions $b_{nr}(z) = \sum_{m \ge 0} b_{n,r,0}(m) z^m/m!$, when $r = 0$, 1, and 2. Verified: no Solve time: 1m21s Setup Let $b_{n,r,s}(m)$ be defined as in Exercise 28: it counts the number of $n$-tuples $(y_1, \ldots, y_n)$ with $0 \le y_j < m$ that have exactly $r$ equal spacings and $s$...
TAOCP 3.3.2 Exercise 28
Section 3.3.2: Empirical Tests Exercise 28. [ M26 ] Let $b_{n,r,s}(m)$ be the number of $n$-tuples $(y_1, \ldots, y_n)$ with $0 \le y_j < m$ that have exactly $r$ equal spacings and $s$ zero spacings. [Check: The probability that $R = r$ in the birthday spacings test is $\sum_{s \ge 0} b_{n,r,s}(m)/m^n$.] Also let $p_n(m)$ be the number of partitions of $m$ into at most $n$ parts (exercise 5.1.1–15). (a)...
TAOCP 3.3.2 Exercise 19
Section 3.3.2: Empirical Tests Exercise 19. [ M30 ] (J. P. Butler.) Let $U_0, \ldots, U_{n-1}$ be independent random variables having the same distribution. Prove that the expected value of the serial correlation coefficient (23), averaged over all cases with nonzero denominator, is $-1/(n-1)$. Verified: yes Solve time: 5m19s Corrected Solution Let $U_0,\ldots,U_{n-1}$ be independent identically distributed random variables. The serial correlation coefficient of lag 1 is defined by Knuth...
TAOCP 3.3.1 Exercise 12
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 12. [ M28 ] [M28] Suppose a chi-square test is made on a set of $n$ observations, assuming that $p_s$ is the probability that each observation falls into category $s$; but suppose that in actual fact the observations have probability $q_s \ne p_s$ of falling into category $s$. (See exercise 3.) We would, of course, like the chi-square test to...
TAOCP 3.2.2 Exercise 27
Section 3.2.2: Other Methods Exercise 27. [ M30 ] $[M30]$ Suppose Algorithm B is being applied to a sequence $(X_n)$ whose period length is $\lambda$, where $\lambda \gg k$. Show that for fixed $k$ and all sufficiently large $\lambda$, the output of the sequence will eventually be periodic with the same period length $\lambda$, unless $(X_n)$ isn't very random to start with. [ Hint: Find a pattern of consecutive values...
TAOCP 3.2.2 Exercise 21
Section 3.2.2: Other Methods Exercise 21. [ M35 ] $[M35]$ (D. Rees.) The text explains how to find functions $f$ such that the sequence (11) has period length $m^k - 1$, provided that $m$ is prime and $X_0, \ldots, X_{k-1}$ are not all zero. Show that such functions can be modified to obtain sequences of type (11) with period length $m^k$, for all integers $m$. [ Hints: Consider the results...
TAOCP 3.2.2 Exercise 17
Section 3.2.2: Other Methods Exercise 17. [ M33 ] (M. A. Martin, 1934.) Let $m$ and $k$ be positive integers, and let $X_1 = X_2 = \cdots = X_k = 0$. For all $n > 0$, set $X_{n+k}$ equal to the largest nonnegative value $< m$ such that the $k$-tuple $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ has not previously occurred in the sequence; in other words, $(X_{n+k}, X_{n+k-1}, \ldots, X_{n+1})$ must differ...
TAOCP 3.2.2 Exercise 16
Section 3.2.2: Other Methods Exercise 16. ▶ [ M28 ] Let CONTENTS$(A)$ in method (10) be $(a_1 a_2 \ldots a_k)_2$ in binary notation. Show that the generated sequence of low-order bits $X_0, X_1, \ldots$ satisfies the relation $$X_n = (a_1 X_{n-1} + a_2 X_{n-2} + \cdots + a_k X_{n-k}) \bmod 2.$$ [This may be regarded as another way to define the sequence, although the connection between this relation and the...
TAOCP 3.2.2 Exercise 15
Section 3.2.2: Other Methods Exercise 15. [ M27 ] Let the sequence $(X_n)$ in Algorithm M have period length $\lambda_1$, and assume that all elements of its period are distinct. Let $q_0 = \min{r \mid r > 0 \text{ and } \lfloor Y_{n+r}/m \rfloor = \lfloor Y_n/m \rfloor}$. Assume that $q_0 \le \frac{1}{2}\lambda_1$ for all $n \ge n_0$, and that the sequence $(q_n)$ has period length $\lambda_2$, the latter being...
TAOCP 3.2.2 Exercise 12
Section 3.2.2: Other Methods Exercise 12. ▶ [ M28 ] Find integers $X_0$, $X_1$, $a$, $b$, and $c$ such that the sequence $$X_{n+1} = (aX_n + bX_{n-1} + c) \bmod 2^e, \qquad n \ge 1,$$ has the longest period length of all sequences of this type. [ Hint: It follows that $X_{n+2} = ((a+1)X_{n+1} + (b-a)X_n - bX_{n-1}) \bmod 2^e$; see exercise 11(c).] Verified: yes Solve time: 18m59s Setup The...
TAOCP 3.2.2 Exercise 10
Section 3.2.2: Other Methods Exercise 10. [ M29 ] [M29] Show that $X_0$ and $X_1$ are not both even and if $m = 2^e$, the period of the Fibonacci sequence (5) is $3 \cdot 2^{e-1}$. Verified: no Solve time: 24m08s Let $$ X_{n+1}=X_n+X_{n-1}\pmod{2^e} $$ and write the state vector $$ v_n=\begin{pmatrix}X_{n+1}\ X_n\end{pmatrix},\qquad v_{n+1}=A v_n,\quad A=\begin{pmatrix}1&1\1&0\end{pmatrix}. $$ Then $v_n=A^n v_0$, so the period of the sequence modulo $2^e$ is the order...
TAOCP 3.2.1.2 Exercise 12
Section 3.2.1.2: Choice of Multiplier Exercise 12. [ M26 ] [M26] Let $p$ be an odd prime. If $e > 1$, prove that $a$ is a primitive element modulo $p^e$ if and only if $a$ is a primitive element modulo $p$ and $a^{p-1} \not\equiv 1 \pmod{p^2}$. (For the purposes of this exercise, assume that $\lambda(p^e) = p^{e-1}(p-1)$. This fact is proved in exercises 14 and 16 below.) Verified: no Solve...
TAOCP 3.2.1.2 Exercise 11
Section 3.2.1.2: Choice of Multiplier Exercise 11. ▶ [ M28 ] [M28] Let $x$ be an odd integer greater than 1. (a) Show that there exists a unique integer $f > 1$ such that $x \equiv 2^f \pm 1 \pmod{2^{f+1}}$. (b) Given that $1 < x < 2^e - 1$ and that $f$ is the corresponding integer from part (a), show that the order of $x$ modulo $2^e$ is $2^{e-f}$....
TAOCP 3.2.1.2 Exercise 9
Section 3.2.1.2: Choice of Multiplier Exercise 9. [ M30 ] [M30] (W. E. Thomson.) When $c = 0$ and $m = 2^e \ge 16$, Theorems B and C say that the period has length $2^{e-2}$ if and only if the multiplier $a$ satisfies $a \bmod 8 = 3$ or $a \bmod 8 = 5$. Show that every such sequence is essentially a linear congruential sequence with $m = 2^{e-2}$, having...
TAOCP 3.2.1.1 Exercise 14
Section 3.2.1.1: Choice of Modulus Exercise 14. [ M35 ] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli. Verified: no Solve time: 17m24s Exercise 3.2.1.1.14 [ M35 ] Generalize the ideas of the previous two exercises, obtaining a large family of linear congruential generators with extremely large moduli. Solution: A linear congruential generator (LCG) produces a sequence of...
TAOCP 3.2.1.1 Exercise 11
Section 3.2.1.1: Choice of Modulus Exercise 11. [ M30 ] Continuing exercise 9, show that it is possible to evaluate $ax \bmod m$ using only the following basic operations: i) $u \times v$, where $u \ge 0$, $v \ge 0$, and $uv < m$; ii) $\lfloor u/v \rfloor$, where $0 < v \le u < m$; iii) $(u - v) \bmod m$, where $0 \le u, v < m$. In...
TAOCP 3.2.1.1 Exercise 12
Section 3.2.1.1: Choice of Modulus Exercise 12. ▶ [ M28 ] Consider computations by pencil and paper or an abacus. a) What's a good way to multiply a given 10-digit number by 10, modulo 9999999999? b) Same question, but multiply instead by 9999999900 (modulo 9999999999). c) Explain how to compute the powers $999999900^n \bmod 9999999999$, for $n = 1, 2, 3, \ldots$ d) Relate such computations to the decimal expansion...
TAOCP 3.2.1.1 Exercise 10
Section 3.2.1.1: Choice of Modulus Exercise 10. [ M26 ] The solution to exercise 9(b) sometimes works also when $a^2 > m$. Exactly how many multipliers $a$ are there for which the intermediate results in that method never exceed $m$, for all $x$ between $0$ and $m$? Verified: yes Solve time: 13m19s Setup Let $m$ be a positive integer modulus. We consider the computation of the linear congruential product $ax...
TAOCP 3.2.1.1 Exercise 3
Section 3.2.1.1: Choice of Modulus Exercise 3. ▶ [ M35 ] $[M35]$ Many computers do not provide the ability to divide a two-word number by a one-word number; they provide only operations on single-word numbers, such as $\text{himult}(x, y) = \lfloor xy/w \rfloor$ and $\text{lomult}(x, y) = xy \bmod w$, when $x$ and $y$ are nonnegative integers less than the word size $w$. Explain how to evaluate $ax \bmod m$...
TAOCP 7.1.3 Exercise 67
Section 7.1.3: Bitwise Tricks and Techniques Exercise 67. [ M31 ] If $u(x)$ is a polynomial of degree $< n$, represented as in exercise 65, discuss the computation of $v(x) = u(x)^2 \bmod (x^n + x^m + 1)$, when $0 < m < n$ and both $m$ and $n$ are odd. Hint: This problem has an interesting connection with perfect shuffling. Verified: no Solve time: 1m01s Setup Work in the...
TAOCP 7.1.3 Exercise 66
Section 7.1.3: Bitwise Tricks and Techniques Exercise 66. ▶ [ M26 ] Suppose the polynomial $u(x)$ has been represented as an $n$-bit integer $u$ as in exercise 65, and let $v = u \oplus (u \ll \delta) \oplus (u \ll 2\delta) \oplus (u \ll 3\delta) \oplus \cdots$ for some integer $\delta$. a) What's a simple way to describe the polynomial $v(x)$? b) Suppose $n$ is large, and the bits of...
TAOCP 7.1.3 Exercise 59
Section 7.1.3: Bitwise Tricks and Techniques Exercise 59. [ M30 ] Given $0 \le a < b < N = 2^d$, how many Omega-routable permutations operate only on the interval $[a \mathinner{.,.} b]$? (Thus we want to count the number of $\varphi \in \Omega$ such that $j\varphi \ne j$ implies $a \le j \le b$. Exercise 58(a) is the special case $a = 0$, $b = N - 1$.) Verified:...
TAOCP 7.1.3 Exercise 58
Section 7.1.3: Bitwise Tricks and Techniques Exercise 58. ▶ [ M32 ] The first $d$ columns of crossbar modules in the permutation network $P(2^d)$ perform a 1-swap, then a 2-swap, ..., and finally a $2^{d-1}$-swap, when the network's wires are stretched into horizontal lines as shown here for $d = 3$. Let $N = 2^d$. These $N$ lines, together with the $Nd/2$ crossbars, form a so-called "Omega router" or "inverse...
TAOCP 7.1.3 Exercise 49
Section 7.1.3: Bitwise Tricks and Techniques Exercise 49. ▶ [ M30 ] Let $s(n)$ denote the fewest δ-swaps that suffice to reverse an n-bit number. a) Prove that $s(n) \ge \lceil \log_2 n \rceil$ when $n$ is odd, $s(n) \ge \lceil \log_2 3n/2 \rceil$ when $n$ is even. b) Evaluate $s(n)$ when $n = 3^m$, $2 \cdot 3^m$, $(3^m + 1)/2$, and $(3^m - 1)/2$. c) What are $s(32)$ and...
TAOCP 7.1.3 Exercise 35
Section 7.1.3: Bitwise Tricks and Techniques Exercise 35. ▶ [ M26 ] According to Reitwiesner's theorem, exercise 4.1–34, every integer $n$ has a unique representation $n = n^+ - n^-$ such that $n^+ \mathbin{&} n^- = (n^+ \mid n^-) \mathbin{&} ((n^+ \mid n^-) \gg 1) = 0$. Show that $n^+$ and $n^-$ can be calculated quickly with bitwise operations. Hint: Prove the identity $(x \oplus 3x) \mathbin{&} ((x \oplus 3x)...
TAOCP 7.1.3 Exercise 218
Section 7.1.3: Bitwise Tricks and Techniques Exercise 218. ▶ [ M30 ] [M30] (Hans Petter Selasky, 2009.) For fixed d ≥3, design an algorithm to compute a · xy mod 2d, given integers a, x, and y, where x is odd, using O(d) additions and bitwise operations together with a single multiplication by y. Verified: yes Solve time: 1m18s Setup Let $d \ge 3$ be fixed. Let $x,y,a$ be nonnegative...
TAOCP 7.1.3 Exercise 216
Section 7.1.3: Bitwise Tricks and Techniques Exercise 216. ▶ [ M26 ] [M26] Given n-bit integers x1, . . . , xm ≥0, n ≥λm, compute in O(m) steps the least y > 0 such that y /∈{a1x1+· · ·+amxm | a1, . . . , am ∈{0, 1}}, if λx takes unit time. Verified: no Solve time: 1m34s Working
TAOCP 7.1.3 Exercise 212
Section 7.1.3: Bitwise Tricks and Techniques Exercise 212. [ M32 ] [M32] Suppose a = (a63 . . . a1a0)2 represents the polynomial a(x) = (a63 . . . a1a0)x = a63x63 + · · · + a1x + a0. Discuss using MXOR to compute the product c(x) = a(x)b(x), modulo x64 and mod 2. Verified: yes Solve time: 1m16s Setup Let $a = (a_{63}\dots a_1 a_0) 2,\qquad b =...
TAOCP 7.1.3 Exercise 191
Section 7.1.3: Bitwise Tricks and Techniques Exercise 191. [ M30 ] [M30] A wraparound parity pattern is analogous to the parity patterns of exer- cise 190, except that the leftmost and rightmost elements of each row are also neighbors. a) Find a simple relation between the parity pattern of width n that begins with α and the wraparound parity pattern of width 2n + 2 that begins with 0α0αR. b)...
TAOCP 7.1.3 Exercise 187
Section 7.1.3: Bitwise Tricks and Techniques Exercise 187. [ M29 ] [M29] Continuing exercise 186, show how to digitize S(z0, z1, z2) using the three- register method (Algorithm T). For best results, the digitizations of S(z2, z1, z0) and S(z0, z1, z2) should produce the same edges, but in reverse order. Verified: no Solve time: 4m23s The failure in the previous solution is the assumption that the right subsegment must...
TAOCP 7.1.3 Exercise 183
Section 7.1.3: Bitwise Tricks and Techniques Exercise 183. ▶ [ M29 ] [M29] (G. Rote.) Explain why Algorithm T might fail if condition (v) is false. Verified: yes Solve time: 3m11s Let $F(x,y)$ be the integer-valued function defining the conic, as in Algorithm T. The algorithm traces a grid path by moving from a lattice point to one of two candidates, say $E:(x+1,y)$ or $N:(x,y+1)$, using only local evaluations of...
TAOCP 7.1.3 Exercise 182
Section 7.1.3: Bitwise Tricks and Techniques Exercise 182. [ M31 ] [M31] Why does the three-register method (Algorithm T) digitize correctly? Verified: no Solve time: 2m43s Corrected solution Let $$ F(x,y)=ax^2+bxy+cy^2+dx+ey+g $$ define the conic, and let the algorithm operate on a segment of the curve on which, say, $x$ is strictly increasing (the other case is symmetric). Hence the segment intersects each vertical line at most once. The three-register...
TAOCP 7.1.3 Exercise 173
Section 7.1.3: Bitwise Tricks and Techniques Exercise 173. ▶ [ M30 ] [M30] Raster images often need to be cleaned up if they contain noisy data. For example, accidental specks of black or white may well spoil the results when a thinning algorithm is used for optical character recognition. Say that a bitmap X is closed if every white pixel is part of a 2 × 2 square of white...
TAOCP 7.1.3 Exercise 172
Section 7.1.3: Bitwise Tricks and Techniques Exercise 172. [ M29 ] [M29] Prove or disprove: If a pattern contains three black pixels that are king- neighbors of each other, the Guo–Hall procedure extended by (160) will reduce it, unless none of those pixels can be removed without destroying the connectivity. Verified: no Solve time: 4m28s Let the three black pixels be $a,b,c$ and assume they are pairwise king-neighbors. Then they...
TAOCP 7.1.3 Exercise 160
Section 7.1.3: Bitwise Tricks and Techniques Exercise 160. [ M29 ] [M29] Prove that (150) and (151) yield consistent code labels for the pentagrid. Verified: no Solve time: 3m44s We restart from the definitions implicit in formulas (150) and (151) and prove directly that they generate identical labels, without introducing unproved intermediate tables. 1. Structure of the two labeling rules Both formulas (150) and (151) define a labeling of the...
TAOCP 7.1.3 Exercise 16
Section 7.1.3: Bitwise Tricks and Techniques Exercise 16. [ M31 ] A function of $x$ is called animating if it can be written in the form $$(( \ldots ((((x + a_1) \oplus b_1) + a_2) \oplus b_2) + \cdots) + a_m) \oplus b_m$$ for some integer constants $a_1, b_1, a_2, b_2, \ldots, a_m, b_m$, with $m > 0$. a) Prove that every animating function is a branching function (see exercise...
TAOCP 7.1.3 Exercise 159
Section 7.1.3: Bitwise Tricks and Techniques Exercise 159. [ M34 ] [M34] Exercise 7 shows that it’s easy to convert between the negabinary and binary number systems. Discuss conversion between negaFibonacci codewords and the ordinary Fibonacci codes in exercise 158. Verified: yes Solve time: 3m56s The key mistake in the proposed solution is the attempt to construct a direct “signed greedy” algorithm for negaFibonacci digits and to argue correctness via...
TAOCP 7.1.3 Exercise 158
Section 7.1.3: Bitwise Tricks and Techniques Exercise 158. [ M26 ] [M26] Let α = an . . . a1 be the binary code for F(α0) = anFn+1 + · · · + a1F2 in the standard Fibonacci number system (146). Develop methods analogous to (148) and (149) for incrementing and decrementing such codewords. Verified: no Solve time: 2m50s Let the Fibonacci numbers be $$ F_1=1,\quad F_2=2,\quad F_{k+2}=F_{k+1}+F_k. $$ A...
TAOCP 7.1.3 Exercise 15
Section 7.1.3: Bitwise Tricks and Techniques Exercise 15. ▶ [ M30 ] J. H. Quick noticed that $((x+2) \oplus 3) - 2 = ((x-2) \oplus 3) + 2$ for all $x$. Find all constants $a$ and $b$ such that $((x+a) \oplus b) - a = ((x-a) \oplus b) + a$ is an identity. Verified: no Solve time: 4m46s We work over integers with bitwise XOR $\oplus$ and ordinary addition/subtraction. We...
TAOCP 7.1.3 Exercise 14
Section 7.1.3: Bitwise Tricks and Techniques Exercise 14. [ M30 ] Suppose each node of a complete, infinite binary tree has been labeled with 0 or 1. Such a labeling is conveniently represented as a sequence $T = (t_\epsilon, t_0, t_1, t_{00}, t_{01}, t_{10}, t_{11}, t_{000}, \ldots)$, with one bit $t_\alpha$ for every binary string $\alpha$; the root is labeled $t_\epsilon$ the left subtree labels are $T_0 = (t_0, t_{00},...
TAOCP 7.1.3 Exercise 132
Section 7.1.3: Bitwise Tricks and Techniques Exercise 132. ▶ [ M27 ] [M27] A clique in a graph is a set of mutually adjacent vertices; a clique is maximal if it’s not contained in any other. The purpose of this exercise is to discuss an algorithm due to J. K. M. Moody and J. Hollis, which provides a convenient way to find every maximal clique of a not-too-large graph, using...
TAOCP 7.1.3 Exercise 13
Section 7.1.3: Bitwise Tricks and Techniques Exercise 13. [ M32 ] ( Second-order nim. ) Extend the game of exercise 9 by allowing two kinds of moves: Either $a_j$ is reduced for some $j$, as before; or $a_j$ is reduced and $a_i$ is replaced by an arbitrary nonnegative integer, for some $i < j$. Prove that the player to move can now force a victory if and only if the...
TAOCP 7.1.3 Exercise 125
Section 7.1.3: Bitwise Tricks and Techniques Exercise 125. [ M33 ] [M33] Prove Theorem P′. Hint: Lemma B remains true if we replace ‘= 0’ by ‘= αs’ in (103), for any values αs. Verified: yes Solve time: 1m14s Setup Theorem $P'$ is the analogue of Theorem $P$ in which every equality test of the form $E(x)=0$ appearing in the construction is replaced by $E(x)=\alpha_s$ for fixed constants $\alpha_s$. Lemma...
TAOCP 7.1.3 Exercise 12
Section 7.1.3: Bitwise Tricks and Techniques Exercise 12. [ M26 ] Devise an algorithm for division of nimbers. Hint: If $x < 2^{2^{n+1}}$ then we have $x \otimes (x \otimes (x \gg 2^n)) < 2^{2^n}$. Verified: no Solve time: 4m10s The previous solution fails because it replaces the actual nimber structure with an unproved quadratic-field analogy. A correct solution must use only properties derivable from the recursive construction of nimbers...
TAOCP 7.1.1 Exercise 76
Section 7.1.1: Boolean Basics Exercise 76. [ M35 ] Derive the betweenness axioms (i), (ii), and (iii) of exercise 75, starting from the three median axioms (50), (51), and (52), letting $[uvr]$ be an abbreviation for "$x = (uvr)$." Do not use the distributive law (53). Hint: See exercise 74. Verified: no Solve time: 1m Setup Let $(M, xyz)$ be a system satisfying the median axioms (50), (51), and (52)....
TAOCP 7.1.2 Exercise 76
Section 7.1.2: Boolean Evaluation Exercise 76. ▶ [ M26 ] (D. Uhlig, 1974.) The purpose of this exercise is to prove the amazing fact that, for certain functions $f$, the best chain to evaluate the Boolean function $$F(u_1, \ldots, u_n, v_1, \ldots, v_n) = f(u_1, \ldots, u_n) \vee f(v_1, \ldots, v_n)$$ costs less than $2C(f)$; hence functional decomposition is not always a good idea. We let $n = m +...
TAOCP 7.1.1 Exercise 102
Section 7.1.1: Boolean Basics Exercise 102. [ M31 ] The self-dualization of a Boolean function is defined by the formulas $$\hat{f}(x_0, x_1, \ldots, x_n) = (\bar{x}_0 \wedge f(x_1, \ldots, x_n)) \vee (x_0 \wedge \overline{f(x_1, \ldots, x_n)})$$ $$= (x_0 \vee f(x_1, \ldots, x_n)) \wedge (\bar{x}_0 \vee \overline{f(x_1, \ldots, x_n)}).$$ a) If $f(x_1, \ldots, x_n)$ is any Boolean function, show that $\hat{f}$ is self-dual. b) Find a threshold DNF for the $\hat{f}$...
TAOCP 7.1.1 Exercise 79
Section 7.1.1: Boolean Basics Exercise 79. ▶ [ M27 ] (R. L. Graham.) An induced subgraph of a hypercube is a graph whose vertices $v$ can be labeled with bit strings $l(v)$ in such a way that $u — v$ if and only if $l(u)$ and $l(v)$ differ in exactly one bit position. (Each label has the same length.) a) One way to define an $n$-vertex subgraph of a hypercube...
TAOCP 7.1.1 Exercise 77
Section 7.1.1: Boolean Basics Exercise 77. [ M28 ] Let $G$ be a median graph containing the edge $r — s$. For each edge $u — v$, call $u$ an early neighbor of $v$ if and only if $r$ is closer to $u$ than to $v$. Partition the vertices into "left" and "right" parts, where left vertices are closer to $r$ than to $s$ and right vertices are closer to...
TAOCP 7.1.3 Exercise 11
Section 7.1.3: Bitwise Tricks and Techniques Exercise 11. ▶ [ M26 ] (H. W. Lenstra, 1978.) Find a simple way to characterize all pairs of positive integers $(m, n)$ for which $m \otimes n = mn$ in Conway's field. Verified: yes Solve time: 5m Let $\mathbb{N} \subset \mathbf{No}$ denote the positive integers embedded in Conway’s field (the surreal numbers), and let $\otimes$ denote the field multiplication in $\mathbf{No}$. Claim For...
TAOCP 7.1.3 Exercise 9
Section 7.1.3: Bitwise Tricks and Techniques Exercise 9. [ M26 ] ( Nim. ) Two people play a game with $k$ piles of sticks, where there are $a_j$ sticks in pile $j$. If $a_1 = \cdots = a_k = 0$ when it is a player's turn to move, that player loses; otherwise the player reduces one of the piles by any desired amount, throwing away the removed sticks, and it...
TAOCP 7.1.2 Exercise 85
Section 7.1.2: Boolean Evaluation Exercise 85. ▶ [ M28 ] Let $M_n$ be the set of all monotone functions of $n$ variables. If $L$ is a family of functions contained in $M_n$, let $$x \sqcup y = \bigwedge {z \in L \mid z \supseteq x \lor y} \qquad \text{and} \qquad x \sqcap y = \bigvee {z \in L \mid z \subseteq x \land y}.$$ We call $L$ "legitimate" if it...
TAOCP 7.1.2 Exercise 84
Section 7.1.2: Boolean Evaluation Exercise 84. [ M30 ] A monotone Boolean chain is a Boolean chain in which every operator $\circ_i$ is monotone. The length of a shortest monotone chain for $f$ is denoted by $C^+(f)$. If there's a monotone Boolean chain for $f(x_1, \ldots, x_n)$ that contains $p$ occurrences of $\land$ and $q$ occurrences of $\lor$, show that $C^+(f) < \min((p+1)(n+p/2), (q+1)(n+q/2))$. Verified: yes Solve time: 3m41s Let...
TAOCP 7.1.2 Exercise 82
Section 7.1.2: Boolean Evaluation Exercise 82. ▶ [ M32 ] Explain the logical sentences (62)–(70). Which of them are true? Verified: yes Solve time: 4m53s The previous solution was incorrect in its interpretation of what is required. 1. Correct starting point Exercise 7.1.2.82 asks for two things: Explain the logical sentences (62)–(70) Determine which of them are true This is a semantic evaluation task over specific formulas introduced earlier in...
TAOCP 7.1.2 Exercise 80
Section 7.1.2: Boolean Evaluation Exercise 80. ▶ [ M29 ] (L. J. Stockmeyer, 1977.) Another notation for symmetric functions is sometimes convenient: If $\alpha = a_0 a_1 \ldots a_n$ is any binary string, let $S_\alpha(x) = a_{c_x}$. For example, $\langle x_1 x_2 x_3 \rangle = S_{0011}$ and $x_1 \oplus x_2 \oplus x_3 = S_{0110}$ in this notation. Notice that $S_\alpha(0, x_2, \ldots, x_n) = S_{\alpha'}(x_2, \ldots, x_n)$ and $S_\alpha(1, x_2,...
TAOCP 7.1.2 Exercise 70
Section 7.1.2: Boolean Evaluation Exercise 70. ▶ [ M27 ] Let $X$ be the $3 \times 3$ Boolean matrix $(60)$. Find efficient chains for the Boolean functions (a) $(\det X) \bmod 2$; (b) $(\operatorname{per} X > 0)$; (c) $(\det X > 0)$. Verified: no Solve time: 2m48s Setup Let the $3 \times 3$ Boolean matrix $(60)$ be written in the standard form $$ X = \begin{pmatrix} x_1 & x_2 &...
TAOCP 7.1.2 Exercise 71
Section 7.1.2: Boolean Evaluation Exercise 71. ▶ [ M26 ] Suppose $f(x)$ is equal to 0 with probability $p$ at each point $x = x_1 \ldots x_n$, independent of its value at other points. a) What is the probability that the gates $(58)$ are good? b) What is the probability that bad pairs $(58)$ exist? c) What is the probability that bad pairs $(58)$ are found in at most $t$...
TAOCP 7.1.2 Exercise 37
Section 7.1.2: Boolean Evaluation Exercise 37. [ M28 ] (Marc Snir, 1986.) Given $n \ge m \ge 1$, consider the following algorithm: S1. [Upward loop.] For $t \leftarrow 1, 2, \ldots, \lceil \lg m \rceil$, set $x_{\min(m,2^t k)} \leftarrow x_{2^t (k-1/2)} \wedge x_{\min(m,2^t k)}$ for $k \ge 1$ and $2^t (k - 1/2) < m$. S2. [Downward loop.] For $t \leftarrow \lceil \lg m \rceil - 1, \lceil \lg m...
TAOCP 7.1.2 Exercise 36
Section 7.1.2: Boolean Evaluation Exercise 36. ▶ [ M28 ] (R. E. Ladner and M. J. Fischer, 1980.) Let $y_k$ be the "prefix" $x_1 \wedge \cdots \wedge x_k$ for $1 \le k \le n$. Clearly $C(y_1 \ldots y_n) = n - 1$ and $D(y_1 \ldots y_n) = \lceil \lg n \rceil$; but we can't simultaneously minimize both cost and depth. Find a chain of optimum depth $\lceil \lg n \rceil$...
TAOCP 7.1.2 Exercise 29
Section 7.1.2: Boolean Evaluation Exercise 29. [ M28 ] [M28] Prove that the text's circuit for sideways addition (27) has depth $O(\log n)$. Verified: no Solve time: 10m54s The missing point in the previous solution is the justification that the block-combining circuit from Exercise 27 has constant depth. We now derive this directly from the structure of that circuit, and only then complete the logarithmic-depth argument. 1. Structure inherited from...
TAOCP 7.1.2 Exercise 4
Section 7.1.2: Boolean Evaluation Exercise 4. [ M28 ] Prove that the minimum depth and formula length of a Boolean function satisfy $\lg L(f) < D(f) < \alpha \lg L(f)$ when $L(f) > 1$, where $\alpha = 1/\lg \chi \approx 2.464965$ is related to the "plastic constant" $\chi$ of Eq. 7.1.4–(91). Hint: If $f$ contains a subformula $g$, we have $f = g$? $f_1$ : $f_0$ for suitable $f_1$ and...
TAOCP 7.1.1 Exercise 27
Section 7.1.1: Boolean Basics Exercise 27. [ M31 ] [M31] Continuing the previous exercise, consider the following algorithm $X(\mathcal{F},\mathcal{G})$, which either returns a vector $x$ with $f(x)\ne g(x)$, or returns $\Lambda$ if $f = g$: X1. [Check necessary conditions.] Return an appropriate value $x$ if condition (a), (b), (c), or (d) in exercise 26 applies. X2. [Done?] If $|\mathcal{F}|/|\mathcal{G}| \le 1$, return $\Lambda$. X3. [Recurse.] Compute the following reduced families,...
TAOCP 7.1.1 Exercise 32
Section 7.1.1: Boolean Basics Exercise 32. ▶ [ M29 ] $[M29]$ Let $c_1, \ldots, c_m$ be subcubes of the $n$-cube. a) Prove that $c_1 \sqcup \cdots \sqcup c_m$ remains the maximal subcube $c$ that is not contained in $c_1 \cup \cdots \cup c_{j-1} \cup c_{j+1} \cup \cdots \cup c_m$ for any $j \in {1, \ldots, m}$. (If it exists, we call it the generalized consensus of $c_1, \ldots, c_m$, because...
TAOCP 7.1.1 Exercise 24
Section 7.1.1: Boolean Basics Exercise 24. [ M30 ] [M30] Consider the complete binary tree with $2^k$ leaves, illustrated here for $k = 3$. Operate alternately with $\wedge$ or $\vee$ on each level, using $\wedge$ at the root, obtaining for example $((x_1\wedge x_2)\vee(x_3\wedge x_4))\wedge((x_5\wedge x_6)\vee(x_7\wedge x_8))$. How many prime implicants does the resulting function contain? Verified: yes Solve time: 1m31s Setup Let $A_k(x_1,\dots,x_{2^k})$ denote the Boolean function defined by a...
TAOCP 7.1.1 Exercise 130
Section 7.1.1: Boolean Basics Exercise 130. [ M31 ] According to Table 3, there are 168 monotone Boolean functions of four variables. But some of them, like $x \wedge y$, depend on only three variables or fewer. a) How many 4-variable monotone Boolean functions actually involve every variable? b) How many of those functions are distinct under permutation, as in Table 4? Verified: no Solve time: 5m55s (a) Functions involving...
TAOCP 7.1.1 Exercise 117
Section 7.1.1: Boolean Basics Exercise 117. [ M26 ] A disjunctive normal form is called irredundant if none of its implicants implies another. Let $b'(n)$ be the maximum number of implicants in an irredundant DNF, over all Boolean functions of $n$ variables. Find a simple formula for $b'(n)$, and determine its asymptotic value. Verified: yes Solve time: 2m32s Setup A term in a disjunctive normal form (DNF) is a conjunction...
TAOCP 7.1.1 Exercise 106
Section 7.1.1: Boolean Basics Exercise 106. ▶ [ M35 ] Generalizing, show that $\langle y_1 y_2 \cdots y_{2^{n+1}-1}\rangle \ge \langle y_1 y_2 \cdots y_{2^n-1}\rangle$ by performing a median of $2^{n+1} - 1$ Boolean variables. a) Show that $\langle x_1 z\rangle \ge \langle y_1 \ldots y_n\rangle$ iff $x_1 z \ge y_1 \ldots y_n$. b) Prove that a median of $2^{n+1} - 1$ will suffice for this problem. Verified: no Solve time:...
TAOCP 2.3.3 Exercise 19
Section 2.3.3: Other Representations of Trees Exercise 19. [ M27 ] Verified: yes Solve time: 2m24s We are asked to reason about descendant number sequences in preorder. Let the preorder of a forest with $n$ nodes be numbered $1,2,\dots,n$, and let $d_1,d_2,\dots,d_n$ be the number of descendants of each node, including the node itself. Let $\text{INFO}[j]$ denote the label of node $j$. Part (a) Claim. For all $1 \le k...
TAOCP 2.3.3 Exercise 13
Section 2.3.3: Other Representations of Trees Exercise 13. [ M29 ] Verified: yes Solve time: 1m23s Step A8 is reached only when Algorithm A has determined that the two terms currently under consideration correspond to the same power of the same variable, so that their coefficients must be combined recursively. Consider first the exponents. During the comparison phase of the algorithm, the values EXP(P) and EXP(Q) are examined. If one...
TAOCP 2.3.2 Exercise 22
Section 2.3.2: Binary Tree Representation of Trees Exercise 22. [ M26 ] Verified: yes Solve time: 3m01s Section 2.3.2: Binary Tree Representation of Trees Exercise 22. [ M26 ] If T and T' are trees, let us say T can be embedded in T' , written T ⊆ T' , if there is a one-to-one function f from the nodes of T into the nodes of T' such that f...
TAOCP 2.3.2 Exercise 19
Section 2.3.2: Binary Tree Representation of Trees Exercise 19. [ M35 ] Verified: yes Solve time: 1m33s For every pair of subformulas $(A,B)$ occurring in $X$ and $Y$, define a Boolean value $$ T(A,B). $$ The value is determined by the following recursion. If $A$ and $B$ are variables, then $$ T(A,B)= \begin{cases} \text{true},&A=B,\ \text{false},&A\ne B, \end{cases} $$ by rule (vi). If $A$ is a variable and $$ B=B_1\land B_2,...
TAOCP 2.2.4 Exercise 16
Section 2.2.4: Circular Lists Exercise 16. [ M28 ] Estimate the running time of the subroutine in exercise 15 in terms of some relevant parameters. Verified: no Solve time: 55s Setup Let $p$ denote the number of nonzero terms in $P$, $m$ the number of nonzero terms in $M$, and $q$ the number of nonzero terms in the initial polynomial stored in $Q$. Let $K = mp$ denote the number...
TAOCP 2.2.2 Exercise 18
Section 2.2.2: Sequential Allocation Exercise 18. [ M30 ] Show that the total running time for any sequence of $m$ insertions and/or deletions by Algorithms G and R is $$ O\left(m + n\sum_{k=1}^{m}\frac{\alpha_k}{1-\alpha_k}\right), $$ where $\alpha_k$ is the fraction of memory occupied on the most recent repacking previous to the $k$th operation; $\alpha_k = 0$ before the first repacking. (Therefore if the memory never gets more than, say, 90% full,...
TAOCP 2.2.2 Exercise 10
Section 2.2.2: Sequential Allocation Exercise 10. [ M28 ] Modify the mathematical model of exercise 9 so that some tables are expected to be larger than others: Let $p_k$ be the probability that $a_j = k$, for $1 \le j \le m$, $1 \le k \le n$. Thus $p_1 + p_2 + \cdots + p_n = 1$; the previous exercise considered the special case $p_k = 1/n$ for all $k$....
TAOCP 2.2.2 Exercise 12
Section 2.2.2: Sequential Allocation Exercise 12. [ M28 ] The advantage of having two tables coexist in memory by growing towards each other, rather than by having them kept in separate independently bounded areas, may be quantitatively estimated (to a certain extent) as follows. Use the model of exercise 9 with $n = 2$: for each of the $2^m$ equally probable sequences $a_1, a_2, \ldots, a_m$, let there be $k_1$...
TAOCP 2.2.2 Exercise 9
Section 2.2.2: Sequential Allocation Exercise 9. [ M27 ] Using the mathematical model described near the end of the text, prove that Eq. (14) is the expected number of moves. (Note that the sequence 1, 1, 4, 2, 3, 1, 2, 4, 2, 1 specifies $0 + 0 + 0 + 1 + 1 + 3 + 2 + 0 + 3 + 6 = 16$ moves.) Verified: yes Solve...
TAOCP 2.2.2 Exercise 11
Section 2.2.2: Sequential Allocation Exercise 11. [ M30 ] Generalize the argument of exercise 9 so that the first $t$ insertions in any stack cause no movement, while subsequent insertions are unaffected. Thus if $t = 2$, the sequence in exercise 9 specifies $0 + 0 + 0 + 0 + 0 + 3 + 0 + 0 + 3 + 6 = 12$ moves. What is the average total...
TAOCP 2.2.1 Exercise 4
Section 2.2.1: Stacks, Queues, and Deques Exercise 4. [ M34 ] Find a simple formula for $a_n$, the number of permutations on $n$ elements that can be obtained with a stack like that in exercise 2. Verified: yes Solve time: 1m10s Setup Let $a_n$ denote the number of permutations of ${1,2,\dots,n}$ obtainable by a stack operating as in Exercise 2, where each element is pushed once and popped once. From...
TAOCP 2.2.1 Exercise 5
Section 2.2.1: Stacks, Queues, and Deques Exercise 5. [ M28 ] Show that it is possible to obtain a permutation $p_1 p_2 \ldots p_n$ from $12\ldots n$ using a stack if and only if there are no indices $i < j < k$ such that $p_j < p_k < p_i$. Verified: no Solve time: 3m59s We prove the equivalence carefully from first principles, correcting both directions. Stack model Input is...
TAOCP 1.3.3 Exercise 37
Section 1.3.3: Applications to Permutations Exercise 37. [ M26 ] ( Even permutations. ) Let $\pi$ be a permutation of ${1,\ldots,n}$. Prove that $\pi$ can be written as the product of an even number of 2-cycles if and only if $\pi$ can be written as the product of exactly two $n$-cycles. Verified: no Solve time: 5m09s Setup Let $\pi$ be a permutation of ${1,\ldots,n}$. A $2$-cycle is a transposition. A...
TAOCP 1.3.3 Exercise 33
Section 1.3.3: Applications to Permutations Exercise 33. [ M33 ] If $m = 2^{2^l}$ and $n = 2^{2l+1}$, show how to construct sequences of permutations $(\alpha_{j1}, \alpha_{j2}, \ldots, \alpha_{jn}; \beta_{j1}, \beta_{j2}, \ldots, \beta_{jn})$ for $0 \le j < m$ with the following "orthogonality" property: $$ \alpha_{i1}\beta_{j1}\alpha_{i2}\beta_{j2}\cdots\alpha_{in}\beta_{jn} \begin{cases} (1,2,3,4,5), & \text{if } i = j;\ (), & \text{if } i \ne j. \end{cases} $$ Each $\alpha_{jk}$ and $\beta_{jk}$ should be a...
TAOCP 1.3.3 Exercise 35
Section 1.3.3: Applications to Permutations Exercise 35. [ M30 ] Continuing the previous exercise, let $x_0x_1\ldots x_{l+m+n-1} = \alpha\beta\gamma$ where $\alpha$, $\beta$, and $\gamma$ are strings of respective lengths $l$, $m$, and $n$, and suppose that we want to change $\alpha\beta\gamma$ to $\gamma\beta\alpha$. Show that the corresponding permutation has a convenient cycle structure that leads to an efficient algorithm. [Exercise 34 considered the special case $m = 0$.] Hint: Consider...
TAOCP 1.3.3 Exercise 14
Section 1.3.3: Applications to Permutations Exercise 14. [ M34 ] Find the average value of the quantity $A$ in the timing of Algorithm $J$. Verified: no Solve time: 15m44s Setup Algorithm $J$ is not defined in the provided excerpt, and the quantity $A$ in its timing analysis is also not defined within the given material. The exercise requests the average value of $A$ over the behavior of Algorithm $J$, which...
TAOCP 1.3.3 Exercise 10
Section 1.3.3: Applications to Permutations Exercise 10. [ M28 ] Examine the timing characteristics of Program $B$, namely, the quantities $A$, $B$, $\ldots$, $Z$ shown there; express the total time in terms of the quantities $X$, $Y$, $M$, $N$, $U$, $V$ defined in (19), and of $F$. Compare the total time for Program $B$ with the total time for Program $A$ on the input (6), as computed in exercise 7....
TAOCP 1.3.3 Exercise 6
Section 1.3.3: Applications to Permutations Exercise 6. [ M28 ] What changes are made to the timing of Program $A$ if we remove the assumption that all blank words occur at the extreme right? Verified: no Solve time: 7m15s Setup Program A is analyzed in the text under the assumption that all blank words occur at the extreme right of the input. Under this assumption, every nonblank input word is...
TAOCP 1.2.9 Exercise 23
Section 1.2.9: Generating Functions Exercise 23. [ M33 ] (L. Carlitz.) (a) Prove that for all integers $m \ge 1$ there are polynomials $f_m(z_1,\ldots,z_m)$ and $g_m(z_1,\ldots,z_m)$ such that the formula $$ \sum_{k_1,\ldots,k_m \ge 0} \binom{r}{n-k_1}\binom{k_1}{n-k_2}\cdots\binom{k_{m-1}}{n-k_m} z_1^{k_1}\cdots z_m^{k_m} = f_m(z_1,\ldots,z_m)^{,n-r} g_m(z_1,\ldots,z_m)^{,r} $$ is an identity for all integers $n \ge r \ge 0$. (b) Generalizing exercise 15, find a closed form for the sum $$ S_n(z_1,\ldots,z_m) = \sum_{k_1,\ldots,k_m \ge 0} \binom{k_1}{n-k_2}\binom{k_2}{n-k_3}\cdots\binom{k_m}{n-k_1}...
TAOCP 1.2.9 Exercise 15
Section 1.2.9: Generating Functions Exercise 15. [ M28 ] By considering $H(w)=\sum_{n \ge 0} G_n(z)w^n$, find a closed form for the generating function $$ G_n(z) = \sum_{k=0}^{n} \binom{n-k}{k} z^k = \sum_{k=0}^{n} \binom{2k-n-1}{k} (-z)^k. $$ Verified: yes Solve time: 1m27s Setup Let $$ G_n(z) = \sum_{k=0}^{n} \binom{n-k}{k} z^k, $$ and define the bivariate generating function $$ H(w) = \sum_{n \ge 0} G_n(z), w^n. $$ The goal is to find a closed...
TAOCP 1.2.8 Exercise 42
Section 1.2.8: Fibonacci Numbers Exercise 42. [ M26 ] (D. A. Klarner.) Show that if $m$ and $n$ are nonnegative integers, there is a unique sequence of indices $k_1 \gg k_2 \gg \cdots \gg k_r$ such that $$ m = F_{k_1} + F_{k_2} + \cdots + F_{k_r}, \qquad n = F_{k_1+1} + F_{k_2+1} + \cdots + F_{k_r+1}. $$ (See exercise 34. The $k$'s may be negative, and $r$ may be...
TAOCP 1.2.8 Exercise 36
Section 1.2.8: Fibonacci Numbers Exercise 36. [ M32 ] ( Fibonacci strings. ) Let $S_1=\text{"a"}$, $S_2=\text{"b"}$, and $S_{n+2}=S_{n+1}S_n$, $n>0$; in other words, $S_{n+2}$ is formed by placing $S_n$ at the right of $S_{n+1}$. We have $S_3=\text{"ba"}$, $S_4=\text{"bab"}$, $S_5=\text{"babba"}$, etc. Clearly $S_n$ has $F_n$ letters. Explore the properties of $S_n$. (Where do double letters occur? Can you predict the value of the $k$th letter of $S_n$? What is the density of...
TAOCP 1.2.8 Exercise 37
Section 1.2.8: Fibonacci Numbers Exercise 37. [ M35 ] (R. E. Gaskell, M. J. Whinihan.) Two players compete in the following game: There is a pile containing $n$ chips; the first player removes any number of chips except that he cannot take the whole pile. From then on, the players alternate moves, each person removing one or more chips but not more than twice as many chips as the preceding...
TAOCP 1.2.8 Exercise 19
Section 1.2.8: Fibonacci Numbers Exercise 19. [ M27 ] What is $\cos 36^\circ$? Verified: yes Solve time: 1m32s Setup Let $\phi = \frac{1}{2}(1+\sqrt{5})$ as in equation (3). The goal is to determine the exact value of $\cos 36^\circ$. Consider a regular pentagon inscribed in a circle of radius $R$. Let $s$ denote the side length of the pentagon and $d$ the length of a diagonal. The central angle subtending one...
TAOCP 1.2.8 Exercise 14
Section 1.2.8: Fibonacci Numbers Exercise 14. [ M28 ] Let $m$ be a fixed positive integer. Find $a_n$, given that $$ a_0 = 0, \qquad a_1 = 1, \qquad a_{n+2} = a_{n+1} + a_n + \binom{n}{m}, \quad n \ge 0. $$ Verified: yes Solve time: 3m11s Let $F_n$ be the Fibonacci numbers: $$ F_0=0,\quad F_1=1,\quad F_{n+2}=F_{n+1}+F_n. $$ We solve $$ a_0=0,\quad a_1=1,\quad a_{n+2}=a_{n+1}+a_n+\binom{n}{m}. $$ 1. Decomposition Write $$ a_n =...
TAOCP 1.2.8 Exercise 12
Section 1.2.8: Fibonacci Numbers Exercise 12. [ M26 ] The "second order" Fibonacci sequence is defined by the rule $$ \mathcal{F} 0 = 0, \qquad \mathcal{F} 1 = 1, \qquad \mathcal{F} {n+2} = \mathcal{F} {n+1} + \mathcal{F}_n + F_n. $$ Express $\mathcal{F} n$ in terms of $F_n$ and $F {n+1}$. [Hint: Use generating functions.] Verified: yes Solve time: 3m18s The issue in the previous submission is not the method but...
TAOCP 1.2.7 Exercise 22
Section 1.2.7: Harmonic Numbers Exercise 22. [ M28 ] Evaluate $\sum_{k=0}^{n} H_k H_{n-k}$. Verified: yes Solve time: 2m58s The error identified in the review is genuine: the admissible region for $(i,j)$ was shifted from $i+j\le n$ to $i+j\le n+1$. The correct derivation must therefore be restarted from the triple-sum representation with the correct bounds. 1. Triple-sum expansion and correct region Let $H_k=\sum_{i=1}^k \frac{1}{i}$, with $H_0=0$. Then $$ S=\sum_{k=0}^n H_k H_{n-k}...
TAOCP 1.2.7 Exercise 18
Section 1.2.7: Harmonic Numbers Exercise 18. [ M33 ] (J. Selfridge.) What is the highest power of $2$ that divides the numerator of $1 + \frac{1}{3} + \cdots + \frac{1}{2n-1}$? Verified: no Solve time: 5m01s Let $$ S_n=\sum_{k=1}^n \frac{1}{2k-1}. $$ Since all denominators are odd, when $S_n=A_n/B_n$ is reduced, $B_n$ is odd. Hence $$ v_2(\text{numerator of }S_n)=v_2(S_n). $$ We determine $v_2(S_n)$. 1. Reduction to harmonic numbers Let $H_n=\sum_{k=1}^n \frac{1}{k}$. Split...
TAOCP 1.2.7 Exercise 19
Section 1.2.7: Harmonic Numbers Exercise 19. [ M30 ] List all nonnegative integers $n$ for which $H_n$ is an integer. Verified: no Solve time: 1m08s Setup For $n \ge 0$, the harmonic number is defined by $$ H_n = \sum_{k=1}^{n}\frac{1}{k}, $$ with $H_0 = 0$ by the empty sum convention. The task is to determine all nonnegative integers $n$ for which $H_n$ is an integer. It is required to show:...
TAOCP 1.2.6 Exercise 63
Section 1.2.6: Binomial Coefficients Exercise 63. [ M30 ] If $l,m,n$ are integers and $n \ge 0$, prove that $$ \sum_{j,k} (-1)^{j+k}\binom{j+k}{k+l}\binom{r}{j}\binom{n}{k}\binom{s+n-j-k}{m-j} = (-1)^l \binom{n+r}{n+l}\binom{s-r}{m-n-l}. $$ Verified: yes Solve time: 4m59s The original solution fails because it introduces an incorrect algebraic factorization and then builds a decoupling argument on it. The correct approach must avoid any structural separation that is not algebraically justified and instead keep the coefficient extraction consistent...
TAOCP 1.2.4 Exercise 45
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 45. ▶ [ M28 ] The result of exercise 37 is somewhat surprising, since it implies that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor \sum_{0 \le k < m} \left\lfloor \frac{nk+x}{m} \right\rfloor $$ when $m$ and $n$ are positive integers and $x$ is arbitrary. This “reciprocity relationship” is one of many similar formulas (see Section 3.3.3). Show that in...
TAOCP 1.2.4 Exercise 46
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 46. [ M29 ] ( General reciprocity law. ) Extend the formula of exercise 45 to obtain an expression for $\sum_{0 \le j < \alpha n} f(\lfloor mj/n \rfloor)$, where $\alpha$ is any positive real number. Verified: yes Solve time: 1m13s Setup Let $m,n$ be positive integers and let $\alpha>0$ be real. Define $S=\sum_{0 \le j < \alpha n} f!\left(\left\lfloor \frac{mj}{n}\right\rfloor\right).$...
TAOCP 1.2.4 Exercise 38
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 38. [ M26 ] (E. Busche, 1909.) Prove that, for all real $x$ and $y$ with $y>0$, $$ \sum_{0 \le k < y} \left\lfloor x+\frac{k}{y} \right\rfloor = \lfloor xy + \lfloor x+1 \rfloor(\lceil y \rceil - y)\rfloor. $$ In particular, when $y$ is a positive integer $n$, we have the important formula $$\lfloor x \rfloor + \left\lfloor x+\frac1n \right\rfloor + \cdots...
TAOCP 1.2.4 Exercise 37
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 37. ▶ [ M30 ] Let $m$ and $n$ be integers, $n>0$. Show that $$ \sum_{0 \le k < n} \left\lfloor \frac{mk+x}{n} \right\rfloor = \frac{(m-1)(n-1)}{2} + \frac{d-1}{2} + d\left\lfloor \frac{x}{d} \right\rfloor, $$ where $d$ is the greatest common divisor of $m$ and $n$, and $x$ is any real number. Verified: no Solve time: 4m54s Let $d=\gcd(m,n)$ and write $$ m=d m_1,\qquad...
TAOCP 1.2.4 Exercise 30
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 30. [ M30 ] Prove that the function $\varphi(n)$ of exercise 27 is multiplicative. Using this fact, evaluate $\varphi(1000000)$, and give a method for evaluating $\varphi(n)$ in a simple way once $n$ has been factored into primes. Verified: yes Solve time: 1m22s Setup Let $\varphi(n)$ denote the number of integers $a$ with $1 \le a \le n$ such that $a \perp...
TAOCP 1.2.3 Exercise 46
Section 1.2.3: Sums and Products Exercise 46. ▶ [ M30 ] Let $A$ be an $m \times n$ matrix, and let $B$ be an $n \times m$ matrix. Given that $1 \le j_1, j_2, \ldots, j_m \le n$, let $A_{j_1 j_2 \ldots j_m}$ denote the $m \times m$ matrix consisting of columns Verified: yes Solve time: 4m19s We restart from the correct expansion and repair only the faulty combinatorial step...
TAOCP 1.2.3 Exercise 44
Section 1.2.3: Sums and Products Exercise 44. ▶ [ M26 ] What is the sum of all $n^2$ elements in the inverse of Cauchy’s matrix? Verified: no Solve time: 7m31s Setup Let $$ A=(a_{ij}), \qquad a_{ij}=\frac1{x_i+y_j}, \qquad 1\le i,j\le n, $$ be Cauchy's matrix, and let $$ B=(b_{ij})=A^{-1}. $$ Exercise 41 gives $$ b_{ij} \frac{ \displaystyle \prod_{1\le k\le n}(x_j+y_k)(x_k+y_i) }{ \displaystyle (x_j+y_i) \left( \prod_{\substack{1\le k\le n\k\ne j}} (x_j-x_k) \right) \left(...
TAOCP 1.2.3 Exercise 41
Section 1.2.3: Sums and Products Exercise 41. [ M26 ] Show that the inverse of Cauchy’s matrix is given by $$b_{ij} = \left( \prod_{1 \le k \le n} (x_j + y_k)(x_k + y_i) \right) \bigg/ (x_j + y_i) \left( \prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k) \right) \left( \prod_{\substack{1 \le k \le n \ k \ne i}} (y_i - y_k) \right).$$ Verified: yes Solve time:...
TAOCP 1.2.3 Exercise 33
Section 1.2.3: Sums and Products Exercise 33. ▶ [ M30 ] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20: $$ \begin{aligned} \frac{1}{(a-b)(a-c)} + \frac{1}{(b-a)(b-c)} + \frac{1}{(c-a)(c-b)} &= 0, \[5pt] \frac{a}{(a-b)(a-c)} + \frac{b}{(b-a)(b-c)} + \frac{c}{(c-a)(c-b)} &= 0, \[5pt] \frac{a^2}{(a-b)(a-c)} + \frac{b^2}{(b-a)(b-c)} + \frac{c^2}{(c-a)(c-b)} &= 1, \[5pt] \frac{a^3}{(a-b)(a-c)} + \frac{b^3}{(b-a)(b-c)} + \frac{c^3}{(c-a)(c-b)} &= a+b+c. \end{aligned} $$ Prove that these formulas...
TAOCP 1.2.3 Exercise 29
Section 1.2.3: Sums and Products Exercise 29. ▶ [ M30 ] (a) Express $\sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k$ in terms of the multiple-sum notation explained at the end of the section. (b) Express the same sum in terms of $\sum_{i=0}^n a_i$, $\sum_{i=0}^n a_i^2$, and $\sum_{i=0}^n a_i^3$ [see Eq. (13)]. Verified: yes Solve time: 5m05s (a) Multiple-sum notation The iterated sum $$ \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j a_i a_j a_k $$ ranges...
TAOCP 1.2.2 Exercise 28
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 28. [ M30 ] (R. Feynman.) Develop a method for computing $b^x$ when $0 \le x < 1$, using only shifting, addition, and subtraction (similar to the algorithm in exercise 25), and analyze its accuracy. Verified: no Solve time: 5m27s Correct Solution The goal is to compute $b^x$ for $0 \le x < 1$ using only shifting, addition, and subtraction, and to analyze...
TAOCP 1.2.2 Exercise 26
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 26. [ M27 ] Find a rigorous upper bound on the error made by the algorithm in the previous exercise, based on the precision used in the arithmetic operations. Verified: yes Solve time: 2m49s We restart from a consistent floating-point model and propagate the error through the iterative state update. 1. Correct error model Assume IEEE-style relative rounding for each arithmetic operation: $$...
TAOCP 1.2.10 Exercise 17
Section 1.2.10: Analysis of an Algorithm Exercise 17. [ M27 ] Let $f(z)$ and $g(z)$ be generating functions that represent probability distributions. a) Show that $h(z)=g(f(z))$ is also a generating function representing a probability distribution. b) Interpret the significance of $h(z)$ in terms of $f(z)$ and $g(z)$. c) Give formulas for the mean and variance of $h$ in terms of those for $f$ and $g$. Verified: yes Solve time: 2m18s...
TAOCP 1.2.10 Exercise 18
Section 1.2.10: Analysis of an Algorithm Exercise 18. [ M28 ] Suppose that the values taken on by $X[1],X[2],\ldots,X[n]$ in Algorithm M include exactly $k_1$ ones, $k_2$ twos, $\ldots$, $k_n$ $n$'s, arranged in random order, where $$ k_1+k_2+\cdots+k_n = n. $$ Show that in this generalized situation, the generating function (8) becomes $$ \left(\frac{k_n z}{k_n}\right) \left(\frac{k_{n-1}z+k_n}{k_{n-1}+k_n}\right) \left(\frac{k_{n-2}z+k_{n-1}+k_n}{k_{n-2}+k_{n-1}+k_n}\right)\cdots \left(\frac{k_1z+k_2+\cdots+k_n}{k_1+k_2+\cdots+k_n}\right)z, $$ using the convention $0/0=1$. Verified: yes Solve time: 5m49s Let the...
TAOCP 1.2.10 Exercise 7
Section 1.2.10: Analysis of an Algorithm Exercise 7. [ M27 ] In our analysis of Algorithm M, we assumed that all the $X[k]$ were distinct. Suppose, instead, that we make only the weaker assumption that $X[1],X[2],\ldots,X[n]$ contain precisely $m$ distinct values; the values are otherwise random, subject to this constraint. What is the probability distribution of $A$ in this case? Verified: yes Solve time: 1m44s Setup Let $X[1],X[2],\ldots,X[n]$ be a...
TAOCP 1.2.1 Exercise 11
Section 1.2.1: Mathematical Induction Exercise 11. [ M30 ] Find and prove a simple formula for the sum $$ \frac{1^3}{1^4 + 4} - \frac{3^3}{3^4 + 4} + \frac{5^3}{5^4 + 4} - \cdots + \frac{(-1)^n(2n + 1)^3}{(2n + 1)^4 + 4}. $$ Verified: yes Solve time: 3m11s 1. Correcting the algebraic decomposition The previous solution failed because the proposed identity was incorrect. We restart by finding the correct partial fraction decomposition...