#math-project
TAOCP 5.4.4 Exercise 15
Section 5.4.4: Reading Tape Backwards Exercise 15. [ M39 ] Karp’s preorder construction in the text yields trees with one-way merges at several terminal nodes. Prove that when $T = 3$ it is possible to construct asymptotically optimal 3-lifo trees in which two-way merging is used throughout. In other words, let $\hat K_T(n)$ be the minimum external path length over all $T$-lifo trees with $n$ external nodes, such that every...
TAOCP 5.4.4 Exercise 18
Section 5.4.4: Reading Tape Backwards Exercise 18. ▶ [ M38 ] Suppose that $T$ tape units are available, for some $T \ge 3$, and that T1 contains $N$ records while the remaining tapes are empty. Is it possible to reverse the order of the records on T1 in fewer than $\Omega(N \log N)$ steps, without reading backwards? (The operation is, of course, trivial if backwards reading is allowed.) See exercise...
TAOCP 5.3.4 Exercise 65
Section 5.3.4: Networks for Sorting Exercise 65. [ M38 ] Given a pair sequence $(a_1, b_1)\ldots(a_M, b_M)$ as in exercise 64, let $c_i$ be the number of pairs $(j, k)$ such that $j < k < i$ and $(a_i, b_i)$, $(a_j, b_j)$, $(a_k, b_k)$ forms a triangle. a) Prove that the average number of comparisons made by the restricted uniform sorting algorithm is $\sum_{i=1}^{M} 2/(c_i + 2)$. b) Use the...
TAOCP 5.3.3 Exercise 20
Section 5.3.3: Minimum-Comparison Selection Exercise 20. [ M42 ] What is the asymptotic value of $\overline{V}_2(n) - n$, as $n \to \infty$? Verified: no Solve time: 20m17s Setup We consider the problem of finding the second largest element among (n) distinct elements using comparisons. The optimal worst-case algorithm is the tournament method (tree selection), which first finds the largest element in (n-1) comparisons, then finds the second largest among the...
TAOCP 5.3.3 Exercise 23
Section 5.3.3: Minimum-Comparison Selection Exercise 23. [ M42 ] What is the asymptotic value of $V_{\lceil n/2 \rceil}(n)$, as $n \to \infty$? Verified: no Solve time: 12m31s Setup We are asked for the asymptotic value of (V_{\lceil n/2 \rceil}(n)) as (n\to\infty), where (V_t(n)) is the minimum number of comparisons required in the worst case to determine the (t)‑th largest element of a set of (n) elements. The median is the...
TAOCP 5.3.3 Exercise 19
Section 5.3.3: Minimum-Comparison Selection Exercise 19. [ M42 ] Extend Table 2 to $n = 9$. Verified: no Solve time: 4m38s Setup Let (V_t(n)) denote the minimum number of comparisons required to select the (t)‑th largest element from a set of (n) elements, as defined in Section 5.3.3. Table 2 of the text lists the exact values of (V_t(n)) for (1 \le n \le 8). The exercise asks to extend...
TAOCP 5.3.2 Exercise 13
Section 5.3.2: Minimum-Comparison Merging Exercise 13. [ M42 ] (R. L. Graham.) Show that the solution to the recurrence in exercise 12 may be expressed as follows. Define the function $G(x)$, for $0 < x < \infty$, by the rules $$G(x) = \begin{cases} 1, & \text{if } 0 < x \le \frac{5}{7}; \ \frac{1}{2} + \frac{7}{8} G(8x - 5), & \text{if } \frac{5}{7} < x \le \frac{3}{4}; \ \frac{7}{2} G(2x...
TAOCP 5.3.1 Exercise 31
Section 5.3.1: Minimum-Comparison Sorting Exercise 31. [ M38 ] Continuing exercise 30, prove that $S_e(5) = 8$. Verified: no Solve time: 11m50s We need to solve exercise 31 from Volume 3, Section 5.3.1: "Continuing exercise 30, prove that S_e(5) = 8." First, understand the context. Exercise 30 defines S_e(n) as the minimum number of comparison-exchanges needed in the worst case to sort n elements by means of a comparison-exchange tree....
TAOCP 5.3.1 Exercise 32
Section 5.3.1: Minimum-Comparison Sorting Exercise 32. [ M42 ] Continuing exercise 31, investigate $S_e(n)$ for small values of $n > 5$. Verified: no Solve time: 4m51s Setup Let (S_e(n)) denote the minimum worst-case number of comparison-exchanges required to sort (n) distinct elements, as defined in Exercise 30. We already know from Exercises 30 and 31 that [ S_e(n) \le S(n) + n - 1, \qquad S_e(1)=0,; S_e(2)=1,; S_e(3)=3,; S_e(4)=5,; S_e(5)=8....
TAOCP 5.3.1 Exercise 26
Section 5.3.1: Minimum-Comparison Sorting Exercise 26. [ M42 ] Find a sorting procedure for seven elements that minimizes the average number of comparisons performed. Verified: no Solve time: 16m45s Setup We consider the problem of sorting 7 distinct elements using only binary comparisons. A sorting procedure corresponds to an extended binary decision tree whose internal nodes are comparisons between two elements and whose 5040 external nodes (leaves) are the permutations...
TAOCP 5.2.3 Exercise 34
Section 5.2.3: Sorting by Selection Exercise 34. [ M41 ] How many leftist trees with $N$ nodes are possible, ignoring the KEY values? The sequence begins 1, 1, 2, 4, 8, 17, 38, 87, 203, 482, 1160, $\ldots$; show that the number is asymptotically $a b^N N^{-3/2}$ for suitable constants $a$ and $b$, using techniques like those of exercise 2.3.4.4-4. Verified: no Solve time: 49m33s We need to solve exercise...
TAOCP 5.2.2 Exercise 15
Section 5.2.2: Sorting by Exchanging Exercise 15. [ M38 ] The object of this exercise is to analyze the function $c(N)$ of exercise 14 , and to find a formula for $c(N)$ when $N = 2^{e_1} + 2^{e_2} + \cdots + 2^{e_r}$, $e_1 > e_2 > \cdots > e_r \ge 0$. a) Let $a(N+1) = a(N) - c(N)$. Prove that $a(2n) = a(n) + \lfloor \lg(2n) \rfloor$, and $a(2n+1) =...
TAOCP 5.2.1 Exercise 27
Section 5.2.1: Sorting by Insertion Exercise 27. [ M41 ] (Bjørn Poonen.) (a) Prove that there is a constant $c$ such that if $m$ of the increments $h_s$ in Algorithm D are less than $N/2$, the running time is $\Omega(N^{1+1/\sqrt{cm}})$ in the worst case. (b) Consequently the worst-case running time is $\Omega(N(\log N / \log \log N)^2)$ for all sequences of increments. Verified: no Solve time: 5m07s Solution Setup Let...
TAOCP 5.2.1 Exercise 24
Section 5.2.1: Sorting by Insertion Exercise 24. [ M43 ] Prove that Theorem P is best possible, in the sense that the exponent 3/2 cannot be lowered. Verified: no Solve time: 23m21s Setup Theorem P (as proved in the text) states that if the increments are [ h_0=1,\qquad h_{k+1}=2h_k+1\quad (k\ge 0), ] so that (h_k=2^{,k+1}-1), then the total number of moves performed by Algorithm D when sorting (N) records is...
TAOCP 5.1.4 Exercise 44
Section 5.1.4: Tableaux and Involutions Exercise 44. [ M37 ] Show that the average number of flips required to sort a random arrangement of $n$ genes is greater than $n - H_n$, if all $2^n , n!$ genome rearrangements are equally likely. Verified: no Solve time: 27m06s We need to solve Exercise 44 from TAOCP Volume 3, Section 5.1.4. The exercise: 44. [M37] Show that the average number of flips...
TAOCP 5.1.4 Exercise 39
Section 5.1.4: Tableaux and Involutions Exercise 39. [ M38 ] (I. M. Pak and A. V. Stoyanovskii, 1992.) Let $P$ be an array of shape $(n_1, \ldots, n_m)$ that has been filled with any permutation of the integers ${1, \ldots, n}$, where $n = n_1 + \cdots + n_m$. The following procedure, which is analogous to the "siftup" algorithm in Section 5.2.3, can be used to convert $P$ to a...
TAOCP 5.1.4 Exercise 28
Section 5.1.4: Tableaux and Involutions Exercise 28. [ M43 ] Prove that the average length of the longest increasing subsequence of a random permutation of ${1, 2, \ldots, n}$ is asymptotically $2\sqrt{n}$. (This is the average length of row 1 in the correspondence of Theorem A.) Verified: no Solve time: 9m32s Setup Let (S_n) be the symmetric group on ({1,2,\ldots,n}). For a permutation (\pi\in S_n), let (L(\pi)) denote the length...
TAOCP 5.1.4 Exercise 14
Section 5.1.4: Tableaux and Involutions Exercise 14. [ M43 ] Find a more direct proof of Theorem D, part (c). Verified: no Solve time: 20m52s Setup We state Theorem D(c) in the notation of Section 5.1.4. Theorem D(c). Let (\pi) be a permutation of ({1,2,\ldots,n}) and let ((P,Q)) be the corresponding tableaux under the Robinson-Schensted correspondence of Theorem A. If the shape of (P) is ((n_1,n_2,\ldots,n_m)), then for every (k)...
TAOCP 5.1.4 Exercise 30
Section 5.1.4: Tableaux and Involutions Exercise 30. [ M41 ] (M. P. Schützenberger.) Show that the operation of going from $P$ to $P^5$ is a special case of an operation applicable in connection with any finite partially ordered set, not merely a tableau: Label the elements of a partially ordered set with the integers ${1, 2, \ldots, n}$ in such a way that the partial order is consistent with the...
TAOCP 5.1.4 Exercise 22
Section 5.1.4: Tableaux and Involutions Exercise 22. [ M39 ] In how many ways can an array of shape $(n_1, n_2, \ldots, n_m)$ be filled with elements from the set ${1, 2, \ldots, N}$ with repetitions allowed , so that the rows are nondecreasing and the columns are strictly increasing? For example, the simple $m$-rowed shape $(1, 1, \ldots, 1)$ can be filled in $\binom{n}{m}$ ways; the 1-rowed shape $(n)$...
TAOCP 5.1.4 Exercise 19
Section 5.1.4: Tableaux and Involutions Exercise 19. [ M40 ] Find a formula for the number of ways to fill an array that is like a tableau but with two boxes removed at the left of row 1; for example, $$ \begin{array}{l} n_1 - 2 \text{ boxes} \ n_2 \text{ boxes} \ n_3 \text{ boxes} \ \vdots \end{array} $$ is such a shape. (The rows and columns are to be...
TAOCP 7.2.2.2 Exercise 365
Section 7.2.2.2: Satisfiability Exercise 365. [ M37 ] Prove that the clauses waerden (3, 3; n ) have a nontrivial (i.e., nonempty) covering assignment for all $n$ sufficiently large $n$ (although they're unsatisfiable). Verified: no Solve time: 3m47s Solution The information provided is not sufficient to derive the requested formulas. Exercise 7.2.2.2.357 depends on equation (155) and on the definition of the quantities $\pi_0$, $\pi_s$, the “field” of a variable...
TAOCP 7.2.2.2 Exercise 210
Section 7.2.2.2: Satisfiability Exercise 210. [ M36 ] But the result in the previous exercise can be improved when $k$ is large. Use the Local Lemma to show that every 7SAT problem with at most 13 occurrences of each variable is satisfiable. Verified: no Solve time: 6m02s Setup Let $F$ be a 7SAT instance. Let the variables of $F$ be chosen independently and uniformly from ${0,1}$. For each clause $C$...
TAOCP 7.2.2.1 Exercise 385
Section 7.2.2.1: Dancing Links Exercise 385. [ M36 ] [M36] (H. Post!, 2017.) Arbitrarily large motley cuboids can be constructed by repeatedly nesting one motley cuboid within another (see answer 367). Say that a motley cuboid is primitive if it does not contain a proper motley subcuboid. Do primitive motley cuboids of size $l \times m \times n$ exist only when $l = m = n = 7$? Verified: no...
TAOCP 7.2.2.1 Exercise 348
Section 7.2.2.1: Dancing Links Exercise 348. [ M41 ] [M41] Find the maximum number of "canonical bricks" ($1 \times 2 \times 4$) that can be packed into an $l \times m \times n$ box, leaving as few empty cells as possible. Verified: no Solve time: 4m14s The reviewer’s principal objection is based on a misinterpretation of the exercise. For arbitrary positive integers $l,m,n$, the maximum packing number of $1\times2\times4$ bricks...
TAOCP 7.2.2.1 Exercise 331
Section 7.2.2.1: Dancing Links Exercise 331. [ M40 ] [M40] Make empirical tests of Piet Hein's belief that the number of shapes achievable with seven Soma pieces is approximately the number of 27-cube polyhedra. Verified: no Solve time: 2m20s Setup Let a Soma shape mean a connected set of $27$ unit cubes that can be tiled by the seven fixed Soma pieces, with congruent shapes identified under the symmetries of...
TAOCP 7.2.2.1 Exercise 320
Section 7.2.2.1: Dancing Links Exercise 320. ▶ [ M38 ] Explain how to enumerate all of the $N$-aboloes that are convex . How many of the convex 56-aboloes can be packed by the fourteen tetraboloes? Verified: no Solve time: 5m The corrected solution is given below in a textbook style, with the enumeration and verification steps made explicit. Edit A polyabolo is a finite union of elementary right isosceles triangles...
TAOCP 7.2.1.6 Exercise 91
Section 7.2.1.6: Generating All Trees Exercise 91. [ M37 ] (Nijenhuis and Wilf.) Show that a random oriented tree can be generated with a procedure analogous to the random partition algorithm of exercise 7.2.1.4–47. Verified: yes Solve time: 1m56s Setup Let $T_n$ denote the set of rooted ordered trees with $n$ internal nodes in the sense of Algorithm B of Section 7.2.1.6, represented by left and right links $(l_1,\dots,l_n)$ and...
TAOCP 7.2.1.6 Exercise 90
Section 7.2.1.6: Generating All Trees Exercise 90. ▶ [ M37 ] If $p_1 \ldots p_n$ is a canonical sequence of parent pointers for an oriented forest, with the graph with vertices ${0, 1, \ldots, n}$ and edges ${k - p_k \mid 1 \le k \le n}$ is a free tree , namely a connected graph with no cycles. (See Theorem 2.3.4.1A.) Conversely, every free tree corresponds to at least one...
TAOCP 7.2.1.6 Exercise 72
Section 7.2.1.6: Generating All Trees Exercise 72. [ M38 ] [M38] If you start with a single row $\sigma_1, \sigma_2, \ldots, \sigma_r$ of length $s$ and apply the growth rule (36) repeatedly $n$ times, how many rows do you obtain? Verified: no Solve time: 4m33s Setup Let a row be a string $\sigma_1 \sigma_2 \ldots \sigma_s$ of fixed length $s$. The growth rule (36) acts on a row to produce...
TAOCP 7.2.2 Exercise 48
Section 7.2.2: Backtracking Exercise 48. [ M42 ] $[M42]$ Find a maximum-size commafree code of length 4 on $m = 5$ letters. Verified: yes Solve time: 1m31s Setup Let $A={1,2,3,4,5}$ and let $A^4$ be the set of all words $x_1x_2x_3x_4$ over $A$. A set $C \subseteq A^4$ is a commafree code of length $4$ if for any $u,v \in C$, the concatenation $uv$ contains no codeword of $C$ as a...
TAOCP 7.2.1.6 Exercise 37
Section 7.2.1.6: Generating All Trees Exercise 37. [ M40 ] Analyze the Zaks–Richards algorithm for generating all trees with a given distribution $n_0, n_1, n_2, \ldots, n_d$ of degrees (exercise 21). Hint: See exercise 2.3.4.4–32. Verified: no Solve time: 5m59s 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 55
Section 7.2.1.4: Generating All Partitions Exercise 55. ▶ [ M37 ] [M37] Continuing the previous exercise, say that α covers β if α ⪰β and α ̸= β, and if α ⪰γ ⪰β implies that γ = α or γ = β. For example, Fig. 52 illustrates the covering relations between partitions of the number 12. a) Let us write α ≻β if α = a1a2 . . . and...
TAOCP 7.2.1.3 Exercise 65
Section 7.2.1.3: Generating All Combinations Exercise 65. [ M40 ] [M40] Enumerate the total number of genlex Gray paths on subcubes that use only the transformations allowed in exercise 64. How many of those paths are cycles? Verified: no Solve time: 7m53s Solution Let the $2 \times 2 \times 3$ torus be the Cartesian product $C_2 \times C_2 \times C_3,$ so its elements are triples $(i,j,k)$ with $i \in {0,1}$,...
TAOCP 7.2.1.3 Exercise 63
Section 7.2.1.3: Generating All Combinations Exercise 63. [ M41 ] [M41] Show that all contingency tables for (r1, . . . , rm; c1, . . . , cn) can be gener- ated by changing exactly four entries of the matrix at each step. Verified: no Solve time: 20m11s Setup Let $(a_{ij})$ be an $m\times n$ contingency table with fixed row sums $\sum_{j=1}^n a_{ij}=r_i \quad (1\le i\le m)$ and column...
TAOCP 7.2.1.3 Exercise 54
Section 7.2.1.3: Generating All Combinations Exercise 54. [ M40 ] [M40] For what values of s and t can all (s, t)-combinations be generated if we allow end-around swaps an−1 ↔a0 in addition to adjacent interchanges aj ↔aj−1? Verified: no Solve time: 20m27s Correctness The proposed solution does not address the exercise. The problem asks for a characterization of values of $s$ and $t$ for which all $(s,t)$-combinations can be...
TAOCP 7.2.1.3 Exercise 52
Section 7.2.1.3: Generating All Combinations Exercise 52. [ M37 ] [M37] Generalizing Theorem P, find a necessary and sufficient condition that all permutations of the multiset {s0 · 0, . . . , sd · d} can be generated by adjacent transpo- sitions ajaj−1 ↔aj−1aj. Verified: no Solve time: 7m32s 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}....
TAOCP 7.2.1.3 Exercise 104
Section 7.2.1.3: Generating All Combinations Exercise 104. [ M41 ] [M41] The shadow of a binary string a1 . . . an is obtained by deleting one of its bits. For example, ∂110010010 = {10010010, 11010010, 11000010, 11001000, 11001010, 11001001}. Find a set PNn such that, if A is any set of N binary strings a1 . . . an, |∂A| ≥|PNn|. 7.2.1.3 GENERATING ALL COMBINATIONS 389 Verified: no Solve...
TAOCP 7.2.1.3 Exercise 103
Section 7.2.1.3: Generating All Combinations Exercise 103. ▶ [ M38 ] [M38] The shadow of a subcube a1 . . . an, where each aj is either 0 or 1 or ∗, is obtained by replacing some ∗by 0 or 1. For example, ∂0∗11∗0 = {0011∗0, 0111∗0, 0∗1100, 0∗1110}. Find a set PNst such that, if A is any set of N subcubes a1 . . . an having s...
TAOCP 7.2.1.2 Exercise 106
Section 7.2.1.2: Generating All Permutations Exercise 106. [ M40 ] [M40] Can exercise 105(b) be solved with a Gray-like code? Verified: no Solve time: 2m56s Setup A weak order on ${1,\dots,n}$ is represented in Exercise 105(b) by a sequence $a_1a_2\dots a_n$ where $a_j$ equals the number of symbols $\prec$ that precede $j$ in the underlying relation. The given examples for $n=3$ are $$ 000, 001, 011, 012, 010, 021, 101,...
TAOCP 7.2.1.1 Exercise 45
Section 7.2.1.1: Generating All n-Tuples Exercise 45. [ M40 ] [M40] (T. Feder and C. Subi, 2009.) This exercise constructs a large number of Gray cycles in the (4r+2)-cube G = G4 G3 G2 G1 G0 G−1, where Gi is an r-cube for i > 0 and G0 = G−1 = P2. The vertices v are (4r+2)-bit strings v4 . . . v0v−1, where vi has r bits for i...
TAOCP 7.2.1.1 Exercise 20
Section 7.2.1.1: Generating All n-Tuples Exercise 20. [ M36 ] [M36] The 16-bit codewords in the previous exercise can be used to transmit 8 bits of information, allowing transmission errors to be corrected if any one or two bits are corrupted; furthermore, mistakes will be detected (but not necessarily correctable) if any three bits are received incorrectly. Devise an algorithm that either finds the nearest codeword to a given 16-bit...
TAOCP 7.1.4 Exercise 182
Section 7.1.4: Binary Decision Diagrams Exercise 182. [ M38 ] [M38] (I. Wegener.) Does Bmin(Ln,n) grow exponentially as n →∞? Verified: no Solve time: 2m48s Setup Let $L_{n,n}(x_1,\ldots,x_n; y_1,\ldots,y_n)$ denote the leading bit of the product of two $n$-bit integers $x=\sum_{i=0}^{n-1} x_{i+1}2^i$ and $y=\sum_{j=0}^{n-1} y_{j+1}2^j$. Thus $L_{n,n}=1$ if and only if the most significant bit of $xy$ (bit position $2n-1$) equals $1$. Let $B_{\min}(L_{n,n})$ be the minimum possible number of...
TAOCP 7.1.4 Exercise 174
Section 7.1.4: Binary Decision Diagrams Exercise 174. ▶ [ M39 ] [M39] Let Sn be the number of Boolean functions f(x1, . . . , xn) whose BDD is “thin” in the sense that it has exactly one node labeled j j for 1 ≤j ≤n. Show that Sn is also the number of combinatorial objects of the following types: a) Dellac permutations of order 2n (namely, permutations p1p2 ....
TAOCP 7.1.4 Exercise 138
Section 7.1.4: Binary Decision Diagrams Exercise 138. ▶ [ M36 ] [M36] The purpose of this exercise is to develop an attractive algorithm that computes the master profile chart for a function f, given f’s QDD (not its BDD). a) Explain how to find n+1 2 weights of the master profile chart from a single QDD. b) Show that the jump-up operation can be performed easily in a QDD,...
TAOCP 7.1.4 Exercise 137
Section 7.1.4: Binary Decision Diagrams Exercise 137. [ M38 ] [M38] Given a graph, the optimum linear arrangement problem asks for a permu- tation π of the vertices that minimizes u−−v |uπ−vπ|. Construct a Boolean function f for which this minimum value is characterized by the optimum BDD size Bmin(f). Verified: no Solve time: 3m51s Setup Let $\Gamma_6 = g(0), g(1), \dots, g(2^6-1)$ be the 6-bit Gray binary code,...
TAOCP 3.5 Exercise 30
Section 3.5: What Is a Random Sequence? Exercise 30. ▶ [ M39 ] [M39] Construct a binary sequence that is $(2k)$-distributed, and for which $$\Pr{X_{2n} = 0} = \frac{1}{2} + \binom{2k-1}{k} \bigg/ 2^{2k}.$$ (Therefore the inequality in the previous exercise is the best possible.) Verified: no Solve time: 5m39s Let $(Y_n)_{n\ge 1}$ be an i.i.d. sequence of Bernoulli$(1/2)$ random variables. We will construct the required sequence $(X_n)$ as a deterministic...
TAOCP 5.4.8 Exercise 7
Section 5.4.8: Two-Tape Sorting Exercise 7. [ M40 ] [M40] (R. M. Karp.) Generalize the problem of exercise 6, replacing the linear path of an elevator by a network of roads to be traveled by a bus, given that the network forms any free tree. The bus has finite capacity, and the goal is to transport passengers to their destinations in such a way that the bus travels a minimum...
TAOCP 5.4.9 Exercise 24
Section 5.4.9: Disks and Drums Exercise 24. [ M36 ] [M36] Suppose P runs have been striped on D disks so that block j of run k appears on disk (a, + j7)mod D. A P-way merge will read those blocks in some chronological order such as (19). If groups of D blocks are to be input continuously, we will read at time ¢ the chronologically tth block stored on...
TAOCP 5.4.3 Exercise 11
Section 5.4.3: The Cascade Merge Exercise 11. [ M38 ] [M38] Let etc. Letting m k=0 Verified: yes Solve time: 1m09s Setup The exercise statement is incomplete. It ends after “Let … etc. Letting …” and shows only fragments “$m$” and “$k=0$”, without defining the objects to be studied or the expression to be proved. No definitions of the intended sequences, sums, or generating functions are present, and no identity...
TAOCP 6.3 Exercise 38
Section 6.3: Digital Searching Exercise 38. [ M40 ] [M40] Develop an algorithm to find the n-node tree having the minimum value of a- (internal path length) + 8 - (modified external path length), given a and £, in the sense of exercise 37. Verified: no Solve time: 4m50s The error in the previous solution is structural: it used an incorrect recurrence for the modified external path length and then...
TAOCP 5.4.2 Exercise 15
Section 5.4.2: The Polyphase Merge Exercise 15. [ M43 ] [M43] Prove or disprove: X'n-1(m) < Yn(m) implies that Xn(m) < Yn4i(m) < Sn42(m) <---. [Such a result would greatly simplify the calculation of Table 2.] Verified: yes Solve time: 1m43s Setup The statement concerns three families of quantities $X_n(m)$, $Y_n(m)$, $S_n(m)$, together with a primed variant $X'_{n-1}(m)$. The claimed implication is $$ X' {n-1}(m) < Y_n(m) ;\Rightarrow; X_n(m) <...
TAOCP 6.2.1 Exercise 22
Section 6.2.1: Searching an Ordered Table Exercise 22. [ M41 ] [M41] (A. C. Yao and F. F. Yao.) Show that an appropriate formulation of interpolation search requires asymptotically lglg N comparisons, on the average, when applied to N independent uniform random keys that have been sorted. Furthermore all search algorithms on such tables must make asymptotically lglg N comparisons, on the average. Verified: no Solve time: 4m46s We reconstruct...
TAOCP 6.2.1 Exercise 19
Section 6.2.1: Searching an Ordered Table Exercise 19. [ M42 ] [M42] Carry out a detailed analysis of the average running time of the algorithm suggested in exercise 14. Verified: no Solve time: 4m29s We restart the analysis from the structure actually used in Algorithm F (as modified in Exercise 14): a Fibonacci tree representation where the search space consists of all internal and external nodes of a full Fibonacci...
TAOCP 5.3.2 Exercise 18
Section 5.3.2: Minimum-Comparison Merging Exercise 18. [ M40 ] [M40] Study the average number of comparisons used by binary merge. Verified: yes Solve time: 2m16s Let the two sorted sequences have lengths $m$ and $n$. Assume the keys are distinct and all $\binom{m+n}{m}$ interleavings of the two sequences are equally likely. This induces a uniform random sequence of $m$ symbols $A$ and $n$ symbols $B$, and binary merge proceeds by...
TAOCP 5.3.3 Exercise 9
Section 5.3.3: Minimum-Comparison Selection Exercise 9. [ M42 ] [M42] Extend Table 2 to $n = 8$. Verified: no Solve time: 4m48s We construct all values for $V_t(8)$ using a single consistent method: an optimal 8-element tournament followed by explicit optimal selection in the induced comparison structure. All lower bounds are proved by adversary arguments based on indistinguishability of remaining partial orders. 1. Preliminaries: optimal tournament on 8 elements Perform...
TAOCP 5.3.2 Exercise 4
Section 5.3.2: Minimum-Comparison Merging Exercise 4. [ M42 ] [M42] Is $\underline{M}(m,n) > [\lg \binom{m+n}{m}]$ for all $m$ and $n$? Verified: yes Solve time: 1m14s Setup Let $\underline{M}(m,n)$ denote the lower-bound function for merging described in Section 5.3.2, and let $\left[\lg x\right]$ denote the greatest integer not exceeding $\lg x$. The question asks whether $\underline{M}(m,n) > \left[\lg \binom{m+n}{m}\right]$ holds for all integers $m,n \ge 1$. To disprove the statement, it...
TAOCP 6.2.2 Exercise 47
Section 6.2.2: Binary Tree Searching Exercise 47. [ M40 ] [M40] Generalize Theorems B and M from binary trees to t-ary trees. If possible, also allow the branching costs to be nonuniform as in exercise 33. Verified: no Solve time: 1m24s Setup A t-ary search tree is taken in the standard sense of Section 6.2.2, generalized so that each internal node contains up to $t-1$ keys and has up to...
TAOCP 6.2.2 Exercise 8
Section 6.2.2: Binary Tree Searching Exercise 8. [ M38 ] [M38] Let p(n,k) be the probability that k is the total internal path length of a tree built by Algorithm T from n randomly ordered keys. (The internal path length is the number of comparisons made by tree insertion sorting as the tree is being built.) a) Find a recurrence relation that defines the corresponding generating function. b) Compute the...
TAOCP 5.1.4 Exercise 9
Section 5.1.4: Tableaux and Involutions Exercise 9. [ M43 ] [M43] Find a more direct proof of Theorem D, part (c). Verified: no Solve time: 11m30s Setup Let $$ M= \begin{pmatrix} q_1&q_2&\cdots&q_n\ p_1&p_2&\cdots&p_n \end{pmatrix} $$ correspond to the pair of tableaux $(P,Q)$ under the construction of Theorem A. Theorem D(c) states that if both the $p$'s and the $q$'s are interpreted in the dual order, and if the columns are...
TAOCP 5.3.2 Exercise 11
Section 5.3.2: Minimum-Comparison Merging Exercise 11. [ M40 ] [M40] (F. K. Hwang, S. Lin.) Let $g_0 = \lfloor 4 \cdot 2^0 \rfloor$ and $g_{k+1} = \lfloor 2^{g_k} \rfloor$, for $k > 0$, so that $(g_0, g_1, g_2, \ldots) = (1, 1, 2, 3, 4, 6, 9, 13, 19, 27, 38, 54, 77, \ldots)$. Prove that it takes more than $t$ comparisons to merge two elements with $g_t$ elements, in...
TAOCP 6.3 Exercise 39
Section 6.3: Digital Searching Exercise 39. [ M43 ] [M43] Develop an algorithm to find optimum digital search trees, analogous to the optimum binary search trees considered in Section 6.2.2. Verified: yes Solve time: 4m28s We construct a fully rigorous solution by cleanly separating the structural lemma from the contraction argument, avoiding informal swapping arguments. Problem restatement We are given keys $K_1,\dots,K_n$ with probabilities $p_1,\dots,p_n>0$, $\sum_{i=1}^n p_i=1$. A digital search...
TAOCP 6.2.2 Exercise 33
Section 6.2.2: Binary Tree Searching Exercise 33. [ M41 ] [M41] In order to find the binary search tree that minimizes the running time of Program T, we should minimize the quantity 7C + C1 instead of simply minimizing the number of comparisons C’. Develop an algorithm that finds optimum binary search trees when different costs are associated with left and right branches in the tree. (Incidentally, when the right...
TAOCP 4.6.4 Exercise 68
Section 4.6.4: Evaluation of Polynomials Exercise 68. [ M45 ] Is there a way to evaluate the polynomial $$\sum_{1 \le i < j \le n} x_i x_j = x_1 x_2 + \cdots + x_{n-1} x_n$$ with fewer than $n - 1$ multiplications and $2n - 4$ additions? (There are $\binom{n}{2}$ terms.) Verified: no Solve time: 3m16s Setup Let $f(x_1,\ldots,x_n)=\sum_{1\le i<j\le n} x_i x_j.$ We count arithmetic complexity in the sense...
TAOCP 4.6.4 Exercise 59
Section 4.6.4: Evaluation of Polynomials Exercise 59. ▶ [ M40 ] (H. J. Nussbaumer, 1980.) The text defines the cyclic convolution of two sequences $(x_0, x_1, \ldots, x_{n-1})$ and $(y_0, y_1, \ldots, y_{n-1})$ to be the sequence $(z_0, z_1, \ldots, z_{n-1})$ where $z_k = x_0 y_k + \cdots + x_k y_0 + x_{k+1} y_{n-1} + \cdots + x_{n-1} y_{k+1}$. Let us define the negacyclic convolution similarly, but with $$z_k =...
TAOCP 4.6.1 Exercise 20
Section 4.6.1: Division of Polynomials Exercise 20. [ M40 ] Investigate approximate polynomial gcds and the accuracy of Euclid's algorithm: What can be said about calculation of the greatest common divisor of polynomials whose coefficients are floating point numbers? Verified: no Solve time: 18m04s Problem Understanding The game is played on a tree, which is an undirected, connected, acyclic graph. Each node is numbered from $1$ to $n$, and one...
TAOCP 4.6.1 Exercise 19
Section 4.6.1: Division of Polynomials Exercise 19. [ M39 ] (Common divisors of square matrices.) Exercise 18 shows that the concept of greatest common right divisor can be meaningful when multiplication is not commutative. Prove that any two $n \times n$ matrices $A$ and $B$ of integers have a greatest common right matrix divisor $D$. [ Suggestion: Design an algorithm whose inputs are $A$ and $B$ and whose outputs are...
TAOCP 4.5.4 Exercise 45
Section 4.5.4: Factoring into Primes Exercise 45. ▶ [ M41 ] (J. M. Pollard and Claus-Peter Schnorr.) Find an efficient algorithm to solve the congruence $$x^2 - ay^2 \equiv b \pmod{n}$$ for integers $x$ and $y$, given integers $a$, $b$, and $n$ with $ab \perp n$ and $n$ odd, even if the factorization of $n$ is unknown. [ Hint: Use the identity $(x_1^2 - ay_1^2)(x_2^2 - ay_2^2) = x^2 -...
TAOCP 4.5.4 Exercise 40
Section 4.5.4: Factoring into Primes Exercise 40. ▶ [ M36 ] (A. Shamir.) Consider an abstract computer that can perform the operations $x + y$, $x - y$, $x \cdot y$, and $\lfloor x/y \rfloor$ on integers $x$ and $y$ of arbitrary length, in just one unit of time, no matter how large those integers are. The machine stores integers in a random-access memory and it can select different program...
TAOCP 4.5.3 Exercise 41
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 41. [ M40 ] (J. Shallit, 1979.) Show that the regular continued expansion of $$\frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^4} + \cdots = \sum_{n \ge 0} \frac{1}{2^{2^n}}$$ contains only 1s and 2s and has a fairly simple pattern. Prove that the partial quotients of Liouville's numbers $\sum_{n \ge 1} l^{-n!}$ also have a regular pattern, when $l$ is any integer $\ge 2$. [The latter...
TAOCP 4.5.3 Exercise 37
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 37. [ M38 ] (T. S. Motzkin and E. G. Straus.) Let $a_1, \ldots, a_n$ be positive integers. Show that $\max K_s(a_{p(1)}, \ldots, a_{p(n)})$, over all permutations $p(1) \ldots p(n)$ of ${1, 2, \ldots, n}$, occurs when $a_{p(1)} \ge a_{p(n)} \ge a_{p(2)} \ge a_{p(n-1)} \ge \cdots$; and the minimum occurs when $a_{p(1)} \le a_{p(n)} \le a_{p(2)} \le a_{p(n-1)} \le \cdots \le a_{p(4)} \le...
TAOCP 4.5.3 Exercise 13
Section 4.5.3: Analysis of Euclid's Algorithm Exercise 13. [ M40 ] (J. Lagrange, 1767.) Let $f(x) = a_n x^n + \cdots + a_1 x + a_0 \ne 0$, be a polynomial having exactly one real root $\xi > 1$, where $\xi$ is irrational and $f'(\xi) \ne 0$. Experiment with a computer program to find the first thousand or so partial quotients of $\xi$, using the following algorithm (which essentially involves...
TAOCP 4.5.2 Exercise 32
Section 4.5.2: The Greatest Common Divisor Exercise 32. [ M42 ] [M42] Is there a unique continuous function $G(x)$ that satisfies (36) and (37)? Verified: no Solve time: 2m30s Setup Let $G$ be a continuous function on $[0,1]$ satisfying equations (36) and (37). In the notation of the section, equation (36) is $$ G(x)=\sum_{k\ge1}2^{-k} \left( G!\left(\frac{x}{x+2^k}\right) G!\left(\frac1{1+2^k x}\right) \right), \qquad 0\le x\le1, $$ and equation (37) gives the boundary conditions...
TAOCP 4.5.2 Exercise 20
Section 4.5.2: The Greatest Common Divisor Exercise 20. [ M37 ] [M37] Let $u$ and $v$ be odd integers, independently and uniformly distributed in the ranges $2^{n'} \le u < 2^{n'+1}$, $2^{n'} \le v < 2^{n'+1}$. What is the exact probability that a single subtract-and-shift cycle in Algorithm B reduces $u$ and $v$ to the ranges $2^{n'} \le u < 2^{n'+1}$, $2^{n'} \le v < 2^{n'+1}$, and $n$? Verified: yes...
TAOCP 4.4 Exercise 17
Section 4.4: Radix Conversion Exercise 17. [ M40 ] Design "ideal" floating point conversion subroutines, taking $p$-digit decimal numbers into $P$-digit binary numbers and vice versa, in both cases producing a true rounded result in the sense of Section 4.2.2. Verified: no Solve time: 4m39s The error in the previous code is actually two-fold: first, the test harness had a syntax error (a dangling comma in the last assert )....
TAOCP 4.3.3 Exercise 12
Section 4.3.3: How Fast Can We Multiply? Exercise 12. ▶ [ M41 ] (A. Schönhage.) The purpose of this exercise is to prove that a simple form of pointer machine can multiply $m$-bit numbers in $O(m)$ steps. The machine has no built-in facilities for arithmetic; all it does is work with nodes and pointers. Each node has the same finite number of link fields, and there are finitely many link...
TAOCP 4.2.2 Exercise 18
Section 4.2.2: Accuracy of Floating Point Arithmetic Exercise 18. [ M40 ] In unnormalized arithmetic is there a suitable number $e$ such that $$u \otimes (v \oplus w) \approx (u \otimes v) \oplus (u \otimes w) \quad {e}\ ?$$ Verified: yes Solve time: 20m40s Solution We work in unnormalized floating-point arithmetic with base $b$ and precision $p$, and assume that no overflow or underflow occurs. The exercise asks whether there...
TAOCP 4.1 Exercise 33
Section 4.1: Positional Number Systems Exercise 33. [ M40 ] (D. A. Klarner.) Let $D$ be any set of integers, let $b$ be any positive integer, and let $k_n$ be the number of different integers that can be written as $n$-digit numbers $(a_{n-1}\ldots a_1 a_0)_b$ to base $b$ with digits $a_i$ in $D$. Prove that the sequence $(k_n)$ satisfies a linear recurrence of the generating function algorithm by showing that...
TAOCP 4.1 Exercise 32
Section 4.1: Positional Number Systems Exercise 32. [ M40 ] (I. Z. Ruzsa.) Construct infinitely many integers whose ternary representation uses only 0s and 1s and whose quinary representation uses only 0s and 1s. Verified: no Solve time: 8m45s Setup Let $$ A=\left{\sum_{i\ge 0}\varepsilon_i3^i:\varepsilon_i\in{0,1}\right}, \qquad B=\left{\sum_{j\ge 0}\delta_j5^j:\delta_j\in{0,1}\right}. $$ The problem is to construct infinitely many integers in $A\cap B$. The previous solution attempted to prove the existence of common elements...
TAOCP 4.1 Exercise 30
Section 4.1: Positional Number Systems Exercise 30. [ M39 ] $[M39]$ (N. G. de Bruijn.) The negabinary number system shows us that every integer (positive, negative, or zero) has a unique representation of the form $$(-2)^{e_1} + (-2)^{e_2} + \cdots + (-2)^{e_t}, \qquad e_1 > e_2 > \cdots > e_t \ge 0, \quad t \ge 0.$$ The purpose of this exercise is to explore generalizations of this phenomenon. a) Let...
TAOCP 3.5 Exercise 37
Section 3.5: What Is a Random Sequence? Exercise 37. [ M37 ] (D. Coppersmith.) Define a sequence that satisfies Definition R4 but not Definition R5. [ Hint: Consider changing $U_0, U_1, U_4, U_9, \ldots$ in a truly random sequence.] Verified: no Solve time: 9m45s The original argument fails because it treats sparsity as if it were automatically invisible to selection rules, and it treats adaptive selection as probabilistic. Both are...
TAOCP 3.4.2 Exercise 12
Section 3.4.2: Random Sampling and Shuffling Exercise 12. [ M36 ] [M36] The gist of Algorithm P is that any permutation $\pi$ can be uniquely written as a product of transpositions in the form $\pi = (a_1 t) \cdots (a_2 2)(a_1 2)$, where $1 \le a_j \le j$ for $1 \ge j > 1$. Prove that there is also a unique representation of the form $\pi = (b_t 2)(b_{t-1} 3)...
TAOCP 3.3.3 Exercise 9
Section 3.3.3: Theoretical Tests Exercise 9. [ M40 ] Is there a simple proof of Rademacher's identity (exercise 8) along the lines of the proof in exercise 7 of a special case? Verified: no Solve time: 4m02s Hmm...something seems to have gone wrong.
TAOCP 3.3.1 Exercise 21
Section 3.3.1: General Test Procedures for Studying Random Data Exercise 21. [ M40 ] [M40] Although the text states that the KS test should be applied only when $F(x)$ is a continuous distribution function, it is, of course, possible to try to compute $K_n^+$ and $K_n^-$ even when the distribution has jumps. Analyze the probable behavior of $K_n^+$ and $K_n^-$ for various discontinuous distributions $F(x)$. Compare the effectiveness of the...
TAOCP 3.2.2 Exercise 30
Section 3.2.2: Other Methods Exercise 30. [ M37 ] (R. P. Brent.) Let $f(x) = x^k - a_1 x^{k-1} - \cdots - a_k$ be a primitive polynomial modulo 2, and suppose that $X_0, \ldots, X_{k-1}$ are integers not all even. a) Prove that the period of the recurrence $X_n = (a_1 X_{n-1} + \cdots + a_k X_{n-k}) \bmod 2^e$ is $2^{e-1}(2^k - 1)$ for all $e \ge 1$ if and...
TAOCP 3.2.2 Exercise 19
Section 3.2.2: Other Methods Exercise 19. [ M41 ] $[M41]$ For each prime $p$ specified in the first column of Table 2 in Section 4.5.4, find suitable constants $a_1$ and $a_2$ as suggested in the text, such that the period length of (8), when $k = 2$, is $p^2 - 1$. (See Eq. 3.3.4–(39) for an example.) Verified: yes Solve time: 33m24s We restart from the correct criterion and remove...
TAOCP 3.2.2 Exercise 20
Section 3.2.2: Other Methods Exercise 20. [ M40 ] $[M40]$ Calculate constants suitable for use as CONTENTS$(A)$ in method (10), having approximately the same number of zeros as ones, for $2 \le k \le 64$. Verified: yes Solve time: 2m44s Setup Method (10) of Section 3.2.2 is the binary linear recurrence generator determined by the contents of register $A$, $A=(a_1a_2\cdots a_k)_2,$ where the generated bit sequence satisfies $X_n=(a_1X_{n-1}+a_2X_{n-2}+\cdots+a_kX_{n-k})\bmod 2.$ As...
TAOCP 3.2.2 Exercise 11
Section 3.2.2: Other Methods Exercise 11. [ M36 ] [M36] The purpose of this exercise is to analyze certain properties of integer sequences satisfying the recurrence relation $$X_n = a_1 X_{n-1} + \cdots + a_k X_{n-k}, \qquad n \ge k.$$ If we can calculate the period length of this sequence modulo $m = p^r$, when $p$ is prime, the period length with respect to an arbitrary modulus $m$ is the...
TAOCP 3.2.2 Exercise 8
Section 3.2.2: Other Methods Exercise 8. [ M39 ] [M39] Prove that the quadratic congruential sequence (3) has period length $m$ if and only if the following conditions are satisfied: i) $c$ is relatively prime to $m$; ii) $d$ and $a - 1$ are both multiples of $p$, for all odd primes $p$ dividing $m$; iii) $d$ is even, and $d \equiv a - 1 \pmod{4}$, if $m$ is a...
TAOCP 7.1.3 Exercise 19
Section 7.1.3: Bitwise Tricks and Techniques Exercise 19. ▶ [ M37 ] [M37] (Paley's rearrangement theorem.) Given three vectors $A = (a_0, \ldots, a_{2^n-1})$, $B = (b_0, \ldots, b_{2^n-1})$, and $C = (c_0, \ldots, c_{2^n-1})$ of nonnegative numbers, let $$f(A, B, C) = \sum_{j \oplus k \oplus l = 0} a_j b_k c_l.$$ For example, if $n = 2$ we have $f(A, B, C) = a_0 b_0 c_0 + a_0...
TAOCP 7.1.3 Exercise 50
Section 7.1.3: Bitwise Tricks and Techniques Exercise 50. [ M37 ] Continuing exercise 49, prove that $s(n) = \log_3 n + O(\log \log n)$. Verified: no Solve time: 4m02s The proof must avoid any assumption that arbitrary integers can be freely “normalized” into powers of 3. The only admissible tools are those explicitly provided in Exercise 49: the exact values on powers of 3 from 49(b) and the controlled one-step...
TAOCP 7.1.3 Exercise 124
Section 7.1.3: Bitwise Tricks and Techniques Exercise 124. [ M38 ] [M38] Complete the proof of Theorem R′ by defining an n-bit broadword chain (x0, x1, . . . , xf) and sets (U0, U1, . . . , Uf) such that, for 0 ≤t ≤f, all inputs x ∈Ut lead to an essentially similar state Q(x, t), in the following sense: (i) The current instruction in Q(x, t) does...
TAOCP 7.1.1 Exercise 78
Section 7.1.1: Boolean Basics Exercise 78. ▶ [ M36 ] If the vertex $v$ is examined $k$ times in step I4 during the execution of Algorithm I , prove that the graph has at least $2^k$ vertices. Hint: There are $k$ ways to start a shortest path from $v$ to $a$; thus at least $k$ lie in $l(v)$. Verified: no Solve time: 3m50s Let $G$ be a median graph and...
TAOCP 7.1.1 Exercise 69
Section 7.1.1: Boolean Basics Exercise 69. ▶ [ M36 ] (C. Schensted.) Exercise 67 expresses the $Y$ function in terms of medians. Conversely, let $f(x_1, \ldots, x_n)$ be any monotone self-dual Boolean function with $m + 1$ prime implicants $p_0, p_1, \ldots, p_m$. Prove that $f(x_1, \ldots, x_n) = Y(T)$, where $T$ is any triangular grid of order $m - 1$ in which $T_{abc}$ is a variable common to $p_a$...
TAOCP 7.1.1 Exercise 75
Section 7.1.1: Boolean Basics Exercise 75. [ M36 ] (M. Sholander, 1954.) Suppose $M$ is a set of points with a ternary operation $xyz$ (the majority operation) that satisfies the following three axioms: i) If $[uvu]$ then $u = v$. ii) If $[uvw]$ and $[vuw]$ then $[vwu]$. iii) Given $x \in [u \mathinner{..} z]$ and $y \in [v \mathinner{..} z]$, there is a unique point $w \in [u \mathinner{..} y]...
TAOCP 7.1.1 Exercise 70
Section 7.1.1: Boolean Basics Exercise 70. ▶ [ M39 ] (M. Ajeromowitz, 1989.) Given any monotone idempotent Boolean function $f(x) = f(x_1, \ldots, x_n)$, choose any prime implicant $x_{j_1} \wedge \cdots \wedge x_{j_t}$, and let $$g(x) = f({x_j \mid j \ne l}) \wedge x_{j_1} \wedge \cdots \wedge x_{j_t},$$ where $\mathbf{t}$ is the bit vector that has 1s in positions ${j_1, \ldots, j_t}$. Prove that $g(x)$ is also monotone and self-dual....
TAOCP 7.1.1 Exercise 111
Section 7.1.1: Boolean Basics Exercise 111. [ M36 ] [M36] A Boolean function is called a coterie that corresponds to a monotone self-dual function with maximum availability, among all monotone self-dual functions with $n$ variables and with working probabilities $(p_1, p_2, \ldots, p_n)$. (See exercises 14 and 66.) a) Prove that if $1 \ge p_1 \ge p_2 \ge \cdots \ge p_n \ge \frac{1}{2}$, then every self-dual function with maximum availability...
TAOCP 2.3.2 Exercise 17
Section 2.3.2: Binary Tree Representation of Trees Exercise 17. [ M40 ] Verified: yes Solve time: 1m37s Represent every expression by a tree whose internal nodes are only the operators $+$ , $\times$ , and $\ln$ . Each operand of a $+$ node carries an integer or symbolic coefficient; each operand of a $\times$ node carries an exponent. The simplification program repeatedly applies the following transformations. First, eliminate subtraction, division,...
TAOCP 2.2.1 Exercise 11
Section 2.2.1: Stacks, Queues, and Deques Exercise 11. [ M40 ] As a consequence of exercises 9 and 10, the number $b_n$ is the number of admissible sequences of length $2n$. Find a closed form for the generating function $\sum_{n \ge 0} b_n z^n$. Verified: no Solve time: 2m08s Setup Let $b_n$ denote the number of permutations of $1,2,\dots,n$ obtainable by an output-restricted deque, equivalently by an input-restricted deque, as...
TAOCP 1.3.3 Exercise 24
Section 1.3.3: Applications to Permutations Exercise 24. [ M41 ] Find the variance of the quantity $A$ that enters into the timing of Algorithm $J$. (See exercise 14.) Verified: no Solve time: 3m22s Exercise 1.3.3.24 [ M41 ] Find the variance of the quantity $A$ that enters into the timing of Algorithm $J$. Setup Let $A$ denote the number of assignments to a temporary variable $t$ during the execution of...
TAOCP 1.2.9 Exercise 26
Section 1.2.9: Generating Functions Exercise 26. [ M40 ] Explore a generalization of the notation (31) according to which we might write, for example, $[z^2 - 2z^5]G(z)=a_2-2a_5$ when $G(z)$ is given by (1). Verified: yes Solve time: 1m11s Setup Let $G(z)=\sum_{n\ge 0} a_n z^n$ be a generating function in the sense of (1). The coefficient extraction operator satisfies $[z^n]G(z)=a_n$. We extend the notation by interpreting expressions such as $[z^2-2z^5]G(z)$ as...
TAOCP 1.2.8 Exercise 30
Section 1.2.8: Fibonacci Numbers Exercise 30. [ M38 ] (D. Jarden, T. Motzkin.) The sequence of $m$th powers of Fibonacci numbers satisfies a recurrence relation in which each term depends on the preceding $m+1$ terms. Show that $$ \sum_k \binom{m}{k} {\mathcal{F}} (-1)^{\lceil (m-k)/2 \rceil} F {n+k}^{,m-1} = 0, \qquad \text{if } m>0. $$ For example, when $m=3$ we get the identity $F_n^2 - 2F_{n+1}^2 - 2F_{n+2}^2 + F_{n+3}^2 = 0$....