TAOCP 5.3.2: Minimum-Comparison Merging
Section 5.3.2 exercises: 20/20 solved.
Section 5.3.2. Minimum-Comparison Merging
Exercises from TAOCP Volume 3 Section 5.3.2: 20/20 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [**] | verified | 3m56s | |
| 2 | [22] | medium | verified | 1m33s |
| 3 | [M24] | math-medium | verified | 2m21s |
| 4 | [M42] | math-project | verified | 1m14s |
| 5 | [M30] | math-hard | solved | 4m31s |
| 6 | [M26] | math-hard | solved | 2m21s |
| 7 | [21] | medium | verified | 4m11s |
| 8 | [24] | medium | verified | 3m04s |
| 9 | [27] | hard | solved | 4m44s |
| 10 | [33] | hard | solved | 4m14s |
| 11 | [M40] | math-project | solved | 4m16s |
| 12 | [M21] | math-medium | solved | 4m11s |
| 14 | [41] | project | solved | 4m17s |
| 15 | [12] | simple | verified | 1m |
| 16 | [18] | medium | solved | 2m22s |
| 17 | [M25] | math-medium | verified | 1m56s |
| 18 | [M40] | math-project | verified | 2m16s |
| 19 | [23] | medium | verified | 1m17s |
| 20 | [20] | medium | solved | 5m02s |
| 21 | [M47] | math-research | solved | 1m39s |
TAOCP 5.3.2 Exercise 1
We restart from the correct structural interpretation of $S'(k)$ as an optimal **merging-based sorting cost**, and we avoid assuming any fixed decomposition into prescribed sizes.
TAOCP 5.3.2 Exercise 2
Let $m=1$.
TAOCP 5.3.2 Exercise 3
We restart from the definitions of the two quantities in Knuth’s merging model.
TAOCP 5.3.2 Exercise 4
Let $\underline{M}(m,n)$ denote the lower-bound function for merging described in Section 5.
TAOCP 5.3.2 Exercise 5
Let $T$ be any comparison decision tree for merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_{n+1}$, and let its height be the number of comparisons in the worst case.
TAOCP 5.3.2 Exercise 6
The proof of Theorem K is carried out by verifying that a proposed closed form agrees with the values of the adversary functions $_M(m,n)$ defined by the recurrence inequalities coming from Strategies...
TAOCP 5.3.2 Exercise 7
The original argument fails because it never establishes a real comparison between the two quantities $M(k+m,n)$ and $M(k,n)+M(m,n)$.
TAOCP 5.3.2 Exercise 8
We construct a deterministic comparison algorithm and verify a uniform worst-case bound of $6$ comparisons.
TAOCP 5.3.2 Exercise 9
We construct a single, explicit decision tree of comparisons whose worst-case depth is at most 7.
TAOCP 5.3.2 Exercise 10
Working
TAOCP 5.3.2 Exercise 11
The sequence is defined explicitly by g_0 = \lfloor 4\cdot 2^0 \rfloor,\qquad g_{k+1} = \lfloor 2^{g_k} \rfloor.
TAOCP 5.3.2 Exercise 12
We restart the argument cleanly and avoid any reliance on incorrect monotonicity substitutions.
TAOCP 5.3.2 Exercise 14
We restart from a correct decision-tree formulation and remove the unverified state model.
TAOCP 5.3.2 Exercise 15
We compute $\left\lfloor \lg(n/m) \right\rfloor$ for $n>m$ by characterizing it as the unique integer $k \ge 0$ such that $m \cdot 2^k \le n < m \cdot 2^{k+1}.$ This reformulation eliminates division...
TAOCP 5.3.2 Exercise 16
Let $H(m,n)$ denote the number of comparisons performed by Hwang and Lin’s binary merging algorithm when merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_n$ under worst-case behavior.
TAOCP 5.3.2 Exercise 17
We now reconstruct equation (21) from the standard context of Section 5.
TAOCP 5.3.2 Exercise 18
Let the two sorted sequences have lengths $m$ and $n$.
TAOCP 5.3.2 Exercise 19
Let $M(m,n)$ denote the minimum number of comparisons required to merge two increasing sequences of lengths $m$ and $n$.