TAOCP 5.4.4 Exercise 18

We consider the standard tape model with \(T \ge 3\) tape units.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.4.4: Reading Tape Backwards

Exercise 18. ▶ [M38] Suppose that $T$ tape units are available, for some $T \ge 3$, and that T1 contains $N$ records while the remaining tapes are empty. Is it possible to reverse the order of the records on T1 in fewer than $\Omega(N \log N)$ steps, without reading backwards? (The operation is, of course, trivial if backwards reading is allowed.) See exercise 5.2.5–14 for a class of such algorithms that do require order $N \log N$ steps.

The following exercises develop the theory of tape merging on read-forward tapes; in this case each tape acts as a queue instead of as a stack. A merge pattern can be represented as a sequence of vectors $y^{(m)} \ldots y^{(1)} y^{(0)}$ exactly as in the text, but when we convert the vector representation to a tree representation we change “last formed, first grown on” to “first formed, first grown on.” Thus the invalid configurations (4) would be changed to

$$ \begin{array}{ccccccccc} & i & & & & j & & & \ \text{both} & A & \text{and} & A & \text{or} & \text{both} & A & \text{and} & A . \qquad (4') \end{array} $$

A tree that can be labeled so as to represent a read-forward merge on $T$ tapes is called $T$-fifo, analogous to the term “$T$-lifo” in the read-backward case.

When tapes can be read backwards, they make very good stacks. But unfortunately they don’t make very good general-purpose queues. If we randomly write and read, in a first-in-first-out manner, we waste a lot of time moving from one part of the tape to another. Even worse, we will soon run off the end of the tape! We run into the same problem as the queue overrunning memory in 2.2.2–(4) and (5), but the solution in 2.2.2–(6) and (7) doesn’t apply to tapes since they aren’t circular loops. Therefore we shall call a tree strongly $T$-fifo if it can be labeled so that the corresponding merge pattern makes each tape follow the special queue discipline “write, rewind, read all, rewind; write, rewind, read all, rewind; etc.”

Verified: no
Solve time: 14m57s

Setup

We consider the standard tape model with (T \ge 3) tape units. Each tape operates as a queue: records can be read sequentially in the forward direction, written sequentially at the end, and the tape can be rewound to the beginning. Reading backwards is not allowed. Initially tape 1 (T1) contains (N) records in order (r_1, r_2, \dots, r_N); tapes 2,…,(T) are empty. The task is to rearrange the records so that T1 ends up containing (r_N, r_{N-1}, \dots, r_1) (the reverse order). Other tapes may hold arbitrary data at the end.

A step is the reading or writing of a single record. Rewinding is assumed to take negligible time (or is not counted). The question asks whether there exists an algorithm that accomplishes the reversal in (o(N\log N)) steps, i.e. in fewer than (\Omega(N\log N)) steps.

Solution

We prove that no such algorithm exists; every algorithm requires (\Omega(N\log N)) steps. The proof uses the tree representation of merge patterns developed in the text (Section 5.4.4) for read‑forward tapes.

1. From algorithm to tree

Any read‑forward tape algorithm that reverses the order of the records can be decomposed into a sequence of merge operations. A merge operation selects (k) input tapes ((1 \le k \le T-1)), reads one run from each (starting at the current head positions, which are at the beginnings of the runs because tapes are rewound before a merge), and writes the merged run to a single output tape. The initial distribution pass reads the (N) records from T1 and writes them as runs onto the (T) tapes; this can be viewed as a set of trivial merges (copies) that split the original run into smaller runs. Because the final order is the complete reverse of the initial order, every record must eventually be separated from its neighbours; hence the initial distribution can be assumed to produce (N) runs of length 1 (the individual records) without increasing the total number of steps - any algorithm that starts with larger runs must later break them down, which only adds moves.

Thus we obtain a tree where:

  • The (N) leaves correspond to the (N) initial runs of length 1.
  • Each internal node corresponds to a merge that combines at most (T-1) runs (the children) into one run (the parent).
  • The root corresponds to the final run of length (N) on T1 in reversed order.

The tree has maximum degree (d = T-1). The number of times a record is read/written during the merge phases equals the depth of its leaf in this tree (each merge reads the record once from an input tape and writes it once to the output tape). The initial distribution adds exactly one read and one write per record (total (2N) steps). Therefore the total number of steps (S) satisfies [ S = \text{external path length of the tree} + 2N, ] where the external path length is the sum of the depths of all (N) leaves.

2. Lower bound on external path length

Let (L) be the external path length of a tree with (N) leaves and maximum degree (d = T-1 \ge 2). We show (L = \Omega(N\log N)).

For a tree of maximum degree (d), the number of leaves at depth (\le k) is at most [ 1 + d + d^2 + \cdots + d^k = \frac{d^{k+1}-1}{d-1} < d^{k+1}. ] To minimize (L = \sum_i i, n_i) (where (n_i) is the number of leaves at depth (i)) subject to (\sum_i n_i = N) and (n_i \le d^i), we must place leaves as shallow as possible. The optimal configuration is a balanced (d)-ary tree where all leaves have depth either (\lfloor \log_d N \rfloor) or (\lceil \log_d N \rceil). Its external path length is [ L_{\min} = N \log_d N + O(N). ] Thus for any such tree (L \ge N \log_d N - O(N)). Since (d = T-1) is a constant (\ge 2), (L = \Omega(N\log N)).

3. Conclusion

The total number of steps is (S = L + 2N = \Omega(N\log N)). Hence it is impossible to reverse the tape in fewer than (\Omega(N\log N)) steps without reading backwards.

The bound is tight: Exercise 5.2.5-14 describes a class of algorithms (balanced merge, polyphase merge, etc., adapted for forward reading) that achieve (O(N\log N)) steps.

Verification

  1. Tree representation validity - Every read‑forward tape algorithm that reverses a sequence of distinct records can be simulated by a sequence of merges. The initial run on T1 must be split into unit runs because the relative order of every pair of records is inverted; any larger block would require further splits, which only increases the total record moves. Each merge uses at most (T-1) input tapes because one tape is the output. The tree built from these merges has exactly the properties used in the proof.

  2. External path length bound - The inequality (L \ge N \log_d N - O(N)) for trees with maximum degree (d) and (N) leaves is a standard combinatorial fact. It can be verified by induction on (N) or by the Kraft inequality. For (N=1) the bound gives (L=0), which is correct (no merges needed). For (N>1) the balanced (d)-ary tree achieves the minimum, confirming the bound is tight up to an additive linear term.

  3. Boundary cases - If (N=0) or (N=1) the problem is trivial (0 or 1 steps), and the (\Omega(N\log N)) bound holds vacuously. The argument works for any constant (T\ge 3); the base of the logarithm is (T-1), which is absorbed in the (\Omega) notation.

  4. Matching upper bound - Exercise 5.2.5-14 provides explicit algorithms (e.g., the balanced merge pattern adapted to forward reading) that reverse the tape in (O(N\log N)) steps, showing the lower bound is asymptotically optimal.

∎