#hm-project
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 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 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 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.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.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...