TAOCP 5.4.4: Reading Tape Backwards
Section 5.4.4 exercises: 22/22 solved.
Section 5.4.4. Reading Tape Backwards
Exercises from TAOCP Volume 3 Section 5.4.4: 22/22 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [17] | medium | solved | 4m31s |
| 2 | [20] | medium | solved | 11m29s |
| 3 | ▶ [20] | medium | solved | 15m17s |
| 4 | [M22] | math-medium | solved | 2m02s |
| 5 | ▶ [23] | medium | solved | 10m24s |
| 6 | [07] | simple | solved | 3m34s |
| 7 | [16] | medium | solved | 8m49s |
| 8 | [23] | medium | solved | 16m46s |
| 9 | [M22] | math-medium | solved | 13m23s |
| 10 | [41] | project | solved | 29m26s |
| 11 | ▶ [20] | medium | solved | 10m09s |
| 12 | [22] | medium | solved | 11m33s |
| 13 | [16] | medium | solved | 14m28s |
| 14 | [40] | project | solved | 6m07s |
| 15 | [M39] | math-project | solved | 38m59s |
| 16 | [M46] | math-research | solved | 1m40s |
| 17 | ▶ [28] | hard | solved | 7m03s |
| 18 | ▶ [M38] | math-project | solved | 14m57s |
| 19 | ▶ [22] | medium | solved | 1h02m |
| 20 | ▶ [22] | medium | solved | 10m09s |
| 21 | [18] | medium | solved | 14m43s |
| 22 | [28] | hard | solved | 1m16s |
TAOCP 5.4.4 Exercise 1
In read-forward merging, runs are written in ascending order and each run is terminated by an artificial sentinel record with key $+\infty$.
TAOCP 5.4.4 Exercise 2
The array (1) in the text shows the distribution of runs for the read‑backward polyphase merge on six tapes, where tape T1 is designated as the final output tape.
TAOCP 5.4.4 Exercise 3
We consider the read‑backward polyphase merge on six tapes (T1,…,T6) using the perfect distributions shown in table (1).
TAOCP 5.4.4 Exercise 4
No, it is not a good idea.
TAOCP 5.4.4 Exercise 5
In standard polyphase merging (Section 5.
TAOCP 5.4.4 Exercise 6
The tree representation (8) illustrates the balanced merge on four tapes with eight initial runs, as summarized in the tableau of the section.
TAOCP 5.4.4 Exercise 7
The given vector representation defines a read‑backward merge pattern on \(T=3\) tapes.
TAOCP 5.4.4 Exercise 8
The tree representation (8) for $S=7$, $T=4$ read-backward merging is the following pattern (shown in the text as equation (8)).
TAOCP 5.4.4 Exercise 9
We consider a read-backward merge pattern on \(T\) tapes that sorts \(S\) initial runs in \(m\) merge phases.
TAOCP 5.4.4 Exercise 10
In the theory of optimal merge patterns developed by Karp in this section, \(K_{T}(n)\) is the maximum number of initial runs that can be sorted in \(n\) merge phases using \(T\) tapes when reading ba...
TAOCP 5.4.4 Exercise 11
**False.
TAOCP 5.4.4 Exercise 12
We recall Karp's preorder construction as given in the text.
TAOCP 5.4.4 Exercise 13
The pure cascade merge for 14 initial runs on four tapes (read backwards) is described by the vector representation in the text.
TAOCP 5.4.4 Exercise 14
The preorder merge algorithm (Algorithm P in the text) controls an optimal read‑backward merge pattern using Karp’s tree representation.
TAOCP 5.4.4 Exercise 15
We work within the framework of Karp's tree representation for merge patterns on three tapes with LIFO (last-in-first-out) discipline.
TAOCP 5.4.4 Exercise 16
A **\(T\)-lifo tree** is a rooted ordered tree that represents a merge pattern for \(T\) tapes with backward reading.
TAOCP 5.4.4 Exercise 17
In a read‑backward cascade merge on \(T\) tapes, each merge pass reverses the order of the runs.
TAOCP 5.4.4 Exercise 18
We consider the standard tape model with \(T \ge 3\) tape units.
TAOCP 5.4.4 Exercise 19
The binary tree that is not 3-fifo is the tree depicted in the invalid configurations (4') of the text.
TAOCP 5.4.4 Exercise 20
A tree is **strongly $T$-fifo** if and only if it can be labeled with $T$ labels (tape numbers) so that the following two *invalid configurations* never appear: 1.