#math-project
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 2.3.2 Exercise 17
Section 2.3.2: Binary Tree Representation of Trees Exercise 17. [ M40 ] Write a program to do algebraic simplification capable of reducing, for example, (20) or (21) to (22) . [ Hints: Include a new field with each node, representing its coefficient (for summands) or its exponent (for factors in a product). Apply algebraic identities, like replacing \ln(u ↑ v) by v \ln u ; remove the operations - ,...
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: yes Solve time: 1m12s Setup Let $b_n$ denote the number of permutations of $1,2,\ldots,n$ obtainable with an input-restricted deque. By Exercise 9, $b_n$ is also...
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: yes Solve time: 4m38s Let the permutation be decomposed into cycles, and let $\alpha_k$ denote the number of cycles of length $k$. In the timing analysis of Algorithm $J$ from Exercise 14, the quantity $A$ is the total number of repetitions...
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: 42s Setup Let $$ G(z)=\sum_{n\ge 0} a_n z^n. $$ For each nonnegative integer $k$, the coefficient extraction operator satisfies $$ [z^k]G(z)=a_k. $$ Let $P(z)=\sum_{k=0}^m c_k z^k$ be a polynomial. The expression to be...
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$....