#hm-medium
TAOCP 7.2.1.5 Exercise 57
Section 7.2.1.5: Generating All Set Partitions Exercise 57. [ HM22 ] In the notation of (43), prove that (a) $n+1-m<2N$; (b) $N<2(n+1-m)$. Verified: no Solve time: 42m08s Solution In the notation of (43) the integers (m) and (N) are defined by [ m = \lfloor \alpha \rfloor, \qquad N = \lfloor \beta \rfloor. ] From (40) we have (\alpha = s(\coth s + 1)) and (\beta = s(\coth s -...
TAOCP 7.2.1.5 Exercise 54
Section 7.2.1.5: Generating All Set Partitions Exercise 54. [ HM20 ] If $\alpha$ and $\beta$ are defined by (40), show that their arithmetic and geometric means are respectively $\dfrac{\alpha+\beta}{2}=s,\coth s$ and $\sqrt{\alpha\beta}=s,\csch s$, where $s=\sigma/2$. Verified: no Solve time: 12m54s Solution From equation (40) of the text, the parameters (\alpha) and (\beta) are given by [ \alpha = s(\coth s + 1), \qquad \beta = s(\coth s - 1), ]...
TAOCP 7.2.1.5 Exercise 55
Section 7.2.1.5: Generating All Set Partitions Exercise 55. [ HM20 ] Suggest a good way to compute the number $\beta$ needed in (43). Verified: no Solve time: 6m03s Solution In the asymptotic analysis of the Bell numbers ( \varpi_n ), the saddle-point method is applied to the generating function (\Pi(z)=e^{e^z-1}). The dominant contribution comes from the point where the derivative of the exponent vanishes, leading to the saddle-point equation [...
TAOCP 7.2.1.5 Exercise 52
Section 7.2.1.5: Generating All Set Partitions Exercise 52. [ HM22 ] The cumulants of a probability distribution are defined in Eq. 1.2.10–(23). What are the cumulants, when the probability that a random integer equals $k$ is (a) $e^{1-e^\xi}\varpi_k\xi^k/k!$? (b) $\sum_j \left{\begin{array}{c} k \ j \end{array}\right}e^{e^{-1}-j/k!}$? Verified: no Solve time: 14m29s Solution We use the definition of cumulants from Eq. 1.2.10-(23): if a random variable (X) has probability generating function (G(z)...
TAOCP 7.2.1.5 Exercise 48
Section 7.2.1.5: Generating All Set Partitions Exercise 48. [ HM25 ] If $n$ is not an integer, the integral in (23) can be taken over a Hankel contour to define a generalized Bell number $\varpi_x$ for all real $x > 0$. Show that, as in (16), $$ \varpi_x=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^x}{k!}. $$ Verified: no Solve time: 9m44s Solution The integral in equation (23) of the text is the Cauchy integral representation for the...
TAOCP 7.2.1.5 Exercise 50
Section 7.2.1.5: Generating All Set Partitions Exercise 50. ▶ [ HM21 ] If $\xi(n)e^{\xi(n)}=n$ and $\xi(n)>0$, how does $\xi(n+k)$ relate to $\xi(n)$? Verified: no Solve time: 3m03s Solution We define $\xi(x)$ for $x>0$ as the unique positive solution of $\xi e^{\xi}=x$. Thus $\xi(n)>0$ satisfies [ \xi(n),e^{\xi(n)} = n. ] For a given integer $k\ge 0$ we wish to relate $\xi(n+k)$ to $\xi(n)$. Let $\xi = \xi(n)$ and $\eta = \xi(n+k)$....
TAOCP 7.2.1.5 Exercise 46
Section 7.2.1.5: Generating All Set Partitions Exercise 46. [ HM25 ] Estimate the value of $\varpi_{nk}$ in Peirce’s triangle when $n \to \infty$. Verified: no Solve time: 12m03s Solution We wish to estimate the numbers $\varpi_{nk}$ defined by Peirce's triangle recurrence [ \varpi_{nk} = \varpi_{n-1,k} + \varpi_{n,k+1}\qquad (1\le k < n),\qquad \varpi_{nn} = \varpi_{n-1,1},\qquad \varpi_{11}=1, ] as $n\to\infty$. The combinatorial meaning of $\varpi_{nk}$ is the number of partitions of ${1,2,\ldots,n}$...
TAOCP 6.2.2 Exercise 36
Section 6.2.2: Binary Tree Searching Exercise 36. ▶ [ HM25 ] (Claude Shannon.) Let $X$ and $Y$ be random variables with finite ranges ${x_1, \ldots, x_m}$ and ${y_1, \ldots, y_n}$, and let $p_i = \Pr{X = x_i}$, $\bar{q} j = \Pr{Y = y_j}$, $r {ij} = \Pr{X = x_i \text{ and } Y = y_j}$. Let $H(X) = H(p_1, \ldots, p_m)$ and $H(Y) = H(q_1, \ldots, q_n)$ be the respective...
TAOCP 5.4.9 Exercise 17
Section 5.4.9: Disks and Drums Exercise 17. ▶ [ HM25 ] (R. W. Floyd, 1980.) Show that the lower bound of Theorem F can be improved to $$\frac{n(b\ln n-\ln b-1)}{\ln n+b(1+\ln(1+m/b))},$$ in the sense that some initial configuration must require at least this many stops. [Hint: Count the configurations that can be obtained after $s$ stops.] Verified: no Solve time: 23m51s Solution We consider the elevator problem as defined in...
TAOCP 5.3.4 Exercise 30
Section 5.3.4: Networks for Sorting Exercise 30. [ HM22 ] Prove that any formula involving $\wedge$ and $\vee$ and the independent variables ${x_1, \ldots, x_n}$ can be reduced using the identities in exercise 28 to a "canonical" form $\tau_1 \vee \tau_2 \vee \cdots \vee \tau_n$, where $k \ge 1$, each $\tau_i$ has the form $\bigwedge {x_j \mid j \in S_i}$ where $S_i$ is a subset of ${1, 2, \ldots, n}$,...
TAOCP 5.3.1 Exercise 11
Section 5.3.1: Minimum-Comparison Sorting Exercise 11. [ HM22 ] When sorting $n$ elements as in exercise 5, and knowing that all keys are members of the set ${1, 2, \ldots, m}$, let $S_m(n)$ be the minimum number of comparisons needed in the worst case. [Thus by exercise 6, $S_n(n) = S(n)$.] Prove that, for fixed $m$, $S_m(n)$ is asymptotically $n \lg m + O(1)$ as $n \to \infty$. Verified: no...
TAOCP 5.2.3 Exercise 30
Section 5.2.3: Sorting by Selection Exercise 30. ▶ [ HM25 ] (R. Schaffer and R. Sedgewick.) Let $h_{nm}$ be the number of heaps on the elements ${1, 2, \ldots, n}$ for which the selection phase of heapsort does exactly $m$ promotions. Prove that $h_{nm} \le 2^m \prod_{k=2}^n \lg k$, and use this relation to show that the average number of promotions performed by Algorithm H is $N \lg N +...
TAOCP 5.2.2 Exercise 50
Section 5.2.2: Sorting by Exchanging Exercise 50. [ HM24 ] Find the asymptotic value of the function $$U_{mn} = \sum_{k \ge 2} \binom{n}{k} (-1)^k \frac{1}{m^{k-1} - 1}.$$ when $m$ is any fixed number greater than 1. (When $m$ is an integer greater than 2, this quantity arises in the study of generalizations of radix exchange, as well as the trie memory search algorithms of Section 6.3.) Verified: no Solve time:...
TAOCP 5.2.2 Exercise 54
Section 5.2.2: Sorting by Exchanging Exercise 54. [ HM24 ] (S. O. Rice.) Show that $U_n$ can be written $$U_n = (-1)^n \frac{n!}{2\pi i} \oint_C \frac{dz}{z(z-1)\ldots(z-n)} \frac{1}{2^{1-z}-1},$$ where $C$ is a skinny closed curve encircling the points $2, 3, \ldots, n$. Changing $C$ to an arbitrarily large circle centered at the origin, derive the convergent series $$U_n = \frac{(H_{n-1} - 1)n}{\ln 2} - \frac{n}{2} + 2 + \frac{2}{\ln 2} \sum_{m...
TAOCP 5.2.2 Exercise 48
Section 5.2.2: Sorting by Exchanging Exercise 48. [ HM24 ] Find the asymptotic value of the quantity $V_n$ defined in exercise 38, using a method analogous to the text's study of $U_n$, obtaining terms up to $O(1)$. Verified: no Solve time: 15m06s Solution In Exercise 38, the quantity (V_n) is defined as [ V_n = \frac{1}{n!}\sum_{s=1}^{n} s! \sum_{r=0}^{s-1} r^{,n-s}. ] This sum arises naturally in the analysis of the average...
TAOCP 5.2.2 Exercise 47
Section 5.2.2: Sorting by Exchanging Exercise 47. [ HM21 ] Prove that $\sum_{j \ge 1} (n/2^j) e^{-n/2^j}$ is a bounded function of $n$. Verified: no Solve time: 4m07s Solution We need to prove that the function [ S(n) = \sum_{j=1}^{\infty} \frac{n}{2^j} e^{-n/2^j} ] is bounded for all (n > 0). (If (n \le 0), the sum is trivially zero or not defined; we consider (n>0).) Define (f(x) = x e^{-x})...
TAOCP 5.2.2 Exercise 45
Section 5.2.2: Sorting by Exchanging Exercise 45. [ HM20 ] Explain why (43) is true, when $x > 0$. Verified: no Solve time: 23m06s Solution In the text, equation (43) is the integral representation $$ \frac{1}{n!}\sum_{0\le r<s\le n}s!,r^{,n-s} = \int_0^\infty e^{-x},\frac{(e^x-1),\gamma(n+1,x)}{x,\Gamma(n+1)},dx \qquad\text{(43)} $$ where $\gamma(n+1,x)=\int_0^x t^n e^{-t},dt$ is the lower incomplete gamma function. The condition “when $x>0$” refers to the domain of integration; the integrand is well‑defined for all $x>0$...
TAOCP 5.2.2 Exercise 46
Section 5.2.2: Sorting by Exchanging Exercise 46. [ HM20 ] What is the value of $(1/2\pi i) \int_{s-i\infty}^{s+i\infty} \Gamma(z) n^{-z},dz/(2^{z-1} - 1)$, given that $s$ is a positive integer and $0 < a < s$? Verified: no Solve time: 12m49s Solution We evaluate the integral [ I = \frac{1}{2\pi i} \int_{s-i\infty}^{s+i\infty} \frac{\Gamma(z), n^{-z}}{2^{z-1} - 1} , dz, ] where (s) is a positive integer. The condition (0 < a <...
TAOCP 5.2.2 Exercise 44
Section 5.2.2: Sorting by Exchanging Exercise 44. [ HM24 ] Derive (37) as suggested in the text. Verified: no Solve time: 12m24s Solution We derive the asymptotic formula for the average number of comparisons in the bubble sort (Equation (37) in the text). From the analysis in Section 5.2.2, the average number of comparisons is [ C_{\text{ave}} = \binom{N+1}{2} - \frac{1}{N!}\sum_{s=1}^{N} s! \sum_{r=0}^{s-1} r^{,N-s}. ] Setting (k = N-s) and...
TAOCP 5.2.2 Exercise 43
Section 5.2.2: Sorting by Exchanging Exercise 43. [ HM21 ] Prove that $\int_0^y y^{-1}(e^{-y} - 1),dy + \int_1^\infty y^{-1} e^{-y},dy = -\gamma$. [ Hint: Consider $\lim_{a \to 0} y^{a-1}$.] Verified: no Solve time: 52s Solution We prove the identity [ \int_0^1 \frac{e^{-y}-1}{y},dy ;+; \int_1^\infty \frac{e^{-y}}{y},dy ;=; -\gamma, ] where (\gamma) is the Euler-Mascheroni constant. (The upper limit of the first integral is (1); the notation (\int_0^y) in the exercise statement...
TAOCP 5.1.4 Exercise 32
Section 5.1.4: Tableaux and Involutions Exercise 32. [ HM21 ] Prove that the involution number $t_n$ is the expected value of $X^n$, when $X$ is a normal deviate with mean 1 and variance 1. Verified: yes Solve time: 13m11s Solution Let (X) be a normal random variable with mean (1) and variance (1). Its moment generating function is [ M(t) = \mathbb{E}[e^{tX}] = \exp!\left(t + \frac{t^2}{2}\right). ] Expanding as a...
TAOCP 5.1.4 Exercise 29
Section 5.1.4: Tableaux and Involutions Exercise 29. [ HM25 ] Prove that a random permutation of $n$ elements has an increasing subsequence of length $\ge t$ with probability $\le \binom{n}{t}/t!$. This probability is $O(1/\sqrt{n})$ when $l = c\sqrt{n} + O(1)$, and $O(\exp(-c\sqrt{n}))$ when $l = 3\sqrt{n}$, $c = 6\ln 3 - 6$. Verified: yes Solve time: 1h15m Solution 1. Upper bound for the probability Let (\pi) be a uniformly random...
TAOCP 5.1.4 Exercise 17
Section 5.1.4: Tableaux and Involutions Exercise 17. [ HM25 ] Let $$g(x_1, x_2, \ldots, x_n;, y) = x_1, \Delta(y, x_2, \ldots, x_n) + x_2, \Delta(x_1, x_2, \ldots, x_n)$$ $$+ \cdots + x_n, \Delta(x_1, x_2, \ldots, x_{n-1}, y).$$ Prove that $$g(x_1, x_2, \ldots, x_n;, y) = (x_1 + x_2 + \cdots + x_n + \tbinom{n}{2}, y), \Delta(x_1, x_2, \ldots, x_n).$$ [ Hint: The function is homogeneous (all terms have the same...
TAOCP 4.5.4 Exercise 13
Section 4.5.4: Factoring into Primes Exercise 13. [ HM25 ] (J. D. Dixon.) Prove that whenever the algorithm of exercise 12 is pre- sented with a solution $(x,e_0,\ldots,e_m)$ whose exponents are linearly dependent modulo 2 on the exponents of previous solutions, the probability is $2^{1-d}$ that a factorization will not be found, when $N$ has $d$ distinct prime factors and $x$ is chosen at random. Verified: no Solve time: 53m27s...
TAOCP 1.2.11.3 Exercise 12
Section 1.2.11.3: Some Asymptotic Calculations Exercise 12. [ HM20 ] The function $\int_0^x e^{-t^2/2},dt$ that appeared in connection with the normal distribution (see Section 1.2.10) can be expressed as a special case of the incomplete gamma function. Find values of $a$, $b$, and $y$ such that $b,\gamma(a,y)$ equals $\int_0^x e^{-t^2/2},dt$. Verified: yes Solve time: 5m01s Solution We want to express the integral [ \int_0^x e^{-t^2/2},dt ] in terms of the...
TAOCP 1.2.5 Exercise 24
Section 1.2.5: Permutations and Factorials Exercise 24. ▶ [ HM21 ] Prove the handy inequalities $$ \frac{n^n}{e^{,n-1}} \le n! \le \frac{n^{n+1}}{e^{,n-1}}, \qquad \text{integer } n \ge 1. $$ [Hint: $1+x \le e^x$ for all real $x$; hence $(k+1)/k \le e^{1/k} \le k/(k-1)$.] Verified: yes Solve time: 9m39s Solution From (1+x\le e^x), taking (x=1/k) gives, for (k\ge1), [ \frac{k+1}{k}\le e^{1/k}. ] Taking (x=-1/k), where (k\ge2), gives [ 1-\frac1k\le e^{-1/k}. ] Both...
TAOCP 1.2.5 Exercise 22
Section 1.2.5: Permutations and Factorials Exercise 22. ▶ [ HM20 ] Try to put yourself in Euler's place, looking for a way to generalize $n!$ to noninteger values of $n$. Since $(n+\tfrac12)!/n!$ times $((n+\tfrac12)+\tfrac12)!/(n+\tfrac12)!$ equals $(n+1)!/n! = n+1$, it seems natural that $(n+\tfrac12)!/n!$ should be approximately $\sqrt{n}$. Similarly, $(n+\tfrac13)!/n!$ should be approximately $n^{1/3}$. Invent a hypothesis about the ratio $(n+x)!/n!$ as $n$ approaches infinity. Is your hypothesis correct when $x$...
TAOCP 1.2.5 Exercise 10
Section 1.2.5: Permutations and Factorials Exercise 10. ▶ [ HM20 ] Does the identity $\Gamma(x+1)=x\Gamma(x)$ hold for all real numbers $x$? (See exercise 7.) Verified: yes Solve time: 8m06s Solution Let [ D=\mathbb{R}\setminus{0,-1,-2,\ldots}, ] the set of real numbers for which both (\Gamma(x)) and (\Gamma(x+1)) are defined by Eq. (15). For (x\in D), Eq. (15) gives [ x\Gamma(x) =\lim_{m\to\infty} \frac{x,m^x m!}{x(x+1)\cdots(x+m)} =\lim_{m\to\infty} \frac{m^x m!}{(x+1)(x+2)\cdots(x+m)}. ] On the other hand, [...
TAOCP 7.2.2.2 Exercise 457
Section 7.2.2.2: Satisfiability Exercise 457. [ HM19 ] $[HM19]$ Show that every Boolean $f(x_1, x_2, x_3, x_4)$ has more than 51 quadrillion endomorphisms, and an $n$-variable function has more than $2^{2^{n-1}}$ endomorphisms. Verified: no Solve time: 3m43s Solution In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write $$ x_{i,j}=1\iff x_i=j, $$ where $0\le i<p$ and $1\le j\le d$ if the domain has...
TAOCP 7.2.2.2 Exercise 355
Section 7.2.2.2: Satisfiability Exercise 355. [ HM21 ] In (152), prove that $E_j \le 1/\delta$ when $(p_1, \ldots, p_m)$ has positive slack $\delta$. Hint: Consider replacing $p_i$ by $p_j + \delta p_j$. Verified: no Solve time: 3m44s Solution Let $E_j$ denote the expected number of executions of the resampling step associated with the bad event $A_j$, as in (152). The standard witness-tree expression for this expectation is $$ E_j=\sum_{\tau\in\mathcal{T}_j} w(\tau),...
TAOCP 7.2.2.2 Exercise 354
Section 7.2.2.2: Satisfiability Exercise 354. [ HM20 ] Show that the expected number $E,N$ of resampling steps in Algorithm M is at most $-M_G''(1)/M_G'(1)$. Verified: no Solve time: 3m47s Solution Let $E_j$ denote the expected number of executions of the resampling step associated with the bad event $A_j$, as in (152). The standard witness-tree expression for this expectation is $$ E_j=\sum_{\tau\in\mathcal{T}_j} w(\tau), $$ where $\mathcal{T}_j$ is the family of proper...
TAOCP 7.2.2.2 Exercise 342
Section 7.2.2.2: Satisfiability Exercise 342. [ HM25 ] (Cartier and Foata, 1969.) Let $G_n$ be the graph whose vertices are the $\sum_{k=1}^{n} \binom{n}{k}(k-1)!$ cyclic permutations of subsets of ${1, \ldots, n}$, with $\sigma \mathbin{\text{---}} \tau$ when $\sigma$ and $\tau$ intersect. For example, the vertices of $G_3$ are $(1)$, $(2)$, $(3)$, $(1,2)$, $(1,3)$, $(2,3)$, $(1,2,3)$, $(1,3,2)$; and they're mutually adjacent except that $(1) \nmid (2)$, $(1) \nmid (3)$, $(1) \nmid (2,3)$,...
TAOCP 7.2.2.2 Exercise 320
Section 7.2.2.2: Satisfiability Exercise 320. [ HM24 ] Given a lospdependency graph $G$, the occurrence threshold $\rho(G)$ is the smallest value $p$ such that it's sometimes impossible to avoid all events when each event occurs with probability $p$. For example, the Möbius polynomial for the path $P_5$ is $1 - p_1 - p_2 - p_3 + p_1 p_5$; so the occurrence threshold is $\phi^{-2}$, the least $p$ with $1 -...
TAOCP 7.2.2.2 Exercise 319
Section 7.2.2.2: Satisfiability Exercise 319. [ HM20 ] Show that $pdc < 1$ implies $p \le (d-1)^{d-1}/d^d$. Verified: no Solve time: 4m04s Solution No. Theorem J and Theorem L concern different probability estimates for Algorithm W, and the hypotheses of Theorem L do not imply the statement of Theorem J. Theorem J gives a bound under the specific assumption that the current assignment is at Hamming distance $d$ from a...
TAOCP 7.2.2.2 Exercise 316
Section 7.2.2.2: Satisfiability Exercise 316. [ HM20 ] Is Theorem J a consequence of Theorem L? Verified: no Solve time: 16m
TAOCP 7.2.2.2 Exercise 312
Section 7.2.2.2: Satisfiability Exercise 312. [ HM24 ] Let $T(m, n) = EX$ when the reluctant doubling method is applied to the probability distribution defined in exercise 306(k). Express $T(m, n)$ in terms of the generating functions in exercise 308(e). Verified: no Solve time: 3m51s Solution The quantity $F_t(r)$ can be found by turning the defining condition into a family of satisfiability problems. For fixed $t$ and $r$, introduce Boolean...
TAOCP 7.2.2.2 Exercise 303
Section 7.2.2.2: Satisfiability Exercise 303. [ HM20 ] Solve exercise 294 with Algorithm W in place of Algorithm P. Verified: no Solve time: 3m55s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The restriction $F|L$ is obtained by setting every literal in $L$ to true, deleting every clause that contains one of these literals, and deleting from the remaining clauses every literal whose complement...
TAOCP 7.2.2.2 Exercise 299
Section 7.2.2.2: Satisfiability Exercise 299. [ HM23 ] Continuing the previous exercise, investigate the case $k = 2$. Verified: no Solve time: 3m48s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The restriction $F|L$ is obtained by setting every literal in $L$ to true, deleting every clause that contains one of these literals, and deleting from the remaining clauses every literal whose complement belongs...
TAOCP 7.2.2.2 Exercise 298
Section 7.2.2.2: Satisfiability Exercise 298. [ HM22 ] Generalize Theorem U and Corollary W to the case where each clause has at most $k$ literals, where $k \ge 3$. Verified: no Solve time: 3m51s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The restriction $F|L$ is obtained by setting every literal in $L$ to true, deleting every clause that contains one of these literals,...
TAOCP 7.2.2.2 Exercise 296
Section 7.2.2.2: Satisfiability Exercise 296. [ HM20 ] Complete the proof of Theorem U by (approximately) maximizing the quantity $f(p, q)$ in (129). Hint: Consider $f(p+1, q)/f(p, q)$. Verified: no Solve time: 3m59s Solution The statement is true. Let $L={l_1,\ldots,l_r}$ be a set of strictly distinct literals. The restriction $F|L$ is obtained by setting every literal in $L$ to true, deleting every clause that contains one of these literals, and...
TAOCP 7.2.2.2 Exercise 294
Section 7.2.2.2: Satisfiability Exercise 294. [ HM21 ] For each binary vector $\alpha = x_1 x_2 x_3 x_4$, find the generating function $g_\alpha(z) = \sum_{j=0}^{\infty} p_{\alpha,j} z^j$, where $p_{\alpha,j}$ is the probability that Algorithm P will solve the seven clauses of (7) after making exactly $j$ flips, given the initial values $\alpha$ in step P1. Deduce the mean and variance of the number of steps needed to find a solution....
TAOCP 7.2.2.2 Exercise 240
Section 7.2.2.2: Satisfiability Exercise 240. [ HM23 ] Choose integers $f_{ij} \in {1, \ldots, m}$ uniformly at random, for $1 \le i \le 5$ and $0 \le j \le m$, and let $G_0$ be the bipartite graph with edges $a_j — b_k$ if and only if $k \in {f_{1j}, \ldots, f_{5j}}$. Show that $\Pr(G_0$ satisfies the strong expansion condition $(108)) \ge 1/2$. Verified: no Solve time: 5m59s Setup Let $F$...
TAOCP 7.2.2.2 Exercise 238
Section 7.2.2.2: Satisfiability Exercise 238. [ HM21 ] Complete the proof of Lemma B. Hint: Make $r \le \rho^{-h}$ when $W = b$. Verified: no Solve time: 6m11s 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 false. Since...
TAOCP 7.2.2.2 Exercise 215
Section 7.2.2.2: Satisfiability Exercise 215. ▶ [ HM23 ] What is the expected profile of the search tree when a simple backtrack procedure is used to find all solutions to a random 3SAT problem with $m$ independent clauses on $n$ variables? (There is a node on level $l$ for every partial solution $x_1 \ldots x_l$ that doesn't contradict any of the clauses.) Compute these values when $m = 200$ and...
TAOCP 7.2.2.2 Exercise 202
Section 7.2.2.2: Satisfiability Exercise 202. [ HM21 ] This exercise amplifies the text's proof of Theorem C when $c > 1$. a) Explain the right-hand side of Eq. (93). b) Why does (97) follow from (95), (96), and the stated choices of $t$ and $m$? Verified: no Solve time: 5m51s Correctness The proposed solution does not answer the stated exercise. Exercise 7.2.2.2.202 asks about the proof of Theorem C, specifically...
TAOCP 7.2.2.2 Exercise 197
Section 7.2.2.2: Satisfiability Exercise 197. [ HM21 ] Prove that the quotient $q(a, b, A, B, n) = \binom{(a+b)n}{an} \binom{(A+B)n}{An} / \binom{(a+b+A+B)n}{(a+A)n}$ is $\Theta(n^{-1/2})$ as $n \to \infty$, if $a, b, A, B > 0$. Verified: no Solve time: 5m13s Correctness The proposed solution identifies the correct reformulation of the problem. A Boolean function on four variables is representable in $3$CNF exactly when its set of falsifying assignments is a...
TAOCP 7.2.2.2 Exercise 196
Section 7.2.2.2: Satisfiability Exercise 196. ▶ [ HM25 ] (D. B. Wilson.) A clause of a satisfiability problem is "easy" if it contains one or more variables that don't appear in any other clauses. Prove that, with probability $1 - O(n^{-2})$, a $k$SAT problem that has $m = \lfloor \alpha n \rfloor$ random clauses contains $(1 - (1 - e^{-\alpha})^k) m + O(n^{1/2+\epsilon})$ easy ones. (For example, about $0.000035n$ of...
TAOCP 7.2.2.2 Exercise 195
Section 7.2.2.2: Satisfiability Exercise 195. [ HM21 ] [HM21] (J. Franco and M. Paull, 1983.) Use the first moment principle MPR-(21) to prove that $\lfloor (2^k \ln 2)n \rfloor$ random $k$SAT clauses are almost always unsatisfiable. Hint: Let $X = \sum_v \lfloor x$-all clauses$\rfloor$, summed over all $2^n$ binary vectors $x = x_1 \ldots x_n$. Verified: no Solve time: 5m33s Correctness The proposed solution identifies the correct reformulation of the...
TAOCP 7.2.2.2 Exercise 194
Section 7.2.2.2: Satisfiability Exercise 194. [ HM19 ] [HM19] If $\alpha < \liminf_{n\to\infty} S_{k,n}/n$, is there a polynomial-time algorithm that is able to satisfy a random $m$SAT clauses with probability $\ge \delta$, for some $\delta > 0$? Verified: no Solve time: 2m02s Solution A Boolean function on variables $x_1,\ldots,x_4$ is represented by a $3$CNF formula exactly when its set of falsifying assignments is a union of subcubes of dimension at...
TAOCP 7.2.2.2 Exercise 192
Section 7.2.2.2: Satisfiability Exercise 192. ▶ [ HM21 ] [HM21] Another way to model satisfiability when there are $N$ equally likely clauses is to study $S(p)$, the probability of satisfiability when each clause is independently present with probability $p$. a) Express $S(p)$ in terms of the numbers $Q_m = \binom{N}{m} q_m$. b) Assign uniform random numbers in $[0,.,1)$ to each clause; then at time $t$, for $0 \le t \le...
TAOCP 7.2.2.2 Exercise 188
Section 7.2.2.2: Satisfiability Exercise 188. [ HM25 ] [HM25] Analyze random 1SAT, the case $k = 1$: What are $S_{1,n}$ and $\hat{S}_{1,n}$? Verified: no Solve time: 6m11s Solution In the random SAT model used here, a formula with $m$ clauses is formed by choosing each clause independently and uniformly from the possible clauses. For $k=1$, there are $2n$ possible clauses, $$ x_1,\bar x_1,x_2,\bar x_2,\ldots,x_n,\bar x_n . $$ Thus a random...
TAOCP 7.2.2.1 Exercise 303
Section 7.2.2.1: Dancing Links Exercise 303. ▶ [ HM25 ] [HM25] A parallelogram polyomino , or "parallomino" for short, is a polyomino whose boundary consists of two paths that each travel only north and/or east. (Equivalently, it is a "staircase polygon," "skew Young tableau," or a "skew Ferrers board," the difference between the diagrams of two tableaux or partitions; see Sections 5.1.4 and 7.2.4.1.) For example, there are five parallelominoes...
TAOCP 7.2.2.1 Exercise 258
Section 7.2.2.1: Dancing Links Exercise 258. [ HM21 ] How many updates does Algorithm Z perform, in that extreme problem? Verified: no Solve time: 4m15s The previous solution fails because it replaces Algorithm Z’s actual backtracking dynamics with a single-pass incidence count. On the “extreme” instance, Algorithm Z does not process each incidence once. Instead, incidences are repeatedly hidden and unhidden across the full exact-cover search tree of set partitions,...
TAOCP 7.2.2.1 Exercise 200
Section 7.2.2.1: Dancing Links Exercise 200. ▶ [ HM25 ] (A. Björklund, 2010.) Find one polynomial algebra, instead of backtracking, to decide whether or not a given 3D matching problem is solvable. Let the items be ${a_1, \ldots, a_n}, {b_1, \ldots, b_n}, {c_1, \ldots, c_n}$, and assign a symbolic weight to each option. If $X$ is any subset of $C$, let $Q(X)$ be the $n \times n$ matrix whose entry...
TAOCP 7.2.2.1 Exercise 194
Section 7.2.2.1: Dancing Links Exercise 194. [ HM25 ] Consider recurrences of the form $X(t+1) = a_t + tX(t-1)$. For example, $a_t = 1$ yields the total number of nodes in the search tree for matching $K_{t+1}$. a) Prove that $1 + 2q + (2q)(2q-2) + \cdots + (2q)(2q-2)\cdots 2 = (e^{1/2}q^2)$. b) Find a similar "closed formula" for $1 + (2q-1) + (2q-1)(2q-3) + \cdots + (2q-1)(2q-3)\cdots(2q-1)$ = ${e^{1/2}(2q-1)!!...
TAOCP 7.2.2.1 Exercise 191
Section 7.2.2.1: Dancing Links Exercise 191. [ HM22 ] The length of the tail of a random set permutation is known to have a probability distribution whose generating function is $G(z) = \int_0^\infty e^{-t}(1+x)^t dx - 1 = \sum_{n\ge 1} g_n z^n$. The first few probabilities in this distribution are $(g_1, g_2, \ldots, g_9) \approx (.59635, .26597, .09678, .03009, .00823, .00202, .00045, .00009, .00002);$ see answer 189. What is the...
TAOCP 7.2.2 Exercise 57
Section 7.2.2: Backtracking Exercise 57. [ HM21 ] Algorithm E can potentially follow $M$ different paths $X_1 \cdots X_{l-1}$ before it terminates, where $M$ is the number of leaves of the backtrack tree. Suppose the final values of $D$ at those leaves are $D^{(1)}, \ldots, D^{(M)}$. Prove that $(D^{(1)} \cdots D^{(M)})^{1/M} \ge M$. Verified: no Solve time: 5m06s Setup We seek all integers $n < 10^9$ such that the equation...
TAOCP 7.2.2 Exercise 52
Section 7.2.2: Backtracking Exercise 52. ▶ [ HM25 ] $[HM25]$ Elmo uses Algorithm E with $D_k = {1, \ldots, n}$, $P_k = {x_1 > \cdots > x_k}$, $c = 1$. a) Alice flips $n$ coins independently, where coin $k$ yields "heads" with probability $1/k$. True or false: She obtains exactly $l$ heads with probability $\binom{n}{l}/n!$. b) Let $Y_1, Y_2, \ldots, Y_l$ be the numbers on the coins that come up...
TAOCP 7.2.1.6 Exercise 105
Section 7.2.1.6: Generating All Trees Exercise 105. [ HM18 ] Continuing exercise 104, we wish to prove that there is often an easy way to determine the aspects of $G$ when $G$ has been constructed from other graphs whose aspects are known. Suppose $G'$ has aspects $\alpha' 0, \ldots, \alpha' {s'-1}$ and $G''$ has aspects $\alpha'' 0, \ldots, \alpha'' {s''-1}$; what are the aspects of $G$ in the following cases?...
TAOCP 7.2.1.6 Exercise 104
Section 7.2.1.6: Generating All Trees Exercise 104. ▶ [ HM21 ] If $G$ is a graph on $n$ vertices ${V_1, \ldots, V_n}$, with $e_{ij}$ edges between $V_i$ and $V_j$, let $C(G)$ be the matrix with entries $c_{ij} = -e_{ij} + \delta_{ij} d_i$, where $d_i = e_{i1} + \cdots + e_{in}$ is the degree of $V_i$. Let us say that the aspects of $G$ are the eigenvalues of $C(G)$, namely the...
TAOCP 7.2.1.5 Exercise 76
Section 7.2.1.5: Generating All Set Partitions Exercise 76. [ HM16 ] Find the asymptotic value of $p(2, \ldots, 2)$ when there are $2n$ 2s. Verified: no Solve time: 5m46s 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 75
Section 7.2.1.5: Generating All Set Partitions Exercise 75. [ HM21 ] Find the asymptotic value of $p(n, n)$. Verified: no Solve time: 5m58s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of terms among...
TAOCP 7.2.1.5 Exercise 67
Section 7.2.1.5: Generating All Set Partitions Exercise 67. [ HM20 ] What are the mean and variance of $M$ in Stan's method (53)? 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 one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be...
TAOCP 7.2.1.5 Exercise 60
Section 7.2.1.5: Generating All Set Partitions Exercise 60. [ HM21 ] (a) Show that the partial sums in the identity $$\left{ n \atop m \right} = \frac{m^n}{m!} - \frac{(m-1)^n}{1!(m-1)!} + \frac{(m-2)^n}{2!(m-2)!} - \cdots + (-1)^n \frac{0^n}{n!0!}$$ alternately overestimate and underestimate the final value. (b) Calculate $\binom{10}{5}$. (c) Derive a similar result from (43). Verified: no Solve time: 6m03s Setup We seek all integers $n < 10^9$ such that the equation...
TAOCP 7.2.1.5 Exercise 59
Section 7.2.1.5: Generating All Set Partitions Exercise 59. ▶ [ HM25 ] What does (43) predict for the approximate value of $\binom{n}{m}$? Verified: no Solve time: 5m37s 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.5 Exercise 45
Section 7.2.1.5: Generating All Set Partitions Exercise 45. ▶ [ HM23 ] Show that, in addition to (26), we also have the expansion $$\varpi_n = \frac{e^{e^t - 1}}{t^n \sqrt{2\pi(t+1)}} \Biggl( 1 + \frac{b_1'}{n} + \frac{b_2'}{n^2} + \cdots + \frac{b_m'}{n^m} + O!\left(\frac{1}{n^{m+1}}\right) \Biggr),$$ where $b_1' = -(2t^4 + 9t^3 + 6t^2 + 6t + 2)/(24(t+1)^3)$. Verified: no Solve time: 5m32s Setup We seek all integers $n < 10^9$ such that the...
TAOCP 7.2.1.5 Exercise 44
Section 7.2.1.5: Generating All Set Partitions Exercise 44. [ HM22 ] Explain how to compute $b_1, b_2, \ldots$ in (26) from $a_2, a_3, \ldots$ in (25). Verified: no Solve time: 5m31s 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.1.5 Exercise 43
Section 7.2.1.5: Generating All Set Partitions Exercise 43. [ HM22 ] Justify replacing the integral in (23) by (25). Verified: no Solve time: 5m26s 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.1.5 Exercise 42
Section 7.2.1.5: Generating All Set Partitions Exercise 42. [ HM23 ] Use the saddle point method to estimate $[z^{n-1}] e^{z^2}$ with relative error $O(1/n^2)$. Verified: no Solve time: 5m36s 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 41
Section 7.2.1.5: Generating All Set Partitions Exercise 41. [ HM21 ] Solve the previous exercise when $c = -1$. Verified: no Solve time: 5m53s 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.1.5 Exercise 40
Section 7.2.1.5: Generating All Set Partitions Exercise 40. [ HM20 ] Suppose the saddle point method is used to estimate $[z^{n-1}] e^z$. The text's derivation of (21) from (20) deals with the case $c = 1$; how should that derivation change if $c$ is an arbitrary positive constant? Verified: no Solve time: 5m52s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots...
TAOCP 7.2.1.5 Exercise 39
Section 7.2.1.5: Generating All Set Partitions Exercise 39. [ HM18 ] Evaluate $\int_0^\infty e^{-pt^q} t^r , dt$ when $p$ and $q$ are nonnegative integers. Hint: See exercise 1.2.5–20. Verified: no Solve time: 5m41s 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.5 Exercise 31
Section 7.2.1.5: Generating All Set Partitions Exercise 31. [ HM21 ] [HM21] Generalizing (15), show that the elements of Peirce's triangle have a simple generating function, if we compute the sum $$\sum_n \varpi_n(x, y) \frac{z^{n-k}}{(n-k)!,(k-1)!}.$$ Verified: no Solve time: 4m30s 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.4 Exercise 47
Section 7.2.1.4: Generating All Partitions Exercise 47. ▶ [ HM22 ] [HM22] (A. Nijenhuis and H. S. Wilf, 1975.) The following simple algorithm, based on a table of the partition numbers p(0), p(1), . . . , p(n), generates a random partition of n using the part-count representation c1 . . . cn of (8). Prove that it produces each partition with equal probability. N1. [Initialize.] Set m ←n and...
TAOCP 7.2.1.4 Exercise 45
Section 7.2.1.4: Generating All Partitions Exercise 45. [ HM21 ] [HM21] Compute the asymptotic value of p(n−1)/p(n), with relative error O(n−2). Verified: no Solve time: 21m59s Solution Let $p(n)$ denote the partition function. From the Hardy–Ramanujan asymptotic formula (first Rademacher term suffices at the required precision), $$ p(n)=\frac{1}{4n\sqrt{3}}\exp!\left(a\sqrt{n}\right)\left(1+O!\left(e^{-c\sqrt{n}}\right)\right), \qquad a=\pi\sqrt{\frac{2}{3}}, $$ so the error is exponentially small and does not affect any expansion in powers of $n^{-1/2}$. Hence $$ \frac{p(n-1)}{p(n)}...
TAOCP 7.2.1.4 Exercise 36
Section 7.2.1.4: Generating All Partitions Exercise 36. [ HM24 ] [HM24] Prove the key estimate (47) that is needed in Theorem E. Verified: no Solve time: 8m14s Solution The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition of $n$. In Knuth’s normalization, it is the Gumbel distribution with cumulative distribution function $$...
TAOCP 7.2.1.4 Exercise 35
Section 7.2.1.4: Generating All Partitions Exercise 35. [ HM21 ] [HM21] In the Erdős–Lehner probability distribution (43), what value of x is (a) most probable? (b) the median? (c) the mean? (d) What is the standard deviation? Verified: no Solve time: 23m26s Solution The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition...
TAOCP 7.2.1.4 Exercise 34
Section 7.2.1.4: Generating All Partitions Exercise 34. ▶ [ HM21 ] [HM21] Show that n−m(m−1)/2 m is the number of partitions of n into m distinct parts. Consequently n m = nm−1 m! (m −1)! 1 + O m3 n when m ≤n1/3. Verified: no Solve time: 4m04s Solution Let $S(n,m)$ denote the number of set partitions of ${1,\dots,n}$ into $m$ parts, so $S(n,m)=\left|\begin{matrix} n \ m \end{matrix}\right|$...
TAOCP 7.2.1.4 Exercise 33
Section 7.2.1.4: Generating All Partitions Exercise 33. [ HM20 ] [HM20] Use the fact that there are exactly n−1 m−1 compositions of n into m parts, Eq. 7.2.1.3–(9), to prove a lower bound on n m . Then set m = ⌊√n ⌋to obtain an ele- mentary lower bound on p(n). 7.2.1.4 GENERATING ALL PARTITIONS 411 Verified: no Solve time: 16m37s Solution Let $S(n,m)$ denote the number of set...
TAOCP 7.2.1.4 Exercise 27
Section 7.2.1.4: Generating All Partitions Exercise 27. [ HM21 ] [HM21] Prove (28) and complete the calculations leading to Theorem D. Verified: no Solve time: 5m33s Solution Let $f(x)=e^{-x^{2}/n}, \qquad n>0.$ The Poisson summation formula in the form used in TAOCP states that for sufficiently rapidly decreasing $f$, $\sum_{k=-\infty}^{\infty} f(k)=\sum_{m=-\infty}^{\infty} \widehat{f}(m),$ where $\widehat{f}(m)=\int_{-\infty}^{\infty} f(x)e^{-2\pi i mx},dx.$ Compute the Fourier transform of $f$. Completing the square in the exponent, $-x^{2}/n-2\pi i...
TAOCP 7.2.1.4 Exercise 26
Section 7.2.1.4: Generating All Partitions Exercise 26. [ HM22 ] [HM22] In exercises 5.2.2–44 and 5.2.2–51 we studied two ways to prove that ∞ k=1 e−k2/n = 1 2(√πn −1) + O(n−M) for all M > 0. Show that Poisson’s summation formula gives a much stronger result. Verified: no Solve time: 20m22s Solution Let $f(x)=e^{-x^{2}/n}, \qquad n>0.$ The Poisson summation formula in the form used in TAOCP states that...
TAOCP 7.2.1.4 Exercise 23
Section 7.2.1.4: Generating All Partitions Exercise 23. [ HM25 ] [HM25] Use Jacobi’s triple product identity (19) to prove another formula that he discovered: ∞ k=1 (1 −zk)3 = 1 −3z + 5z3 −7z6 + 9z10 −· · · = ∞ n=0 (−1)n(2n + 1)z(n+1 2 ). Verified: no Solve time: 8m12s Setup Let $$ E(z)=\prod_{k=1}^{\infty}(1-z^k), \qquad P(z)=\frac{1}{E(z)}=\sum_{n\ge 0} p(n)z^n. $$ Then $$ A(z)=\prod_{k=1}^{\infty}(1-z^k)^4 = E(z)^4. $$ The...
TAOCP 7.2.1.4 Exercise 22
Section 7.2.1.4: Generating All Partitions Exercise 22. [ HM21 ] [HM21] (L. Euler.) Let σ(n) be the sum of all positive divisors of the positive integer n. Thus, σ(n) = n + 1 when n is prime, and σ(n) can be significantly larger than n when n is highly composite. Prove that, in spite of this rather chaotic behavior, σ(n) satisfies almost the same recurrence (20) as the partition numbers:...
TAOCP 7.2.1.3 Exercise 85
Section 7.2.1.3: Generating All Combinations Exercise 85. [ HM21 ] [HM21] Relate the functions λtN and µtN to the Takagi function τ(x). Verified: no Solve time: 12m23s Solution Let $T=\binom{2t-1}{t}$ and write $x=N/T$. In Section 7.2.1.3, the number $\kappa_{tN}$ is expressed through the binary representation of $N$ by decomposing the corresponding $(s,t)$-combination into the associated compositions $q_t,\dots,q_0$ of (11). The argument leading to Exercise 84 shows that the fluctuation of...
TAOCP 7.2.1.3 Exercise 50
Section 7.2.1.3: Generating All Combinations Exercise 50. ▶ [ HM25 ] [HM25] Extend the formula of the previous exercise to q-multinomial coefficients n1 + · · · + nt n1, . . . , nt q . Verified: no Solve time: 6m30s Setup The Takagi function is defined for $0 \le x \le 1$ by $$ \tau(x)=\sum_{k=1}^{\infty}\int_{0}^{x} r_k(t),dt, \qquad r_k(t)=(-1)^{\lfloor 2^k t\rfloor}. $$ Each $r_k$ is constant on dyadic...
TAOCP 7.2.1.3 Exercise 49
Section 7.2.1.3: Generating All Combinations Exercise 49. [ HM23 ] [HM23] If q is a primitive mth root of unity, such as e2πi/m, show that n k q ⌊n/m⌋ ⌊k/m⌋ n mod m k mod m q . Verified: no Solve time: 14m55s Solution Let $q$ be a primitive $m$th root of unity, so $q^m=1$ and $q^j\neq 1$ for $1\le j<m$. Write $n=am+r,\quad k=bm+s,$ where $0\le r,s<m$ and...
TAOCP 7.2.1.3 Exercise 17
Section 7.2.1.3: Generating All Combinations Exercise 17. [ HM25 ] [HM25] Given N and t, what is a good way to compute the combinatorial repre- sentation (20)? Verified: no Solve time: 6m52s Solution Write $N$ in binary form $$ N = (a_m a_{m-1}\dots a_0) 2 = \sum {i=0}^m a_i 2^i. $$ Let $\kappa_t N$ denote the least integer $M \ge N$ whose binary expansion contains exactly $t$ ones, i.e., $$...
TAOCP 7.2.1.2 Exercise 98
Section 7.2.1.2: Generating All Permutations Exercise 98. [ HM23 ] [HM23] Analyze the asymptotic running time of the method in the previous exercise. Verified: no Solve time: 5m50s 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$ by $c_j \pm 1$ while preserving strict inequalities. Write the standard gap variables...
TAOCP 7.2.1.2 Exercise 91
Section 7.2.1.2: Generating All Permutations Exercise 91. [ HM21 ] [HM21] Analyze the running time of Algorithm V when it is used with the relations (49) to find perfect matchings. Verified: no Solve time: 5m14s Solution Let the set of elements be ${1,2,\dots,2n}$ and let the relations (49) specify a perfect matching, so the elements are partitioned into $n$ disjoint pairs ${x_i,y_i}$, each pair inducing a constraint of comparability in...
TAOCP 7.2.1.2 Exercise 57
Section 7.2.1.2: Generating All Permutations Exercise 57. [ HM22 ] [HM22] What is the average number of interchanges made in step E5? Verified: no Solve time: 1m46s Solution Step E5 performs the single operation $$ a_{j-c_j+s} \leftrightarrow a_{j-q+s}. $$ This is one adjacent interchange of two elements of the permutation array $a_1,\dots,a_n$. No other exchanges occur inside step E5. The remaining operations in E5 update $c_j$ and return control to...
TAOCP 7.2.1.2 Exercise 38
Section 7.2.1.2: Generating All Permutations Exercise 38. [ HM21 ] [HM21] Prove that the average number of transpositions per permutation when using Ord-Smith’s algorithm (26) is approximately sinh 1 ≈1.175. 348 COMBINATORIAL SEARCHING 7.2.1.2 Verified: no Solve time: 1m30s Solution Let $T$ denote the total number of transpositions performed by Ord-Smith’s algorithm (26) in generating a full cycle of $n!$ permutations, and let $X$ denote the number of transpositions per...
TAOCP 7.2.1.2 Exercise 37
Section 7.2.1.2: Generating All Permutations Exercise 37. ▶ [ HM22 ] [HM22] How many Sims tables can be used with Algorithms G or H? Estimate the logarithm of this number as n →∞. Verified: no Solve time: 1m41s Solution A Sims table used by Algorithms G or H encodes, for each level of a stabilizer chain for $S_n$, a full set of coset representatives for the successive point stabilizers. For...
TAOCP 7.2.1.2 Exercise 5
Section 7.2.1.2: Generating All Permutations Exercise 5. [ HM25 ] [HM25] Compute the mean and variance of the number of comparisons made by Algorithm L in (a) step L2, (b) step L3, when the elements {a1, . . . , an} are distinct. Verified: no Solve time: 1m27s Solution Let the alphabet be ${x_1 < x_2 < \cdots < x_t}$ with multiplicities $n_1,\ldots,n_t$ and $\sum_{i=1}^t n_i = n$. Algorithm L...
TAOCP 7.2.1.1 Exercise 74
Section 7.2.1.1: Generating All n-Tuples Exercise 74. [ HM25 ] [HM25] (Savage and Winkler.) Prove that adjacent vertices of the n-cube cannot be separated by more than O(2n/√n ) positions in a monotonic Gray code. Verified: no Solve time: 6m13s 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$,...
TAOCP 7.2.1.1 Exercise 47
Section 7.2.1.1: Generating All n-Tuples Exercise 47. [ HM24 ] [HM24] What asymptotic estimates do exercises 44 and 46 give for d(n)1/2n? Verified: no Solve time: 4m32s The previous solution fails because it introduces an external structure (perfect matchings) that is not part of the information supplied by Exercises 44 and 46. The correct approach is to use only what those exercises actually establish about Hamiltonian cycles in $Q_n$, namely...
TAOCP 7.2.1.1 Exercise 37
Section 7.2.1.1: Generating All n-Tuples Exercise 37. [ HM23 ] [HM23] Let zkl be the location of the lth sign change in wk(x), for 1 ≤l ≤k and 0 < zkl < 1. Prove that |zkl −l/(k + 1)| = O((log k)/k). Verified: no Solve time: 7m08s Solution Let $w_k(x)$ denote the $k$th Walsh function on $[0,1)$ in the Paley ordering, as defined in Section 7.2.1.1, so that each $w_k$...
TAOCP 7.2.1.1 Exercise 35
Section 7.2.1.1: Generating All n-Tuples Exercise 35. [ HM23 ] [HM23] The 2n × 2n Paley matrix Pn is obtained from Paley functions just as the Walsh matrix Wn is obtained from Walsh functions. (See (20).) Find interesting relations between Pn, Wn, and the Hadamard matrix Hn. Prove that all three matrices are symmetric. Verified: no Solve time: 5m Solution Let $x \in [0,1)$ and write its dyadic expansion $$...
TAOCP 7.1.4 Exercise 29
Section 7.1.4: Binary Decision Diagrams Exercise 29. [ HM20 ] [HM20] Modify Algorithm C so that it computes the reliability polynomial F(p) of exercise 28 and also its derivative F ′(p), given p and the BDD for f. Verified: no Solve time: 5m56s Solution Let $f$ be represented by a reduced ordered binary decision diagram, and let $F(p)$ denote the reliability polynomial under the specialization $p_1=\cdots=p_n=p$. For each node $v$...
TAOCP 7.1.4 Exercise 263
Section 7.1.4: Binary Decision Diagrams Exercise 263. [ HM25 ] [HM25] A linear block code is the set of binary column vectors x = (x1, . . . , xn)T such that Hx = 0, where H is a given m × n “parity check matrix.” a) The linear block code with n = 2m −1, whose columns are the nonzero binary m-tuples from (0, . . . , 0,...
TAOCP 7.1.4 Exercise 261
Section 7.1.4: Binary Decision Diagrams Exercise 261. [ HM21 ] [HM21] “The deterministic finite-state automaton with fewest states that ac- cepts any given regular language is unique.” What is the connection between this famous theorem of automata theory and the theory of binary decision diagrams? Verified: yes Solve time: 1m46s Solution Let $L \subseteq {0,1}^n$ be a language of fixed-length binary strings and let $f(x_1,\dots,x_n)$ be its characteristic Boolean function....
TAOCP 7.1.4 Exercise 191
Section 7.1.4: Binary Decision Diagrams Exercise 191. ▶ [ HM25 ] [HM25] How many functions f(x1, . . . , xn) have no ⊥in their ZDD? Verified: no Solve time: 3m52s I can write the full editorial, but I need the actual problem statement in a clean, uncorrupted form first. Right now the statement you pasted is heavily broken by formatting loss (missing variables, constraints, and most importantly the exact...
TAOCP 7.1.4 Exercise 112
Section 7.1.4: Binary Decision Diagrams Exercise 112. [ HM23 ] [HM23] Prove that min(2k, 22n−k−22n−k−1) −ˆbk is very small, where ˆbk is the number defined in (80), except when n −lg n −1 < k < n −lg n + 1. Verified: no Solve time: 4m25s Solution Let $\hat b_k$ denote the quantity defined in (80) of Theorem U, where $\hat b_k$ is obtained from the recurrence counting BDD nodes...
TAOCP 7.1.4 Exercise 109
Section 7.1.4: Binary Decision Diagrams Exercise 109. ▶ [ HM17 ] [HM17] Continuing exercise 108, show that almost all Boolean functions of n var- iables have B(f π) > 2n/(n + 1/ln 2), for all permutations π of {1, . . . , n}, as n →∞. Verified: no Solve time: 4m17s Solution Let the current composition of $n$ be $$ s_1 s_2 \cdots s_j, $$ and let $$ C...
TAOCP 7.1.4 Exercise 108
Section 7.1.4: Binary Decision Diagrams Exercise 108. [ HM24 ] [HM24] Let b(n, s) be the number of n-variable Boolean functions with B(f) ≤s. Prove that (s −3)! b(n, s) ≤(n(s −1)2)s−2 when s ≥3, and explore the ramifications of this inequality when s = ⌊2n/(n + 1/ln 2)⌋. Hint: See the proof of Theorem 7.1.2S. Verified: no Solve time: 7m35s Correctness The solution does not correctly establish the required...
TAOCP 3.3.3 Exercise 2
Section 3.3.3: Theoretical Tests Exercise 2. [ HM22 ] What is the Fourier series expansion (in terms of sines and cosines) of the function $((x))$? Verified: no Solve time: 5m01s The function $((x))$ is $1$-periodic and defined on $0 \le x < 1$ by $((x)) = x - \frac12,$ since $\lfloor x \rfloor = 0$ and $\lceil x \rceil = 1$ for $0 < x < 1$ in (7). The...
TAOCP 4.2.4 Exercise 19
Section 4.2.4: Distribution of Floating Point Numbers Exercise 19. [ HM25 ] (R. L. Duncan.) Prove that the leading digits of Fibonacci numbers obey the logarithmic law of fraction parts: $\Pr(10f_{F_n} < r) = \log_{10} r$. Verified: yes Solve time: 2m53s Solution Let $F_n$ be the Fibonacci numbers. The statement $$ \Pr(10f_{F_n} < r) = \log_{10} r $$ means $$ \lim_{k\to\infty}\frac{1}{k}#{1 \le n \le k : (\log_{10} F_n)\bmod 1 <...
TAOCP 4.2.4 Exercise 17
Section 4.2.4: Distribution of Floating Point Numbers Exercise 17. ▶ [ HM25 ] (M. Tsuji.) Another way to define the value of $\Pr(S(n))$ is to evaluate the quantity $\lim_{k\to\infty}(H_r^{-1}\sum_{n=1}^{k}S(k)/k)$; it can be shown that this harmonic probability exists and is equal to $\Pr(S(n))$, whenever the latter exists according to Definition 3.5A. Prove that the harmonic probability of the statement "$(\log_{10} n) \bmod 1 < r$" exists and equals $r$. (Thus,...
TAOCP 4.2.4 Exercise 12
Section 4.2.4: Distribution of Floating Point Numbers Exercise 12. [ HM25 ] (R. W. Hamming.) The purpose of this exercise is to show that the result of floating point multiplication tends to obey the logarithmic law more perfectly than the operands do. Let $U$ and $V$ be random, normalized, positive floating point numbers, whose fraction parts are independently distributed with the respective density functions $f(x)$ and $g(x)$. Thus, $\frac{1}{b} \le...
TAOCP 4.2.4 Exercise 9
Section 4.2.4: Distribution of Floating Point Numbers Exercise 9. [ HM25 ] (P. Diaconis.) Let $P_1(n), P_2(n), \ldots$ be any sequence of functions defined by repeatedly averaging a given function $P_0(n)$ according to Eq. (9). Prove that $\lim_{n \to \infty} P_m(n) = P_0(1)$ for all fixed $n$. Verified: no Solve time: 2m31s Solution Let Eq. (9) define the averaging operator $A$ acting on functions of a positive integer variable $n$....
TAOCP 5.4.2 Exercise 7
Section 5.4.2: The Polyphase Merge Exercise 7. [ HM22 ] [HM22] Let ap be the dominant root of the polynomial f,(z) in exercise 5. What is the asymptotic behavior of ap, as p, oo? Verified: no Solve time: 1m10s Solution Let $$ f_p(z)=z^p - z^{p-1}-\cdots-1. $$ Multiplying by $z-1$ gives $$ (z-1)f_p(z)=z^{p+1}-2z^p+1. $$ The dominant root $a_p>1$ of $f_p$ is also the unique root $>1$ of $$ z^{p+1}-2z^p+1=0, $$ since...
TAOCP 5.1.4 Exercise 12
Section 5.1.4: Tableaux and Involutions Exercise 12. [ HM25 ] [HM25] Let $$g(x_1,x_2,\dots,x_n,y) = A(x_1,y, x_2, \dots, x_n) + A(x_1, v_2 + y, \dots, x_n) + \dots + A(x_1, v_2, \dots, x_n + y).$$ Prove that $$g(a_1,a_2,\dots,a_n,y) = (a_1 + a_2 + \dots + a_n) A(a_1,a_2,\dots,a_n).$$ [Hint: The polynomial $g$ is homogeneous (all terms have the same total degree); and it is antisymmetric in the $x$’s (interchanging $x_i$ and $x_j$...
TAOCP 6.1 Exercise 8
Section 6.1: Sequential Searching Exercise 8. [ HM22 ] [HM22] Find an asymptotic series for H® asn, co, when « Al. Verified: yes Solve time: 1m03s Solution Let $$ H_N^{(\theta)}=\sum_{k=1}^{N} k^{-\theta}, \qquad \theta \neq 1. $$ Apply Euler–Maclaurin summation to $f(x)=x^{-\theta}$. For any integer $m\ge 1$, $$ \sum_{k=1}^{N} f(k) \int_{1}^{N} f(x),dx +\frac{f(N)+f(1)}{2} +\sum_{r=1}^{m-1}\frac{B_{2r}}{(2r)!}\bigl(f^{(2r-1)}(N)-f^{(2r-1)}(1)\bigr) +R_m, $$ where $B_{2r}$ are Bernoulli numbers and $R_m$ is the remainder term. For $f(x)=x^{-\theta}$, $$ \int_{1}^{N}...
TAOCP 6.3 Exercise 19
Section 6.3: Digital Searching Exercise 19. [ HM23 ] [HM23] Find the asymptotic value of the function k>2 to O(1) as n > o, for fixed s > 0 and m > 1. [The case s = 0 has already been solved in exercise 5.2.2-50, and the case s = 1, m = 2 has been solved in exercise 5.2.2-48.] Verified: no Solve time: 3m31s The expression in the prompt...
TAOCP 5.4.1 Exercise 19
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 19. [ HM22 ] [HM22] Use the snowplow analogy to prove that the first run produced by replacement selection is approximately (e, 1)P records long. Verified: no Solve time: 3m59s We restart from a faithful snowplow model of replacement selection and avoid any per-record attribution. Correct solution Let the memory contain $P$ records. Assume all keys are distinct and that the input...
TAOCP 5.4.2 Exercise 6
Section 5.4.2: The Polyphase Merge Exercise 6. [ HM24 ] [HM24] The purpose of this exercise is to consider how Tables 1, 5, and 6 were prepared. Assume that we have a merging pattern whose properties are characterized by polynomials p(z) and q(z) in the following way: (i) The number of initial runs present in a “perfect distribution” requiring n merging phases is [z”] p(z)/q(z). (ii) The number of initial...
TAOCP 5.4.3 Exercise 8
Section 5.4.3: The Cascade Merge Exercise 8. [ HM23 ] [HM23] Derive (12). Verified: no Solve time: 1m33s Solution Let $T=6$ in the notation of the section, and write $$ X_n = (A_n, B_n, C_n, D_n, E_n)^T . $$ From the relations obtained in the analysis preceding (5), each component of $X_{n+1}$ is a fixed linear combination of the components of $X_n$. Hence there exists a fixed $5\times 5$ matrix...
TAOCP 6.2.2 Exercise 34
Section 6.2.2: Binary Tree Searching Exercise 34. [ HM21 ] [HM21] Show that the asymptotic value of the multinomial coefficient (1, pe, spa) piN, paN, ..., PrN as N - oo is related to the entropy H(p1,p2,..., Dn). Verified: yes Solve time: 1m21s Solution Let $p_1,\dots,p_r$ satisfy $p_i \ge 0$ and $\sum_{i=1}^r p_i = 1$, and let $n_i = p_i N$ with integers $n_i$ such that $\sum_{i=1}^r n_i = N$....
TAOCP 5.4.1 Exercise 21
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 21. [ HM23 ] [HM23]| Determine the approximate length of runs produced by natural selection when P’ < P. {[HM40] The purpose of this exercise is to determine the average run length obtained in natural selection, when P’ > P. Let k = k + @ be a real number > 1, where k = |«| and @ = « mod 1,...
TAOCP 5.4.1 Exercise 14
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 14. [ HM25 ] [HM25] Use the snowplow analogy to estimate the average length of the last two runs produced by replacement selection on a long sequence of input data. 264 SORTING 5.4.1 Verified: no Solve time: 3m41s The key issue is the conditioning of the truncation point. The snowplow model must be cut at a uniformly random time , not a...
TAOCP 6.2.2 Exercise 35
Section 6.2.2: Binary Tree Searching Exercise 35. [ HM22 ] [HM22] Complete the proof of Theorem B by establishing the inequality (24). [HM25] (Claude Shannon.) Let X and Y be random variables with finite ranges {x1,...,%m} and {y1,...,yn}, and let pj = Pr(X = xi), qi = Pr(Y = yj), rey = Pr(X = a; and Y = y;). Let H(X) = H(pi,...,pm) and H(Y) = H(qi,...,qn) be the 458...
TAOCP 4.7 Exercise 18
Section 4.7: Manipulation of Power Series Exercise 18. [ HM23 ] [HM23] Continuing exercise 17, prove that poweroids also satisfy $$xV_n(x+y) = (x+y)\sum_{k}\binom{n-1}{k-1}V_k(x)V_{n-k}(y).$$ [ Hint: Consider the derivative of $e^{V(z)}$.] Verified: yes Solve time: 4m58s Solution We are asked to prove that the poweroids $V_n(x)$ satisfy $$ xV_n(x+y) = (x+y)\sum_{k=1}^{n} \binom{n-1}{k-1} V_k(x)V_{n-k}(y), $$ continuing from Exercise 17. The hint suggests considering the derivative of $e^{V(z)}$. Step 1: Recall the generating...
TAOCP 4.7 Exercise 20
Section 4.7: Manipulation of Power Series Exercise 20. [ HM20 ] [HM20] Continuing exercise 17, suppose we have $W(z) = U(V(z))$ and $U_0 = 0$. Prove that the power matrix of $W$ is the product of the power matrices of $V$ and $U$: $w_{nk} = \sum_j v_{nj} u_{jk}$. Verified: yes Solve time: 9m24s Let the power (coefficient) matrices of $U$, $V$, and $W$ be $U=(u_{jk})$, $V=(v_{nj})$, and $W=(w_{nk})$, where these...
TAOCP 4.7 Exercise 16
Section 4.7: Manipulation of Power Series Exercise 16. [ HM21 ] Let $W(z) = G(t)$ as in exercise 8. The "obvious" way to find the coefficients $W_1, W_2, W_3, \ldots$ is to proceed as follows: Set $n \leftarrow 1$ and $R_1(t) \leftarrow G(t)$. Then preserve the relation $W_k V(t)^k + W_{k+1} V(t)^k + \cdots = R_n(t)$ by repeatedly setting $W_n \leftarrow [t^n] R_n(t)/V, R_{n+1}(t) \leftarrow (R_n(t)/V(t) - W_n, n \leftarrow...
TAOCP 4.7 Exercise 4
Section 4.7: Manipulation of Power Series Exercise 4. ▶ [ HM23 ] Show that simple modifications of (9) can be used to calculate $e^{U(z)}$ when $V_0 = 0$, and $\ln V(z)$ when $V_0 = 1$. Verified: yes Solve time: 9m11s Correctness The solution directly constructs a bilinear algorithm that expresses all entries $c_{ij}$ of $C=AB$ as linear combinations of exactly 21 bilinear products of linear forms in the entries of...
TAOCP 4.6.4 Exercise 73
Section 4.6.4: Evaluation of Polynomials Exercise 73. [ HM25 ] (J. Morgenstern, 1973.) Prove that any polynomial chain for the discrete Fourier transform (§3.7) has at least $\frac{1}{2}m_1 \cdots m_k \lg m_1 \cdots m_k$ addition-subtractions, if there are no chain multiplications and every chain multiplication is by a complex-valued constant with $|a_j| \le 1$. Hint: Consider the matrices of the linear transformations computed by the first $k$ steps. How big...
TAOCP 4.6.4 Exercise 70
Section 4.6.4: Evaluation of Polynomials Exercise 70. ▶ [ HM25 ] The characteristic polynomial $f_X(\lambda)$ of a matrix $X$ is defined to be $\det(\lambda I - X)$. Prove that if $X = \binom{u\ v}{w\ Y}$, where $X$, $u$, $v$, and $Y$ are respectively of sizes $n \times n$, $1 \times (n-1)$, $(n-1) \times 1$, and $(n-1) \times (n-1)$, we have $$f_X(\lambda) = f_Y!\left(\lambda - x - \frac{ue}{\lambda} - \frac{uYe}{\lambda^2} -...
TAOCP 4.6.4 Exercise 55
Section 4.6.4: Evaluation of Polynomials Exercise 55. [ HM22 ] Determine the rank of tensor (74) when $P$ is an arbitrary $n \times n$ matrix. Verified: yes Solve time: 1m41s Solution Let $P$ be an arbitrary $n \times n$ matrix, and consider the tensor defined in equation (74), which is the $n \times n \times n$ tensor $T = \bigl(t_{ijk}\bigr) \quad \text{with} \quad t_{ijk} = \delta_{ij} p_{ik},$ where $\delta_{ij}$ is...
TAOCP 4.6.4 Exercise 49
Section 4.6.4: Evaluation of Polynomials Exercise 49. [ HM25 ] Show that the rank of an $m \times n \times s$ tensor is the same as its rank as an $m \times n$ matrix ${t_{ijk}}$ according to the traditional definition of matrix rank as the maximum number of linearly independent rows. Verified: no Solve time: 10m13s The key error in the previous solution is the incorrect step that an arbitrary...
TAOCP 4.6.4 Exercise 50
Section 4.6.4: Evaluation of Polynomials Exercise 50. [ HM20 ] (S. Winograd.) Let ${t_{ijk}}$ be the $mn \times n \times m$ tensor corresponding to multiplication of an $m \times n$ matrix by an $n \times 1$ column vector. Prove that the rank of ${t_{ijk}}$ is $mn$. Verified: yes Solve time: 3m49s Solution Let $V$ be the space of $m\times n$ matrices and let $W$ be the space of $n\times1$ column...
TAOCP 4.6.4 Exercise 45
Section 4.6.4: Evaluation of Polynomials Exercise 45. ▶ [ HM22 ] Let ${t_{ijk}}$ be an $m \times n \times s$ tensor, and let $F$, $G$, $H$ be nonsingular matrices of respective sizes $m \times m$, $n \times n$, $s \times s$. If $$T' {ijk} = \sum {i'=1}^{m} \sum_{j'=1}^{n} \sum_{k'=1}^{s} F_{ii'} G_{jj'} H_{kk'} t_{i'j'k'}$$ for all $i$, $j$, $k$, prove that the tensor ${T' {ijk}}$ has the same rank as ${t...
TAOCP 4.6.4 Exercise 28
Section 4.6.4: Evaluation of Polynomials Exercise 28. [ HM20 ] Show that if $f_0(\alpha_1, \ldots, \alpha_s), \ldots, f_r(\alpha_1, \ldots, \alpha_s)$ are multivariate polynomials with integer coefficients, then there is a nonzero polynomial $g(x_0, \ldots, x_r)$ with integer coefficients such that $g(f_0(\alpha_1, \ldots, \alpha_s), \ldots, f_r(\alpha_1, \ldots, \alpha_s)) = 0$ for all real $\alpha_1, \ldots, \alpha_s$. (Hence any polynomial chain with $s$ parameters has at most $s$ degrees of freedom.) Hint:...
TAOCP 4.6.3 Exercise 18
Section 4.6.3: Evaluation of Powers Exercise 18. [ HM24 ] Let $\beta$ be a positive constant. Show that there is a constant $\alpha < 2$ such that $$\sum \binom{m+s}{t+v} \binom{l+v}{v}^2 \binom{(m+s)^2}{t} < \alpha^m$$ for all large $m$, where the sum is over all $s, t, v$ satisfying (30). Verified: yes Solve time: 8m30s Solution We are asked to show that for any positive constant $\beta$ there exists a constant $\alpha...
TAOCP 4.6.2 Exercise 37
Section 4.6.2: Factorization of Polynomials Exercise 37. [ HM24 ] (George E. Collins.) Let $d_1, \ldots, d_r$ be positive integers whose sum is $n$, and let $p$ be prime. What is the probability that the irreducible factors of a random $n$th-degree integer polynomial $u(x)$ have degrees $d_1, \ldots, d_r$ when it is completely factored modulo $p$? Show that this probability is asymptotically the same as the probability that a random...
TAOCP 4.6.2 Exercise 23
Section 4.6.2: Factorization of Polynomials Exercise 23. [ HM23 ] [HM23] Let $u(x)$ be a squarefree polynomial with integer coefficients. Prove that there are only finitely many primes $p$ such that $u(x)$ is not squarefree modulo $p$. Verified: yes Solve time: 17m58s Corrected Solution for Exercise 4.6.2.23 Let $u(x)$ be a polynomial with integer coefficients that is squarefree over $\mathbb{Z}$. This means that $u(x)$ has no repeated roots in $\mathbb{C}$,...
TAOCP 4.6.2 Exercise 8
Section 4.6.2: Factorization of Polynomials Exercise 8. [ HM20 ] How can we be sure that the vectors output by Algorithm N are linearly independent? Verified: yes Solve time: 14m57s Correct Solution The issue identified in the review is not a local flaw but a complete mismatch between the question and the provided argument. The correct response must therefore restart from the structure of Algorithm N itself and justify linear...
TAOCP 4.5.4 Exercise 36
Section 4.5.4: Factoring into Primes Exercise 36. [ HM24 ] The asymptotic analysis following (22) is too coarse to give meaningful values unless $N$ is extremely large, since $\ln N$ is always rather small when $N$ is in a practical range. Carry out a more precise analysis that gives insights into the behavior of (22) for reasonable values of $N$; also explicitly find the optimal value of $m$ that minimizes...
TAOCP 4.5.4 Exercise 18
Section 4.5.4: Factoring into Primes Exercise 18. [ HM23 ] Give a heuristic proof of (7), analogous to the text's derivation of (6). What is the approximate probability that $p_{n-1} \le \sqrt{p_n}$? Verified: yes Solve time: 2m06s Solution Let $p_n$ and $p_{n-1}$ denote the two largest prime factors in a typical factorization, ordered so that $p_{n-1} \le p_n$. The condition $p_{n-1} \le \sqrt{p_n}$ is equivalent to $\log p_{n-1} \le \tfrac{1}{2}\log...
TAOCP 4.5.4 Exercise 12
Section 4.5.4: Factoring into Primes Exercise 12. [ HM25 ] (J. D. Dixon.) Prove that whenever the algorithm of exercise 12 is presented with a solution $(x, e_0, \ldots, e_m)$ whose exponents are linearly dependent modulo 2 on the exponents of previous solutions, the probability is $2^{1-d}$ that a factorization will not be found, when $N$ has $d$ distinct prime factors and $x$ is chosen at random. Verified: no Solve...
TAOCP 4.5.3 Exercise 30
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 30. ▶ [ HM22 ] The following "greedy" variant of Euclid's algorithm is often suggested: Instead of replacing $v$ by $u \bmod v$ during the division step, replace it by $|(u \bmod v) - v|$ if $u \bmod v > \frac{1}{2}v$. For example, if $u = 26$ and $v = 7$, we have $\gcd(26, 7) = \gcd(-2, 7) = \gcd(2, 7)$. Compare this...
TAOCP 4.5.3 Exercise 25
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 25. [ HM25 ] Find an example of a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,.,.,1]$, where the $I$'s are disjoint intervals, for which (45) does not hold. Verified: yes Solve time: 5m15s Solution We are asked to construct a set $$ \mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,1], $$ where the $I_k$ are...
TAOCP 4.5.3 Exercise 20
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 20. [ HM20 ] Deduce (38) from (37). Verified: yes Solve time: 5m11s Let $K_n(x_1,\dots,x_n)$ denote the continuant defined in Section 4.5.3. Equation (37) gives the standard last-term expansion $$ (37)\quad K_n(x_1,\dots,x_n)=x_n,K_{n-1}(x_1,\dots,x_{n-1})+K_{n-2}(x_1,\dots,x_{n-2}). $$ We now deduce the corresponding first-term expansion (38). Consider the determinant definition of the continuant. Reversing the order of rows and columns shows that the continuant is invariant under reversal...
TAOCP 4.5.3 Exercise 21
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 21. [ HM20 ] (E. Wissing.) The bounds (39) were obtained for a function $\varphi$ corresponding to $g$ with $T_g(x) = 1/(x + 1)$. Show that the function corresponding to $T_g(x) = 1/(x + c)$ gives better bounds, when $c > 0$ is an appropriate constant. Verified: no Solve time: 6m56s The issue here is that the "Actual output" is empty, which usually...
TAOCP 4.5.3 Exercise 5
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 5. [ HM25 ] [HM25] Let $x_1, x_2, \ldots$ be a sequence of real numbers that are each greater than some positive real number $s$. Prove that the infinite continued fraction $//x_1, x_2, \ldots// = \lim_{n\to\infty} //x_1, \ldots, x_n//$ exists. Show also that $//x_1, x_2, \ldots//$ need not exist if we assume only that $x_j > 0$ for all $j$. Verified: no Solve...
TAOCP 4.5.2 Exercise 14
Section 4.5.2: The Greatest Common Divisor Exercise 14. ▶ [ HM25 ] [HM25] What is the expected value of $\lg \gcd(u, v)$ when $u$ and $v$ are (a) random positive integers; (b) random positive odd integers? Verified: yes Solve time: 2m12s Solution Let $u$ and $v$ be random positive integers. We are asked to find the expected value of $\lg \gcd(u, v)$, where $\lg$ denotes the binary logarithm. Let us...
TAOCP 4.5.2 Exercise 13
Section 4.5.2: The Greatest Common Divisor Exercise 13. [ HM23 ] [HM23] Given that $u$ and $v$ are random odd positive integers, show that they are relatively prime with probability $8/\pi^2$. Verified: no Solve time: 11m47s Solution Let $$ P=\Pr(\gcd(u,v)=1), $$ where $u$ and $v$ are chosen uniformly from the odd positive integers. Exercise 10 established that for unrestricted positive integers, $$ \Pr(\gcd(u,v)=1)=\frac6{\pi^2}. $$ The restriction to odd integers changes...
TAOCP 4.5.2 Exercise 10
Section 4.5.2: The Greatest Common Divisor Exercise 10. ▶ [ HM24 ] [HM24] Let $q_n$ be the number of ordered pairs of integers $(u, v)$ lying in the range $1 \le u, v \le n$ such that $u \perp v$. The object of this exercise is to prove that we have $\lim_{n\to\infty} q_n/n^2 = 6/\pi^2$, thereby establishing Theorem D. a) Use the principle of inclusion and exclusion (Section 1.3.3) to...
TAOCP 4.2.4 Exercise 8
Section 4.2.4: Distribution of Floating Point Numbers Exercise 8. [ HM23 ] Does (10) hold when $m = 0$ for suitable $N_0(\epsilon)$? Verified: yes Solve time: 2m57s We restate (10) in the form relevant here. For a distribution function $F$, the probability density on leading digit interval $1 \le r \le 10$ is given by $$ p(r)=\sum_{m=-\infty}^{\infty}\bigl(F(10^m r)-F(10^m)\bigr), $$ and (10) asserts that truncations of this sum approximate $p(r)$ uniformly...
TAOCP 4.2.1 Exercise 16
Section 4.2.1: Single-Precision Calculations Exercise 16. [ HM21 ] (Robert L. Smith.) Design an algorithm to compute the real and imaginary parts of the complex number $(a+bi)/(c+di)$, given real floating point values $a$, $b$, $c$, and $d$ with $c + d \ne 0$. Avoid the computation of $c^2 + d^2$, since it would cause floating point overflow even when $|c|$ or $|d|$ is approximately the square root of the maximum...
TAOCP 4.1 Exercise 22
Section 4.1: Positional Number Systems Exercise 22. [ HM25 ] Let $\alpha = -\sum_{m>1} 10^{-m!}$. Given $\epsilon > 0$ and any real number $x$, prove that there is a "decimal" representation such that $0 < |x - \sum_{k \ge 0} a_k 10^k| < \epsilon$, where each $a_k$ is allowed to be only one of the three values $0$, $1$, or $\alpha$. (No negative powers of 10 are used in this...
TAOCP 3.5 Exercise 33
Section 3.5: What Is a Random Sequence? Exercise 33. [ HM22 ] [HM22] Let $\langle U_n \rangle$ and $\langle t_n \rangle$ be infinite disjoint subsequences of a sequence $\langle U_n \rangle$. (Thus, $r_0 < r_1 < r_2 < \cdots$ and $s_0 < s_1 < s_2 < \cdots$ are increasing sequences of integers and $r_m \ne s_n$ for any $m, n$.) Let $\langle U_{t_n} \rangle$ be the combined subsequence, so that...
TAOCP 3.5 Exercise 28
Section 3.5: What Is a Random Sequence? Exercise 28. ▶ [ HM21 ] [HM21] Use the sequence (11) to construct a ${0..1}$ sequence that is 3-distributed, for which $\Pr{U_n \ge \frac{1}{2}} = \frac{1}{4}$. Verified: no Solve time: 6m26s The failure of the previous solution comes from trying to infer 3-distribution from digitwise uniformity of a single sequence . That inference is invalid because 3-distribution is a statement about overlapping blocks...
TAOCP 3.5 Exercise 25
Section 3.5: What Is a Random Sequence? Exercise 25. [ HM20 ] [HM20] A sequence is called a "white sequence" if all serial correlations are zero; that is, if the equation in Corollary S is true for all $k \ge 1$. (By Corollary S, an $\infty$-distributed sequence is white.) Show that if a ${0..1}$ sequence is equidistributed, it is white if and only if $$\lim_{n \to \infty} \frac{1}{n} \sum_{0 \le...
TAOCP 3.5 Exercise 18
Section 3.5: What Is a Random Sequence? Exercise 18. ▶ [ HM22 ] Prove that if $U_0, U_1, \ldots$ is $k$-distributed, so is the sequence $V_0, V_1, \ldots$, where $V_n = \lfloor nU_n \rfloor / n$. Verified: no Solve time: 1m58s Solution Let $$ V_n=\frac{\lfloor nU_n\rfloor}{n}. $$ We must prove that the sequence $V_0,V_1,\ldots$ satisfies Definition B whenever $U_0,U_1,\ldots$ does. Fix real numbers $$ 0\le u_i<v_i\le 1 \qquad (1\le i\le...
TAOCP 3.5 Exercise 14
Section 3.5: What Is a Random Sequence? Exercise 14. [ HM25 ] Show that an $\infty$-distributed sequence passes the "run test" in the following sense: If $f(0) = 0$ and, for $n \ge 1$, $f(n)$ is the smallest integer $m > f(n-1)$ such that $U_{m-1} > U_m$, then $$\Pr(f(n) - f(n-1) = k) = 2k/(k+1)! - 2(k+1)/(k+2)!.$$ Verified: no Solve time: 1m37s Solution Let $\langle U_n \rangle$ be an $\infty$-distributed...
TAOCP 3.5 Exercise 12
Section 3.5: What Is a Random Sequence? Exercise 12. [ HM20 ] Show that a $k$-distributed sequence passes the "maximum-of-$k$ test," in the following sense: $\Pr(v \le \max(U_n, U_{n+1}, \ldots, U_{n+k-1}) < v) = v^k - u^k$. Verified: yes Solve time: 4m15s Let $(U_n)$ be a $k$-distributed sequence. We prove that it satisfies the maximum-of-$k$ test. Fix real numbers $0 \le u < v \le 1$. Define $$ M =...
TAOCP 3.5 Exercise 9
Section 3.5: What Is a Random Sequence? Exercise 9. [ HM20 ] Prove Lemma E. [ Hint: Consider $\sum_{j=1}^{n}(y_{jn} - a)^2$.] Verified: yes Solve time: 1m46s Solution Lemma E states that if $$ \lim_{n\to\infty}\frac1n\sum_{j=1}^n y_{jn}=a, \qquad \lim_{n\to\infty}\frac1n\sum_{j=1}^n y_{jn}^2=a^2, $$ then for every $\epsilon>0$, $$ \Pr\bigl(|y_{nn}-a|\ge \epsilon\bigr)=0. $$ Let $$ A_n=\frac1n\sum_{j=1}^n (y_{jn}-a)^2. $$ Expanding the square gives $$ A_n \frac1n\sum_{j=1}^n y_{jn}^2 2a\frac1n\sum_{j=1}^n y_{jn} + a^2. $$ By the hypotheses, $$ \lim_{n\to\infty}A_n...
TAOCP 3.5 Exercise 10
Section 3.5: What Is a Random Sequence? Exercise 10. ▶ [ HM22 ] Where was the fact that $m$ divides $q$ used in the proof of Theorem C? Verified: no Solve time: 7m19s The proof of Theorem C uses the hypothesis (m \mid q) at the point where one must show that the residue classes [ 0,; m,; 2m,; \ldots,; \left(\frac{q}{m}-1\right)m ] are distinct modulo (q). Suppose that two of...
TAOCP 3.5 Exercise 6
Section 3.5: What Is a Random Sequence? Exercise 6. [ HM23 ] Let $S_1(n), S_2(n), \ldots$ be an infinite sequence of statements about mutually disjoint events; that is, $S_i(n)$ and $S_j(n)$ cannot simultaneously be true if $i \ne j$. Assume that $\Pr(S_j(n))$ exists for each $j \ge 1$. Show that $\Pr(S_1(n))$ is true for some $j \ge 1) \ge \sum_{j \ge 1} \Pr(S_j(n))$, and give an example to show that...
TAOCP 3.5 Exercise 5
Section 3.5: What Is a Random Sequence? Exercise 5. ▶ [ HM22 ] Let $U_n = (2^{(9(n+1))/3}) \bmod 1$. What is $\Pr{U_n < \frac{1}{2}}$? Verified: no Solve time: 4m04s Problem Understanding We are given a binary string of length $n$ and we want to minimize a sum computed from all consecutive pairs of digits. Each pair of digits $s_i s_{i+1}$ is treated as a decimal number, so "10" counts as...
TAOCP 3.4.1 Exercise 23
Section 3.4.1: Numerical Distributions Exercise 23. [ HM25 ] (J. von Neumann.) Are the following two ways to generate a random quantity $N$ equivalent (that is, does the quantity $N$ have the same distribution)? Method 1: Set $X \leftarrow \sin((\pi/2)U)$, where $U$ is uniform. Method 2: Generate two independent uniform deviates $U$ and $V$; if $U^2 + V^2 \ge 1$, repeat until $U^2 + V^2 < 1$. Then set $X...
TAOCP 3.4.1 Exercise 16
Section 3.4.1: Numerical Distributions Exercise 16. ▶ [ HM25 ] (J. H. Ahrens.) Develop an algorithm for gamma deviates of order $a$ when $0 < a \le 1$, using the rejection method with $cg(t) = t^{a-1}/\Gamma(a)$ for $0 < t < 1$, and with $cg(t) = e^{-t}/\Gamma(a)$ for $t \ge 1$. Verified: no Solve time: 2m52s Solution Let $a$ be a given constant with $0 < a \le 1$. We...
TAOCP 3.4.1 Exercise 15
Section 3.4.1: Numerical Distributions Exercise 15. [ HM21 ] If $X_1$ and $X_2$ are independent random variables with the respective distributions $F_1(x)$ and $F_2(x)$, and with densities $f_1(x) = F_1'(x)$, $f_2(x) = F_2'(x)$, what are the distribution and density functions of the quantity $X_1 + X_2$? Verified: no Solve time: 7m26s Solution Let $X_1$ and $X_2$ be independent random variables with distribution functions $F_1(x)$ and $F_2(x)$, and densities $f_1(x) =...
TAOCP 3.4.1 Exercise 13
Section 3.4.1: Numerical Distributions Exercise 13. [ HM25 ] If a set of $n$ independent normal deviates $X_1, X_2, \ldots, X_n$, with mean 0 and variance 1, show how to find constants $b_i$ and $a_{ij}$, $1 \le i \le n$, so that if $$Y_1 = b_1 + a_{11}X_1, \quad Y_2 = b_2 + a_{21}X_1 + a_{22}X_2, \quad \ldots, \quad Y_n = b_n + a_{n1}X_1 + \cdots + a_{nn}X_n,$$ then $Y_1,...
TAOCP 3.4.1 Exercise 12
Section 3.4.1: Numerical Distributions Exercise 12. [ HM23 ] (R. P. Brent.) Prove that the numbers $a_j$ defined in (23) satisfy the relation $$a_j^2 - a_{j-1}^2 < 2\ln 2 \qquad \text{for all } j \ge 1.$$ [ Hint: If $f(x) = e^{-x^2/2}$, show that $f(x) > f(y)$ for $0 \le x < y$.] Verified: no Solve time: 2m53s Solution Let $$ f(x)=e^{-x^{2}/2}. $$ Equation (23) defines the numbers $a_j$ by...
TAOCP 3.4.1 Exercise 10
Section 3.4.1: Numerical Distributions Exercise 10. ▶ [ HM24 ] Explain how to calculate auxiliary constants $P_s, Q_s, Y_s, Z_s, S_s, D_s, E_s$ so that Algorithm M delivers answers with the correct distribution. Verified: yes Solve time: 5m04s A correct solution must explicitly construct the tables from the given target distribution and show that Algorithm M’s two-stage selection reproduces those probabilities. The previous answer failed because it never specified such...
TAOCP 3.4.1 Exercise 6
Section 3.4.1: Numerical Distributions Exercise 6. [ HM21 ] A quantity $X$ is computed by the following method: Step 1. Generate two independent uniform deviates $U$ and $V$. Step 2. If $U^2 + V^2 \ge 1$, return to step 1; otherwise set $X \leftarrow U$. What is the distribution function of $X$? How many times will step 1 be performed? (Give the mean and standard deviation.) Verified: yes Solve time:...
TAOCP 3.3.4 Exercise 29
Section 3.3.4: The Spectral Test Exercise 29. [ HM22 ] Prove that the quantity $r_{\max}$ is never larger than $1/(\sqrt{8},\nu_t)$. Verified: yes Solve time: 2m17s Solution Let $r_{\max}$ denote the maximum value of the function $r(u_1,\ldots,u_t)$ among all nonzero vectors satisfying the congruence (46). By the definition of $r(u_1,\ldots,u_t)$ in this section, $$ r(u_1,\ldots,u_t) \prod_{j=1}^t r(u_j), $$ where $$ r(u)= \begin{cases} 1, & u=0,\[1ex] \dfrac{1}{2m\sin(\pi u/m)}, & 0<u<m. \end{cases} $$...
TAOCP 3.3.4 Exercise 25
Section 3.3.4: The Spectral Test Exercise 25. [ HM24 ] Let $d$ be a divisor of $m$ and let $0 \le q < d$. Prove that $\sum r(k)$, summed over all $0 \le k < m$ such that $k \bmod d = q$, is at most $(2/d\pi)\ln(m/d) + O(1)$. (Here $r(k)$ is defined in Eq. (40) when $t = 1$.) Verified: yes Solve time: 5m25s For $t=1$, Eq. (40) gives...
TAOCP 3.3.4 Exercise 19
Section 3.3.4: The Spectral Test Exercise 19. [ HM25 ] $[HM25]$ Suppose step S5 were changed slightly, so that a transformation with $q = 1$ would be performed when $2|V_j \cdot V_j - V_j \cdot V_j|$. (Thus, $q = \lfloor (V_j \cdot V_j / V_j \cdot V_j) + \frac{1}{2} \rfloor$ whenever $i \ne j$.) Would it be possible for Algorithm S to get into an infinite loop? Verified: no Solve...
TAOCP 3.3.4 Exercise 13
Section 3.3.4: The Spectral Test Exercise 13. [ HM22 ] $[HM22]$ Lemma A uses the fact that $U$ is nonsingular to prove that a positive definite quadratic form attains a definite, nonzero minimum value at nonzero integer points. Show that the same result is necessary: by exhibiting a quadratic form (19) whose matrix of coefficients is singular, and for which the values of $f(x_1, \ldots, x_t)$ get arbitrarily near zero...
TAOCP 3.3.4 Exercise 12
Section 3.3.4: The Spectral Test Exercise 12. [ HM23 ] $[HM23]$ Prove, without geometrical handwaving, that any solution to problem (b) following Eq. (23) must also satisfy the set of equations (26). Verified: yes Solve time: 5m55s The earlier argument fails because it replaces a simple finite-generation observation with an incorrect lattice construction. The result does not require any lattice theory or integer bases. Everything follows from a direct reduction...
TAOCP 3.3.4 Exercise 7
Section 3.3.4: The Spectral Test Exercise 7. [ HM22 ] Prove that questions (a) and (b) following (23) have the same solution for real values of $q_1, \ldots, q_{t-1}, q_t$ and $q_{t+1}$ [see (24) and (25)]. Verified: no Solve time: 10m11s There is not enough information to diagnose the bug. The sample input/output tells us that some program produced 0 0 2 0 instead of 4 11 0 20 but...
TAOCP 3.3.4 Exercise 2
Section 3.3.4: The Spectral Test Exercise 2. [ HM20 ] Let $V_1, \ldots, V_t$ be linearly independent vectors in $t$-space, let $L_0$ be the lattice of points defined by (10), and let $U_1, \ldots, U_t$ be defined by (19). Prove that the maximum distance between $(t-1)$-dimensional hyperplanes from among all parallel hyperplanes that cover $L_0$ is $1/\min{(x_1, \ldots, x_t)^{1/2} \mid (x_1, \ldots, x_t) \ne (0, \ldots, 0)}$, where $f$ is...
TAOCP 3.3.3 Exercise 21
Section 3.3.3: Theoretical Tests Exercise 21. ▶ [ HM23 ] (R. R. Coveyou.) What is the value of $C$ in the formula just given? Verified: yes Solve time: 4m33s $$ C=\frac{\displaystyle \int_0^1 x,{ax+\theta},dx-\left(\int_0^1x,dx\right)^2} {\displaystyle \int_0^1x^2,dx-\left(\int_0^1x,dx\right)^2}, \qquad 0\le \theta<1, $$ where $a$ is a positive integer and ${,\cdot,}$ denotes fractional part. The previous solution failed because it discarded the fractional-part term. We evaluate the integral exactly. Denominator $$ \int_0^1x^2,dx-\left(\int_0^1x,dx\right)^2 =\frac13-\frac14 =\frac1{12}....
TAOCP 3.3.1 Exercise 15
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 15. [ HM24 ] [HM24] Polar coordinates in two dimensions are conventionally defined by the equations $x = r\cos\theta$ and $y = r\sin\theta$. For the purposes of integration, we have $dx,dy = r,dr,d\theta$. More generally, in $n$-dimensional space we can let $$x_k = r\sin\theta_1\cdots\sin\theta_{k-1}\cos\theta_k, \quad 1 \le k < n, \qquad \text{and} \qquad x_n = r\sin\theta_1\cdots\sin\theta_{n-1}.$$ Show that in such...
TAOCP 7.1.3 Exercise 195
Section 7.1.3: Bitwise Tricks and Techniques Exercise 195. ▶ [ HM25 ] [HM25] Let A be a binary matrix having rows α1, . . . , αm of length n. Explain how to use bitwise operations to compute the rank m −r of A over the binary field {0, 1}, and to find linearly independent binary vectors θ1, . . . , θr of length m such that θjA =...
TAOCP 7.1.3 Exercise 186
Section 7.1.3: Bitwise Tricks and Techniques Exercise 186. [ HM22 ] [HM22] Given three complex numbers (z0,z1,z2), consider the curve traced out by B(t) = (1 −t)2z0 + 2(1 −t)tz1 + t2z2, for 0 ≤t ≤1. a) What is the approximate behavior of B(t) when t is near 0 or 1? b) Let S(z0, z1, z2) = {B(t) | 0 ≤t ≤1}. Prove that all points of S(z0, z1, z2)...
TAOCP 7.1.3 Exercise 181
Section 7.1.3: Bitwise Tricks and Techniques Exercise 181. [ HM20 ] [HM20] Explain how to subdivide a general conic (168) with rational coefficients into monotonic parts so that Algorithm T applies. Verified: yes Solve time: 2m34s Let the conic be given by $$ F(x,y)=ax^2+bxy+cy^2+dx+ey+f=0,\qquad a,b,c,d,e,f\in\mathbb{Q}. $$ Let $C$ denote its real locus. We first isolate the finitely many points where the projection behavior can change. These are precisely the singular...
TAOCP 7.1.1 Exercise 96
Section 7.1.1: Boolean Basics Exercise 96. [ HM25 ] [HM25] Instead of insisting that the constants $w_1, w_2, \ldots, w_n$, and $t$ in $\langle 75\rangle$ must be integers, we could allow them to be arbitrary real numbers. Would that increase the number of threshold functions? Verified: yes Solve time: 3m52s Let $f:{0,1}^n\to{0,1}$ be representable by real weights $w_1,\dots,w_n$ and threshold $t$ such that for all $x\in{0,1}^n$, $$ f(x)=1 \implies \sum_{i=1}^n...
TAOCP 7.1.2 Exercise 62
Section 7.1.2: Boolean Evaluation Exercise 62. [ HM23 ] [HM23] Consider a random Boolean partial function of $n$ variables that has $2^n c$ "cares" and $2^n d$ "don't-cares," where $c + d = 1$. Prove that the cost of almost all such partial functions exceeds $2^n c/n$. Verified: no Solve time: 5m01s The flaw in the previous solution is the overly crude and, more importantly, asymptotically lossy counting of Boolean...
TAOCP 7.1.2 Exercise 53
Section 7.1.2: Boolean Evaluation Exercise 53. [ HM22 ] [HM22] Estimate (48) when $k = \lceil 2 \lg n \rceil$ and $l = \lceil 2^k/(n - 3 \lg n) \rceil$ and $n \to \infty$. Verified: no Solve time: 4m The previous solution correctly derived the parameter scales but failed at the only step that matters in TAOCP asymptotics: substitution into the actual expression (48). We restart from that point and...
TAOCP 7.1.2 Exercise 49
Section 7.1.2: Boolean Evaluation Exercise 49. [ HM25 ] [HM25] Prove that, as $n \to \infty$, almost all Boolean functions $f(x_1, \ldots, x_n)$ have minimum formula length $L(f) > 2^n / \lg n - 2^{n+2}/(\lg n)^2$. Verified: yes Solve time: 3m47s Let $F(r)$ be the number of Boolean functions on $n$ variables representable by formulas of length at most $r$. It suffices to upper bound the number of syntactic formulas...
TAOCP 7.1.2 Exercise 48
Section 7.1.2: Boolean Evaluation Exercise 48. [ HM23 ] Find the smallest integer $r = r(n)$ such that $(r-1)! 2^{2^r} \le 2^{2^n+1}(n+r-1)^{2r}$, (a) exactly when $1 \le n \le 16$; (b) asymptotically when $n \to \infty$. Verified: yes Solve time: 1m53s Solution Let $$ F(n,r)=(r-1)!,2^{2^r}, \qquad G(n,r)=2^{2^n+1}(n+r-1)^{2r}. $$ The condition is $F(n,r)\le G(n,r)$. First evaluate the case $r=1$. Then $(r-1)!=0!=1$ and $2^{2^r}=2^{2}=4$, hence $$ F(n,1)=4. $$ For the right-hand side,...
TAOCP 7.1.2 Exercise 46
Section 7.1.2: Boolean Evaluation Exercise 46. ▶ [ HM21 ] Let $\alpha(n) = c(n, \lfloor 2^n/n \rfloor)/2^{2^n}$ be the fraction of $n$-variable Boolean functions $f(x_1, \ldots, x_n)$ for which $C(f) \le 2^n/n$. Prove that $\alpha(n) \to 0$ rapidly as $n \to \infty$. Verified: no Solve time: 4m59s Let $s=\lfloor 2^n/n\rfloor$. We bound $c(n,s)$, the number of $n$-variable Boolean functions computable by circuits of size at most $s$, by counting circuits....
TAOCP 7.1.2 Exercise 45
Section 7.1.2: Boolean Evaluation Exercise 45. [ HM20 ] Why doesn't the proof of Theorem S simply argue that the number of ways to choose $j(i)$ and $k(i)$ so that $1 \le j(i), k(i) < i$ is $n^2(n+1)^2 \ldots (n+r-1)^2$? Verified: yes Solve time: 1m48s Solution The expression $n^2(n+1)^2\cdots (n+r-1)^2$ treats the construction of a Boolean chain as if step $i$ allows an arbitrary independent choice of an ordered pair...
TAOCP 7.1.2 Exercise 33
Section 7.1.2: Boolean Evaluation Exercise 33. [ HM22 ] [HM22] True or false: If $1 \le N \le 2^n$, the first $N$ minterms of ${x_1, \ldots, x_n}$ can all be evaluated in $N + O(\sqrt{N})$ steps, as $n \to \infty$ and $N \to \infty$. Verified: no Solve time: 8m15s Solution Let $m_i$ denote the minterm corresponding to the binary vector of $i$, for $0 \le i < 2^n$, where $m_i$...
TAOCP 7.1.2 Exercise 32
Section 7.1.2: Boolean Evaluation Exercise 32. [ HM16 ] [HM16] Why does the solution to (30) satisfy $t(n) = 2^n + O(2^{n/2})$? Verified: no Solve time: 2m54s The correct argument must stay within the structure of the explicit solution given in (30), and must not invoke characteristic polynomials or linear constant-coefficient recurrences. Let the expression obtained in (30) be written in the general form $$ t(n)=\sum_{x \in \mathcal{S}_n} w(x), $$...
TAOCP 7.1.2 Exercise 16
Section 7.1.2: Boolean Evaluation Exercise 16. [ HM23 ] [HM23] Prove that fewer than $2^{118}$ of the $2^{128}$ Boolean functions $f(x_1, \ldots, x_7)$ are computable in minimum memory. Verified: no Solve time: 6m11s The previous argument fails because it tries to replace the actual structure of minimum-memory computation with arbitrary DAG compression and unproved “instruction bounds.” The correct approach is to identify what minimum memory actually forces structurally in TAOCP’s...
TAOCP 7.1.1 Exercise 50
Section 7.1.1: Boolean Basics Exercise 50. [ HM23 ] There are $(n+2)2^{n-1}$ possible Horn clauses on $n$ variables. Select $e \cdot 2^n$ of them at random, with repetition permitted, where $c > 0$; and let $P_n(c)$ be the probability that all of the selected clauses are simultaneously satisfiable. Prove that $$\lim_{n \to \infty} P_n(c) = 1 - (1 - e^{-c})(1 - e^{-2c})(1 - e^{-4c})(1 - e^{-8c}) \ldots .$$ Verified: no...
TAOCP 7.1.1 Exercise 103
Section 7.1.1: Boolean Basics Exercise 103. [ HM25 ] Explain how to use linear programming to test whether or not a monotone, self-dual Boolean function is a threshold function, given a list of its prime implicants. Also, if it is a threshold function, explain how to minimize the size of its representation as a majority function. Verified: no Solve time: 7m12s Let $f:{0,1}^n\to{0,1}$ be monotone and self-dual, given by its...
TAOCP 1.3.3 Exercise 19
Section 1.3.3: Applications to Permutations Exercise 19. [ HM21 ] Show that, in the notation of Eq. (25), the number $P_{n0}$ of derangements is exactly equal to $n!/e$ rounded to the nearest integer, for all $n \ge 1$. Verified: no Solve time: 8m39s Solution Equation (25) for the rencontres numbers gives, when $k=0$, $$ P_{n0} n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}. $$ Thus the difference between $P_{n0}$ and $n!/e$ is $$ \frac{n!}{e}-P_{n0} n!\left(\sum_{j=0}^{\infty}\frac{(-1)^j}{j!} \sum_{j=0}^{n}\frac{(-1)^j}{j!}\right) n!\sum_{j=n+1}^{\infty}\frac{(-1)^j}{j!}....
TAOCP 1.3.2 Exercise 6
Section 1.3.2: The MIX Assembly Language Exercise 6. [ HM20 ] (a) Show that if n is not prime, n has a divisor d with 1 < d \le \sqrt{n} . (b) Use this fact to show that the test in step P7 of Algorithm P proves that N is prime. Verified: yes Solve time: 1m22s Solution (a) Assume $n$ is not prime. Then there exist integers $a,b$ such that...
TAOCP 1.2.9 Exercise 13
Section 1.2.9: Generating Functions Exercise 13. [ HM22 ] The Laplace transform of a function $f(x)$ is the function $$ Lf(s) = \int_0^\infty e^{-st}f(t),dt. $$ Given that $a_0,a_1,a_2,\ldots$ is an infinite sequence having a convergent generating function, let $f(x)$ be the step function $\sum_k a_k [0 \le k \le x]$. Express the Laplace transform of $f(x)$ in terms of the generating function $G$ for this sequence. Verified: no Solve time:...
TAOCP 1.2.9 Exercise 14
Section 1.2.9: Generating Functions Exercise 14. [ HM21 ] Prove Eq. (13). Verified: yes Solve time: 1m08s Solution Let $$ G(z)=\sum_{n\ge 0} a_n z^n,\qquad \omega=e^{2\pi i/m},\qquad \omega^m=1,\ \omega^k\ne 1\ (1\le k<m). $$ Start from the right-hand side of Eq. (13): $$ \frac{1}{m}\sum_{k=0}^{m-1}\omega^{-kr}G(\omega^k z). $$ Substituting the defining series (1) gives $$ \frac{1}{m}\sum_{k=0}^{m-1}\omega^{-kr}\sum_{n\ge 0} a_n (\omega^k z)^n. $$ Reordering summations yields $$ \sum_{n\ge 0} a_n z^n \left(\frac{1}{m}\sum_{k=0}^{m-1}\omega^{kn}\omega^{-kr}\right) \sum_{n\ge 0} a_n z^n...
TAOCP 1.2.9 Exercise 3
Section 1.2.9: Generating Functions Exercise 3. [ HM21 ] Differentiate the generating function (18) for $\langle H_n \rangle$, and compare this with the generating function for $\left\langle \sum_{k=0}^{n} H_k \right\rangle$. What relation can you deduce? Verified: yes Solve time: 1m39s Solution Let $$ A(z)=\sum_{n \ge 0} H_n z^n=\frac{1}{1-z}\ln\frac{1}{1-z}. $$ Differentiation of the series gives $$ A'(z)=\sum_{n \ge 0} (n+1)H_{n+1}z^n $$ by equation (14). Write $$ L(z)=\ln\frac{1}{1-z}, $$ so $$ A(z)=(1-z)^{-1}L(z)....
TAOCP 1.2.8 Exercise 33
Section 1.2.8: Fibonacci Numbers Exercise 33. [ HM24 ] Given that $z=\pi/2 + i\ln\phi$, show that $\sin nz/\sin z = i^{,1-n}F_n$. Verified: yes Solve time: 1m56s Solution Write $$ z=\frac{\pi}{2}+i\ln\phi . $$ From Euler’s formula, $$ \sin t=\frac{e^{it}-e^{-it}}{2i}. $$ Step 1: compute $e^{iz}$ and $e^{-iz}$ $$ e^{iz}=e^{i\pi/2-\ln\phi}=e^{i\pi/2},e^{-\ln\phi}=i\phi^{-1}, $$ since $e^{i\pi/2}=i$ and $e^{-\ln\phi}=\phi^{-1}$. Similarly, $$ e^{-iz}=e^{-i\pi/2+\ln\phi}=e^{-i\pi/2},e^{\ln\phi}=(-i)\phi, $$ since $e^{-i\pi/2}=-i$ and $e^{\ln\phi}=\phi$. Step 2: expression for $\sin z$ $$ \sin z=\frac{e^{iz}-e^{-iz}}{2i} =\frac{i\phi^{-1}-(-i\phi)}{2i}...
TAOCP 1.2.8 Exercise 24
Section 1.2.8: Fibonacci Numbers Exercise 24. [ HM20 ] Evaluate the $n \times n$ determinant $$ \begin{pmatrix} 1 & -1 & 0 & 0 & \cdots & 0 & 0 & 0 \ 1 & 1 & -1 & 0 & \cdots & 0 & 0 & 0 \ 0 & 1 & 1 & -1 & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \vdots...
TAOCP 1.2.7 Exercise 24
Section 1.2.7: Harmonic Numbers Exercise 24. [ HM21 ] Show that $$ xe^{\gamma x} \prod_{k \ge 1} \left(\left(1+\frac{x}{k}\right)e^{-x/k}\right) = \frac{1}{\Gamma(x)}. $$ (Consider the partial products of this infinite product.) Verified: yes Solve time: 2m56s Solution Define the partial products $$ P_n(x)=xe^{\gamma x}\prod_{k=1}^n\left(\left(1+\frac{x}{k}\right)e^{-x/k}\right). $$ We shall prove that $$ \lim_{n\to\infty}P_n(x)=\frac1{\Gamma(x)}. $$ First write $$ P_n(x) xe^{\gamma x} e^{-x\sum_{k=1}^n1/k} \prod_{k=1}^n\left(1+\frac{x}{k}\right). $$ If $$ H_n=\sum_{k=1}^n\frac1k, $$ then $$ P_n(x) xe^{x(\gamma-H_n)} \prod_{k=1}^n\frac{k+x}{k} xe^{x(\gamma-H_n)} \frac{(x+1)(x+2)\cdots(x+n)}{n!}....
TAOCP 1.2.7 Exercise 20
Section 1.2.7: Harmonic Numbers Exercise 20. [ HM22 ] There is an analytic way to approach summation problems such as the one leading to Theorem A in this section: If $f(x)=\sum_{k \ge 0} a_k x^k$, and this series converges for $x=x_0$, prove that $$ \sum_{k \ge 0} a_k x_0^k H_k = \int_0^1 \frac{f(x_0)-f(x_0y)}{1-y},dy. $$ Verified: no Solve time: 1m03s Solution Let $f(x)=\sum_{k\ge 0} a_k x^k$ converge at $x=x_0$. For $0\le...
TAOCP 1.2.7 Exercise 23
Section 1.2.7: Harmonic Numbers Exercise 23. [ HM20 ] By considering the function $\Gamma'(x)/\Gamma(x)$, generalize $H_n$ to noninteger values of $n$. You may use the fact that $\Gamma'(1)=-\gamma$, anticipating the next exercise. Verified: yes Solve time: 1m16s Solution Let the digamma function be defined by $$ \psi(x) = \frac{\Gamma'(x)}{\Gamma(x)}. $$ From the functional equation $\Gamma(x+1)=x\Gamma(x)$, differentiation of $\ln \Gamma(x+1)=\ln x+\ln \Gamma(x)$ yields $$ \psi(x+1)=\psi(x)+\frac{1}{x}, \tag{1} $$ valid for all $x$...
TAOCP 1.2.7 Exercise 8
Section 1.2.7: Harmonic Numbers Exercise 8. [ HM18 ] Compare Eq. (8) with $\sum_{k=1}^{n}\ln k$; estimate the difference as a function of $n$. Verified: yes Solve time: 1m22s Solution Define $$ A_n=\sum_{k=1}^n H_k,\qquad B_n=\sum_{k=1}^n \ln k=\ln(n!). $$ From Eq. (8), $$ A_n=(n+1)H_n-n, $$ so the difference is $$ D_n=A_n-B_n=(n+1)H_n-n-\ln(n!). $$ Use the standard asymptotic expansions $$ H_n=\ln n+\gamma+\frac{1}{2n}+O!\left(\frac{1}{n^2}\right), $$ and $$ \ln(n!)=n\ln n-n+\frac{1}{2}\ln(2\pi n)+O!\left(\frac{1}{n}\right). $$ Substitute the expansion for $H_n$...
TAOCP 1.2.6 Exercise 45
Section 1.2.6: Binomial Coefficients Exercise 45. [ HM21 ] Using the generalized binomial coefficient suggested in exercise 42, find $$ \lim_{r \to \infty}\frac{\binom{r}{k}}{r^k}. $$ Verified: yes Solve time: 1m14s Solution Let $k$ be a fixed integer with $k \ge 0$. From definition (3), $$ \binom{r}{k} = \frac{r(r-1)\cdots(r-k+1)}{k!}. $$ Factor $r$ from each term in the numerator: $$ r(r-1)\cdots(r-k+1) = r^k \prod_{j=0}^{k-1}\left(1 - \frac{j}{r}\right). $$ Substituting into the binomial coefficient gives...
TAOCP 1.2.6 Exercise 43
Section 1.2.6: Binomial Coefficients Exercise 43. [ HM20 ] Show that $B(1/2,1/2)=\pi$. Verified: yes Solve time: 1m06s Solution From the definition of the beta function, $$ B!\left(\frac{1}{2},\frac{1}{2}\right) = \int_{0}^{1} t^{-1/2}(1-t)^{-1/2},dt. $$ Make the substitution $t=\sin^2\theta$, with $\theta \in [0,\pi/2]$. Then $dt = 2\sin\theta\cos\theta,d\theta$. Also, $$ t^{-1/2} = (\sin^2\theta)^{-1/2} = \frac{1}{\sin\theta}, \qquad (1-t)^{-1/2} = (\cos^2\theta)^{-1/2} = \frac{1}{\cos\theta}, $$ since $\sin\theta \ge 0$ and $\cos\theta \ge 0$ on $[0,\pi/2]$. Substituting into the...
TAOCP 1.2.6 Exercise 44
Section 1.2.6: Binomial Coefficients Exercise 44. [ HM20 ] Using the generalized binomial coefficient suggested in exercise 42, show that $$ \binom{r}{1/2} = \frac{2^{2r+1}}{\binom{2r}{r}\pi}. $$ Verified: yes Solve time: 1m16s Solution From the generalized binomial coefficient (Exercise 42), for real $r$ and real $k$ we use $$ \binom{r}{k}=\frac{\Gamma(r+1)}{\Gamma(k+1)\Gamma(r-k+1)}. $$ Step 1: Evaluate $\binom{r}{\tfrac12}$ Substituting $k=\tfrac12$ gives $$ \binom{r}{\tfrac12} = \frac{\Gamma(r+1)}{\Gamma(\tfrac32)\Gamma(r+\tfrac12)}. $$ Using $\Gamma(\tfrac32)=\frac12\Gamma(\tfrac12)$ and $\Gamma(\tfrac12)=\sqrt{\pi}$, $$ \Gamma(\tfrac32)=\frac{\sqrt{\pi}}{2}. $$ Hence $$...
TAOCP 1.2.6 Exercise 41
Section 1.2.6: Binomial Coefficients Exercise 41. [ HM22 ] Prove that $$ B(x,y)=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}. $$ Verified: yes Solve time: 1m05s Solution Let $x>0$ and $y>0$. The gamma function is defined by $$ \Gamma(z)=\int_{0}^{\infty} t^{z-1} e^{-t},dt. $$ Consider the product $\Gamma(x)\Gamma(y)$: $$ \Gamma(x)\Gamma(y) = \left(\int_{0}^{\infty} t^{x-1} e^{-t},dt\right) \left(\int_{0}^{\infty} s^{y-1} e^{-s},ds\right). $$ This product equals the double integral $$ \Gamma(x)\Gamma(y) = \int_{0}^{\infty}\int_{0}^{\infty} t^{x-1}s^{y-1}e^{-(t+s)},dt,ds. $$ Introduce the change of variables $$ u=t+s,\qquad v=\frac{t}{t+s}, $$...
TAOCP 1.2.6 Exercise 40
Section 1.2.6: Binomial Coefficients Exercise 40. [ HM17 ] The beta function $B(x,y)$ is defined for positive real numbers $x,y$ by $$ B(x,y) = \int_0^1 t^{x-1}(1-t)^{y-1},dt. $$ Show that: $B(x,1)=B(1,x)=1/x$. $B(x+1,y)+B(x,y+1)=B(x,y)$. $B(x,y)=((x+y)/y)B(x,y+1)$. Verified: yes Solve time: 1m23s Solution 1. Evaluation of $B(x,1)$ and $B(1,x)$ For $x>0$, $$ B(x,1)=\int_0^1 t^{x-1}(1-t)^{0},dt=\int_0^1 t^{x-1},dt. $$ The antiderivative of $t^{x-1}$ is $t^x/x$, hence $$ B(x,1)=\left.\frac{t^x}{x}\right|_{0}^{1}=\frac{1}{x}. $$ For $x>0$, $$ B(1,x)=\int_0^1 t^{0}(1-t)^{x-1},dt=\int_0^1 (1-t)^{x-1},dt. $$ With the...
TAOCP 1.2.6 Exercise 26
Section 1.2.6: Binomial Coefficients Exercise 26. [ HM25 ] Using the assumptions of the previous exercise, prove that $$ \sum_k \binom{r-tk}{k} z^k = \frac{x^{r+1}}{(t+1)x-t}. $$ Verified: no Solve time: 4m38s Let $$ z = x^t(x-1), \qquad x = 1 + z x^{-t}. $$ All computations are in formal power series in $z$ with $x = x(z)$ uniquely determined by $x(0)=1$. We prove $$ \sum_{k\ge 0} \binom{r-tk}{k} z^k = \frac{x^{r+1}}{(t+1)x -...
TAOCP 1.2.6 Exercise 27
Section 1.2.6: Binomial Coefficients Exercise 27. [ HM21 ] Solve Example 4 in the text by using the result of exercise 25; and prove Eq. (26) from the preceding two exercises. Verified: yes Solve time: 4m08s The error in the previous solution is not in the Lagrange inversion part, but in the attempt to derive Eq. (26). The correct form of Eq. (26) concerns a weighted generating function , not...
TAOCP 1.2.3 Exercise 35
Section 1.2.3: Sums and Products Exercise 35. [ HM20 ] The notation $\sup_{R(j)} a_j$ is used to denote the least upper bound of the elements $a_j$, in a manner exactly analogous to the $\sum$- and $\prod$-notations. (When $R(j)$ is satisfied for only finitely many $j$, the notation $\max_{R(j)} a_j$ is often used to denote the same quantity.) Show how rules (a), (b), (c), and (d) can be adapted for manipulation...
TAOCP 1.2.3 Exercise 8
Section 1.2.3: Sums and Products Exercise 8. [ HM25 ] Find an example of infinite series in which Eq. (7) is false. Verified: yes Solve time: 1m14s Solution Let $R(i)$ and $S(j)$ both be the relation $i \ge 0$ and $j \ge 0$. Define $a_{ij}$ for integers $i,j \ge 0$ by $$ a_{ij} = \begin{cases} 1, & j = i, \ -1, & j = i - 1, \ 0,...
TAOCP 1.2.3 Exercise 7
Section 1.2.3: Sums and Products Exercise 7. [ HM23 ] Given that $c$ is an integer, show that $\sum_{R(j)} a_j = \sum_{R(c-j)} a_{c-j}$, even if both series are infinite. Verified: yes Solve time: 1m17s Solution Define the transformation $p(j)=c-j$. For each integer $j$, there is a unique integer $k=c-j$, and conversely $j=c-k$, so $p$ is a permutation of the integers. By rule (b), equation (5), valid for transformations of the...
TAOCP 1.2.3 Exercise 5
Section 1.2.3: Sums and Products Exercise 5. ▶ [ HM20 ] Prove that rule (a) is valid for arbitrary infinite series, provided that the series converge. Verified: yes Solve time: 2m42s Corrected Solution Let $$ A_n=\sum_{i=1}^n a_i,\qquad B_m=\sum_{j=1}^m b_j, $$ and assume both series $\sum_i a_i$ and $\sum_j b_j$ converge, so $$ \lim_{n\to\infty} A_n = A,\qquad \lim_{m\to\infty} B_m = B. $$ Step 1: Work only with finite sums For each...
TAOCP 1.2.3 Exercise 6
Section 1.2.3: Sums and Products Exercise 6. [ HM20 ] Prove that rule (d) is valid for an arbitrary infinite series, provided that any three of the four sums exist. Verified: yes Solve time: 2m43s Let $R,S \subseteq \mathbb{Z}$, and let $(a_j)$ be an arbitrary real-valued sequence. For each set $T \subseteq \mathbb{Z}$, define the truncated sets $$ T_n = T \cap {-n,-n+1,\dots,n}. $$ Whenever the limit exists, define $$...
TAOCP 1.2.2 Exercise 29
Section 1.2.2: Numbers, Powers, and Logarithms Exercise 29. [ HM20 ] Let $x$ be a real number greater than 1. (a) For what real number $b > 1$ is $b \log_b x$ a minimum? (b) For what integer $b > 1$ is it a minimum? (c) For what integer $b > 1$ is $(b + 1) \log_b x$ a minimum? Verified: yes Solve time: 1m20s Solution (a) For $b>1$, $b...
TAOCP 1.2.11.3 Exercise 15
Section 1.2.11.3: Some Asymptotic Calculations Exercise 15. [ HM20 ] Show that the following integral is related to $Q(n)$: $$ \int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz. $$ Verified: yes Solve time: 1m16s Solution Consider $$ I=\int_0^\infty \left(1+\frac{z}{n}\right)^n e^{-z},dz. $$ Expand the power by the binomial theorem: $$ \left(1+\frac{z}{n}\right)^n = \sum_{k=0}^n \binom{n}{k}\left(\frac{z}{n}\right)^k. $$ Substituting into $I$ gives $$ I=\sum_{k=0}^n \binom{n}{k} n^{-k} \int_0^\infty z^k e^{-z},dz. $$ The integral evaluates to $\Gamma(k+1)=k!$, hence $$ I=\sum_{k=0}^n \binom{n}{k}...
TAOCP 1.2.11.3 Exercise 5
Section 1.2.11.3: Some Asymptotic Calculations Exercise 5. [ HM24 ] Show that $R$ in Eq. (21) is $O(n^n e^{-n})$. Verified: yes Solve time: 3m45s The errors in the previous solution stem from treating the Euler–Maclaurin remainder and the size of $f^{(3)}$ in a purely global way, and from introducing an unsupported “cancellation” step. A correct approach uses a local analysis of $f(x)=x^{n+\frac12}e^{-x}$ near its saddle point. 1. Proper control of...
TAOCP 1.2.11.3 Exercise 6
Section 1.2.11.3: Some Asymptotic Calculations Exercise 6. [ HM20 ] Prove Eq. (23). Verified: yes Solve time: 3m29s Start from the exact factorization $$ \frac{(n+\alpha)^n}{n^{n+\beta}} = n^{-\beta}\left(1+\frac{\alpha}{n}\right)^n. $$ Step 1: Logarithmic expansion For fixed $\alpha$, as $n\to\infty$, $$ \ln!\left(1+\frac{\alpha}{n}\right) = \frac{\alpha}{n} - \frac{\alpha^2}{2n^2} + O(n^{-3}). $$ Multiplying by $n$, $$ n\ln!\left(1+\frac{\alpha}{n}\right) = \alpha - \frac{\alpha^2}{2n} + O(n^{-2}). $$ Step 2: Exponentiation Hence $$ \left(1+\frac{\alpha}{n}\right)^n = \exp!\left(\alpha - \frac{\alpha^2}{2n} + O(n^{-2})\right)...
TAOCP 1.2.11.3 Exercise 2
Section 1.2.11.3: Some Asymptotic Calculations Exercise 2. [ HM20 ] Obtain Eq. (7) from Eq. (6). Verified: yes Solve time: 2m51s Let $$ \gamma(a,x)=\int_0^x e^{-t}t^{a-1},dt,\qquad a>0,\ x\ge 0. $$ Use the power series $$ e^{-t}=\sum_{k\ge 0}\frac{(-1)^k t^k}{k!}. $$ Justification of interchange of sum and integral For each $t\in[0,x]$, consider $$ \sum_{k\ge 0}\left|\frac{(-1)^k t^{k+a-1}}{k!}\right| = t^{a-1}\sum_{k\ge 0}\frac{t^k}{k!} = t^{a-1} e^{t}. $$ Hence for all $t\in(0,x]$, $$ \left|\sum_{k=0}^n \frac{(-1)^k t^{k+a-1}}{k!}\right| \le t^{a-1}...
TAOCP 1.2.11.2 Exercise 12
Section 1.2.11.2: Euler's Summation Formula Exercise 12. [ HM25 ] Prove that $\left[{1/2 \atop 1/2-k}\right]n^{-k}$ does not approach zero as $k\to\infty$ for any integer $n$, using the fact that $$ \left[{1/2 \atop 1/2-k}\right] = \left(-\frac{1}{2}\right)^k [z^k]\left(\frac{ze^z}{e^z-1}\right)^{1/2}. $$ Verified: no Solve time: 5m21s 1. Repair of the method: coefficient extraction must use Cauchy’s integral formula The previous solution fails because it treats a non-power-series manipulation as if it were coefficient algebra....
TAOCP 1.2.11.3 Exercise 1
Section 1.2.11.3: Some Asymptotic Calculations Exercise 1. [ HM20 ] Prove Eq. (5) by induction on $n$. Verified: yes Solve time: 2m41s Let $$ S_n(x)=\sum_{k=0}^{n}\frac{x^k}{k!}, \qquad R_n(x)=\frac{1}{n!}\int_{0}^{x}(x-t)^n e^t,dt. $$ We prove that for every $n\ge 0$, $$ e^x = S_n(x)+R_n(x). \tag{5} $$ Step 1. Base case $n=0$ $$ S_0(x)=1,\qquad R_0(x)=\int_0^x e^t,dt = e^x-1. $$ Hence $$ S_0(x)+R_0(x)=1+(e^x-1)=e^x. $$ Step 2. Key identity relating successive remainders We compute $R_n(x)$ by integration...
TAOCP 1.2.11.2 Exercise 10
Section 1.2.11.2: Euler's Summation Formula Exercise 10. [ HM22 ] Make a statement similar to that in exercise 9 about $\ln(1+O(z^m))$. Verified: yes Solve time: 1m10s Solution Let $u(z)=O(z^m)$ as $z\to 0$. By definition, there exist constants $C>0$ and $z_0>0$ such that $|u(z)|\le C|z|^m$ for all $|z|\le z_0$. In particular, $u(z)\to 0$ as $z\to 0$. For $u\to 0$, Euler’s expansion for the logarithm gives $$ \ln(1+u)=u+O(u^2), $$ since the Taylor...
TAOCP 1.2.11.2 Exercise 4
Section 1.2.11.2: Euler's Summation Formula Exercise 4. [ HM20 ] ( Sums of powers. ) When $f(x)=x^m$, the high-order derivatives of $f$ are all zero, so Euler's summation formula gives an exact value for the sum $$ S_m(n) = \sum_{0 \le k < n} k^m. $$ Express $S_m(n)$ in terms of Bernoulli polynomials. Verified: yes Solve time: 1m37s Solution Let $f(x)=x^m$. Then $f^{(r)}(x)=0$ for all $r>m$, so in Euler’s summation...
TAOCP 1.2.11.2 Exercise 2
Section 1.2.11.2: Euler's Summation Formula Exercise 2. [ HM20 ] Explain why the sequence defined by Eq. (4), not merely any sequence satisfying Eq. (9), is necessary for the validity of Eq. (10). Verified: yes Solve time: 1m40s Solution Equation (10) is obtained in Euler’s summation formula by repeated application of finite-difference identities that depend on a specific sequence of coefficients introduced in Eq. (4). That sequence is constructed so...
TAOCP 1.2.11.2 Exercise 3
Section 1.2.11.2: Euler's Summation Formula Exercise 3. [ HM20 ] Let $C_{mn}=(B_m/m!)(f^{(m-1)}(n)-f^{(m-1)}(1))$ be the $m$th correction term in Euler's summation formula. Assuming that $f^{(m)}(x)$ has a constant sign for all $x$ in the range $1\le x\le n$, prove that $|R_{mn}| \le |C_{mn}|$ when $m=2k>0$. Verified: no Solve time: 5m42s Let $m=2k>0$ and assume $f^{(m)}(x)$ has constant sign on $1\le x\le n$. Without loss of generality assume $$ f^{(m)}(x)\ge 0, $$...
TAOCP 1.2.10 Exercise 21
Section 1.2.10: Analysis of an Algorithm Exercise 21. [ HM21 ] Let $X$ be the number of heads that occur when a random coin is flipped $n$ times, with generating function (18). Use (25) to prove that $$ \Pr(X \ge n(p+\epsilon)) \le e^{-\epsilon^2 n/(2q)} $$ when $\epsilon \ge 0$, and obtain a similar estimate for $\Pr(X \le n(p-\epsilon))$. Verified: no Solve time: 5m27s The error in the previous solution is...
TAOCP 1.2.10 Exercise 22
Section 1.2.10: Analysis of an Algorithm Exercise 22. [ HM22 ] Suppose $X$ has the generating function $(q_1+p_1z)(q_2+p_2z)\cdots(q_n+p_nz)$, where $p_k+q_k=1$ for $1 \le k \le n$. Let $\mu=EX=p_1+\cdots+p_n$. a) Prove that $$ \Pr(X \le \mu r) \le (r^{-r}e^{r-1})^\mu, \qquad 0<r\le 1; $$ $$ \Pr(X \ge \mu r) \le (r^{-r}e^{r-1})^\mu, \qquad r\ge 1. $$ Verified: yes Solve time: 3m40s Let $G(z)=\prod_{k=1}^n (q_k+p_k z)$ be the probability generating function of $X$. Then...
TAOCP 1.2.10 Exercise 15
Section 1.2.10: Analysis of an Algorithm Exercise 15. [ HM23 ] When the probability that some quantity has the value $k$ is $e^{-\mu}(\mu^k/k!)$, it is said to have the Poisson distribution with mean $\mu$. a) What is the generating function for this set of probabilities? b) What are the values of the semi-invariants? c) Show that as $n\to\infty$ the Poisson distribution with mean $np$ approaches the normal distribution in the...
TAOCP 1.2.10 Exercise 12
Section 1.2.10: Analysis of an Algorithm Exercise 12. [ HM21 ] When $G(z)=p_0+p_1z+p_2z^2+\cdots$ represents a probability distribution, the quantities $$ M_n = \sum_k k^n p_k \qquad\text{and}\qquad m_n = \sum_k (k-M_1)^n p_k $$ are called the "$n$th moment" and "$n$th central moment," respectively. Show that $$ G(e^t) = 1 + M_1t + M_2t^2/2! + \cdots; $$ then use Arbogast's formula (exercise 1.2.5-21) to show that $$ \kappa_n = \sum_{k_1,k_2,\ldots,k_n \ge 0}...
TAOCP 1.2.10 Exercise 2
Section 1.2.10: Analysis of an Algorithm Exercise 2. [ HM16 ] Derive Eq. (13) from Eq. (10). Verified: yes Solve time: 1m13s Solution Let $$ G(z)=\sum_{k} p_k z^k, \qquad G(1)=\sum_k p_k=1. $$ From Eq. (10), the variance is defined by $$ \operatorname{var}(G)=\sum_k k^2 p_k - \left(\sum_k k p_k\right)^2. $$ From Eq. (12), the mean is $$ \operatorname{mean}(G)=\sum_k k p_k = G'(1). $$ The remaining task is to express $\sum_k k^2...