#hm-hard
TAOCP 7.2.1.5 Exercise 58
Section 7.2.1.5: Generating All Set Partitions Exercise 58. [ HM31 ] Complete the proof of (43) as follows. a) Show that for all $\sigma>0$ there is a number $\tau\ge 2\sigma$ such that $\tau$ is a multiple of $2\pi$ and $\lvert e^{\sigma+it}-1\rvert/\lvert \sigma+it\rvert$ is monotone decreasing for $0\le t\le \tau$. b) Prove that $\int_{-\tau}^{\tau}\exp((n+1)g(\sigma+it)),dt$ leads to (43). c) Show that the corresponding integrals over the straight-line paths $z=t\pm i\tau$ for $-n\le...
TAOCP 7.2.1.5 Exercise 56
Section 7.2.1.5: Generating All Set Partitions Exercise 56. ▶ [ HM26 ] Let $g(z)=\alpha^{-1}\ln(e^z-1)-\ln z$ and $\sigma=\alpha-\beta$ as in (37). a) Prove that $(-\sigma)^{n+1}g^{(n+1)}(\sigma)=n!-\sum_{k=0}^n \left\langle\begin{array}{c} n \ k \end{array}\right\rangle \alpha^k\beta^{n-k}$, where the Eulerian numbers $\left\langle\begin{array}{c} n \ k \end{array}\right\rangle$ are defined in Section 5.1.3. b) Prove that $\dfrac{\beta}{\alpha}n!<\sum_{k=0}^n \left\langle\begin{array}{c} n \ k \end{array}\right\rangle \alpha^k\beta^{n-k}<n!$ for all $\sigma>0$. Hint: See exercise 5.1.3–25. c) Now verify the inequality (42). Verified: no Solve...
TAOCP 7.2.1.5 Exercise 53
Section 7.2.1.5: Generating All Set Partitions Exercise 53. ▶ [ HM30 ] Let $G(z)=\sum_{k=0}^{\infty}p_k z^k$ be the generating function for a discrete probability distribution, converging for $|z|<1+\delta$; thus the coefficients $p_k$ are nonnegative, $G(1)=1$, and the mean and variance are respectively $\mu=G'(1)$ and $\sigma^2=G''(1)+G'(1)-G'(1)^2$. If $X_1,\ldots,X_n$ are independent random variables having this distribution, the probability that $X_1+\cdots+X_n=m$ is $[z^m],G(z)^n$, and we often want to estimate this probability when $m$ is...
TAOCP 7.2.1.5 Exercise 51
Section 7.2.1.5: Generating All Set Partitions Exercise 51. [ HM27 ] Use the saddle point method to estimate $t_n=n![z^n],e^{z+z^2/2}$, the number of involutions on $n$ elements (aka partitions of ${1,\ldots,n}$ into blocks of sizes $\le 2$). Verified: no Solve time: 5m17s Setup The number of involutions on ({1,\dots,n}) (partitions into blocks of size (\le 2)) is [ t_n = n!,[z^n],e^{z+z^2/2}. ] By Cauchy's integral formula, [ t_n = \frac{n!}{2\pi i}\oint...
TAOCP 7.2.1.5 Exercise 49
Section 7.2.1.5: Generating All Set Partitions Exercise 49. ▶ [ HM35 ] Prove that, for large $n$, the number $\xi$ defined in Eq. (24) is equal to $$ \ln n-\ln\ln n+\sum_{j,k\ge 0}\left[\begin{array}{c} j+k \ j+1 \end{array}\right]\alpha^j\frac{\beta^k}{k!}, \qquad \alpha=-\frac{1}{\ln n}, \qquad \beta=\frac{\ln\ln n}{\ln n}. $$ Verified: no Solve time: 2m06s Setup The number (\xi) in Eq. (24) of the text is defined by the saddle‑point equation [ \xi e^{\xi} = n...
TAOCP 5.3.1 Exercise 16
Section 5.3.1: Minimum-Comparison Sorting Exercise 16. [ HM26 ] (F. Hwang and S. Lin.) Prove that $F(n) > \lceil \lg n! \rceil$ for $n \ge 22$. Verified: no Solve time: 22m58s Setup Let (F(n)) denote the number of comparisons performed by the merge‑insertion (Ford-Johnson) algorithm when sorting (n) distinct elements. From the description in the text (Section 5.3.1) one can derive the explicit formula [ F(n)=\sum_{k=1}^{n}\Bigl\lceil \lg\frac{3k}{4}\Bigr\rceil \qquad (n\ge 1),...
TAOCP 5.2.5 Exercise 18
Section 5.2.5: Sorting by Distribution Exercise 18. [ HM26 ] Prove Theorem T. Hint: Show first that MacLaren's distribution-plus-insertion algorithm does $O(BN)$ operations, on the average, when it is applied to independent random keys whose probability density function satisfies $f(x) \le B$ for $0 \le x \le 1$. For sorting the roots and words we had the use of 1100 lozenge boxes, and used trays for the forms. , GEORGE...
TAOCP 5.2.3 Exercise 37
Section 5.2.3: Sorting by Selection Exercise 37. [ HM32 ] Let $e_N(k)$ be the expected treewise distance of the $k$th-largest element from the root, in a random heap of $N$ elements, and let $e(k) = \lim_{N \to \infty} e_N(k)$. Thus $e(1) = 0$, $e(2) = 1$, $e(3) = 1.5$, and $e(4) = 1.875$. Find the asymptotic value of $e(k)$ to within $O(k^{-1})$. Verified: no Solve time: 16m56s We need to...
TAOCP 5.2.2 Exercise 52
Section 5.2.2: Sorting by Exchanging Exercise 52. [ HM35 ] (N. G. de Bruijn.) What is the asymptotic behavior of the sum $$S_n = \sum_{t \ge 1} \binom{2n}{n+t} d(t),$$ where $d(t)$ is the number of divisors of $t$? (Thus, $d(1) = 1$, $d(2) = d(3) = 2$, $d(4) = 3$, $d(5) = 2$, etc.) (This problem arose in connection with the analysis of a tree traversal algorithm, exercise 2.3.1–11.) Find...
TAOCP 5.2.2 Exercise 42
Section 5.2.2: Sorting by Exchanging Exercise 42. [ HM32 ] For any real number $c > 0$, prove that the probability is less than $e^{-c}$ that Algorithm Q will make more than $(c+1)(N+1)H_N$ comparisons when sorting random data. (This upper bound is especially interesting when $c$ is, say, $N^{\epsilon}$.) Verified: no Solve time: 1h45m We need to solve Exercise 42 from Volume 3, Section 5.2.2 (Sorting by Exchanging). The exercise:...
TAOCP 5.2.2 Exercise 51
Section 5.2.2: Sorting by Exchanging Exercise 51. ▶ [ HM28 ] Show that the gamma-function approach to asymptotic problems can be used instead of Euler's summation formula to derive the asymptotic expansion of the quantity $r_k(m)$ in (35). (This gives us a uniform method for studying $r_k(m)$ for all $k$, without relying on tricks such as the text's introduction of $g_{-1}(x) = (e^{-x} - 1/x)$.) Verified: no Solve time: 7m01s...
TAOCP 5.1.4 Exercise 23
Section 5.1.4: Tableaux and Involutions Exercise 23. ▶ [ HM30 ] (D. André.) In how many ways, $E_m$, can the numbers ${1, 2, \ldots, n}$ be placed into the array of $n$ cells $$\begin{array}{cccc} & & \cdots \ \square & \square & \cdots \end{array}$$ in such a way that the rows and columns are in increasing order? Find the generating function $g(z) = \sum E_m z^m / m!$. Verified: no...
TAOCP 1.2.11.3 Exercise 11
Section 1.2.11.3: Some Asymptotic Calculations Exercise 11. ▶ [ HM35 ] Let us generalize the functions $Q(n)$ and $R(n)$ by introducing a parameter $x$: $$ Q_x(n)=1+\frac{n-1}{n}x+\frac{n-1}{n}\frac{n-2}{n}x^2+\cdots, $$ $$ R_x(n)=1+\frac{n}{n+1}x+\frac{n}{n+1}\frac{n}{n+2}x^2+\cdots. $$ Explore this situation and find asymptotic formulas when $x\ne 1$. Verified: no Solve time: 19m20s Setup The generalized sums are defined for integer (n\ge 1) and real (x) by [ Q_x(n) = \sum_{k=0}^{n-1} \frac{(n-1) k}{n^k},x^k, \qquad R_x(n) = \sum {k=0}^{\infty}...
TAOCP 5.1.4 Exercise 36
Section 5.1.4: Tableaux and Involutions Exercise 36. [ HM27 ] (R. P. Stanley, 1971.) (a) Prove that the number of reverse plane partitions of $m$ in a given shape is $\lfloor s^m \rfloor / \prod (1 - z^{h_{ij}})$, where the numbers $h_{ij}$ are the hook lengths of the shape. (b) Derive Theorem H from this result. [ Hint: What is the asymptotic number of partitions as $m \to \infty$?] Verified:...
TAOCP 5.1.4 Exercise 31
Section 5.1.4: Tableaux and Involutions Exercise 31. [ HM30 ] Let $x_n$ be the number of ways to place $n$ mutually nonattacking rooks on an $n \times n$ chessboard, where each arrangement is unchanged by reflection about both diagonals. Thus, $x_4 = 6$. (Involutions are required to be symmetrical about only one diagonal. Exercise 5.1.3–19 considers a related problem.) Find the asymptotic behavior of $x_n$. Verified: yes Solve time: 4h31m...
TAOCP 5.1.4 Exercise 18
Section 5.1.4: Tableaux and Involutions Exercise 18. [ HM30 ] Generalizing exercise 17, evaluate the sum $$x_1^m, \Delta(y, x_2, \ldots, x_n) + x_2^m, \Delta(x_1, x_2, \ldots, x_n) + \cdots + x_n^m, \Delta(x_1, x_2, \ldots, x_{n-1}, y),$$ when $m \ge 0$. Verified: yes Solve time: 1h24m Setup Let $\Delta(x_1,\dots,x_n)$ denote the Vandermonde determinant $$\Delta(x_1,\dots,x_n) = \prod_{1\le i<j\le n} (x_j - x_i).$$ We are to evaluate, for $m\ge 0$, the sum $$S_m...
TAOCP 5.1.2 Exercise 20
Section 5.1.2: Permutations of a Multiset Exercise 20. ▶ [ HM33 ] (D. Foata.) Let $(a_{ij})$ be any matrix of real numbers. In the notation of exercise 19(b), define $\nu(\pi) = a_{i_1 j_1} \ldots a_{i_n j_n}$, where the two-line notation for $\pi$ is $$\begin{pmatrix} x_{j_1} & x_{j_2} & \cdots & x_{j_n} \ x_{i_1} & x_{i_2} & \cdots & x_{i_n} \end{pmatrix}.$$ This function is useful in the computation of generating functions...
TAOCP 5.1.2 Exercise 19
Section 5.1.2: Permutations of a Multiset Exercise 19. [ HM28 ] Define the Möbius function $\mu(\pi)$ of a permutation $\pi$ to be 0 if $\pi$ contains repeated elements, otherwise $(-1)^k$ if $\pi$ is the product of $k$ primes. (Compare with the definition of the ordinary Möbius function, exercise 4.5.2–10.) a) Prove that if $\pi \ne \epsilon$, we have $$\sum \mu(\lambda) = 0,$$ summed over all permutations $\lambda$ that are left...
TAOCP 1.2.11.3 Exercise 10
Section 1.2.11.3: Some Asymptotic Calculations Exercise 10. [ HM34 ] Under the assumptions of the preceding problem, with $p\ne 1$, obtain the asymptotic expansion of $\gamma(x+1,px+py/(p-1))-\gamma(x+1,px)$, for fixed $y$, to terms of the same order as obtained in the previous exercise. Verified: yes Solve time: 44m31s Setup We consider the difference [ \Delta = \gamma(x+1,, px + \tfrac{p y}{p-1}) - \gamma(x+1,, px), ] where (p \neq 1) is a real...
TAOCP 7.2.2.2 Exercise 350
Section 7.2.2.2: Satisfiability Exercise 350. ▶ [ HM26 ] [HM26] (W. Pegden.) Suppose Algorithm M is applied to the $m = n+1$ events $$A_j = x_j \quad \text{for } 1 \le j \le n; \qquad A_m = x_1 \vee \cdots \vee x_n.$$ Thus $A_m$ is true whenever any of the other $A_j$ is true, so we could implement step M2 by never setting $j \leftarrow m$. Alternatively, we could decide...
TAOCP 7.2.2.2 Exercise 348
Section 7.2.2.2: Satisfiability Exercise 348. [ HM26 ] [HM26] (A. Pringsheim, 1894.) Show that any power series $f(z) = \sum_{n=0}^{\infty} a_n z^n$ with $a_n \ge 0$ and radius of convergence $\rho$, where $0 < \rho < \infty$, has a singularity at $z = \rho$. Verified: no Solve time: 3m42s Setup Let $G$ be a graph with vertices numbered by the ancestor relation $\succ$ in a forest. A graph is tree-ordered...
TAOCP 7.2.2.2 Exercise 346
Section 7.2.2.2: Satisfiability Exercise 346. ▶ [ HM28 ] Write $(142)$ as $M_G = M_{G \setminus a}(1 - aK_{a,G})$ where $K_{a,G} = M_{G \setminus a^*} / M_{G \setminus a}$. a) If $(p_1, \ldots, p_m) \in \mathcal{R}(G)$, prove that $K_{a,G}$ is monotonic in all of its parameters: It does not increase if any of $p_1, \ldots, p_m$ are decreased. b) Exploit this fact to design an algorithm that computes $M_G(p_1, \ldots,...
TAOCP 7.2.2.2 Exercise 34
Section 7.2.2.2: Satisfiability Exercise 34. [ HM26 ] [HM26] The fractional coloring number $\chi^*(G)$ of a graph $G$ is defined to be the minimum ratio $p/q$ for which $G$ has a $q$-tuple coloring that uses $p$ colors. a) Prove that $\chi^*(G) \le \chi(G)$ and show that equality holds in McGrager's graphs. b) Let $S_1, \ldots, S_N$ be all the independent subsets of $G$'s vertices. Show that $$\chi^*(G) = \min_{\lambda_1,\ldots,\lambda_N \ge...
TAOCP 7.2.2.2 Exercise 339
Section 7.2.2.2: Satisfiability Exercise 339. ▶ [ HM26 ] [HM26] (G. Viennot.) This exercise explores factorization of traces into pyramids. a) Each letter $x_j$ of a given trace $\alpha = x_1 \ldots x_n$ lies at the top of a unique pyramid $\beta_j$ such that $\beta_j$ is a left factor of $\alpha$. For example, in the trace $bcebcabc$ of (136), the pyramids $\beta_1, \ldots, \beta_8$ are respectively $b$, $bcb$, $bceb$, $bcf$,...
TAOCP 7.2.2.2 Exercise 335
Section 7.2.2.2: Satisfiability Exercise 335. [ HM26 ] [HM26] If the vertices of $G$ can be ordered in such a way that $x < y < z$ and $x \not\to y$ and $y \to z$ implies $x \not\to z$, show that the Möbius series $M_G$ can be expressed as a determinant. For example, $$\text{if } G = \begin{array}{c} a \circ !!-!!\circ b \ c \circ !!-!!\circ !!-!!d \ e \circ...
TAOCP 7.2.2.2 Exercise 322
Section 7.2.2.2: Satisfiability Exercise 322. ▶ [ HM35 ] [HM35] (K. Kolipaka and M. Szegedy, 2011.) Surprisingly, the previous exercise cannot be solved in the setting of Algorithm M! Suppose we have independent random variables $(W, X, Y, Z)$ such that $A$ depends on $W$ and $X$, $B$ depends on $X$ and $Y$, $C$ depends on $Y$ and $Z$, $D$ depends on $Z$ and $W$. Here $W$ equals $j$ with...
TAOCP 7.2.2.2 Exercise 318
Section 7.2.2.2: Satisfiability Exercise 318. [ HM27 ] (J. B. Shearer.) Prove that Theorem J is the best possible result of its kind: If $p > (d-1)^{d-1}/d^d$ and $d > 1$, there is a graph $G$ of maximum degree $d$ for which $(p, \ldots, p) \notin \mathcal{R}(G)$. Hint: Consider complete $t$-ary trees, where $t = d - 1$. Verified: no Solve time: 4m44s Solution No. Theorem J and Theorem L...
TAOCP 7.2.2.2 Exercise 306
Section 7.2.2.2: Satisfiability Exercise 306. ▶ [ HM32 ] (Luby, Sinclaire, and Zuckerman, 1993.) Consider a "Las Vegas algorithm" that succeeds or fails; it succeeds at step $t$ with probability $p_t$, and fails with probability $p_\infty < 1$. Let $q_t = p_t + p_{t+1} + \cdots + p_1$ and $E_t = p_1 + 2p_2 + \cdots + tp_t$; also let $E_\infty = \infty$ if $p_\infty > 0$, otherwise $E_\infty =...
TAOCP 7.2.2.2 Exercise 304
Section 7.2.2.2: Satisfiability Exercise 304. [ HM34 ] Consider the 2SAT problem with $n(n-1)$ clauses $(\bar{x}_j \vee x_k)$ for all $j \ne k$. Find the generating functions for the number of flips taken by Algorithms P and W. Hint: Exercises 1.2.6–68 and MPR-105 are helpful for finding the exact formulas. Verified: no Solve time: 3m56s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The...
TAOCP 7.2.2.2 Exercise 297
Section 7.2.2.2: Satisfiability Exercise 297. ▶ [ HM26 ] (Emo Welzl.) Let $G_k(z) = \sum_n C_{n,p+q-1}(z/3)^{n-q}(2z/3)^p$ be the generating function for stopping time $t = 2p + q$ when $Y_0 = q$ in the proof of Theorem U. a) Find a closed form for $G_k(z)$, using formulas from Section 7.2.1.6. b) Explain why $G_k(1)$ is less than 1. c) Evaluate and interpret the quantity $G'_k(1)/G_k(1)$. d) Use Markov's inequality to...
TAOCP 7.2.2.2 Exercise 243
Section 7.2.2.2: Satisfiability Exercise 243. [ HM31 ] (E. Ben-Sasson and A. Wigderson.) Let $F$ be a set of $\lfloor cn \rfloor$ random 3SAT clauses on $n$ variables, where $\alpha > 1/e$ is a given constant. For any clause $C$ on those variables, define $\mu(C) = \min{|F'| \mid F' \subseteq F \text{ and } F' \vdash C}$. Also let $V(F')$ denote the variables that occur in a given family of...
TAOCP 7.2.2.2 Exercise 201
Section 7.2.2.2: Satisfiability Exercise 201. [ HM29 ] The $t$-snake clauses specified by a chain $(l_1, \ldots, l_{2t-1})$ can be written $(l_i \vee l_{i+1})$ for $0 \le i < 2t$, where $l_0 = \bar{l}_1$ and subscripts are treated mod $2t$. a) Describe all ways to set two of the $l$'s so that $(\bar{x}_1 \vee x_1)$ is not among those $2t$ clauses. b) Similarly, set three of the $l$'s in order...
TAOCP 7.2.2.2 Exercise 198
Section 7.2.2.2: Satisfiability Exercise 198. ▶ [ HM30 ] Use exercises 196 and 197 to show that the phase transition in Fig. 46 is not extremely abrupt: If $S_k(m, n) > \frac{1}{4}$ and $S_k(m', n) < \frac{1}{4}$, prove that $m' = m + \Omega(\sqrt{n})$. Verified: no Solve time: 5m37s Correctness The proposed solution identifies the correct reformulation of the problem. A Boolean function on four variables is representable in $3$CNF...
TAOCP 7.2.2.2 Exercise 307
Section 7.2.2.2: Satisfiability Exercise 307. [ HM28 ] Continuing exercise 306, consider a more general strategy defined by an infinite sequence of positive integers $(N_1, N_2, \ldots)$: "Set $j \leftarrow 0$; then, while success has not yet been achieved, set $j \leftarrow j+1$ and run the algorithm with cutoff parameter $N_j$." a) Explain how to compute $\mathop{\rm E} X$, where $X$ is the number of steps taken before this strategy...
TAOCP 7.2.2.2 Exercise 177
Section 7.2.2.2: Satisfiability Exercise 177. [ HM26 ] Let $I_q$ be the number of independent sets of the flower snark line graph $L(J_q)$. Compute $I_q$ for $1 \le q \le 8$, and determine the asymptotic growth rate. Verified: no Solve time: 3m51s Setup An independent set in a line graph corresponds exactly to a matching in the original graph. Therefore $I_q$, the number of independent sets of $L(J_q)$, equals the...
TAOCP 7.2.2.2 Exercise 169
Section 7.2.2.2: Satisfiability Exercise 169. ▶ [ HM30 ] (T. Ahmed, O. Kullmann.) Excellent results have been obtained in some problems when the branch variable in step L3 is chosen to minimize the quantity $\tau(H(l), H(\bar{l}))$, where $\tau(a, b)$ is the positive solution to $\tau^{-a} + \tau^{-b} = 1$. (For example, $\tau(1, 2) = \phi \approx 1.62$ and $\tau(\sqrt{2}, \sqrt{2}) = 2^{1/\sqrt{2}} \approx 1.63$, so we prefer $(1, 2)$ to...
TAOCP 7.2.2.2 Exercise 6
Section 7.2.2.2: Satisfiability Exercise 6. ▶ [ HM27 ] [HM27] Use the Local Lemma to show that $W(k, k) > \Omega(k/(\log k))^{1/2}$. Verified: yes Solve time: 1m50s Setup Let $W(r,s)$ denote the least integer $n$ such that every coloring of ${1,\ldots,n}$ with $r$ colors contains a monochromatic arithmetic progression of length $s$. We must prove $$ W(k,k)>\Omega\left(\frac{k}{\log k}\right)^{1/2}. $$ It is enough to construct, for infinitely many $k$, a $k$-coloring...
TAOCP 7.2.2.1 Exercise 255
Section 7.2.2.1: Dancing Links Exercise 255. [ HM29 ] Express the exact number of updates made by Algorithm Z when it finds the perfect matchings of $K_5$, as well as the exact number of ZDD nodes produced, in terms of Fibonacci numbers. Hint: See exercise (93). Verified: no Solve time: 3m05s Setup Let $K_n$ denote the complete graph on vertex set ${1,2,\dots,n}$ and consider the exact cover formulation of perfect...
TAOCP 7.2.2.1 Exercise 189
Section 7.2.2.1: Dancing Links Exercise 189. [ HM31 ] Let $\rho_n = \hat{s} n - g {\varpi_n}$ (see (86)). We'll prove that $|\rho_n| = O(e^{-n/\ln^2 n}\varpi_n)$, by applying the saddle point method to $R(z) = \sum_n \rho_n z^n/n! = e^{e^z} \int_0^\infty e^{-t} dt$. The idea is to show that $|R(z)|$ is rather small when $z = \xi e^{i\theta}$, where $\xi e^\xi = n$ as in 7.2.1.5–(2g). a) Express $|e^{e^z}|$ and...
TAOCP 7.2.1.6 Exercise 85
Section 7.2.1.6: Generating All Trees Exercise 85. [ HM35 ] (Philippe Golle.) Let $V$ be any vector space contained in the set of all real $n$-dimensional vectors, but containing none of the unit vectors $(1, 0, \ldots, 0)$, $(0, 1, 0, \ldots, 0)$, …, $(0, \ldots, 0, 1)$. Prove that $V$ contains at most $M_n$ vectors whose components are all 0 or 1; furthermore the upper bound $M_n$ is achievable....
TAOCP 7.2.1.6 Exercise 84
Section 7.2.1.6: Generating All Trees Exercise 84. ▶ [ HM27 ] (D. Kleitman.) Let $A$ be an $m \times n$ matrix of real numbers in which every column $v$ has length $|v| \ge 1$, and let $b$ be an $m$-dimensional column vector. Prove that at most $M_n$ column vectors $x = (a_1, \ldots, a_n)^T$, with components $a_j = 0$ or $1$, satisfy $|Ax - b| < \frac{1}{2}$. Hint: Use a...
TAOCP 7.2.2 Exercise 72
Section 7.2.2: Backtracking Exercise 72. [ HM28 ] Show that exercise 71 has a surprising, somewhat paradoxical answer if two changes are made to Table 666: 9(E) becomes '$c \in [39,..,43]$'; 15(C) becomes '${11}$'. Verified: no Solve time: 1m59s 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 75
Section 7.2.1.6: Generating All Trees Exercise 75. ▶ [ HM29 ] [HM29] Let $(r_1^{(n)}, r_2^{(n)}, \ldots, r_{c_n}^{(n)})$ be the row numbers in which the Christmas tree pattern of order $n$ has $n-1$ entries; for example, Table 4 tells us that $(r_1^{(3)}, r_2^{(3)}, r_3^{(3)}) = (20, 40, 54, 62, 66, 68, 69)$. Find formulas for $r_1^{(n)} - r_1^{(n)}$ and for $\lim_{n \to \infty} r_j^{(n)}/M_n$. Verified: no Solve time: 4m20s The solution...
TAOCP 7.2.2 Exercise 61
Section 7.2.2: Backtracking Exercise 61. [ HM26 ] Let $P_n$ be the number of integer sequences $x_1 \ldots x_n$ such that $x_1 = 1$ and $1 \le x_{k+1} \le 2x_k$ for $1 \le k < n$. (The first few values are 1, 2, 6, 20, 76, 2280, ...; this sequence was introduced by A. Cayley in Philosophical Magazine (4) 13 (1857), 245–248, who showed that $P_n$ enumerates the partitions of...
TAOCP 7.2.1.6 Exercise 59
Section 7.2.1.6: Generating All Trees Exercise 59. [ HM29 ] Similarly, let $T_{l_{\min}}$ count all $n$-node binary trees in which internal node $n$ appears at level $l$. Find a simple formula for $T_{nm} = \sum_{l \ge 1} T_{l_{\min}}$. Verified: no Solve time: 5m51s 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.1.6 Exercise 58
Section 7.2.1.6: Generating All Trees Exercise 58. [ HM34 ] $[HM34]$ Let $t_{mn}$ be the number of $n$-node binary trees in which each external node appears at level $l$ when the external nodes are numbered from 0 to $n$ in symmetric order. Also let $t_m = \sum_{n\ge 0} t_{mn}$, so that $t_{mn}/C_n$ is the average level of external node $m$; and let $t(w,z)$ be the super generating function $$\sum_{m,n} t_{mn}...
TAOCP 7.2.2 Exercise 47
Section 7.2.2: Backtracking Exercise 47. [ HM29 ] $[HM29]$ A commafree code on $m$ letters is equivalent to at most $2m!$ such codes if we permute the letters and/or replace each codeword by its left-right reflection. Determine all of the nonisomorphic commafree codes of length 4 on $m$ letters when $m$ is (a) 2 (b) 3 (c) 4 and there are (a) 3 (b) 18 (c) 57 codewords. Verified: no...
TAOCP 7.2.1.6 Exercise 54
Section 7.2.1.6: Generating All Trees Exercise 54. [ HM29 ] $[HM29]$ What are the mean and variance of $c_1 + \cdots + c_n$? (See exercise 46.) Verified: no Solve time: 5m52s 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$....
TAOCP 7.2.2 Exercise 38
Section 7.2.2: Backtracking Exercise 38. [ HM28 ] $[HM28]$ What is the probability that Eastman's algorithm finishes in one round? (Assume that $x$ is a random $m$-ary string of odd length $n > 1$, unequal to any of its other cyclic shifts. Use a generating function to express the answer.) Verified: no Solve time: 5m07s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2...
TAOCP 7.2.1.6 Exercise 29
Section 7.2.1.6: Generating All Trees Exercise 29. [ HM31 ] [HM31] The covering graph of a Tamari lattice is sometimes known as an "associahedron," because of its connection with the associative law (§4), proved in exercise 27(b). The associahedron of order 4, depicted in Fig. 61, looks like it has three square faces and six faces that are regular pentagons. (Compare with Fig. 43 in exercise 7.2.1.2.60, which shows the...
TAOCP 7.2.1.5 Exercise 65
Section 7.2.1.5: Generating All Set Partitions Exercise 65. [ HM32 ] What is the variance of the number of blocks of size $k$ in a random partition of ${1, \ldots, n}$? Verified: no Solve time: 5m52s 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...
TAOCP 7.2.1.5 Exercise 61
Section 7.2.1.5: Generating All Set Partitions Exercise 61. [ HM26 ] Prove that if $m = n - r$ where $r \le n^*$ and $z \le n^{1/2}$, Eq. (43) yields $$\left{ n \atop n-r \right} = \frac{n^{2r}}{2^r r!} \left(1 + O(n^{2r-1}) + O!\left(\frac{1}{r}\right)\right).$$ 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...
TAOCP 7.2.1.5 Exercise 30
Section 7.2.1.5: Generating All Set Partitions Exercise 30. [ HM30 ] [HM30] The generalized Stirling number $\begin{Bmatrix}n\m\end{Bmatrix}_q$ is defined by the recurrence $$\begin{Bmatrix}n+1\m\end{Bmatrix}_q = (1+q+\cdots+q^{m-1})\begin{Bmatrix}n\m\end{Bmatrix}_q + \begin{Bmatrix}n\m-1\end{Bmatrix}_q, \qquad \begin{Bmatrix}0\m\end{Bmatrix} q = \delta {m0}.$$ Thus $\begin{Bmatrix}n\m\end{Bmatrix}_q$ is a polynomial in $q$ and $\begin{Bmatrix}n\m\end{Bmatrix}_1 = \begin{Bmatrix}n\m\end{Bmatrix}$, because it satisfies the recurrence relation in Eq. 1.2.6--(46). a) Prove that the generalized Stirling number $\varpi_n(x, y) = R(n-1, \ldots, 1)$ of exercise 28(e) has...
TAOCP 7.2.1.5 Exercise 24
Section 7.2.1.5: Generating All Set Partitions Exercise 24. [ HM35 ] [HM35] Continuing the previous exercise, because the Bell numbers satisfy the periodic law $\varpi_{n+p^{p-1} \cdot N} \equiv \varpi_n \pmod{p^r}$, if $p$ is an odd prime. [ Hint: Show that $$x^p \equiv g_{r}(x) + p^{r-1} g_{r-1}(x) + \cdots + g_1(x) \pmod{p^r}$$ where $g_r(x) = g_r(x, p^{r-1}g_{r-1}(x), \ldots, p \cdot g_1(x))$ and $g_s(x) = (x^p - x)^s$.] Verified: no Solve time:...
TAOCP 7.2.1.5 Exercise 23
Section 7.2.1.5: Generating All Set Partitions Exercise 23. [ HM30 ] [HM30] If $f(z) = \sum_{k} a_k z^k$ is a polynomial, let $\hat{f}(\varpi)$ stand for $\sum a_k \varpi_k$. a) Prove the symbolic formula $f(\varpi + 1) = \pi \hat{f}(\varpi)$. (For example, if $f(x)$ is the polynomial $x^2$, this formula states that $\varpi_2 + 2\varpi_1 + \varpi_0 = \varpi_2$.) b) Similarly, prove that $f(\varpi + k) = \pi^k \hat{f}(\varpi)$ for all...
TAOCP 7.2.1.4 Exercise 50
Section 7.2.1.4: Generating All Partitions Exercise 50. [ HM33 ] [HM33] Let c(m) = cm(2m) in the recurrence (56), (57). a) Prove that cm(m + k) = m −k + c(k) for 0 ≤k ≤m. b) Consequently (58) holds for m ≤n ≤2m, if c(m) < 3p(m) for all m ≥0. c) Show that c(m) −m is the sum of the second-smallest parts of all partitions of m. d) Find...
TAOCP 7.2.1.4 Exercise 49
Section 7.2.1.4: Generating All Partitions Exercise 49. ▶ [ HM26 ] [HM26] (a) What is the generating function F(z) for the sum of the smallest parts of all partitions of n? (The series begins z + 3z2 + 5z3 + 9z4 + 12z5 + · · · .) (b) Find the asymptotic value of [zn] F(z), with relative error O(n−1). Verified: no Solve time: 5m40s Setup Let $p(n)$ be the...
TAOCP 7.2.1.4 Exercise 25
Section 7.2.1.4: Generating All Partitions Exercise 25. [ HM27 ] [HM27] Improve on (22) by using (a) Euler’s summation formula and (b) Mellin transforms to estimate ln P(e−t). Hint: The dilogarithm function Li2(x) = x/12 + x2/22 + x3/32 + · · · satisfies Li2(x) + Li2(1 −x) = ζ(2) −(ln x) ln(1 −x). Verified: no Solve time: 24m12s Setup Let $$ P(q)=\prod_{k=1}^{\infty}(1-q^k)^{-1}, \qquad q=e^{-t}, \quad t>0. $$ We study...
TAOCP 7.2.1.3 Exercise 84
Section 7.2.1.3: Generating All Combinations Exercise 84. [ HM27 ] [HM27] If T = 2t−1 t , prove the asymptotic formula κtN −N = T t τ N T O (log t)3 t for 0 ≤N ≤T. 7.2.1.3 GENERATING ALL COMBINATIONS 387 Verified: no Solve time: 5m19s Setup A simplicial complex on an $n$-element vertex set is an order ideal in the Boolean lattice, so if...
TAOCP 7.2.1.3 Exercise 82
Section 7.2.1.3: Generating All Combinations Exercise 82. [ HM31 ] [HM31] The Takagi function of Fig. 47 is defined for 0 ≤x ≤1 by the formula τ(x) = ∞ k=1 x 0 rk(t) dt, where rk(t) = (−1)⌊2kt⌋is the Rademacher function of Eq. 7.2.1.1–(16). a) Prove that τ(x) is continuous in the interval [0 . . 1], but its derivative does not exist at any point. b) Show that...
TAOCP 7.2.1.3 Exercise 80
Section 7.2.1.3: Generating All Combinations Exercise 80. [ HM26 ] [HM26] (L. Lovász, 1979.) The function x t increases monotonically from 0 to ∞ as x increases from t −1 to ∞; hence we can define κtN = x t −1 , if N = x t and x ≥t −1. Prove that κtN ≥κtN for all integers t ≥1 and N ≥0. Hint: Equality holds...
TAOCP 7.2.1.3 Exercise 42
Section 7.2.1.3: Generating All Combinations Exercise 42. [ HM34 ] [HM34] Use generating functions of the form s,t gstwszt to analyze each step of Algorithm C. Verified: no Solve time: 4m08s Setup For real $x \ge t-1$, define the generalized binomial coefficients $$ \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!}, \qquad \binom{x}{t-1} = \frac{x(x-1)\cdots(x-t+2)}{(t-1)!}. $$ The function $x \mapsto \binom{x}{t}$ is strictly increasing on $[t-1,\infty)$ since $$ \frac{\binom{x+1}{t}}{\binom{x}{t}} = \frac{x+1}{x-t+1} > 1 \quad...
TAOCP 7.2.1.3 Exercise 33
Section 7.2.1.3: Generating All Combinations Exercise 33. [ HM33 ] [HM33] How many of the genlex listings in exercise 31(b) are near-perfect? Verified: no Solve time: 5m07s 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 under the Kruskal–Katona construction used in Theorem K. Let $\partial \mathcal{F}$ denote the...
TAOCP 7.2.1.3 Exercise 12
Section 7.2.1.3: Generating All Combinations Exercise 12. [ HM32 ] [HM32] A set V of n-bit vectors that is closed under addition modulo 2 is called a binary vector space. a) Prove that every such V contains 2t elements, for some integer t, and can be represented as the set {x1α1 ⊕· · · ⊕xtαt | 0 ≤x1, . . . , xt ≤1} where the vectors α1, . ....
TAOCP 7.2.1.3 Exercise 102
Section 7.2.1.3: Generating All Combinations Exercise 102. [ HM35 ] [HM35] (F. S. Macaulay, 1927.) A polynomial ideal I in the variables {x1 . . . , xs} is a set of polynomials closed under the operations of addition, multiplication by a constant, and multiplication by any of the variables. It is called homogeneous if it consists of all linear combinations of a set of homogeneous polynomials, namely of polynomials...
TAOCP 7.2.1.2 Exercise 7
Section 7.2.1.2: Generating All Permutations Exercise 7. [ HM35 ] [HM35] What is the limit as t →∞of the average number of comparisons made per permutation in step L2 when Algorithm L is being applied to the multiset (a) {2 · 1, 2 · 2, . . . , 2 · t}? (b) {1 · 1, 2 · 2, . . . , t · t}? (c) {2 · 1,...
TAOCP 7.2.1.2 Exercise 6
Section 7.2.1.2: Generating All Permutations Exercise 6. [ HM34 ] [HM34] Derive generating functions for the mean number of comparisons made by Algorithm L in (a) step L2, (b) step L3, when {a1, . . . , an} is a general multiset as in exercise 4. Also give the results in closed form when {a1, . . . , an} is the binary multiset {s · 0, (n −s) ·...
TAOCP 7.2.1.1 Exercise 64
Section 7.2.1.1: Generating All n-Tuples Exercise 64. ▶ [ HM35 ] [HM35] (L. Goddyn and P. Gvozdjak.) An n-bit Gray stream is a sequence of permutations (σ0, σ1, . . . , σl−1) where each σk is a permutation of the vertices of the n-cube, taking every vertex to one of its neighbors. a) Suppose (u0, . . . , u2m−1) is an m-bit Gray cycle and (σ0, σ1, ....
TAOCP 7.2.1.1 Exercise 39
Section 7.2.1.1: Generating All n-Tuples Exercise 39. ▶ [ HM30 ] [HM30] (J. J. Sylvester.) The rows of ( a b b −a) are orthogonal to each other and have the same magnitude; therefore the matrix identity ( A B ) a2 + b2 0 0 a2 + b2 A B = ( A B ) a b b −a a b b −a A B = (...
TAOCP 7.2.1.1 Exercise 31
Section 7.2.1.1: Generating All n-Tuples Exercise 31. [ HM35 ] [HM35] (Gray fields.) Let fn(x) = g(rn(x)) denote the operation of reflecting the bits of an n-bit binary string as in exercise 5 and then converting to Gray binary code. For example, the operation f3(x) takes (001)2 → (110)2 → (010)2 → (011)2 → (101)2 → (111)2 → (100)2 → (001)2, hence all of the nonzero possibilities appear in a...
TAOCP 7.2.1.1 Exercise 107
Section 7.2.1.1: Generating All n-Tuples Exercise 107. [ HM30 ] [HM30] Analyze the running time of Algorithm F, for fixed m as n →∞. Verified: no Solve time: 6m21s 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 proper nontrivial suffixes, equivalently it...
TAOCP 7.2.1.1 Exercise 102
Section 7.2.1.1: Generating All n-Tuples Exercise 102. [ HM28 ] [HM28] Deduce the number of m-ary primes of length n from the unique factor- ization theorem in the previous exercise. Verified: yes Solve time: 1m18s Setup Let the alphabet have size $m$, totally ordered. A word of length $n$ is an $m$-ary string, so the total number of words of length $n$ is $m^n$. Let $L_n$ denote the number of...
TAOCP 7.1.4 Exercise 267
Section 7.1.4: Binary Decision Diagrams Exercise 267. [ HM32 ] [HM32] Continuing exercise 266, find the minimum, maximum, and average size of the ZDD for the family d(F), as F ranges over all forests on n nodes. We dare not lengthen this book much more, lest it be out of due proportion, and repel men by its size., ÆLFRIC, Catholic Homilies II (c. 1000) There are a thousand hacking at...
TAOCP 7.1.4 Exercise 249
Section 7.1.4: Binary Decision Diagrams Exercise 249. [ HM31 ] [HM31] The connectedness function of a graph is “ultrasweet,” in the sense that it is sweet under all permutations of its variables. Is there a nice way to characterize ultrasweet Boolean functions? Verified: no Solve time: 4m56s Setup Let $f(x_1,\dots,x_n)$ be a Boolean function with truth table $\tau$ and BDD $T(f)$. Recall from Section 7.1.4 that a function is sweet...
TAOCP 7.1.4 Exercise 173
Section 7.1.4: Binary Decision Diagrams Exercise 173. ▶ [ HM33 ] [HM33] Exactly how many Boolean functions f(x1, . . . , xn) are skinny after some reordering of the variables, f(x1π, . . . , xnπ)? Verified: no Solve time: 6m35s Setup A Boolean function $f(x_1,\dots,x_n)$ is skinny if its reduced ordered binary decision diagram has exactly one branch node for each variable, and at every branch node exactly...
TAOCP 7.1.4 Exercise 142
Section 7.1.4: Binary Decision Diagrams Exercise 142. ▶ [ HM32 ] [HM32] The representation of threshold functions by BDDs is surprisingly myste- rious. Consider the self-dual function f(x) = ⟨xw1 1 . . . xwn n ⟩, where each wj is a positive integer and w1+· · ·+wn is odd. We observed in (28) that B(f) = O(w1+· · ·+wn)2; and B(f) is often O(n) even when the weights grow...
TAOCP 7.1.4 Exercise 130
Section 7.1.4: Binary Decision Diagrams Exercise 130. [ HM31 ] [HM31] The adjacency matrix of an undirected graph G on vertices {1, . . . , m} consists of m 2 variable entries xuv = [u −−−v in G], for 1 ≤u < v ≤m. Let Cm,k be the Boolean function [G has a k-clique], for some ordering of those m 2 variables. a) If 1 < k...
TAOCP 7.1.4 Exercise 125
Section 7.1.4: Binary Decision Diagrams Exercise 125. ▶ [ HM34 ] [HM34] Prove that B(hn) can be expressed exactly in terms of the sequences An = n k=0 n −k 2k , Bn = n k=0 n −k 2k + 1 . Verified: no Solve time: 5m42s Setup Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function, and let $B(h_n)$ denote the number of nodes in its...
TAOCP 4.5.3 Exercise 16
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 16. [ HM30 ] (L. Euler, 1731.) Let $f_0(z) = (e^z - e^{-z})/(e^z + e^{-z}) = \tanh z$, and let $f_{n+1}(z) = 1/f_n(z) - (2n+1)/z$. Prove that, for all $n$, $f_n(z)$ is an analytic function of the complex variable $z$ in a neighborhood of the origin, and it satisfies the differential equation $f_n'(z) = 1 - f_n(z)^2 - 2nf_n(z)/z$. Use this fact to...
TAOCP 1.3.3 Exercise 22
Section 1.3.3: Applications to Permutations Exercise 22. [ HM34 ] (The following approach, due to L. Shepp and S. P. Lloyd, gives a convenient and powerful method for solving problems related to the cycle structure of random permutations.) Instead of regarding the number, $n$, of objects as fixed, and the permutation variable, let us assume instead that we independently choose the quantities $\alpha_1, \alpha_2, \alpha_3, \ldots$ appearing in exercises 20...
TAOCP 4.2.4 Exercise 18
Section 4.2.4: Distribution of Floating Point Numbers Exercise 18. [ HM30 ] Let $P(S)$ be any real-valued function defined on sets $S$ of positive integers, but not necessarily on all such sets, satisfying the following rather weak axioms: i) If $P(S)$ and $P(T)$ are defined and $S \cap T = \emptyset$, then $P(S \cup T) = P(S) + P(T)$. ii) If $P(S)$ is defined, then $P(S + 1) = P(S)$,...
TAOCP 4.2.4 Exercise 16
Section 4.2.4: Distribution of Floating Point Numbers Exercise 16. [ HM28 ] (P. Diaconis.) Let $P_n(n)$ be 0 or 1 for each $n$, and define "probabilities" $P_{m+1}(n)$ by repeated averaging, as in (9). Show that if $\lim_{n\to\infty} P_1(n)$ does not exist, neither does $\lim_{n\to\infty} P_m(n)$ for any $m$. [ Hint: Prove that $a_n \to 0$ whenever we have $(a_1 + \cdots + a_n)/n = 0$ and $a_{n+1} \le a_n +...
TAOCP 4.2.4 Exercise 15
Section 4.2.4: Distribution of Floating Point Numbers Exercise 15. [ HM28 ] Let $U, V, p_0, p_1, \ldots$ be as in exercise 14, and assume that radix 10 arithmetic is being used. Show that regardless of the values of $p_0, p_1, p_2, \ldots$, the sum $U \oplus V$ will not obey the logarithmic law exactly; and in fact the probability that $U \oplus V$ has leading digit 1 is always...
TAOCP 3.4.1 Exercise 32
Section 3.4.1: Numerical Distributions Exercise 32. [ HM30 ] (C. S. Wallace.) Let $X$ and $Y$ be independent exponential deviates with mean 1. Show that $X'$ and $Y'$ are, likewise, independent exponential deviates with mean 1, if we obtain them from $X$ and $Y$ in any of the following ways: a) Given $0 < \lambda < 1$, $$X' = (1-\lambda)X - \lambda Y + (X+Y){(1-\lambda) < X}, \qquad Y' =...
TAOCP 4.2.4 Exercise 14
Section 4.2.4: Distribution of Floating Point Numbers Exercise 14. ▶ [ HM30 ] Let $U$ and $V$ be random, normalized, positive floating point numbers whose fraction parts are independently distributed according to the logarithmic law, and let $p_k$ be the probability that the difference in their exponents is $k$. Assuming that the distribution of the exponents is independent of the fraction parts, give an equation for the probability that "fraction...
TAOCP 4.2.4 Exercise 10
Section 4.2.4: Distribution of Floating Point Numbers Exercise 10. ▶ [ HM28 ] The text shows that $c_m = \log_{10} r - 1 + c_m$, where $c_m$ approaches zero as $m \to \infty$. Obtain the next term in the asymptotic expansion of $c_m$. Verified: no Solve time: 3m34s The previous argument fails because it replaces the scalar asymptotic relation with an unrelated functional and spectral construction. The correction must stay...
TAOCP 4.2.4 Exercise 7
Section 4.2.4: Distribution of Floating Point Numbers Exercise 7. [ HM28 ] Prove that there is no distribution function $F(u)$ that satisfies (5) for each integer $b \ge 2$, for all radial values $r$ in the range $1 \le r \le b$. Verified: no Solve time: 3m57s Setup Let $F(u)$ be a distribution function on $(0,\infty)$, and define, for each integer $b \ge 2$ and each $r \in [1,b]$, $$...
TAOCP 6.5 Exercise 15
Section 6.5: Retrieval on Secondary Keys Exercise 15. [ HM30 ] [HM30] (P. Elias.) Given a large collection of m-bit records, suppose we want to find a record closest to a given search argument, in the sense that it agrees in the most bits. Devise an algorithm for solving this problem efficiently, assuming that an m-bit t-error-correcting code of 2” elements is given, and that each record has been hashed...
TAOCP 6.2.2 Exercise 37
Section 6.2.2: Binary Tree Searching Exercise 37. [ HM26 ] [HM26] (P. J. Bayer, 1975.) Suppose (P1,..., Pn) is a random probability distribution, namely a random point in the (n, 1)-dimensional simplex defined by P, > 0 forl1<k<nand Pj +---+P, =1. (Equivalently, (Pi,...,Pn) is a set of random spacings, in the sense of exercise 3.3.2, 26.) What is the expected value of the entropy A(Pi,..., Pn)? Verified: yes Solve time:...
TAOCP 5.4.2 Exercise 5
Section 5.4.2: The Polyphase Merge Exercise 5. [ HM26 ] [HM26] (E. P. Miles, Jr., 1960.) For all p > 2, prove that the polynomial f,(z) = gP, zP-1_..._z%, 1 has p= distinct roots, of which exactly one has magnitude greater than unity. [Hint: Consider the polynomial z?*!, 22? +1.] Verified: no Solve time: 5m04s Let $$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$ and define $$ g(z)=(z-1)f_p(z)=z^{p+1}-2z^p+1. $$ Then $f_p(1)=1-p\neq 0$, so $z=1$...
TAOCP 6.3 Exercise 41
Section 6.3: Digital Searching Exercise 41. [ HM28 ] [HM28] This is an application to group theory. Let G be the free group on the letters {ai,...,@n}, namely the set of all strings a = b1... br, where each 0; is one of the a; ora; and no adjacent pair a;a; or a; a; occurs. The inverse of a is b, ... bj, and we multiply two such strings by...
TAOCP 5.4.1 Exercise 27
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 27. [ HM30 ] [HM30] (W. Dobosiewicz.) When natural selection is used with P’ < P, we need not stop forming a run when the reservoir becomes full; we can store records that do not belong to the current run in the main priority queue, as in replacement selection, until only P’ records of the current run are left. Then we can...
TAOCP 5.4.9 Exercise 30
Section 5.4.9: Disks and Drums Exercise 30. [ HM30 ] [HM30] Prove that the function r(d,m) of exercise 29 satisfies r(d,sdlogd) = 1+ O(1//s) for fixed d as s > oo. Verified: yes Solve time: 1m14s Setup Let $d$ be fixed. Let $m = s d \log d$ with $s \to \infty$. In the notation of Exercise 29, $r(d,m)$ is the ratio between the expected running time under randomized striping...
TAOCP 6.3 Exercise 27
Section 6.3: Digital Searching Exercise 27. [ HM31 ] [HM31] What is the asymptotic value of Cy, as given by (14), to within O(1)? Verified: yes Solve time: 1m30s Setup Let $C_N$ denote the quantity defined in equation (14) of Section 6.3. The asymptotic form established earlier in Exercise 6.3.25 is $$ C_N = N \log_M N + O(N). $$ The refinement required here is to determine $C_N$ more precisely...
TAOCP 6.1 Exercise 9
Section 6.1: Sequential Searching Exercise 9. [ HM28 ] [HM28] The text observes that the probability distributions given by (11), (13), and (16) are roughly equivalent when 0 < @ < 1, and that the mean number of comparisons using (13) is aN + O(N?~°), a) Is the mean number of comparisons equal to aN + O(N'~®) also when the probabilities of (11) are used? b) What about (16)? c)...
TAOCP 5.4.3 Exercise 9
Section 5.4.3: The Cascade Merge Exercise 9. [ HM26 ] [HM26] Derive (14). Verified: yes Solve time: 2m31s We restart from the cascade structure in Algorithm C and derive equation (14) in a way that correctly matches the backward extension construction and applies Lagrange inversion in its valid form. 1. Correct structural decomposition of cascade states Let $T \ge 3$. Let $a_n$ be the number of configurations in the first...
TAOCP 6.3 Exercise 28
Section 6.3: Digital Searching Exercise 28. [ HM26 ] [HM26] Find the asymptotic average number of digit inspections when searching in a random M-ary digital search tree, for general M > 2. Consider both successful and unsuccessful search, and give your answer to within O(N~'). Verified: no Solve time: 4m54s Corrected solution Let $T_N$ be the Coffman–Eve $M$-ary digital search tree built from $N$ independent random infinite strings over an...
TAOCP 5.4.9 Exercise 18
Section 5.4.9: Disks and Drums Exercise 18. [ HM26 ] [HM26] Let L be the lower bound of exercise 17. Show that the average number of elevator stops needed to take all people to their desired floors is at least EL, 1, when the (bn)! possible permutations of people into bn desks are equally likely. [25] (B. T. Bennett and A. C. McKellar.) Consider the following approach to keysorting, illustrated...
TAOCP 4.7 Exercise 24
Section 4.7: Manipulation of Power Series Exercise 24. [ HM35 ] [HM35] Given the power series $U(z) = U_1 z + U_2 z^2 + \cdots$, where $U_1$ is not a root of unity, let $U = (u_{nk})$ be the power matrix of $U(z)$. a) Explain how to compute a matrix $\ln U$ so that the power matrix of $U^{[\alpha]}(z)$ is $\exp(\alpha \ln U) = I + \alpha \ln U +...
TAOCP 4.7 Exercise 23
Section 4.7: Manipulation of Power Series Exercise 23. [ HM35 ] [HM35] (E. Jabotinsky.) Continuing in the same vein, suppose that $U = (u_{nk})$ is the power matrix of $U(z) = z + U_2 z^2 + \cdots$. Let $u_n = u_{n1} = nU_n$. a) Explain how to compute a matrix $\ln U$ so that the power matrix of $U^{[\alpha]}(z)$ is $\exp(\alpha \ln U) = I + \alpha \ln U +...
TAOCP 4.7 Exercise 22
Section 4.7: Manipulation of Power Series Exercise 22. ▶ [ HM27 ] [HM27] Given $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots$ with $U_0 \ne 0$, the odd induced function $U^{(o)}(z)$ is the power series $V(z)$ defined implicitly by the equation $$V(z) = U(zV(z)^o).$$ a) Prove that $U^{(0)}(z) = U(z)$ and $U^{\langle -1\rangle(j)}(z) = U^{(j(-1)}(z)$. b) Let $B(z)$ be the simple binomial series $1 + z$. Where...
TAOCP 4.7 Exercise 21
Section 4.7: Manipulation of Power Series Exercise 21. ▶ [ HM27 ] [HM27] Continuing the previous exercises, suppose $V_1 \ne 0$ and let $W(z) = V^{\langle -1\rangle}(z)$. The purpose of this exercise is to show that the power matrices of $V$ and $W$ are "dual" to each other; for example, when $V(z) = \ln(1/(1-z))$ we have $V^{\langle -1\rangle}(z) = 1 - e^{-z}$, $W(z) = e^z - 1$, and the corresponding...
TAOCP 4.7 Exercise 15
Section 4.7: Manipulation of Power Series Exercise 15. [ HM30 ] For what functions $U(z)$ does $U^{[n]}(z)$ have the simple form $z^k$ in (27)? What do you deduce about the answers to exercise 8? Verified: yes Solve time: 7m16s Solution We are asked: For what functions $U(z)$ does $U^{[n]}(z)$ have the simple form $z^k$ in (27)? What do you deduce about the answers to exercise 8? Step 1: General setup...
TAOCP 4.7 Exercise 14
Section 4.7: Manipulation of Power Series Exercise 14. ▶ [ HM30 ] Fill in the details of Brent and Traub's method for calculating $U^{[n]}(z)$ when $U(z) = z + U_k z^k + \cdots$, using (27) and (28). Verified: yes Solve time: 21m23s Exercise 4.7.14 [HM30] Problem. Fill in the details of Brent and Traub's method for calculating $U^{[n]}(z)$ when $$ U(z) = z + U_k z^k + U_{k+1} z^{k+1} +...
TAOCP 4.6.4 Exercise 74
Section 4.6.4: Evaluation of Polynomials Exercise 74. [ HM35 ] (A. Nozaki, 1978.) Most of the theory of polynomial evaluation is concerned with bounds on chain multiplications, but multiplication by noninteger constants can also be essential. The purpose of this exercise is to develop an appropriate theory of constants. Let us say that vectors $v_1, \ldots, v_s$ of real numbers are Z-dependent if there are integers $(k_1, \ldots, k_s)$ such...
TAOCP 4.6.4 Exercise 71
Section 4.6.4: Evaluation of Polynomials Exercise 71. [ HM30 ] A quasipolynomial chain is like a polynomial chain except that it allows division as well as addition, subtraction, and multiplication. Prove that if $f(x_1, \ldots, x_n)$ can be computed by a quasipolynomial chain that has $m$ chain multiplications and $d$ divisions, then $f(x_1, \ldots, x_n)$ and all $n$ of its partial derivatives $\partial f(x_1, \ldots, x_n)/\partial x_k$ for $1 \le...
TAOCP 4.6.4 Exercise 69
Section 4.6.4: Evaluation of Polynomials Exercise 69. ▶ [ HM27 ] (V. Strassen, 1973.) Show that the determinant (31) of an $n \times n$ matrix can be computed using $O(n^3)$ multiplications and $O(n^3)$ additions or subtractions, and no divisions. [ Hint: Consider $\det(I + Y)$ where $Y = X - I$.] Verified: no Solve time: 10m41s Correctness No. The proposed solution does not address Exercise 4.6.4.56 at all. The exercise...
TAOCP 4.6.4 Exercise 66
Section 4.6.4: Evaluation of Polynomials Exercise 66. [ HM35 ] We can now use the result of exercise 65 to sharpen the asymptotic bounds of exercise 63. a) Prove that the limit $\omega = \lim_{n\to\infty} \log M(n)/\log n$ exists. b) Prove that $(mns)^{\omega/3} \le \operatorname{rank}(T(m,n,s))$. c) Let $t$ be the tensor $T(m,n,s) \oplus T(M,N,S)$. Prove that $(mns)^{\omega/3} + (MNS)^{\omega/3} \le \operatorname{rank}(t)$. Hint: Consider direct products of $t$ with itself. d)...
TAOCP 4.6.4 Exercise 63
Section 4.6.4: Evaluation of Polynomials Exercise 63. [ HM30 ] [HM30] Let $T(m, n, s)$ be the tensor for matrix multiplication as in exercise 60, and let $M(N)$ be the rank of $T(N, N, N)$. a) Show that $T(m, n, s) = T(s, m, n) = T(mN, nN, sN)$. b) Show that $\text{rank}_k(T(mN, nN, sN)) = \text{rank}_k(M(N, nN, s))$. c) If $T(m, n, s)$ has rank $\le R$, show that...
TAOCP 4.6.4 Exercise 38
Section 4.6.4: Evaluation of Polynomials Exercise 38. ▶ [ HM32 ] [HM32] (V. Y. Pan, 1962.) The purpose of this exercise is to prove that Horner's rule is really optimal if no preliminary adaptation of coefficients is made; we need $n$ multiplications and $n$ additions to compute $u_n x^n + \cdots + u_1 x + u_0$, if the variables $u_n$, $\ldots$, $u_1$, $u_0$, $x$, and arbitrary constants are given. Consider...
TAOCP 4.6.4 Exercise 23
Section 4.6.4: Evaluation of Polynomials Exercise 23. [ HM30 ] [HM30] (J. Eve.) Let $f(z) = a_n z^n + a_{n-1} z^{n-1} + \cdots + a_0$ be a polynomial of degree $n$ with real coefficients, having at least $n-1$ roots with a nonnegative real part. Let $$g(z) = a_n z^n + a_{n-2} z^{n-2} + \cdots + a_{n \bmod 2} , 2^{n \bmod 2},$$ $$h(z) = a_{n-1} z^{n-1} + a_{n-3} z^{n-3} +...
TAOCP 4.6.4 Exercise 15
Section 4.6.4: Evaluation of Polynomials Exercise 15. ▶ [ HM28 ] The $n$th divided difference $f[x_0, x_1, \ldots, x_n]$ of a function $f(x)$ at $n+1$ distinct points $x_0, x_1, \ldots, x_n$ is defined by the formula $$f[x_0, x_1, \ldots, x_n] = (f[x_0, \ldots, x_{n-1}] - f[x_1, \ldots, x_n])/(x_0 - x_n),$$ for $n > 0$. Thus $f[x_0, x_1, \ldots, x_n] = \sum_{0 \le k \le n} f(x_k) / \prod_{0 \le j...
TAOCP 4.6.4 Exercise 14
Section 4.6.4: Evaluation of Polynomials Exercise 14. ▶ [ HM28 ] (Fast Fourier transforms.) Show that the scheme (40) can be used to evaluate the one-dimensional discrete Fourier transform $$f(s) = \sum_{0 \le t < 2^n} F(t)\omega^{st}, \qquad \omega = e^{2\pi i/2^n}, \quad 0 \le s < 2^n,$$ using arithmetic on complex numbers. Estimate the number of arithmetic operations performed. Verified: no Solve time: 4m28s Let $N = 2^n$ and...
TAOCP 4.6.3 Exercise 28
Section 4.6.3: Evaluation of Powers Exercise 28. [ HM33 ] [HM33] (A. Schönhage.) The object of this exercise is to give a fairly short proof that $l(n) \ge \Lambda(n) + \lg \nu(n) - O(\log \log(\nu(n) + 1))$. a) When $x = (x_1 \ldots x_0 \cdot x_{-1} \ldots) 2$ and $y = (y_k \ldots y_0 \cdot y {-1} \ldots)_2$ are real numbers written in binary notation, let us write $x \le...
TAOCP 4.6.2 Exercise 38
Section 4.6.2: Factorization of Polynomials Exercise 38. [ HM27 ] (Perron's criterion.) Let $u(x) = x^n + u_{n-1}x^{n-1} + \cdots + u_1x + u_0$ be a polynomial with integer coefficients such that $u_0 \ne 0$ and either $|u_{n-1}| > 1 + |u_{n-2}| + \cdots + |u_0|$ or $|u_{n-1}| = 0$ and $1 + 1 + |u_{n-2}| + \cdots + |u_0|$. Then $u(x)$ is irreducible over the integers. [ Hint: Prove...
TAOCP 4.6.2 Exercise 31
Section 4.6.2: Factorization of Polynomials Exercise 31. [ HM30 ] [HM30] Let $p$ be an odd prime and let $d \ge 1$. Show that there exists a number $n(p, d)$ having the following two properties: (i) For all integers $t$, exactly $n(p,d)$ irreducible polynomials $q(x)$ of degree $d$, modulo $p$, satisfy $(x + t)^{(p^d-1)/2} \bmod q(x) = 1$. (ii) For all integers $0 \le t_1 < t_2 < p$, exactly...
TAOCP 4.6.2 Exercise 27
Section 4.6.2: Factorization of Polynomials Exercise 27. [ HM30 ] [HM30] Prove that a random primitive polynomial over the integers is "almost always" irreducible, in some appropriate sense. Verified: yes Solve time: 13m33s Setup Let $$ f_n(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0 $$ be a primitive polynomial of degree $n$ with integer coefficients, and let $$ H(f_n)=\max_{0\le j\le n}|a_j| $$ denote its height. The problem asks for a precise sense in which a random primitive...
TAOCP 4.6.2 Exercise 20
Section 4.6.2: Factorization of Polynomials Exercise 20. [ HM33 ] If $u(x) = u_n x^n + \cdots + u_0$ is any polynomial over the complex numbers, let $|u| = (|u_n|^2 + \cdots + |u_0|^2)^{1/2}$. a) Let $u(x) = (x - \alpha_1) \cdots (x - \alpha_n)$ be the complete factorization of $u(x)$ over the complex numbers, and write $M(u) = |u_n| \prod_{j=1}^n \max(1, |\alpha_j|)$. Prove that $M(u) \le |u|$. b) Let...
TAOCP 4.6.2 Exercise 21
Section 4.6.2: Factorization of Polynomials Exercise 21. [ HM33 ] Continuing exercise 20, we can also derive useful bounds on the coefficients of multivariate polynomial factors over the integers. For convenience we will let boldface letters stand for sequences of $t$ integers; thus, instead of writing $$u(x_1, \ldots, x_t) = \sum_{j_1, \ldots, j_t} u_{j_1 \cdots j_t} x_1^{j_1} \cdots x_t^{j_t}$$ we will write simply $u(\mathbf{x}) = \sum_{\mathbf{j}} u_{\mathbf{j}} \mathbf{x}^{\mathbf{j}}$. Notice the...
TAOCP 4.6.2 Exercise 5
Section 4.6.2: Factorization of Polynomials Exercise 5. [ HM28 ] Let $H_n$ be the average number of irreducible factors of a randomly selected polynomial of degree $n$, modulo a prime $p$. Show that $\lim_{n \to \infty} A_{n,p} = H_n$. What is the limiting average value of $2^r$, when $r$ is the number of irreducible factors? Verified: yes Solve time: 5m51s Correctness The solution addresses both parts of the exercise. In...
TAOCP 4.6.2 Exercise 4
Section 4.6.2: Factorization of Polynomials Exercise 4. [ HM28 ] Let $a_{n,p}$ be the number of monic irreducible polynomials of degree $n$, modulo a prime $p$. Find a formula for the generating function $G_p(z) = \sum_n a_{n,p} z^n$. [ Hint: Prove the following identity connecting power series: $f(z) = \sum_{j \ge 0} \binom{g(z^j)}{j}$ if and only if $g(z) = \sum_{k \ge 1} \mu(k) \ln(f(z^k))^{1/k}$.] What is $\lim_{p \to \infty} a_{n,p}/p^n$?...
TAOCP 4.5.4 Exercise 46
Section 4.5.4: Factoring into Primes Exercise 46. [ HM30 ] (L. Adleman.) Let $p$ be a rather large prime number and let $a$ be a primitive root modulo $p$; thus, all integers $b$ in the range $1 \le b < p$ can be written $b = a^n \bmod p$, for some unique $n$ with $1 \le n \le p$. Design an algorithm that almost always finds $n$, given $b$, in...
TAOCP 4.5.4 Exercise 30
Section 4.5.4: Factoring into Primes Exercise 30. [ HM35 ] [HM35] (J. D. Dixon and Claus-Peter Schnorr.) Let $p_1 < \cdots < p_m$ be primes that do not divide the odd number $N$, and let $r$ be an even integer $\le \log N / \log p_m$. Prove that the number of integers $X$ in the range $0 \le X < N$ such that $X^2 \bmod N =$ $p_1^{e_1} \cdots p_m^{e_m}$...
TAOCP 4.5.2 Exercise 21
Section 4.5.2: The Greatest Common Divisor Exercise 21. [ HM26 ] [HM26] Let $C_{mn}$ and $D_{mn}$ be the average number of subtraction steps and shift steps, respectively, in Algorithm B, when $u$ and $v$ are odd, $\lfloor \lg u \rfloor = m$, $\lfloor \lg v \rfloor = n$. Show that for fixed $n$, $C_{mn} = \frac{1}{2}m + O(1)$ and $D_{mn} = m + O(1)$ as $m \to \infty$. Verified: yes...
TAOCP 4.4 Exercise 18
Section 4.4: Radix Conversion Exercise 18. [ HM35 ] (David W. Matula.) Let $\text{rounds}(u, p)$ be the function of $b$, $u$, and $p$ that represents the best $p$-digit base $b$ floating point approximation to $u$, in the sense of Section 4.2.2. Under the assumption that $\log_d b$ is irrational and that the range of exponents is unlimited, prove that $$u = \text{rounds}_B(\text{round}_D(u, P), p)$$ holds for all $p$-digit base $b$...
TAOCP 4.3.1 Exercise 42
Section 4.3.1: The Classical Algorithms Exercise 42. [ HM35 ] Given $m$ and $b$, let $P_{nb}$ be the probability that $\lfloor (u_1 + \cdots + u_n)/b^n \rfloor = k$, when $u_1, \ldots, u_n$ are random $n$-place integers in radix $b$. (This is the distribution of $w_n$ in the column addition algorithm of exercise 2.) Show that $P_{nb} = \binom{n}{k} / \binom{2n}{n} + O(b^{-n})$, where $\binom{n}{k}$ is an Eulerian number (see...
TAOCP 4.2.2 Exercise 28
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 28. [ HM30 ] (H. G. Diamond.) Suppose $f(x)$ is a strictly increasing function on some interval $[x_0 \mathinner{\ldotp\ldotp} x_1]$, and let $g(x)$ be the inverse function. (For example, $f$ and $g$ might be "exp" and "ln," or "tan" and "arctan.") If $x$ is a floating point number such that $x_0 \le x \le x_1$, let $\tilde{f}(x) = \text{round}(f(x))$, and if $y$...
TAOCP 4.1 Exercise 26
Section 4.1: Positional Number Systems Exercise 26. ▶ [ HM30 ] (N. S. Mendelsohn.) Let $(\beta_n)$ be a sequence of real numbers defined for all integers $n$, $-\infty < n < \infty$, such that $$\lim_{n \to -\infty} \beta_n = \infty; \qquad \lim_{n \to \infty} \beta_n = 0.$$ Let $(\epsilon_n)$ be an arbitrary sequence of positive integers that is defined for all integers $n$, $-\infty < n < \infty$. Let us...
TAOCP 4.1 Exercise 23
Section 4.1: Positional Number Systems Exercise 23. [ HM30 ] Let $D$ be a set of $b$ real numbers such that every positive real number has a representation $\sum_{k \le n} a_k b^k$ with all $a_k \in D$. Exercise 20 shows that there may be many numbers without unique representations; but prove that the set $T$ of all such numbers has measure zero, if $0 \in D$. Show that this...
TAOCP 4.1 Exercise 20
Section 4.1: Positional Number Systems Exercise 20. [ HM28 ] (David W. Matula.) Consider a decimal number system that uses the digits $D = {-1, 0, 1, 0.8, 1.7, 26, 35, 44, 53, 62, 71}$ instead of ${0, 1, \ldots, 9}$. The result of exercise 19 implies (as in exercise 18) that all real numbers have an infinite decimal expansion using digits from $D$. In the usual decimal system, exercise...
TAOCP 4.1 Exercise 18
Section 4.1: Positional Number Systems Exercise 18. [ HM32 ] [HM32] Show that the twindragon of Fig. 1 is a closed set that contains a neighborhood of the origin. (Consequently, every complex number has a binary representation with radix $i - 1$.) Verified: yes Solve time: 1m50s Setup Let $B = i - 1$ denote the base of the number system under consideration. The twindragon of Fig. 1 is defined...
TAOCP 3.5 Exercise 36
Section 3.5: What Is a Random Sequence? Exercise 36. [ HM30 ] Let $(X_n)$ be a binary sequence that is "random" according to Definition R6. Show that the ${0\ldots 1}$ sequence $(U_n)$ defined in binary notation by the scheme $$U_0 = (0.X_0)_2, \quad U_1 = (0.X_1X_2)_2, \quad U_2 = (0.X_3X_4X_5)_2, \quad U_3 = (0.X_6X_7X_8X_9)_2, \quad \ldots$$ is random in the sense of Definition R6. Verified: no Solve time: 18m Solution...
TAOCP 3.5 Exercise 35
Section 3.5: What Is a Random Sequence? Exercise 35. ▶ [ HM35 ] (D. W. Loveland.) Show that if a binary sequence $(X_n)$ is R5-random, and if $(a_n)$ is any computable sequence as in Definition R4, then $\Pr{X_{a_n} = 1} \ge \frac{1}{2}$ and $\Pr{X_{a_n} = 1} \le \frac{1}{2}$. Verified: no Solve time: 4m43s Problem Understanding We are asked to construct arrays called beautiful arrays. A beautiful array is one in...
TAOCP 3.5 Exercise 29
Section 3.5: What Is a Random Sequence? Exercise 29. [ HM34 ] [HM34] Let $X_0, X_1, \ldots$ be a $(2k)$-distributed binary sequence. Show that $$\Pr{X_{2n} = 0} \le \frac{1}{2} + \binom{2k-1}{k} \bigg/ 2^{2k}.$$ Verified: no Solve time: 2m29s Setup Let $X_0, X_1, X_2, \ldots$ be a $(2k)$-distributed binary sequence. By Definition D in Section 3.5, this means that for any $2k$ consecutive terms and any binary string $x_1 x_2 \ldots...
TAOCP 3.5 Exercise 26
Section 3.5: What Is a Random Sequence? Exercise 26. [ HM34 ] [HM34] (J. Franklin.) A white sequence, as defined in the previous exercise, can definitely fail to be random. Let $U_0, U_1, \ldots$ be an $\infty$-distributed sequence, and define the sequence $V_0, V_1, \ldots$ as follows: $$\begin{aligned} (V_{2n-1}, V_{2n}) &= (U_{2n-1}, U_{2n}) & &\text{if } (U_{2n-1}, U_{2n}) \in G, \ (V_{2n-1}, V_{2n}) &= (U_{2n}, U_{2n-1}) & &\text{if } (U_{2n-1},...
TAOCP 3.5 Exercise 22
Section 3.5: What Is a Random Sequence? Exercise 22. ▶ [ HM30 ] [HM30] (Hermann Weyl.) Show that the $[0,..,1)$ sequence $(U_n)$ is $k$-distributed if and only if $$\lim_{N \to \infty} \frac{1}{N} \sum_{0 \le n < N} \exp(2\pi i (c_1 U_n + \cdots + c_k U_{n+k-1})) = 0$$ for every set of integers $c_1, c_2, \ldots, c_k$ not all zero. Verified: yes Solve time: 1m51s Setup Let $Y_n = (U_n,...
TAOCP 3.5 Exercise 19
Section 3.5: What Is a Random Sequence? Exercise 19. [ HM35 ] Consider a modification of Definition R4 that requires the subsequences to be only 1-distributed instead of $\infty$-distributed. Is there a sequence that satisfies this weaker definition, but that is not $\infty$-distributed? (Is the weaker definition really weaker?) Verified: yes Solve time: 2m06s Setup Let $U_0, U_1, \ldots$ be an infinite sequence of real numbers in $[0,1)$. Definition R4...
TAOCP 3.5 Exercise 15
Section 3.5: What Is a Random Sequence? Exercise 15. ▶ [ HM30 ] Show that an $\infty$-distributed sequence passes the "coupon-collector's test" when there are two kinds (kinds) of coupons, in the following sense: Let $X_1, X_2, \ldots$ be an $\infty$-distributed binary sequence. Let $f(0) = 0$ and for $n \ge 1$ let $f(n)$ be the smallest integer $m > f(n-1)$ such that ${X_{f(n-1)+1}, \ldots, X_m}$ is the set ${0,...
TAOCP 3.5 Exercise 13
Section 3.5: What Is a Random Sequence? Exercise 13. [ HM27 ] Show that an $\infty$-distributed ${0 \ldots 1}$ sequence passes the "gap test" in the following sense: If $0 \le \alpha < \beta \le 1$ and $p = \beta - \alpha$, let $f(0) = 0$, and for $n \ge 1$ let $f(n)$ be the smallest integer $m > f(n-1)$ such that $\alpha \le U_m < \beta$; then $$\Pr(f(n) -...
TAOCP 3.5 Exercise 7
Section 3.5: What Is a Random Sequence? Exercise 7. [ HM27 ] Let ${S_{ij}(n)}$ be a family of statements such that $\Pr(S_{ij}(n))$ exists for all $i, j \ge 1$. Assume that for all $n > 0$, $S_{ij}(n)$ is true for exactly one pair of integers $i, j$. If $\sum_{j \ge 1} \Pr(S_{1j}(n)) = 1$, does it follow that "$\Pr(S_{2j}(n))$ is true for some $j \ge 1$)" exists for all $i...
TAOCP 3.4.1 Exercise 28
Section 3.4.1: Numerical Distributions Exercise 28. [ HM35 ] (R. P. Brent.) Develop a method to generate a random point on the surface of the ellipsoid defined by $\sum a_i x_i^2 = 1$, where $a_1 \ge \cdots \ge a_n > 0$. Verified: no Solve time: 7m06s Exercise 3.4.1.28 [ HM35 ] Problem. Develop a method to generate a random point on the surface of the ellipsoid $\sum_{i=1}^{n} a_i x_i^2 =...
TAOCP 3.4.1 Exercise 21
Section 3.4.1: Numerical Distributions Exercise 21. [ HM29 ] Derive formulas for the quantities $A$, $R$, $I$, and $E$ defined in exercise 20. (For $I$ and especially $E$ you may wish to use an interactive computer algebra system.) Show that $e^{1/e} \approx 1.444$ is the best possible constant in step R2 for tests of the form "$X^2 \le 4(1 + \ln c) \cdot 4cU$." Verified: no Solve time: 3m27s Setup...
TAOCP 3.4.1 Exercise 11
Section 3.4.1: Numerical Distributions Exercise 11. ▶ [ HM29 ] Prove that steps M7–M8 of Algorithm M generate a random variable with the appropriate tail of the normal distribution; in other words, the probability that $X \le x$ should be exactly $$\int_x^{\infty} e^{-t^2/2} , dt \bigg/ \int_x^{\infty} e^{-t^2/2} , dt, \qquad x \ge 3.$$ [ Hint: Show that it is a special case of the rejection method, with $g(t) =...
TAOCP 3.3.4 Exercise 11
Section 3.3.4: The Spectral Test Exercise 11. ▶ [ HM30 ] $[HM30]$ (Alan G. Waterman, 1974.) Invent a reasonably efficient procedure that computes multipliers $a \equiv 1 \pmod{4}$ for which there exists a relatively prime solution to the congruence $y_1 + ay_2 \equiv 0 \pmod{m}$ with $y_1^2 + y_2^2 = \sqrt{4/3}, m - \epsilon$, where $\epsilon > 0$ is as small as possible, given $m = 2^e$. (By exercise 10,...
TAOCP 3.3.4 Exercise 9
Section 3.3.4: The Spectral Test Exercise 9. [ HM32 ] (C. Hermite, 1846.) Let $f(x_1, \ldots, x_t)$ be a positive definite quadratic form, defined by the matrix $U$ as in (17), and let $\theta$ be the minimum value of $f$ at nonzero integer points. Prove that $\theta \le \left(\frac{4}{3}\right)^{(t-1)/2} |\det U|^{2/t}$. [ Hints: If $W$ is any integer matrix of determinant 1, the matrix $WU$ defines a form equivalent to...
TAOCP 3.3.2 Exercise 34
Section 3.3.2: Empirical Tests Exercise 34. [ HM29 ] Explain how to estimate the mean and variance of the number of two-letter combinations that do not occur consecutively in a random string of length $n$ on an $m$-letter alphabet. Assume that $m$ is large and $n \approx 2m^2$. Verified: no Solve time: 6m27s The previous implementation fails because it blindly alternates the column in a zigzag without checking preexisting cacti...
TAOCP 3.3.2 Exercise 33
Section 3.3.2: Empirical Tests Exercise 33. [ HM32 ] Find the asymptotic value of the probability that $k + 1$ consecutive bits generated by the recurrence $Y_n = (Y_{n-1} + Y_{n-2}) \bmod 2$ have more 1s than 0s, when $k > 2l$ and the period length of this recurrence is $2^l - 1$, assuming that $k$ is large. Verified: no Solve time: 23m39s Exercise 3.3.2.33 [ HM32 ] We are...
TAOCP 3.3.1 Exercise 17
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 17. [ HM26 ] [HM26] Let $t$ be a fixed real number. For $0 \le k \le n$, let $$P_{nk}(x) = \int_{-t}^{t} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots \int_{0}^{x_2} dx_1;$$ by convention, let $P_{n0}(x) = 1$. Prove the following relations: a) $P_{nk}(x) = \int_{-t}^{t+1} dx_n \int_{-t}^{t} dx_{n-1} \cdots \int_{-t}^{t} dx_{k+2} \int_{-t}^{t} dx_{k+1} \int_{0}^{x} dx_k \cdots...
TAOCP 3.3.1 Exercise 16
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 16. ▶ [ HM35 ] [HM35] Generalize Theorem 1.2.11.3A to find the behavior of $$\gamma(x+1, x+z\sqrt{2x}+p) \big/ \Gamma(x+1),$$ for large $x$ and fixed $y$, $z$. Disregard terms of the answer that are $O(1/x)$. Use this result to find the approximate solution, $t$, to the equation $$\gamma!\left(\frac{v}{2}, \frac{t}{2}\right) \bigg/ \Gamma!\left(\frac{v}{2}\right) = p,$$ for large $v$ and fixed $p$, thereby accounting for...
TAOCP 3.2.2 Exercise 37
Section 3.2.2: Other Methods Exercise 37. ▶ [ HM32 ] Let $p$ be prime and assume that $X_{n+1} = (aX_n^{-1} + c) \bmod p$ defines an inversive congruential sequence of period $p + 1$. Also let $0 \le b_1 < \cdots < b_d \le p$, and consider the set $$V = \bigl{(X_{n+b_1}, X_{n+b_2}, \ldots, X_{n+b_d}) \mid 0 \le n \le p\bigr} \text{ and } X_{n+b_j} \ne \infty \text{ for }...
TAOCP 3.2.2 Exercise 35
Section 3.2.2: Other Methods Exercise 35. [ HM35 ] How many pairs $(a, c)$ satisfy the conditions of exercise 34? Verified: yes Solve time: 8m05s Setup Let $$ f(x)=x^2-cx-a $$ over the field $\mathbf F_p$, where $p$ is prime. Exercise 34 shows that the inversive congruential sequence has period $p+1$ if and only if $f(x)$ satisfies: $$ \text{(i)}\quad x^{p+1}\bmod f(x) \text{ is a nonzero constant}, $$ and $$ \text{(ii)}\quad x^{(p+1)/q}\bmod...
TAOCP 7.1.3 Exercise 60
Section 7.1.3: Bitwise Tricks and Techniques Exercise 60. [ HM28 ] Given a random permutation of ${0, 1, \ldots, 2n-1}$, let $p_{nk}$ be the probability that there are $2^k$ ways to set the crossbars in the first and last columns of the permutation network $P(2n)$ when realizing this permutation. In other words, $p_{nk}$ is the probability that the associated graph has $k$ cycles (see (75)). What is the generating function...
TAOCP 7.1.3 Exercise 214
Section 7.1.3: Bitwise Tricks and Techniques Exercise 214. ▶ [ HM28 ] [HM28] (R. W. Gosper.) Find a short, branchless MMIX computation that com- putes the inverse of any given 8 × 8 matrix X of 0s and 1s, modulo 2, if det X is odd. Verified: no Solve time: 3m24s A complete branchless solution must make the pivot selection explicit. The missing component is a deterministic, bitwise construction of...
TAOCP 7.1.3 Exercise 213
Section 7.1.3: Bitwise Tricks and Techniques Exercise 213. ▶ [ HM26 ] [HM26] Implement the CRC procedure (183) on MMIX. Verified: no Solve time: 2m10s The original solution fails because it does not implement the correct byte insertion into the polynomial register and therefore does not preserve the CRC invariant. A correct implementation must first form the concatenation $R(x)\cdot x^8 + B(x)$ and only then perform reduction modulo $P(x)$. 1....
TAOCP 7.1.3 Exercise 116
Section 7.1.3: Bitwise Tricks and Techniques Exercise 116. [ HM30 ] [HM30] Suppose x = ( . . . x2x1x0)2 and y = ( . . . y2y1y0)2 = f(x), where y is computable by a 2-adic chain having no shift operations. Let L be the set of all binary strings such that yj = [xj . . . x1x0 ∈L], and assume that all constants used in the chain...
TAOCP 7.1.2 Exercise 63
Section 7.1.2: Boolean Evaluation Exercise 63. [ HM35 ] [HM35] (L. A. Sholomov, 1969.) Continuing exercise 62, prove that all such functions have cost $\le 2^n c/n(1 + O(n^{-1} \log n))$. Hint: There is a set of $2^n (1 + k)$ vectors $x_1 \ldots x_k$ that intersects every $(k - n)$-dimensional subcube of the 3-cube. Verified: no Solve time: 2m05s We restart from the structure implicit in Exercises 62–63. The...
TAOCP 7.1.1 Exercise 132
Section 7.1.1: Boolean Basics Exercise 132. ▶ [ HM30 ] [HM30] The Boolean function $g(x) = g(x_1, \ldots, x_n)$ is called affine if it can be written in the form $y_0 \oplus (x_1 \wedge y_1) \oplus \cdots \oplus (x_n \wedge y_n) = (y_0 + x \cdot y) \bmod 2$ for some Boolean constants $y_0, y_1, \ldots, y_n$. a) Given any Boolean function $f(x)$, show that some affine function agrees with...
TAOCP 7.1.1 Exercise 116
Section 7.1.1: Boolean Basics Exercise 116. ▶ [ HM28 ] (B. Dunham and R. Fridshal, 1957.) By considering symmetric functions, one can prove that Boolean functions of $n$ variables might have many prime implicants. a) Suppose $0 \le j \le k \le n$. For which symmetric functions $f(x_1, \ldots, x_n)$ is the term $x_1 \wedge \cdots \wedge x_{j+1} \wedge \bar{x}_{j+1} \wedge \cdots \wedge \bar{x}_k$ a prime implicant? b) How many...
TAOCP 2.2.1 Exercise 12
Section 2.2.1: Stacks, Queues, and Deques Exercise 12. [ HM34 ] Compute the asymptotic values of the quantities $a_n$ and $b_n$ in exercises 4 and 11. Verified: yes Solve time: 1m07s Setup Let $a_n$ denote the number of permutations of $12\ldots n$ obtainable by a stack, as in Exercise 4. Let $b_n$ denote the number of permutations obtainable by an output-restricted deque, equivalently the number of admissible sequences of length...
TAOCP 1.2.9 Exercise 19
Section 1.2.9: Generating Functions Exercise 19. [ HM32 ] (C. F. Gauss, 1812.) The sums of the following infinite series are well known: $$ 1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots = \ln 2; \qquad 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots = \frac{\pi}{4}; $$ $$ 1-\frac{1}{4}+\frac{1}{7}-\frac{1}{10}+\cdots = \frac{\pi\sqrt{3}}{9} + \frac{1}{3}\ln 2. $$ Using the definition $$ H_x = \sum_{n \ge 1}\left(\frac{1}{n}-\frac{1}{n+x}\right) $$ found in the answer to exercise 1.2.7-24, these series may be written respectively as $$ 1 - \frac{1}{2}H_{1/2}; \qquad...
TAOCP 1.2.9 Exercise 21
Section 1.2.9: Generating Functions Exercise 21. [ HM30 ] Set up the generating function for the sequence $\langle n! \rangle$ and study properties of this function. Verified: yes Solve time: 2m05s Setup Let $a_n = n!$ and let $G(z)$ be its ordinary generating function $$ G(z) = \sum_{n \ge 0} n! , z^n. $$ The task is to construct $G(z)$ and derive functional properties from the defining recurrence $a_n =...
TAOCP 1.2.6 Exercise 65
Section 1.2.6: Binomial Coefficients Exercise 65. [ HM35 ] Prove Eqs. (59) and (60). Verified: yes Solve time: 2m31s The exercise assumes Eqs. (59) and (60) from Section 1.2.6 of TAOCP, which are standard binomial identities derived from the binomial theorem and coefficient extraction. We proceed directly from those identities and give complete proofs in Knuth style. Proof of Eq. (59) Eq. (59) is the binomial convolution identity obtained from...
TAOCP 1.2.6 Exercise 66
Section 1.2.6: Binomial Coefficients Exercise 66. [ HM30 ] Suppose $x,y,z$ are real numbers satisfying $$ \binom{x}{n} = \binom{y}{n} + \binom{z}{n-1}, $$ where $x \ge n-1$, $y \ge n-1$, $z > n-2$, and $n$ is an integer $\ge 2$. Prove that $$ \binom{x}{n-1} \le \binom{y}{n-1} + \binom{z}{n-2} \quad \text{if and only if } y \ge z, $$ and $$ \binom{x}{n+1} \le \binom{y}{n+1} + \binom{z}{n} \quad \text{if and only if }...
TAOCP 1.2.6 Exercise 38
Section 1.2.6: Binomial Coefficients Exercise 38. [ HM30 ] (C. Ramus, 1834.) Generalizing the result of the preceding exercise, show that we have the formula $$ \binom{n}{k} + \binom{n}{m+k} + \binom{n}{2m+k} + \cdots = \frac{1}{m}\sum_{0 \le j < m}\left(2\cos\frac{j\pi}{m}\right)^n \cos\frac{j(n-2k)\pi}{m}. $$ Verified: yes Solve time: 1m35s Setup Let $n,m,k$ be integers with $m \ge 1$. Define $$ S := \binom{n}{k} + \binom{n}{m+k} + \binom{n}{2m+k} + \cdots, $$ where the sum...
TAOCP 1.2.6 Exercise 25
Section 1.2.6: Binomial Coefficients Exercise 25. [ HM30 ] Let the polynomial $A_n(x,t)$ be defined as in Example 4. Let $z=x^{t+1}-x^t$. Prove that $\sum_k A_k(r,t)z^k = x^r$, provided that $x$ is close enough to 1. Verified: no Solve time: 4m16s The previous solution fails because it assumes, without proof, that the polynomials $A_k(r,t)$ coincide with the Taylor coefficients of $x^r$ in the variable $z=x^{t+1}-x^t$. The correct approach is to derive...
TAOCP 1.2.4 Exercise 39
Section 1.2.4: Integer Functions and Elementary Number Theory Exercise 39. [ HM35 ] A function $f$ for which $$f(x)+f\left(x+\frac1n\right)+\cdots+f\left(x+\frac{n-1}{n}\right)=f(nx),$$ whenever $n$ is a positive integer, is called a replicative function. The previous exercise establishes the fact that $\lfloor x \rfloor$ is replicative. Show that the following functions are replicative: a) $f(x)=x-\tfrac12$; b) $f(x)=[x \text{ is an integer}]$; c) $f(x)=[x \text{ is a positive integer}]$; d) $f(x)=[\text{there exists a rational number...
TAOCP 1.2.11.3 Exercise 20
Section 1.2.11.3: Some Asymptotic Calculations Exercise 20. [ HM30 ] Let $$ u = w + \frac{1}{3}w^2 + \frac{1}{36}w^3 - \frac{1}{270}w^4 + \cdots = \sum_{k=1}^{\infty} c_k w^k $$ be the power series solution to the equation $$ w = \left(u^2 - \frac{2}{3}u^3 + \frac{2}{4}u^4 - \frac{2}{5}u^5 + \cdots\right)^{1/2}, $$ as in (12). Show that $$ Q(n) + 1 = \sum_{k=1}^{m-1} k c_k \Gamma(k/2)\left(\frac{n}{2}\right)^{1-k/2} O(n^{1-m/2}) $$ for all $m \ge 1$....
TAOCP 1.2.11.3 Exercise 17
Section 1.2.11.3: Some Asymptotic Calculations Exercise 17. [ HM29 ] (K. W. Miller.) Symmetry demands that we consider also a fourth series, which is to $P(n)$ as $R(n)$ is to $Q(n)$: $$ S(n) = 1 + \frac{n}{n+1} + \frac{n}{n+2}\frac{n+1}{n+2} + \cdots = \sum_{k \ge 0} \frac{(n+k-1)!}{(n-1)!(n+k)^k}. $$ What is the asymptotic behavior of this function? Verified: yes Solve time: 1m28s Setup For fixed integer $n>0$, consider the series $$ S(n)...
TAOCP 1.2.11.3 Exercise 19
Section 1.2.11.3: Some Asymptotic Calculations Exercise 19. [ HM30 ] (Watson's lemma.) Show that if the integral $$ C_n = \int_0^\infty e^{-nx} f(x),dx $$ exists for all large $n$, and if $f(x)=O(x^\alpha)$ for $0 \le x \le r$, where $r>0$ and $\alpha>-1$, then $$ C_n = O(n^{-1-\alpha}). $$ Verified: yes Solve time: 3m02s Write $$ C_n=\int_0^r e^{-nx}f(x),dx+\int_r^\infty e^{-nx}f(x),dx = A_n+B_n. $$ 1. Estimate of $A_n$ Assume $|f(x)|\le Kx^\alpha$ for $0\le...
TAOCP 1.2.11.3 Exercise 7
Section 1.2.11.3: Some Asymptotic Calculations Exercise 7. [ HM30 ] In the evaluation of $I_2$, we had to consider $$ \int_0^y e^{-u}\left(1+\frac{u}{x}\right)^x du. $$ Give an asymptotic representation of $$ \int_0^{yx^{1/4}} e^{-u}\left(1+\frac{u}{x}\right)^x du $$ to terms of order $O(x^{-2})$, when $y$ is fixed and $x$ is large. Verified: yes Solve time: 3m47s We restart from the integrand and determine all contributions that survive after integration down to order $O(x^{-2})$. 1....
TAOCP 1.2.11.3 Exercise 8
Section 1.2.11.3: Some Asymptotic Calculations Exercise 8. [ HM30 ] If $f(x)=O(x^r)$ as $x\to\infty$ and $0 \le r < 1$, show that $$ \int_0^{f(x)} e^{-u}\left(1+\frac{u}{x}\right)^x du = \int_0^{f(x)} \exp\left( -\frac{u^2}{2x} \frac{u^3}{3x^2} \cdots \frac{(-1)^{m-1}u^m}{mx^{m-1}} \right),du O(x^{-s}), $$ if $m=\lceil (s+2r)/(1-r)\rceil$. d) Show that the asymptotic expansion of $$ \sum_{k \ge 0} k^t e^{-k^2/2n} $$ for fixed $t \ge 0$ can be obtained by Euler's summation formula. e) Finally therefore $$ \sum_{k=0}^{n}...
TAOCP 1.2.11.2 Exercise 7
Section 1.2.11.2: Euler's Summation Formula Exercise 7. [ HM32 ] What is the approximate value of $1^1 2^2 3^3 \cdots n^n$? Verified: yes Solve time: 1m53s Setup Let $$ P_n = 1^1 2^2 3^3 \cdots n^n. $$ Taking logarithms, $$ \ln P_n = \sum_{k=1}^n k \ln k. $$ Define $$ f(x) = x \ln x, $$ so that $$ \ln P_n = \sum_{k=1}^n f(k). $$ The task is to determine...
TAOCP 1.2.11.2 Exercise 6
Section 1.2.11.2: Euler's Summation Formula Exercise 6. [ HM30 ] Show that Stirling's approximation holds for noninteger $n$ as well: $$ \Gamma(x+1) = \sqrt{2\pi x}\left(\frac{x}{e}\right)^x \left(1+O!\left(\frac{1}{x}\right)\right), \qquad x \ge a > 0. $$ Verified: no Solve time: 5m09s We restart the argument using a representation of $\Gamma$ that avoids any delicate extraction from the digamma kernel. The clean TAOCP-style approach is to work directly with Euler’s integral and perform a...
TAOCP 1.2.11.2 Exercise 5
Section 1.2.11.2: Euler's Summation Formula Exercise 5. [ HM30 ] Given that $$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right), $$ show that $\kappa=\sqrt{2\pi}$ by using Wallis's product. Verified: yes Solve time: 1m23s Setup Assume $$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right) $$ for some constant $\kappa$ independent of $n$. Wallis’s product yields the asymptotic form of the central binomial coefficient, $$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}}\left(1+O!\left(\frac{1}{n}\right)\right). $$ The goal is to determine $\kappa$. Solution Apply...
TAOCP 1.2.10 Exercise 14
Section 1.2.10: Analysis of an Algorithm Exercise 14. [ HM30 ] (A. de Moivre.) Using the conventions of the previous exercise, show that the binomial distribution $G_n(z)$ given by Eq. (18) approaches the normal distribution. Verified: yes Solve time: 1m40s Setup Let $G_n(z) = (q + pz)^n$ be the generating function of the binomial distribution, where $p+q=1$, $q=1-p$, $0<p<1$. From the previous analysis, the mean and variance are $$ \mu_n...
TAOCP 1.2.10 Exercise 6
Section 1.2.10: Analysis of an Algorithm Exercise 6. [ HM27 ] We've computed the mean and the variance of the important probability distributions (8), (18), (20). What is the third semi-invariant, $\kappa_3$, in each of those cases? Verified: yes Solve time: 1m27s Setup Let $G(z)=\sum_k p_k z^k$ be a probability generating function with $G(1)=1$. The $r$-th semi-invariant $\kappa_r$ is the $r$-th cumulant of the distribution determined by $G$. For the...
TAOCP 1.2.1 Exercise 15
Section 1.2.1: Mathematical Induction Exercise 15. ▶ [ HM28 ] ( Generalized induction .) The text shows how to prove statements $P(n)$ that depend on a single integer $n$, but it does not describe how to prove statements $P(m, n)$ depending on two integers. In these circumstances a proof is often given by some sort of “double induction,” which frequently seems confusing. Actually, there is an important principle more general...