#hm-project
TAOCP 4.6.2 Exercise 39
Section 4.6.2: Factorization of Polynomials Exercise 39. [ HM42 ] (David G. Cantor.) Show that if the polynomial $u(x)$ is irreducible over the integers, it has a "succinct" proof of irreducibility, in the sense that the number of bits in the proof is at most a polynomial in $\deg(u)$ and the length of the coefficients. (Only a bound on the length of proofs is required, not the algorithm in exercise...
TAOCP 4.5.3 Exercise 35
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 35. [ HM41 ] (A. C. Yao and D. E. Knuth.) Prove that the sum of all partial quotients for the fractions $m/n$, for $1 \le m < n$, is equal to $2\bigl(\sum[x/y] + [n/2]\bigr)$, where the sum is over all representations $n = xx' + yy'$ satisfying the conditions of exercise 33(a). Show that $\sum[x/y] = 3\pi^{-2}n(\ln n)^2 + O(n \log n...
TAOCP 4.5.3 Exercise 34
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 34. [ HM41 ] (H. Heilbronn.) Let $h_0(n)$ be the number of representations of $n$ as in exercise 33 such that $d < x'$, plus half the number of representations with $2d = x'$. a) Let $g(n)$ be the number of representations without the requirement that $x \perp y$. Prove that $$h(n) = \sum_{d|n} \mu(d) g!\left(\frac{n}{d}\right), \qquad g(n) = 2\sum_{d|n} h_0!\left(\frac{n}{d}\right).$$ b) Generalizing...
TAOCP 4.5.3 Exercise 23
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 23. [ HM45 ] Prove (44) using results from the proof of Theorem W. Verified: no Solve time: 3m56s Exercise 4.5.3.23 [ HM45 ] Problem: Prove equation (44) $$ \Psi_2(x) = \sum_{k=1}^{\infty} \frac{1}{(k+x)^2}, \quad 0 \le x \le 1, $$ using results from the proof of Theorem W. Solution We follow the strategy suggested by Theorem W: show that the candidate series satisfies...
TAOCP 4.2.4 Exercise 20
Section 4.2.4: Distribution of Floating Point Numbers Exercise 20. [ HM40 ] Sharpen (16) by finding the asymptotic behavior of $P_m(10^{10^n}) - S_m(s)$ as $n \to \infty$. Verified: no Solve time: 9m43s Exercise 4.2.4.20 [ HM40 ] 20. Sharpen (16) by finding the asymptotic behavior of $P_m(10^{10^n}) - S_m(s)$ as $n \to \infty$. Solution Let $s = s_1 s_2 \dots s_m$ be a sequence of decimal digits with $1 \le...
TAOCP 3.5 Exercise 39
Section 3.5: What Is a Random Sequence? Exercise 39. [ HM45 ] (W. M. Schmidt.) Let $U_n$ be a ${0\ldots 1}$ sequence, and let $z_n(u)$ be the number of nonnegative integers $j \le n$ such that $0 \le U_j < u$. Prove that there is a positive constant $c$ such that, for any $N$ and for any ${0\ldots 1}$ sequence $(U_n)$, we have $$|z_n(u) - un| > c \ln N$$...
TAOCP 3.5 Exercise 16
Section 3.5: What Is a Random Sequence? Exercise 16. [ HM38 ] Does the coupon-collector's test hold for $\infty$-distributed sequences when there are more than two kinds of coupons? (See the previous exercise.) Verified: yes Solve time: 1m11s Setup Let $b \ge 2$ be an integer representing the number of kinds of coupons. Let $X_1, X_2, \ldots$ be an $\infty$-distributed $b$-ary sequence, so that by Definition D, for any $k...
TAOCP 3.4.1 Exercise 31
Section 3.4.1: Numerical Distributions Exercise 31. [ HM39 ] ( Direct generation of normal deviates. ) a) Prove that if $a_1^2 + \cdots + a_n^2 = 1$ and if $X_1, \ldots, X_n$ are independent normal deviates with mean 0 and variance 1, then $a_1 X_1 + \cdots + a_n X_n$ is a normal deviate with mean 0 and variance 1. b) The result of (a) suggests that we can generate...
TAOCP 3.4.1 Exercise 24
Section 3.4.1: Numerical Distributions Exercise 24. [ HM40 ] (S. Ulam and J. von Neumann.) Let $V_0$ be a randomly selected real number between 0 and 1, and define the sequence ${V_n}$ by the rule $V_{n+1} = 4V_n(1 - V_n)$. If this computation is done with perfect accuracy, the result should be a random sequence with the distribution function $F(x) = \frac{2}{\pi} \arcsin \sqrt{x}$, the arcsine distribution; $F(x) = \int_0^x...
TAOCP 3.4.1 Exercise 22
Section 3.4.1: Numerical Distributions Exercise 22. [ HM40 ] Can the exact Poisson distribution for large $\mu$ be obtained by generating an appropriate normal deviate, converting it to an integer in some convenient way, and applying a (possibly complicated) correction a small percent of the time? Verified: yes Solve time: 1m35s Exercise 3.4.1.22 [ HM40 ] Can the exact Poisson distribution for large $\mu$ be obtained by generating an appropriate...
TAOCP 3.3.4 Exercise 27
Section 3.3.4: The Spectral Test Exercise 27. [ HM39 ] (E. Hlawka, H. Niederreiter.) Let $r(u_1, \ldots, u_t)$ be the function defined in (46). Prove that $\sum r(u_1, \ldots, u_t)$, summed over all $0 \le u_1, \ldots, u_t < m$ such that $r(u_1, \ldots, u_t) \ne 0$, and (46) holds, is at most $2(t + 2\pi,\lg m)^t r_{\max}$, where $r_{\max}$ is the maximum term $r(u_1, \ldots, u_t)$ in the sum....
TAOCP 2.3.1 Exercise 11
Section 2.3.1: Traversing Binary Trees Exercise 11. [ HM41 ] Analyze the average value of the largest stack size occurring during the execution of Algorithm T as a function of n , given that all binary trees with n nodes are considered equally probable. Verified: no Solve time: 49s Setup Let $H_n$ denote the largest number of entries simultaneously present in stack $A$ during the execution of Algorithm $T$ on...
TAOCP 2.2.2 Exercise 13
Section 2.2.2: Sequential Allocation Exercise 13. [ HM42 ] The value $\max(k_1, k_2)$ investigated in exercise 12 will be even greater if larger fluctuations in the tables are introduced by allowing random deletions as well as random insertions. Suppose we alter the model so that with probability $p$ the sequence value $a_j$ is interpreted as a deletion instead of an insertion; the process continues until $k_1 + k_2$ (the total...
TAOCP 2.2.2 Exercise 14
Section 2.2.2: Sequential Allocation Exercise 14. [ HM43 ] Generalize the result of exercise 12 to arbitrary $n \ge 2$, by showing that, when $n$ is fixed and $m$ approaches infinity, the quantity $$ \frac{m!}{n^m} \sum_{\substack{k_1+k_2+\cdots+k_n=m\k_1,k_2,\ldots,k_n\ge0}} \frac{\max(k_1,k_2,\ldots,k_n)}{k_1!k_2!\cdots k_n!} $$ has the asymptotic form $m/n + c_n\sqrt{m} + O(1)$. Determine the constants $c_2, c_3, c_4$, and $c_5$. Verified: no Solve time: - Setup Let $$ E_m=\frac{m!}{n^m} \sum_{\substack{k_1+\cdots+k_n=m\ k_j\ge0}} \frac{\max(k_1,\ldots,k_n)}{k_1!\cdots k_n!}. $$...
TAOCP 1.3.3 Exercise 23
Section 1.3.3: Applications to Permutations Exercise 23. [ HM42 ] (Golomb, Shepp, Lloyd.) If $l_n$ denotes the average length of the longest cycle in a permutation of $n$ objects, show that $l_n \approx \lambda n + \tfrac{1}{2}\lambda$, where $\lambda \approx 0.62433$ is a constant. Prove in fact that $\lim_{n \to \infty}(l_n - \lambda n - \tfrac{1}{2}\lambda) = 0$. Verified: no Solve time: 11m45s Corrected Solution for Exercise 1.3.3.23 (Golomb, Shepp,...
TAOCP 1.3.3 Exercise 31
Section 1.3.3: Applications to Permutations Exercise 31. [ HM38 ] Generalizing exercises 29 and 30, prove that the $j$th man to be executed, for general $m$ and $n$, is in position $x$, where $x$ may be computed as follows: Set $x \leftarrow jm$; then, while $x > n$, set $x \leftarrow \lfloor (m(x - n) - 1)/(m - 1)\rfloor$. Consequently the average number of fixed elements, for $1 \le n...
TAOCP 1.2.10 Exercise 13
Section 1.2.10: Analysis of an Algorithm Exercise 13. [ HM38 ] A sequence of probability generating functions $G_n(z)$ with means $\mu_n$ and deviations $\sigma_n$ is said to approach a normal distribution if $$ \lim_{n\to\infty} e^{-it\mu_n/\sigma_n}G_n(e^{it/\sigma_n}) = e^{-t^2/2} $$ for all real values of $t$. Using $G_n(z)$ as given by Eq. (8), show that $G_n(z)$ approaches a normal distribution. Verified: yes Solve time: 7m56s Setup Let $$ G_n(z)=\frac1{n!}(z+1)(z+2)\cdots(z+n-1), $$ as given...