Exercise 14. [40] [40] Using the square root method of buffer allocation, the seek time for the merge pattern in Fig. 92 would be proportional to (/2 +VJ744VJ14vV1i4+ v8)? + (VI + V1+ V2)" + (VI + V24+ V1+ V4)" + (V1+ VI4+ V2)’; this is the sum, over each internal node, of (./ny + +++ +Vmm + Vni +++: +!m); where that node’s respective subtrees have (n1,...,%m) leaves. Write a computer program that generates minimum-seek time trees having 1, 2, 3, ... leaves, based on this formula.

Verified: no
Solve time: 3m29s

Setup

Let a rooted ordered tree $T$ have $n$ leaves. For an internal node $v$, let its children roots of subtrees $T_1,\dots,T_m$ contain $n_1,\dots,n_m$ leaves respectively. The square root buffer allocation model assigns to $v$ a contribution

$$ \left(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{m}\right)^2. $$

The total seek time of $T$ is the sum of these contributions over all internal nodes.

Let $F(n)$ denote the minimum possible seek time among all trees with $n$ leaves.

A tree with a single leaf has no internal nodes, hence

$$ F(1)=0. $$

For $n\ge 2$, every admissible tree consists of a root with $m\ge 2$ subtrees whose leaf counts form a partition of $n$. The optimal substructure gives

$$ F(n)=\min_{\substack{m\ge 2\ n_1+\cdots+n_m=n}} \left[\left(\sqrt{n_1}+\cdots+\sqrt{n_m}+\sqrt{m}\right)^2 + \sum_{i=1}^m F(n_i)\right]. $$

The task is to construct, for each $n$, a tree achieving $F(n)$.

Solution

Define a table $F[1..N]$ and a companion table $\operatorname{root}[n]$ storing an optimal decomposition of $n$ into child sizes. The construction proceeds in increasing order of $n$.

For each fixed $n\ge 2$, every candidate solution is determined by a choice of $m\ge 2$ and a composition $(n_1,\dots,n_m)$ of $n$. For each such choice, define the candidate cost

$$ C(n_1,\dots,n_m)

\left(\sum_{i=1}^m \sqrt{n_i}+\sqrt{m}\right)^2 + \sum_{i=1}^m F[n_i]. $$

The value $F[n]$ is the minimum of these quantities over all admissible compositions.

The corresponding optimal tree is recorded by storing, for each $n$, one pair $(m,(n_1,\dots,n_m))$ that attains the minimum. The tree itself is reconstructed recursively from these stored decompositions.

The generation of all compositions is performed by recursion on partitions of $n$ into $m$ positive integers. Each partition step reduces the remaining sum, ensuring termination. Each complete partition yields exactly one evaluation of $C(n_1,\dots,n_m)$, after which a comparison with the current best value of $F[n]$ determines whether replacement occurs.

The program is as follows.

procedure BUILD(n)
    if n = 1 then
        F[1] ← 0
        ROOT[1] ← NIL
        return
    F[n] ← +∞
    for m ← 2 to n do
        generate all compositions (n1, …, nm) of n
        for each composition do
            S ← 0
            for i ← 1 to m do
                S ← S + sqrt(ni) + F[ni]
            C ← (S + sqrt(m))^2
            if C < F[n] then
                F[n] ← C
                ROOT[n] ← (m, n1, …, nm)

procedure GENERATE(N)
    for n ← 1 to N do
        BUILD(n)

Tree reconstruction is defined by a separate procedure that expands stored roots:

procedure EXPAND(n)
    if ROOT[n] = NIL then
        output leaf
    else
        (m, n1, …, nm) ← ROOT[n]
        output internal node
        for i ← 1 to m do
            EXPAND(ni)

Verification

For $n=1$, the construction produces a single leaf and no internal nodes, so the computed value is $F(1)=0$, matching the definition.

Assume $n\ge 2$. Every tree with $n$ leaves has a root with some degree $m\ge 2$ and a partition $n=n_1+\cdots+n_m$. The contribution of the root depends only on $(m,n_1,\dots,n_m)$ and equals $\left(\sum_{i=1}^m \sqrt{n_i}+\sqrt{m}\right)^2$. The remaining cost is the sum of optimal costs of the subtrees, since each subtree is independent once its leaf count is fixed.

Every decomposition is enumerated by the inner loop over compositions, since for fixed $m$ the recursion over positive integer compositions of $n$ into $m$ parts generates each ordered $m$-tuple exactly once. Each such tuple yields exactly one computed value $C(n_1,\dots,n_m)$, and the update rule preserves the minimum among all evaluated candidates.

The recursion defining $F[n]$ depends only on values $F[k]$ with $k<n$, since each $n_i<n$ holds for every proper composition of $n$. Thus each $F[n_i]$ is already fixed when $F[n]$ is computed, ensuring consistency of evaluation order.

The stored pair $\operatorname{ROOT}[n]$ records a decomposition attaining the minimum in the defining recurrence, hence recursive expansion of these records reconstructs a tree whose cost equals $F[n]$.

This completes the proof. ∎

Notes

The procedure is exponential in $n$ because the number of compositions of $n$ grows exponentially, and each composition evaluation requires summing $m$ terms. The formulation remains exact and matches the recurrence structure induced by the square-root buffer allocation cost.

A practical implementation would restrict candidate degrees $m$ or prune compositions using bounds derived from convexity of $\sqrt{x}$, but such optimizations are external to the definition of $F(n)$ and do not affect correctness of the construction above.

TAOCP 5.4.9 Exercise 14

Setup

Solution

$$ C(n_1,\dots,n_m)

Verification

Notes