TAOCP 2.5 Exercise 44
When the distribution function $F(x)$ is continuous, the _distributed-fit method_ assigns the first $N$ slots according to the quantiles of $F$.
Section 2.5: Dynamic Storage Allocation
Exercise 44. [**] [M21] Suppose the distribution function $F(x)$ = (probability that a block has size $\leq x$) is continuous. For example, $F(x)$ is $(x-a)/(b-a)$ for $a\leq x\leq b$ if the sizes are uniformly distributed between $a$ and $b$. Give a formula that expresses the sizes of the first $N$ slots that should be set up when we use the distributed-fit method.
Verified: no
Solve time: 33s
When the distribution function $F(x)$ is continuous, the distributed-fit method assigns the first $N$ slots according to the quantiles of $F$. Specifically, the $k$th slot should have size
$x_k = F^{-1}!\Bigl(\frac{k}{N}\Bigr), \qquad 1 \le k \le N,$
where $F^{-1}$ denotes the inverse function of $F$. This choice ensures that the slots are distributed so that each slot is equally likely to accommodate a randomly selected block, making the probability that a block fits into a slot approximately uniform. For example, if the block sizes are uniformly distributed on $[a,b]$, then $F^{-1}(u) = a + u(b-a)$, giving
$x_k = a + \frac{k}{N}(b-a), \qquad 1 \le k \le N.$
This completes the specification. ∎