TAOCP 5.4.9: Disks and Drums
Section 5.4.9 exercises: 23/23 solved.
Section 5.4.9. Disks and Drums
Exercises from TAOCP Volume 3 Section 5.4.9: 23/23 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M22] | math-medium | solved | 4m32s |
| 2 | [M30] | math-hard | solved | 4m43s |
| 5 | [M20] | math-medium | verified | 1m31s |
| 6 | [22] | medium | solved | 4m51s |
| 7 | [M24] | math-medium | solved | 4m19s |
| 8 | [49] | research | verified | 4m05s |
| 9 | [HM89] | hm-research | solved | 2m17s |
| 10 | [HM44] | hm-project | solved | 1m02s |
| 11 | [M29] | math-hard | solved | 4m14s |
| 12 | [25] | medium | solved | 1m32s |
| 13 | [M24] | math-medium | solved | 4m19s |
| 14 | [40] | project | solved | 3m29s |
| 15 | [M22] | math-medium | solved | 3m25s |
| 16 | [23] | medium | solved | 3m33s |
| 18 | [HM26] | hm-hard | solved | 2m32s |
| 22 | [22] | medium | solved | 4m01s |
| 24 | [M36] | math-project | solved | 4m44s |
| 25 | [23] | medium | solved | 3m30s |
| 26 | [26] | hard | verified | 1m29s |
| 27 | [**] | solved | 4m52s | |
| 28 | [M30] | math-hard | solved | 4m17s |
| 30 | [HM30] | hm-hard | verified | 1m14s |
| 31 | [HM48] | hm-research | solved | 4m42s |
TAOCP 5.4.9 Exercise 1
Let $f(\theta)$ denote the optimal single–arm latency function for a request starting at position $\theta$, with \int_0^1 f(\theta)\,d\theta = 4(1-x^2).
TAOCP 5.4.9 Exercise 2
Working
TAOCP 5.4.9 Exercise 5
Let $T$ be a rooted tree representing a merge pattern as in Theorem K, with leaves carrying weights $w_1,\dots,w_n$, and let the external path length be E(T)=\sum_{i=1}^n w_i d_i, where $d_i$ is the l...
TAOCP 5.4.9 Exercise 6
The previous solution fails because it treats the weight data as missing.
TAOCP 5.4.9 Exercise 7
Let each initial run $i$ have weight $w_i$.
TAOCP 5.4.9 Exercise 8
We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$.
TAOCP 5.4.9 Exercise 9
Let $T$ be a full binary tree with $n$ leaves, and let $D(T)$ and $E(T)$ be the two weighted path functionals defined in Section 5.
TAOCP 5.4.9 Exercise 10
Let $A_i(n)$ denote the minimum transmission cost (external path length) among all merge trees with $n$ leaves, under fixed parameters $a$ and $b$ as in Section 5.
TAOCP 5.4.9 Exercise 11
Working
TAOCP 5.4.9 Exercise 12
Let $T$ be a rooted tree with $n>0$ leaves, and let the degree path length $(6)$ be defined as in Section 5.
TAOCP 5.4.9 Exercise 13
Let $T$ range over admissible merge patterns for $n$ runs, where each internal node has arity at most $8$, and cost is the weighted external path length C(T)=\sum_{i=1}^n w_i d_i.
TAOCP 5.4.9 Exercise 14
Let a rooted ordered tree $T$ have $n$ leaves.
TAOCP 5.4.9 Exercise 15
Let the elevator process be measured in stops, and let each stop be a position at which the elevator services requests while its capacity is $b$ and the access structure contributes at most $m$ additi...
TAOCP 5.4.9 Exercise 16
The previous solution fails because it never uses the actual data of configurations (28) and (29).
TAOCP 5.4.9 Exercise 18
Let $S$ be the number of elevator stops required by a fixed scheduling method applied to a uniformly random permutation of the $bn$ people among the $bn$ desks.
TAOCP 5.4.9 Exercise 22
The previous solution fails because it ignores that block placement is constrained by the _run structure of the merge schedule induced by the Gilbreath principle_, not by the index order of the input...
TAOCP 5.4.9 Exercise 24
Let the $P$ runs be $R_1,\dots,R_P$.
TAOCP 5.4.9 Exercise 25
The correct way to rework the example is to stay inside TAOCP’s randomized striping model: each run is striped across the $Q$ disks by a fixed permutation of disk numbers, and successive blocks of a r...
TAOCP 5.4.9 Exercise 26
A $P$-way merge produces one output block per unit of time, where the time to write a block equals the time to read a block.
TAOCP 5.4.9 Exercise 27
Let M_n = \max_{0 \le i < n} S_i(m_1,\ldots,m_p) be the maximum load.
TAOCP 5.4.9 Exercise 28
We restart from the definition of marking in the TAOCP model and avoid any auxiliary pipeline assumptions.