TAOCP 5.4.6: Practical Considerations for Tape Merging
Section 5.4.6 exercises: 14/14 solved.
Section 5.4.6. Practical Considerations for Tape Merging
Exercises from TAOCP Volume 3 Section 5.4.6: 14/14 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [18] | medium | solved | 1m54s |
| 2 | [15] | simple | solved | 3m34s |
| 3 | [20] | medium | solved | 6m08s |
| 4 | [20] | medium | verified | 4m03s |
| 5 | [21] | medium | verified | 1m13s |
| 6 | [22] | medium | solved | 1m05s |
| 7 | [26] | hard | solved | 3m34s |
| 8 | [20] | medium | verified | 2m28s |
| 9 | [22] | medium | solved | 3m41s |
| 10 | [M23] | math-medium | solved | 4m32s |
| 11 | [23] | medium | solved | 3m57s |
| 12 | [40] | project | solved | 1m22s |
| 13 | [20] | medium | solved | 4m44s |
| 14 | [M19] | math-medium | solved | 3m34s |
TAOCP 5.4.6 Exercise 1
Let $L = 23{,}000{,}000$.
TAOCP 5.4.6 Exercise 2
The key point is not that File 2 is “unused”, but how Algorithm B assigns and clears buffers when a file changes role and when the first output block is actually produced.
TAOCP 5.4.6 Exercise 3
Solution to TAOCP 5.4.6 Exercise 3.
TAOCP 5.4.6 Exercise 4
We must modify Algorithm F _as it is actually written in TAOCP_, not an abstract version of it.
TAOCP 5.4.6 Exercise 5
Algorithm F forecasts the next input operation by examining the last records currently present in the active buffers.
TAOCP 5.4.6 Exercise 6
Algorithm 5.
TAOCP 5.4.6 Exercise 7
We restart from the actual optimization principle used in Exercises 5.
TAOCP 5.4.6 Exercise 8
Let the initial distribution place $S$ runs onto $P$ input tapes for a $P$-way merge under Algorithm F in Section 5.
TAOCP 5.4.6 Exercise 9
The previous solution fails because it never uses the actual structure of Chart A, and therefore never computes the polyphase schedule or I/O count for $T=6$.
TAOCP 5.4.6 Exercise 10
Let $S$ be the total number of runs in the file.
TAOCP 5.4.6 Exercise 11
The core failure in the previous solution is not the lack of prose, but the absence of any actual instantiation of Chart A and Table 1 into computable expressions.
TAOCP 5.4.6 Exercise 12
Six tapes are partitioned into three logical pairs.