TAOCP 5.4.2: The Polyphase Merge
Section 5.4.2 exercises: 30/30 solved.
Section 5.4.2. The Polyphase Merge
Exercises from TAOCP Volume 3 Section 5.4.2: 30/30 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [16] | medium | solved | 3m57s |
| 2 | [21] | medium | solved | 4m28s |
| 3 | [22] | medium | solved | 4m26s |
| 4 | [M20] | math-medium | solved | 4m37s |
| 5 | [HM26] | hm-hard | solved | 5m04s |
| 6 | [HM24] | hm-medium | verified | 3m13s |
| 7 | [HM22] | hm-medium | solved | 1m10s |
| 8 | [M20] | math-medium | verified | 1m29s |
| 9 | [M20] | math-medium | solved | 53s |
| 10 | [M27] | math-hard | solved | 1m03s |
| 11 | [M24] | math-medium | solved | 4m |
| 12 | [M18] | math-medium | solved | 5m |
| 13 | [22] | medium | solved | 4m09s |
| 15 | [M43] | math-project | verified | 1m43s |
| 16 | [HM43] | hm-project | verified | 3m53s |
| 17 | [32] | hard | solved | 2m26s |
| 18 | [30] | hard | solved | 1m18s |
| 19 | [21] | medium | solved | 2m30s |
| 20 | [M24] | math-medium | solved | 1m02s |
| 21 | [11] | simple | verified | 1m23s |
| 22 | [M21] | math-medium | solved | 1m21s |
| 23 | [29] | hard | solved | 4m15s |
| 24 | [**] | solved | 3m48s | |
| 25 | [19] | medium | verified | 2m53s |
| 26 | [M21] | math-medium | solved | 1m08s |
| 27 | [23] | medium | solved | 4m56s |
| 28 | [M26] | math-hard | solved | 1m42s |
| 29 | [M47] | math-research | solved | 4m13s |
| 30 | [42] | project | solved | 1m30s |
| 31 | [M22] | math-medium | solved | 4m57s |
TAOCP 5.4.2 Exercise 1
The reviewer is correct on all four failure points.
TAOCP 5.4.2 Exercise 2
The previous solution failed because it replaced Algorithm D with an unproved “Fibonacci level” abstraction and then reasoned about dummy runs in that model.
TAOCP 5.4.2 Exercise 3
Start from the definition at the end of step D4: D[j] = a + A[j] - A[j+1], \qquad 1 \le j \le T, with $A[T+1]=0$.
TAOCP 5.4.2 Exercise 4
Let $p\ge 1$ and let $(F_n)_{n\ge 0}$ satisfy F_n = \sum_{i=1}^p F_{n-i}\qquad (n\ge p), with fixed initial values $F_0,\dots,F_{p-1}$.
TAOCP 5.4.2 Exercise 5
Let f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, and define
TAOCP 5.4.2 Exercise 6
Let F(z)=\frac{p(z)}{q(z)}, \qquad G(z)=\frac{p(z)}{q(z)^2}.
TAOCP 5.4.2 Exercise 7
Let f_p(z)=z^p - z^{p-1}-\cdots-1.
TAOCP 5.4.2 Exercise 8
Let $N_m^{(p)}$ denote the number of ordered representations of $m$ as a sum of integers from $\{1,2,\dots,p\}$.
TAOCP 5.4.2 Exercise 9
Let $K_m$ denote $K^{(p)}$, the number of sequences of length $m$ consisting of $0$’s and $1$’s that contain no $p$ consecutive $1$’s.
TAOCP 5.4.2 Exercise 10
Let ${F_n^{(p)}}_{n\ge 0}$ denote the $p$th-order Fibonacci numbers defined in Section 5.
TAOCP 5.4.2 Exercise 11
A clean proof must eliminate the earlier two failures: (i) treating both objects as sharing an unproved “common recurrence,” and (ii) conflating a string position with a numeric statistic without grou...
TAOCP 5.4.2 Exercise 12
The flaw in the previous argument is not the linear algebraic part but the missing derivation of the transition rule from the definition of the perfect Fibonacci (perfect polyphase) distributions in (...
TAOCP 5.4.2 Exercise 13
Working
TAOCP 5.4.2 Exercise 15
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)$.
TAOCP 5.4.2 Exercise 16
Let $P = T-1 \ge 2$.
TAOCP 5.4.2 Exercise 17
The previous argument failed because it replaced the polyphase state space with an incorrect arithmetic model.
TAOCP 5.4.2 Exercise 18
Let $T > 3$ be fixed and set $P = T - 1$.
TAOCP 5.4.2 Exercise 19
The previous solution fails because it replaces the actual construction of Caron’s polyphase schedule with an unproven symmetry argument.
TAOCP 5.4.2 Exercise 20
Let $T=6$ and $P=5$.
TAOCP 5.4.2 Exercise 21
In the six-tape case we have $T=6$ and hence $P=T-1=5$.
TAOCP 5.4.2 Exercise 22
Let $T = P+1$ and let $t_n$ denote the total number of runs in the perfect level-$n$ distribution for $T$ tapes, as in equation (6).
TAOCP 5.4.2 Exercise 23
The reviewer is correct that the original attempt destroys the essential feature of TAOCP §5.
TAOCP 5.4.2 Exercise 24
The error in the previous solution is not the use of Perron–Frobenius itself, but the attempt to justify it through an incorrect state-space model.
TAOCP 5.4.2 Exercise 25
We restart from the correct structure of a 4-tape polyphase merge.
TAOCP 5.4.2 Exercise 26
Let $T=4$, so $P=T-1=3$ and the tape-splitting polyphase merge uses the 3-way Fibonacci system defined by the third-order recurrence F_n = F_{n-1}+F_{n-2}+F_{n-3}\quad (n\ge 3), with initial values de...
TAOCP 5.4.2 Exercise 27
The reviewer’s diagnosis is correct: the previous proof implicitly replaced each tape by a globally sorted sequence, which is false.
TAOCP 5.4.2 Exercise 28
Let there be $T=6$ tapes, so $P=5$ input tapes and one output tape.
TAOCP 5.4.2 Exercise 29
The previous argument fails because it replaces the actual TAOCP merge-until-empty mechanism with a two-number Euclidean subtraction process.