TAOCP 5.4.1: Multiway Merging and Replacement Selection
Section 5.4.1 exercises: 27/27 solved.
Section 5.4.1. Multiway Merging and Replacement Selection
Exercises from TAOCP Volume 3 Section 5.4.1: 27/27 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [10] | simple | verified | 56s |
| 2 | [12] | simple | verified | 59s |
| 3 | [16] | medium | solved | 4m20s |
| 4 | [16] | medium | solved | 4m38s |
| 5 | [00] | immediate | verified | 1m28s |
| 6 | [15] | simple | verified | 3m50s |
| 7 | [**] | verified | 1m23s | |
| 8 | [20] | medium | verified | 1m05s |
| 9 | [23] | medium | verified | 1m17s |
| 10 | [26] | hard | solved | 4m |
| 11 | [M20] | math-medium | solved | 4m09s |
| 12 | [M46] | math-research | solved | 1m50s |
| 13 | [13] | simple | verified | 1m13s |
| 14 | [HM25] | hm-medium | solved | 3m41s |
| 15 | [20] | medium | verified | 1m47s |
| 16 | [M26] | math-hard | solved | 4m29s |
| 17 | [20] | medium | verified | 1m34s |
| 18 | [22] | medium | solved | 1m41s |
| 19 | [HM22] | hm-medium | solved | 3m59s |
| 20 | [**] | solved | 4m40s | |
| 21 | [HM23] | hm-medium | solved | 4m17s |
| 23 | [**] | solved | 4m13s | |
| 24 | [**] | solved | 2m45s | |
| 25 | [HM40] | hm-project | solved | 4m59s |
| 26 | [M33] | math-hard | solved | 4m21s |
| 27 | [HM30] | hm-hard | solved | 2m28s |
| 28 | [25] | medium | verified | 3m49s |
TAOCP 5.4.1 Exercise 1
After Step 3 the current front keys of the four runs are $503,\ 170,\ 426,\ 612$ after the replacement of $154$ by $426$.
TAOCP 5.4.1 Exercise 2
Figure 63 is a loser tree in which each internal node stores the loser of the comparison, and the root contains the current champion.
TAOCP 5.4.1 Exercise 3
We restart the analysis from the definition of **four-way replacement selection** (TAOCP §5.
TAOCP 5.4.1 Exercise 4
We restart the construction from the correct replacement-selection algorithm (Knuth, sorting by replacement selection with a min-heap of size 4).
TAOCP 5.4.1 Exercise 5
A selection tree used for replacement selection represents $P$ external nodes as the leaves of a complete binary tree, with internal nodes storing comparison results along the path to the root.
TAOCP 5.4.1 Exercise 6
The issue is not merely tree degeneracy at $P=2$, but the fact that Algorithm R implicitly assumes the existence of at least one comparison.
TAOCP 5.4.1 Exercise 7
Algorithm R initializes the selection tree by filling all external nodes with the next input records.
TAOCP 5.4.1 Exercise 8
Algorithm R relies on a distinguished key value $oo$ such that for every actual key $K$, the relation $K < oo$ holds in the ordering used by the selection tree.
TAOCP 5.4.1 Exercise 9
Let the comparison used in Algorithm R for the selection tree be denoted by $\prec$, where in the original algorithm $a \prec b$ means that key $a$ is smaller than key $b$.
TAOCP 5.4.1 Exercise 10
The flaw in the previous argument is the assumption that LOSER pointers are merely passive storage.
TAOCP 5.4.1 Exercise 11
We analyze the random-permutation model: all $n!$ input permutations of distinct keys are equally likely.
TAOCP 5.4.1 Exercise 12
Let $P$ be the number of external nodes of the loser tree and let $h$ be its height, so that every path from an external node to the root contains exactly $h$ internal nodes.
TAOCP 5.4.1 Exercise 13
Let $P$ be the number of keys held in the selection tree.
TAOCP 5.4.1 Exercise 14
The key issue is the conditioning of the truncation point.
TAOCP 5.4.1 Exercise 15
Let the algorithm be replacement selection with a selection tree containing $P$ external nodes as defined in Section 5.
TAOCP 5.4.1 Exercise 16
The previous solution fails because it replaces the **online heap constraint system** of replacement selection with a global ordering argument.
TAOCP 5.4.1 Exercise 17
Let the input keys satisfy $K_1 > K_2 > \cdots > K_N.$ Algorithm R initializes a selection tree with the first $P$ records.
TAOCP 5.4.1 Exercise 18
Let the output of Algorithm R be the sequence of records obtained from the input file, with each record carrying an extended key $(S,K)$, where $S$ is the run number assigned during replacement select...
TAOCP 5.4.1 Exercise 19
We restart from a faithful snowplow model of replacement selection and avoid any per-record attribution.
TAOCP 5.4.1 Exercise 20
We restart from a correct model of TAOCP replacement selection (“natural selection”) and avoid any assumption of independence or uniform heap ranks.
TAOCP 5.4.1 Exercise 21
The previous solution failed because it replaced the combinatorial snowplow construction with an ungrounded probabilistic model and used undefined parameter substitutions.
TAOCP 5.4.1 Exercise 23
A correct analysis must avoid treating the evolving replacement process as i.
TAOCP 5.4.1 Exercise 24
The errors in the previous solution stem from two issues: (i) failure to verify that the transformation “descending run = apply $x \mapsto 1-x$” preserves the structural hypotheses of Theorem K at the...
TAOCP 5.4.1 Exercise 25
The previous solution failed because it tried to _postulate_ a kernel and then retrofit a “memoryless explanation” instead of deriving the joint law from the actual state evolution at the instants whe...
TAOCP 5.4.1 Exercise 26
The argument fails because it replaces the algorithm of Exercise 25 with an unrelated Touchard model and then manipulates that model without any link to run termination.
TAOCP 5.4.1 Exercise 27
Let $P$ denote the capacity of the selection tree (priority queue), and let $P' < P$ denote the size of the reservoir used in natural selection.
TAOCP 5.4.1 Exercise 28
The key difficulty is not comparison but **storage lifetime**: a variable-length record must remain accessible through its descriptor for as long as it may still reside in the selection tree.