#hm-project
TAOCP 5.4.1 Exercise 22
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 22. [ HM40 ] The purpose of this exercise is to determine the average run length obtained in natural selection, when $P' > P$. Let $\kappa = k + \theta$ be a real number $\ge 1$, where $k = \lfloor \kappa \rfloor$ and $\theta = \kappa \bmod 1$, and consider the function $F(\kappa) = F_k(\theta)$, where $F_k(\theta)$ is the polynomial defined by...
TAOCP 5.3.4 Exercise 40
Section 5.3.4: Networks for Sorting Exercise 40. [ HM44 ] Comparators $[i_1:i_1+1][i_2:i_2+1]\ldots[i_r:i_r+1]$ are chosen at random, with each value of $i_k \in {1, 2, \ldots, n-1}$ equally likely; the process stops when the network contains a bubble sort configuration like that of Fig. 47 as a subnetwork. Prove that $r \le 4n^2 + O(n^{3/2} \log n)$, except with probability $O(n^{-1000})$. Verified: no Solve time: 32m43s Setup The bubble sort configuration...
TAOCP 5.3.3 Exercise 24
Section 5.3.3: Minimum-Comparison Selection Exercise 24. [ HM40 ] Prove that $\overline{V}_t(n) \le n + t + O(\sqrt{n \log n})$ for $t \le \lceil n/2 \rceil$. Hint: Show that with this many comparisons we can in fact find both the $\lfloor t - \sqrt{t \ln n} \rfloor$th and $\lceil t + \sqrt{t \ln n} \rceil$th elements, after which the $t$th is easily located. Verified: no Solve time: 20m25s We need...
TAOCP 5.2.2 Exercise 53
Section 5.2.2: Sorting by Exchanging Exercise 53. [ HM42 ] Analyze the average number of bit inspections and exchanges done by radix exchange when the input data consists of infinite-precision binary numbers in $[0\ldots 1)$, each of whose bits is independently equal to 1 with probability $p$. (Only the case $p = \frac{1}{2}$ is discussed in the text; the methods we have used can be generalized to arbitrary $p$.) Consider...
TAOCP 5.2.2 Exercise 49
Section 5.2.2: Sorting by Exchanging Exercise 49. [ HM44 ] Extend the asymptotic formula (47) for $U_n$ to $O(n^{-1})$. Verified: no Solve time: 13m24s Setup In the analysis of bubble sort (Algorithm B) the average number of comparisons is [ C_{\text{ave}} = \binom{n+1}{2} - U_n, ] where the quantity (U_n) is defined by [ U_n = \frac{1}{n!}\sum_{0\le r<s\le n} s!, r^{,n-s}. ] The text derives an asymptotic formula for (U_n)...
TAOCP 5.2.2 Exercise 29
Section 5.2.2: Sorting by Exchanging Exercise 29. [ HM40 ] Continuing exercise 28, find the asymptotic value of the number of comparisons in Singleton's "median of three" method. Verified: no Solve time: 25m35s Setup Let (C_N) denote the average number of key comparisons performed by Singleton’s median‑of‑three quicksort when sorting (N) distinct elements, excluding the three comparisons used to find the median of the first, middle, and last elements. For...
TAOCP 5.2.2 Exercise 16
Section 5.2.2: Sorting by Exchanging Exercise 16. [ HM42 ] Find the asymptotic value of the average number of exchanges occurring when Batcher's method is applied to a random permutation of $N$ distinct elements, assuming that $N$ is a power of two. Verified: no Solve time: 25m39s Setup We consider Batcher's merge‑exchange sort (Algorithm M in the text) applied to a random permutation of (N = 2^t) distinct keys. The...
TAOCP 5.1.4 Exercise 40
Section 5.1.4: Tableaux and Involutions Exercise 40. [ HM43 ] Suppose a random Young tableau has been constructed by successively placing the numbers $1, 2, \ldots, n$ in such a way that each possibility is equally likely when a new number is placed. For example, the tableau (1) would be obtained with probability $\frac{1}{2} \cdot \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{1}{4} \cdots$ using this procedure. The resulting shape $(n_1, n_2, \ldots,...
TAOCP 1.2.11.3 Exercise 14
Section 1.2.11.3: Some Asymptotic Calculations Exercise 14. ▶ [ HM39 ] (N. G. de Bruijn.) The purpose of this exercise is to find the asymptotic expansion of $\sum_{k=0}^n k^{n+\alpha}e^{-k}$ for fixed $\alpha$, as $n\to\infty$. a) Replacing $k$ by $n-k$, show that the given sum equals $n^{n+\alpha}e^{-n}\sum_{k=0}^n e^{-k^2/2n}f(k,n)$, where $$ f(k,n)=\left(1-\frac{k}{n}\right)^\alpha \exp!\left(-\frac{k^3}{3n^2}-\frac{k^4}{4n^3}-\cdots\right). $$ b) Show that for all $m\ge 0$ and $\epsilon>0$, the quantity $f(k,n)$ can be written in the form...
TAOCP 1.2.11.3 Exercise 13
Section 1.2.11.3: Some Asymptotic Calculations Exercise 13. [ HM42 ] (S. Ramanujan.) Prove that $R(n)-Q(n)=\dfrac{2}{3}+ \dfrac{8}{135(n+\theta(n))}$, where $\dfrac{2}{21}\le \theta(n)\le \dfrac{8}{45}$. (This implies the much weaker result $R(n+1)-Q(n+1)<R(n)-Q(n)$.) Verified: no Solve time: 1h53m Solution We work within the notation of Section 1.2.11.3. The three sums are [ Q(n)=\sum_{k=1}^{n}\frac{n!}{(n-k)!,n^{k}},\qquad R(n)=\sum_{k\ge 0}\frac{n!,n^{k}}{(n+k)!},\qquad Q(n)+R(n)=\frac{n!,e^{n}}{n^{n}}. \tag{4} ] The incomplete gamma function (\gamma(a,x)=\int_{0}^{x}e^{-t}t^{a-1}dt) satisfies (Eq. (9)) [ R(n)=\frac{n!,e^{n}}{n^{n}},\frac{\gamma(n,n)}{(n-1)!}, ] hence [ R(n)-Q(n)=\frac{n!,e^{n}}{n^{n}}\left(2\frac{\gamma(n,n)}{(n-1)!}-1\right). \tag{1} ] 1. An...
TAOCP 1.2.11.3 Exercise 9
Section 1.2.11.3: Some Asymptotic Calculations Exercise 9. ▶ [ HM36 ] What is the behavior of $\gamma(x+1,px)/\Gamma(x+1)$ for large $x$? (Here $p$ is a real constant; and if $p<0$, we assume that $x$ is an integer, so that $t^x$ is well defined for negative $t$.) Obtain at least two terms of the asymptotic expansion, before resorting to $O$-terms. Verified: yes Solve time: 57m10s Setup Let [ G_x(p)=\frac{\gamma(x+1,px)}{\Gamma(x+1)}. ] The answer...
TAOCP 7.2.2.2 Exercise 223
Section 7.2.2.2: Satisfiability Exercise 223. [ HM40 ] [HM40] Step X9 deduces a binary clause that cannot be derived by resolution (see exercise 166). Prove that, nevertheless, the running time of Algorithm L on unsatisfiable input will never be less than the length of a shortest treelike refutation. Verified: no Solve time: 5m49s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly...
TAOCP 7.2.2.2 Exercise 216
Section 7.2.2.2: Satisfiability Exercise 216. [ HM38 ] (P. W. Purdom Jr., and C. A. Brown.) Extend the previous exercise to a more sophisticated kind of backtracking, where all choices forced by unit clauses are pursued before two-way branching is done. (The "pure literal rule" is not exploited, however, because it doesn't find all solutions.) Prove that the expected tree size is greatly reduced when $m = 200$ and $n...
TAOCP 7.2.2.2 Exercise 214
Section 7.2.2.2: Satisfiability Exercise 214. [ HM38 ] Although the previous model in the preceding exercise doesn't teach us how to solve SAT problems, it does lead to interesting mathematics: Let $0 < p < 1$ and consider the recurrence $$T_0 = 0; \qquad T_n = n + 2\sum_{k=0}^{n-1} \binom{n}{k} p^k (1-p)^{n-k} T_k, \quad \text{for } n > 0.$$ a) Find a functional relation satisfied by $T(z) = \sum_{n=0}^{\infty} T_n...
TAOCP 7.2.2.1 Exercise 187
Section 7.2.2.1: Dancing Links Exercise 187. [ HM39 ] Let $X(z) = \sum_{n \ge 0} x_n n!/n!$ generate the sequence $(x_n)$ of (82). a) Use (81) to prove that $X(z) = e^z \int_0^z \bigl[(2t-1)e^{4t} - (t-1)e^{3t} + 2te^{2t} + e^t\bigr] e^{-t^2} dt$. b) Let $T_{r,s}(z) = e^{rz} \int_0^z t^s e^{ct} e^{-t^2} dt$. Then $T_{r,0}(z)^!$ generates $(x_{n+1})$ in (83). c) Show that $T_{r,0}(z) = (T_{r+1,1}(z) + z^{r+1})/(r+1)$; furthermore, when $s >...
TAOCP 7.2.2 Exercise 70
Section 7.2.2: Backtracking Exercise 70. [ HM40 ] (M. Bousquet-Mélou.) Consider self-avoiding paths from the upper left corner of an $m \times n$ grid to the lower right, where each step is either up, down, or to the right. If we generate such paths at random, making either 1 or 2 or 3 choices at each step as in Algorithm E, the expected value $\text{E},D_{mn}$ is the total number of...
TAOCP 7.2.1.6 Exercise 35
Section 7.2.1.6: Generating All Trees Exercise 35. [ HM37 ] (D. B. Tyler and D. R. Hickerson.) Explain why the denominators of the asymptotic formula (16) are all powers of 2. Verified: no Solve time: 5m48s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge...
TAOCP 7.2.2 Exercise 15
Section 7.2.2: Backtracking Exercise 15. [ HM42 ] [HM42] (M. Simkin, 2021.) Show that $Q(n) \approx \sigma^n n!$ as $n \to \infty$, where $\sigma \approx 0.38068$. Verified: no Solve time: 4m57s 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.6 Exercise 108
Section 7.2.1.6: Generating All Trees Exercise 108. [ HM40 ] Extend the results of exercises 104–106 to directed graphs. 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$ be the number of terms...
TAOCP 7.2.1.6 Exercise 103
Section 7.2.1.6: Generating All Trees Exercise 103. ▶ [ HM39 ] ( Sandpiles. ) Consider any digraph $D$ on vertices $V_0, V_1, \ldots, V_n$ with $e_{ij}$ arcs from $V_i$ to $V_j$, where $e_{ii} = 0$. Assume that $D$ has at least one oriented spanning tree rooted at $V_0$; this assumption means that, if we number the vertices appropriately, we have $e_{i0} + \cdots + e_{i,(i-1)} > 0$ for $1 \le...
TAOCP 7.2.1.5 Exercise 64
Section 7.2.1.5: Generating All Set Partitions Exercise 64. [ HM41 ] Prove the approximate ratios following (36) and exercise 50. Verified: no Solve time: 6m20s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$. Let $k$ be the number of...
TAOCP 7.2.1.5 Exercise 62
Section 7.2.1.5: Generating All Set Partitions Exercise 62. [ HM40 ] Prove rigorously that $\binom{n}{m}$ is maximum either when $m = \lceil e^{-1}n \rceil$ or when $m = \lfloor e^{-1}n \rfloor$. Verified: no Solve time: 5m29s Setup We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge...
TAOCP 7.2.1.4 Exercise 48
Section 7.2.1.4: Generating All Partitions Exercise 48. [ HM40 ] [HM40] Analyze the running time of the algorithm in the previous exercise. Verified: no Solve time: 24m13s Setup Let $p(n)$ be the partition function. Algorithm N generates one random partition of $n$ using a sequence of states $(m,c_1,\dots,c_n)$, starting with $m=n$ and terminating when $m=0$. Each iteration performs: Step N3: selection of a random integer $M$ with $0 \le M...
TAOCP 7.2.1.4 Exercise 42
Section 7.2.1.4: Generating All Partitions Exercise 42. [ HM42 ] [HM42] Find the limiting shape, analogous to (49), for random partitions of n into at most θ√n parts, with no part exceeding φ√n, assuming that θφ > 1. Verified: no Solve time: 8m11s Solution Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$. Let the ordinary generating function be $$...
TAOCP 7.2.1.4 Exercise 41
Section 7.2.1.4: Generating All Partitions Exercise 41. [ HM42 ] [HM42] Extend the Hardy–Ramanujan–Rademacher formula (32) to obtain a convergent series for partitions of n into at most m parts, with no part exceeding l. Verified: no Solve time: 8m49s Solution Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$. Let the ordinary generating function be $$ F_{l,m}(x) = \sum_{n...
TAOCP 7.2.1.4 Exercise 28
Section 7.2.1.4: Generating All Partitions Exercise 28. [ HM42 ] [HM42] (D. H. Lehmer.) Show that the Hardy–Ramanujan–Rademacher coeffi- cients Ak(n) defined in (34) have the following remarkable properties: a) If k is odd, then A2k(km + 4n + (k2 −1)/8) = A2(m)Ak(n). b) If p is prime, pe > 2, and k ⊥2p, then Apek(k2m + p2en −(k2 + p2e −1)/24) = (−1)[pe=4]Ape(m)Ak(n). In this formula k2 + p2e...
TAOCP 7.2.1.2 Exercise 113
Section 7.2.1.2: Generating All Permutations Exercise 113. [ HM43 ] [HM43] Exactly how many universal cycles exist, for permutations of ≤9 objects? 7.2.1.3. Generating all combinations. Combinatorial mathematics is often described as “the study of permutations, combinations, etc.,” so we turn our attention now to combinations. A combination of n things, taken t at a time, often called simply a t-combination of n things, is a way to select a...
TAOCP 7.1.4 Exercise 168
Section 7.1.4: Binary Decision Diagrams Exercise 168. ▶ [ HM40 ] [HM40] Consider the following binary operations on ordered pairs z = (x, y): z ◦z′ = (x, y) ◦(x′, y′) = (x + x′, min(x + y′, x′ + y)); z • z′ = (x, y) • (x′, y′) = (x + x′ + min(y, y′), max(y, y′)). (These operations are associative and commutative.) Let S1 = {(1, 0)},...
TAOCP 7.1.4 Exercise 126
Section 7.1.4: Binary Decision Diagrams Exercise 126. [ HM42 ] [HM42] Analyze B(hπ n) for the organ-pipe permutation π = (2, 4, . . . , n, . . . , 3, 1). Verified: no Solve time: 4m17s Setup Let $h_n(x_1,\ldots,x_n)$ denote the hidden weighted bit function and let $h_n^\pi(x_1,\ldots,x_n)=h_n(x_{\pi(1)},\ldots,x_{\pi(n)})$ be its permutation by $\pi$. Let $\pi$ be the organ-pipe permutation $$ \pi = (2,4,6,\ldots,n,\ldots,5,3,1), $$ so indices are read...
TAOCP 3.5 Exercise 21
Section 3.5: What Is a Random Sequence? Exercise 21. [ HM40 ] [HM40] (L. H. Ramshaw.) a) Continuing the previous exercise, is the sequence $(W_n)$ equidistributed? b) Show that $(W_n)$ is the only $[0,..,1)$ sequence for which we have $\sum_{j=1}^{k} l_n^{(j)} \le \lg(1 + k/n)$ whenever $1 \le k \le n$. c) Let ${f_0(l_1, \ldots, l_k)}$ be any sequence of continuous functions on the sets of $n$-tuples ${(l_1, \ldots, l_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: 4m12s Setup Let a permutation of ${1,\dots,n}$ be...
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: 3m05s Setup Let $P_m(x)$ denote the $m$-fold leading-digit distribution function introduced in (16), and let $S_m(s)$ denote its limiting Benford-type distribution in the variable $s$, where $s \in [0,1)$ represents the fractional part of an iterated logarithm scale. From...
TAOCP 5.4.2 Exercise 16
Section 5.4.2: The Polyphase Merge Exercise 16. [ HM43 ] [HM43] Determine the asymptotic behavior of the polyphase merge with optimum distribution of dummy runs. Verified: yes Solve time: 3m53s Let $P = T-1 \ge 2$. Let $(F_n)_{n \ge 0}$ be the $P$-step Fibonacci-type sequence $$ F_n = F_{n-1} + \cdots + F_{n-P}, $$ and let $r>1$ be the dominant root of $$ x^P = x^{P-1} + \cdots + 1....
TAOCP 6.3 Exercise 34
Section 6.3: Digital Searching Exercise 34. [ HM40 ] [HM40] The purpose of this exercise is to find the asymptotic behavior of (18). a) Prove that, ifn > 2, 1 n Bee | wr-tar-by...4 (22 -1)"1+ 29 n > (ae = L( Qi(n, 1) ~ ata): jz Q2<k<n b) Show that the summand in (a) is approximately 1/(e”, 1), 1/x + 1/2, where x = n/2?; the resulting sum equals...
TAOCP 5.4.9 Exercise 10
Section 5.4.9: Disks and Drums Exercise 10. [ HM44 ] [HM44] (L. Hyafil, F. Prusker, J. Vuillemin.) Prove that when a and @ are fixed, Ai(n) = amn + Bn + Am(n) for all sufficiently large n, if m minimizes the coefficient in exercise 9. Verified: no Solve time: 1m02s Setup Let $A_i(n)$ denote the minimum transmission cost (external path length) among all merge trees with $n$ leaves, under fixed...
TAOCP 6.3 Exercise 43
Section 6.3: Digital Searching Exercise 43. [ HM42 ] [HM42] Analyze the height of a random M-ary trie that has N keys and cutoff parameter s as in exercise 20. (When s = 1, this is the length of the longest common prefix of N long random words in an M-ary alphabet.) Verified: no Solve time: 5m33s Working
TAOCP 5.4.1 Exercise 25
Section 5.4.1: Multiway Merging and Replacement Selection Exercise 25. [ HM40 ] [HM40] Consider the following procedure: N1. Read a record into a one-word “reservoir.” Then read another record, R, and let K be its key. N2. Output the reservoir, set LASTKEY to its key, and set the reservoir empty. N3. If K < LASTKEY then output R and set LASTKEY < K and go to N5. Na. If the...
TAOCP 6.2.2 Exercise 49
Section 6.2.2: Binary Tree Searching Exercise 49. [ HM42 ] [HM42] Analyze the average height of a random binary search tree. 6.2.3. Balanced Trees The tree insertion algorithm we have just learned will produce good search trees, when the input data is random, but there is still the annoying possibility that a degenerate tree will occur. Perhaps we could devise an algorithm that keeps the tree optimum at all times;...
TAOCP 6.3 Exercise 29
Section 6.3: Digital Searching Exercise 29. [ HM40 ] [HM40] What is the asymptotic average number of nodes, in an M-ary digital search tree, for which all M links are null? (We might save memory space by eliminating such nodes; see exercise 13.) Verified: no Solve time: 6m13s The previous argument failed because it replaced the actual recursive structure of a digital search tree by an unjustified occupancy limit. The...
TAOCP 5.3.3 Exercise 14
Section 5.3.3: Minimum-Comparison Selection Exercise 14. [ HM40 ] [HM40] Prove that $V_i(n) < n + t/4 + O(\sqrt{n \log n})$ for $t < \lfloor n/2 \rfloor$. Hint: Show that with this many comparisons we can in fact find both the $|t - \sqrt{t n}|$th and $[t + \sqrt{t n}]$th elements, after which the $t$th is easily located. Verified: no Solve time: 3m49s The previous argument fails because it treats...
TAOCP 4.6.4 Exercise 67
Section 4.6.4: Evaluation of Polynomials Exercise 67. [ HM40 ] (D. Coppersmith and S. Winograd.) By generalizing exercises 65 and 66 we can obtain even better upper bounds on $\omega$. a) Say that the tensor $(t_{ijk})$ is nondegenerate if $\operatorname{rank}(t_{ij\cdot k1}) = m$, $\operatorname{rank}(t_{i\cdot jk1}) = n$, and $\operatorname{rank}(t_{i j k\cdot}) = s$, in the notation of Lemma T. Prove that the tensor $T(m,n,s)$ for $mn \times ns$ matrix multiplication...
TAOCP 4.6.4 Exercise 53
Section 4.6.4: Evaluation of Polynomials Exercise 53. [ HM40 ] (S. Winograd.) Let $\omega$ be a complex root of unity, and consider the one-dimensional discrete Fourier transform $$f(s) = \sum_{t=1}^{n} F(t),\omega^{st}, \qquad \text{for } 1 \le s \le m.$$ a) When $m = p^e$ is a power of an odd prime, show that efficient normal schemes for computing cyclic convolutions of degree $(p-1)p^k$, for $0 \le k < e$, will...
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.4 Exercise 25
Section 4.5.4: Factoring into Primes Exercise 25. [ HM41 ] [HM41] (B. Riemann.) Prove that $$\pi(x) = \frac{x}{\ln x} + \frac{\pi(x^{1/2})}{2} + \frac{\pi(x^{1/3})}{3} + \cdots + \int_2^x \frac{dt}{\ln t} - 2 \sum_\rho \int_2^x \frac{x^{(\sigma+i\tau)\ln x}}{t + i\tau} + O(1),$$ where the sum is over all complex $\rho = \sigma + i\tau$ with $\zeta(\rho) = 0$ and $\langle \sigma + i\tau \rangle = 0$. Verified: yes Solve time: 4m02s The statement...
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: 6m54s Exercise 4.5.3.23 [ HM45 ] Prove equation (44) using results from the proof of Theorem W. Solution We first recall the relevant definitions and results. Let $F(x)$ denote a function introduced in TAOCP §4.5.3, and let $T_g(x)$ denote the cumulative sum of a function...
TAOCP 4.5.2 Exercise 28
Section 4.5.2: The Greatest Common Divisor Exercise 28. [ HM36 ] [HM36] Study the asymptotic behavior of $\psi_n$. Hint: See exercise 6.3–34. Verified: yes Solve time: 2m16s Setup Exercise 27 established equation (58), expressing $\psi_n$ in terms of Bernoulli numbers. In the notation of that equation, $$ \psi_n=\frac{2(2n)!}{(2\pi)^{2n}}\zeta(2n), $$ where $$ \zeta(2n)=\sum_{k\ge1}\frac1{k^{2n}}. $$ The problem asks for the asymptotic behavior of $\psi_n$ as $n\to\infty$. Equation (58) is the classical Euler...
TAOCP 4.5.2 Exercise 30
Section 4.5.2: The Greatest Common Divisor Exercise 30. [ HM39 ] [HM39] Continuing the previous exercise, determine $G_2(x)$. Verified: yes Solve time: 4m15s Exercise 4.5.2.30, Correct Solution We are asked to determine $G_2(x)$, the cumulative distribution function of the ratio $$ r_2 = \frac{\min(u_2,v_2)}{\max(u_2,v_2)} $$ after the second subtract-and-shift cycle of Algorithm B, continuing from Exercise 4.5.2.29. Step 1: Setup and Notation Let $(u,v)$ be independent positive integers uniformly drawn...
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 20
Section 3.5: What Is a Random Sequence? Exercise 20. ▶ [ HM36 ] [HM36] (N. G. de Bruijn and P. Erdős.) The first $n$ points of any $[0,..,1)$ sequence $(U_n)$ with $U_0 = 0$ divide the interval $[0,..,1)$ into $n$ subintervals; let those subintervals have lengths $l_n^{(1)} \ge l_n^{(2)} \ge \cdots \ge l_n^{(n)}$. Clearly $l_n^{(1)} \ge \frac{1}{n} \ge l_n^{(n)}$, because $l_n^{(1)} + \cdots + l_n^{(n)} = 1$. One way to...
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: 5m48s Solution to Exercise 3.5.16 [HM38] We are asked whether the coupon-collector's test holds for $\infty$-distributed sequences when there are more than two kinds of coupons. Let us carefully analyze this situation. Let...
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: no Solve time: 2m37s Setup We are asked to determine whether the exact Poisson distribution with mean $\mu$, for large $\mu$, can be...
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 3.3.2 Exercise 35
Section 3.3.2: Empirical Tests Exercise 35. ▶ [ HM42 ] (J. H. Lindholm, 1968.) Suppose we generate random bits ${Y_n}$ using the recurrence $$Y_n = (a_1 Y_{n-1} + a_2 Y_{n-2} + \cdots + a_k Y_{n-k}) \bmod 2,$$ for some choice of $a_0, \ldots, a_k$ such that the period length is $2^e - 1$ start with $Y_0 = 1$ and $Y_j = \cdots = Y_{2e} = 0$. Let $Z_n = (-1)^{X_n}...
TAOCP 3.3.2 Exercise 30
Section 3.3.2: Empirical Tests Exercise 30. [ HM41 ] Continuing the previous exercises, prove that if $m = n^3/\alpha$ we have $$p_n(m) = \frac{m^{n-1} e^{\alpha/4}}{n!,(n-1)!} \left(1 - \frac{13\alpha^2}{288n} + \frac{169\alpha^4 + 2016\alpha^3 - 1728\alpha^2 - 41472\alpha}{165888n^2} + O(n^{-3})\right)$$ for fixed $\alpha$ as $n \to \infty$. Find a similar formula for $q_n(m)$, the number of partitions of $m$ into $n$ distinct positive parts. Deduce the asymptotic probabilities that the birthday spacings...
TAOCP 3.3.2 Exercise 27
Section 3.3.2: Empirical Tests Exercise 27. ▶ [ HM36 ] [HM36] ( Iterated spacings. ) In the notation of the previous exercise, show that the numbers $S' 1 = nS {(1)}$, $S' 2 = (n-1)(S {(2)} - S_{(1)})$, $\ldots$, $S' n = 1 \cdot (S {(n)} - S_{(n-1)})$ have the same joint probability distribution as the original spacings $S_1, \ldots, S_n$ of $n$ uniform deviates. Therefore we can sort them...
TAOCP 3.3.2 Exercise 24
Section 3.3.2: Empirical Tests Exercise 24. [ HM37 ] [HM37] (G. Marsaglia.) Show that the serial test on $n$ overlapping $t$-tuples $(Y_1, Y_2, \ldots, Y_t)$, $(Y_2, Y_3, \ldots, Y_{t+1})$, $\ldots$, $(Y_n, Y_1, \ldots, Y_{t-1})$ can be carried out as follows: For each string $\alpha = a_1 \ldots a_m$ with $0 \le a_i < d$, let $N(\alpha)$ be the number of times $\alpha$ occurs as a substring of $Y_1 Y_2 \ldots...
TAOCP 3.3.2 Exercise 20
Section 3.3.2: Empirical Tests Exercise 20. [ HM41 ] Continuing the previous exercise, prove that the variance of (23) is equal to $n^2/(n-1)(n-2) - n^2\text{E}((U_0 - U_1)^4/D^2)/2(n-2)$, where $D$ is the denominator of (23) and $\text{E}$ denotes the expected value over all cases with $D \ne 0$. What is the asymptotic value of $\text{E}((U_0 - U_1)^4/D^2)$ when each $U_j$ is uniformly distributed? Verified: yes Solve time: 2m07s Setup Let the...
TAOCP 3.3.1 Exercise 25
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 25. [ HM36 ] [HM36] Suppose $Y_i = \sum_{j=1}^{n} a_{ij} X_j + \mu_i$ for $1 \le i \le m$, where $X_1, \ldots, X_n$ are independent random variables with mean zero and unit variance, and the matrix $A = (a_{ij})$ has rank $n$. a) Express the covariance matrix $C = (c_{ij})$, where $c_{ij} = E(Y_i - \mu_i)(Y_j - \mu_j)$, in terms...
TAOCP 3.3.1 Exercise 14
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 14. ▶ [ HM36 ] [HM36] Let $Z_k$ be given by Eq. (18). Show directly by using Stirling's approximation that the multinomial probability $$n! p_1^{k_1} \cdots p_k^{k_k} / Y_1! \cdots Y_k! = e^{-V/2} / \sqrt{(2\pi)^{k-1} p_1 \cdots p_k} + O(n^{-k/2}),$$ if $Z_1, Z_2, \ldots, Z_k$ are bounded as $n \to \infty$. (This idea leads to a proof of the chi-square...
TAOCP 7.1.3 Exercise 192
Section 7.1.3: Bitwise Tricks and Techniques Exercise 192. [ HM38 ] [HM38] The shortest parity pattern that begins with a given string can be quite long; for example, it turns out that the perfect pattern of width 120 whose first row is 10 . . . 0 has length 36,028,797,018,963,966(!). The purpose of this exercise is to consider how to calculate the interesting function c(q) = 1+max{ m | there...
TAOCP 7.1.3 Exercise 17
Section 7.1.3: Bitwise Tricks and Techniques Exercise 17. [ HM36 ] The results of exercise 16 make it possible to decide whether or not any two given animating functions are equal. Is there an algorithm that decides whether any given expression is identically zero, when that expression is constructed from a finite number of integer variables and constants using only the binary operations $+$ and $\oplus$? What if we also...
TAOCP 7.1.3 Exercise 163
Section 7.1.3: Bitwise Tricks and Techniques Exercise 163. [ HM41 ] [HM41] Devise a way to navigate through the triangles in the tiling of Fig. 18. Verified: yes Solve time: 2m32s The previous solution fails because it assumes finiteness of triangle types without deriving it from the actual construction of Fig. 18, and then builds a finite-state machine on top of an unjustified premise. The corrected solution must first extract...
TAOCP 7.1.3 Exercise 162
Section 7.1.3: Bitwise Tricks and Techniques Exercise 162. ▶ [ HM37 ] [HM37] Explain how to draw the pentagrid, Fig. 14. What circles are present? Verified: no Solve time: 5m19s The previous solution fails because it replaces the actual object in Fig. 14 with an ideal-pentagon construction whose vertices lie on the boundary circle. The pentagrid is instead the reflection tiling generated by a regular hyperbolic pentagon with interior vertices...
TAOCP 7.1.3 Exercise 127
Section 7.1.3: Bitwise Tricks and Techniques Exercise 127. [ HM40 ] [HM40] Prove that at least Ω(log n/log log n) broadword steps are needed to compute the parity function, (νx) mod 2, using the theory of circuit complexity. [Hint: Every broadword operation is in complexity class AC0.] Verified: no Solve time: 3m52s The original proof fails because it misclassifies arithmetic as $\mathrm{AC}^0$. The correct repair is to avoid this entirely...
TAOCP 7.1.3 Exercise 10
Section 7.1.3: Bitwise Tricks and Techniques Exercise 10. [ HM40 ] ( Nimbers , also known as Conway's field. ) Continuing exercise 8, define the operation $x \otimes y$ of "nim multiplication" recursively by the formula $$x \otimes y = \mathrm{mex}{(x \otimes j) \oplus (i \otimes y) \oplus (i \otimes j) \mid 0 \le i < x, 0 \le j < y}.$$ Prove that $\oplus$ and $\otimes$ define a field...
TAOCP 7.1.1 Exercise 67
Section 7.1.1: Boolean Basics Exercise 67. ▶ [ HM40 ] (J. W. Milnor and O. Scheinke.) A triangular grid of order $n$, illustrated here for $n = 3$, contains $(n+2)(n+1)/2$ points with nonnegative "barycentric coordinates" $xyz$, where $x + y + z = n$. Two points are adjacent if they differ by $\pm 1$ in exactly two coordinate positions. A point is said to lie on the $x$ side if...
TAOCP 7.1.1 Exercise 34
Section 7.1.1: Boolean Basics Exercise 34. ▶ [ HM37 ] Continuing exercise 33, let $c(m,n)$ be the average total number of implicants, and let $p(m,n)$ be the average total number of prime implicants. a) If $0 \le m \le 2^n/n$, show that $m \le c(m,n) \le \frac{1}{2}m + O(m/n)$ and $p(m,n) \ge me^{-1} + O(m/n)$; hence $p(m,n) = \Theta(c(m,n))$ in this range. b) Now let $2^n/n \le m \le (1-\varepsilon)2^n$,...
TAOCP 7.1.1 Exercise 131
Section 7.1.1: Boolean Basics Exercise 131. [ HM42 ] Table 3 makes it clear that there are many more Horn functions than Krom functions. What is the asymptotic number of Horn functions, as $n \to \infty$? Verified: no Solve time: 4m53s A Boolean function $f:{0,1}^n\to{0,1}$ is Horn iff its set of true assignments is closed under intersection. Equivalently, these true sets are exactly the Moore families (closure systems) on $[n]$,...
TAOCP 2.3.1 Exercise 11
Section 2.3.1: Traversing Binary Trees Exercise 11. [ HM41 ] Verified: no Solve time: 49s Let $B_n$ denote the number of binary trees with $n$ nodes. By the argument of Section 2.3.1, these satisfy the recurrence $$ B_0 = 1,\qquad B_n = \sum_{k=0}^{n-1} B_k B_{n-1-k}, $$ hence $$ B_n = \frac{1}{n+1}\binom{2n}{n}, $$ the $n$th Catalan number. Suppose a binary tree with $n$ nodes has left subtree containing $k$ nodes and...
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 ] Verified: no Solve time: - For fixed $n$, the multinomial vector satisfies the multivariate central limit theorem. Write $$ K_j=\frac{m}{n}+\sqrt m,X_j. $$ Then $(X_1,\ldots,X_n)$ converges in distribution to a centered normal vector with covariance matrix $$ \Sigma_{ii}=\frac{n-1}{n^2}, \qquad \Sigma_{ij}=-\frac1{n^2} \quad(i\neq j). $$ Equivalently, $$ X_j=\frac1{\sqrt n}(Y_j-\bar Y), $$ where $Y_1,\ldots,Y_n$ are independent $N(0,1)$ variables and $$ \bar Y=\frac1n\sum_{r=1}^nY_r. $$ Since subtraction...
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: 2m26s Setup Let $$ G_n(z)=\prod_{k=2}^{n}\frac{z+k-1}{k} $$ be the...