TAOCP 5.4.9 Exercise 3
The text defines \(A_1(n)\) as the minimum value of \(\alpha D(T) + \beta E(T)\) over all \(n\)-leaved trees \(T\) whose internal nodes have degree at most \(P\), where \(P\) is the maximum merge orde...
Section 5.4.9: Disks and Drums
Exercise 3. [M15] Suppose the internal memory is limited so that 10-way merging is not feasible. How can recurrence relations (3), (4), (5) be modified so that $A_1(n)$ is the minimum value of $\alpha D(T)+\beta E(T)$, over all $n$-leaved trees $T$ having no internal nodes of degree greater than 9?
Verified: no
Solve time: 3m36s
Solution
The text defines (A_1(n)) as the minimum value of (\alpha D(T) + \beta E(T)) over all (n)-leaved trees (T) whose internal nodes have degree at most (P), where (P) is the maximum merge order permitted by the internal memory size. In the original recurrences (3), (4), (5) the value (P = 10) was used (since 10-way merging was considered feasible). The recurrences are:
[ \begin{aligned} \text{(3)}\quad & A_1(1) = 0. \[4pt] \text{(4)}\quad & A_1(n) = \min_{2 \le k \le 10}; \Bigl[ \min_{n_1+\cdots+n_k=n}\bigl(A_1(n_1)+\cdots+A_1(n_k)\bigr) + \alpha n + \beta \Bigr] \qquad (n>1). \[4pt] \text{(5)}\quad & A_1(n) = \min_{2 \le k \le 10}; \Bigl[ (k-r)A_1(q) + r A_1(q+1) + \alpha n + \beta \Bigr] \qquad (n>1), \end{aligned} ] where in (5) we write (n = kq + r) with (0 \le r < k); the equality of (4) and (5) holds because the inner minimum is attained when the (n_i) differ by at most one.
If 10-way merging is not feasible, the maximum degree of any internal node is 9. Hence we simply replace the upper bound (10) by (9) in the minimizations of (4) and (5). The modified recurrences become:
[ \begin{aligned} \text{(3)}\quad & A_1(1) = 0. \[4pt] \text{(4)}\quad & A_1(n) = \min_{2 \le k \le 9}; \Bigl[ \min_{n_1+\cdots+n_k=n}\bigl(A_1(n_1)+\cdots+A_1(n_k)\bigr) + \alpha n + \beta \Bigr] \qquad (n>1). \[4pt] \text{(5)}\quad & A_1(n) = \min_{2 \le k \le 9}; \Bigl[ (k-r)A_1(q) + r A_1(q+1) + \alpha n + \beta \Bigr] \qquad (n>1), \end{aligned} ] with (n = kq + r), (0 \le r < k). These recurrences now compute the desired minimum cost for trees with no internal node of degree greater than 9.
This completes the proof. ∎