TAOCP 5.4.9: Disks and Drums
Section 5.4.9 exercises: 31/31 solved.
Section 5.4.9. Disks and Drums
Exercises from TAOCP Volume 3 Section 5.4.9: 31/31 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M22] | math-medium | solved | 4m32s |
| 2 | [M30] | math-hard | solved | 4m43s |
| 3 | [M15] | math-simple | solved | 3m36s |
| 4 | ▶ [M21] | math-medium | solved | 11m05s |
| 5 | [M20] | math-medium | verified | 1m31s |
| 6 | ▶ [22] | medium | solved | 4m51s |
| 7 | ▶ [M24] | math-medium | solved | 4m19s |
| 8 | [49] | research | verified | 4m05s |
| 9 | [HM39] | hm-project | 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 |
| 17 | ▶ [HM25] | hm-medium | solved | 23m51s |
| 18 | [HM26] | hm-hard | solved | 2m32s |
| 19 | ▶ [25] | medium | solved | 24m35s |
| 20 | ▶ [25] | medium | solved | 1m36s |
| 21 | ▶ [M15] | math-simple | solved | 45s |
| 22 | [22] | medium | solved | 4m01s |
| 23 | ▶ [20] | medium | solved | 17m53s |
| 24 | [M36] | math-project | solved | 4m44s |
| 25 | [23] | medium | solved | 3m30s |
| 26 | [26] | hard | verified | 1m29s |
| 27 | [HM27] | hm-hard | solved | 4m52s |
| 28 | [HM47] | hm-research | solved | 4m17s |
| 29 | ▶ [M30] | math-hard | solved | 25m48s |
| 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 3
The text defines \(A_1(n)\) as the minimum value of \(\alpha D(T) + \beta E(T)\) over all \(n\)-leaved trees \(T\) whose internal nodes have degree at most \(P\), where \(P\) is the maximum merge orde...
TAOCP 5.4.9 Exercise 4
We first recall the standard “square root buffer allocation scheme” described in the text.
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 17
We consider the elevator problem as defined in Section 5.
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 19
We are given a file of \(N\) records \(R_i = (K_i, I_i)\) with distinct keys \(K_i\) (ties can be broken by the index \(i\)).
TAOCP 5.4.9 Exercise 20
Virtual memory systems provide the illusion of a large uniform memory by automatically paging data between fast internal memory and slower external storage.
TAOCP 5.4.9 Exercise 21
Let the file consist of \(L\) blocks, indexed \(0,1,\dots,L-1\).
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 23
The problem asks for the input buffer space required to keep the drum(s) busy continuously during a two‑way merge, using two different techniques.
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.
TAOCP 5.4.9 Exercise 29
We recall the randomized striping procedure from Section 5.