TAOCP 5.4.3: The Cascade Merge
Section 5.4.3 exercises: 11/11 solved.
Section 5.4.3. The Cascade Merge
Exercises from TAOCP Volume 3 Section 5.4.3: 11/11 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | solved | 3m29s |
| 2 | [22] | medium | solved | 4m01s |
| 3 | [23] | medium | solved | 4m39s |
| 4 | [M20] | math-medium | solved | 4m25s |
| 5 | [20] | medium | solved | 2m23s |
| 6 | [M20] | math-medium | verified | 1m24s |
| 7 | [M20] | math-medium | solved | 4m26s |
| 8 | [HM23] | hm-medium | solved | 1m33s |
| 9 | [HM26] | hm-hard | verified | 2m31s |
| 10 | [M28] | math-hard | solved | 1m22s |
| 11 | [M38] | math-project | verified | 1m09s |
TAOCP 5.4.3 Exercise 1
Table 1 in Section 5.
TAOCP 5.4.3 Exercise 2
We compare cascade sorting on three tapes (Algorithm C) with polyphase merging on three tapes (Algorithm 5.
TAOCP 5.4.3 Exercise 3
The earlier solution fails primarily because it never instantiates Algorithm C’s actual state mechanism: a 5-way polyphase merge on six tapes driven by a 5-term Fibonacci-type (pentanacci) distributio...
TAOCP 5.4.3 Exercise 4
The previous solution fails because it never uses the actual cascade operator.
TAOCP 5.4.3 Exercise 5
Let V_n = (A_n, b_n, c_n, d_n, e_n).
TAOCP 5.4.3 Exercise 6
Let v_n = (a_n, b_n, c_n, d_n, e_n) denote the six-tape cascade numbers at level $n$, with initial condition
TAOCP 5.4.3 Exercise 7
The reviewer is correct that the original argument fails because it treats the modified algorithm as if it follows the same step-by-step state evolution as the original.
TAOCP 5.4.3 Exercise 8
Let $T=6$ in the notation of the section, and write X_n = (A_n, B_n, C_n, D_n, E_n)^T .
TAOCP 5.4.3 Exercise 9
We restart from the cascade structure in Algorithm C and derive equation (14) in a way that correctly matches the backward extension construction and applies Lagrange inversion in its valid form.