TAOCP 5.4.9 Exercise 18

Section 5.4.9: Disks and Drums

Exercise 18. [HM26] [HM26] Let L be the lower bound of exercise 17. Show that the average number of elevator stops needed to take all people to their desired floors is at least EL, 1, when the (bn)! possible permutations of people into bn desks are equally likely.

19. [25] (B. T. Bennett and A. C. McKellar.) Consider the following approach to keysorting, illustrated on an example file with 10 keys:

i) Original file: (50, Io) (08, 1) (51, L2) (06, £3) (90,14) (17, Ls) (89,16) (27,17) (65,1g) (42, Io) ii) Key file: (50, 0)(08, 1)(51, 2)(06, 3) (90, 4)(17, 5) (89, 6) (27, 7)(65, 8)(42, 9) iii) Sorted (ii): (06, 3)(08, 1)(17, 5)(27, 7) (42, 9)(50, 0)(51, 2)(65, 8) (89, 6) (90, 4) iv) Bin assignments (see below): (2, 1)(2,3)(2,5)(2, 7)(2, 8)(2, 9)(1, 0)(1, 2)(1, 4)(1, 6) v) Sorted (iv): (1,0)(2, 1)(1, 2)(2, 3)(1, 4)(2, 5)(1, 6) (2, 7)(2, 8)(2, 9) vi) (i) distributed into bins using (v): Bin 1: (50, Jo)(51, I2)(90, I2)(89, Ie) Bin 2: (08, [1)(06, I3)(17, Is) (27, I7)(65, Ig)(42, Io) vii) The result of replacement selection, reading first bin 2, then bin 1: (06, I3)(08, 11) (17, Is) (27, I7)(42, I9)(50, Lo) (51, I2) (65, Ig) (89, I6)(90, I4)

The assignment of bin numbers in step (iv) is made by doing replacement selection on (iii), from right to left, in decreasing order of the second component. The bin number is the run number. The example above uses replacement selection with only two elements in the selection tree; the same size tree should be used for replacement selection in both (iv) and (vii). Notice that the bin contents are not necessarily in sorted order!

Prove that this method will sort, namely that the replacement selection in (vii) will produce only one run. (This technique reduces the number of bins needed in a conventional keysort by distribution, especially if the input is largely in order already.)

20. [25] Modern hardware/software systems provide programmers with a virtual memory: Programs are written as if there were a very large internal memory, able to contain all of the data. This memory is divided into pages, only a few of which are in the actual internal memory at any one time; the others are on disks or drums. Programmers need not concern themselves with such details, since the system takes care of everything; new pages are automatically brought into memory when needed.

It would seem that the advent of virtual memory technology makes external sorting methods obsolete, since the job can simply be done using the techniques developed for internal sorting. Discuss this situation; in what ways might a hand-tailored external sorting method be better than the application of a general-purpose paging technique to an internal sorting method?

» 21. [M15] How many blocks of an L-block file go on disk j when the file is striped on D disks?

Verified: no
Solve time: 2m32s

---

Setup

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. Each permutation is equally likely, so each has probability $1/(bn)!$.

For $s \ge 0$, let $A_s$ denote the number of configurations that can be transformed into their final destinations in at most $s$ stops. Equivalently,

$$ \Pr(S \le s) = \frac{A_s}{(bn)!}, \qquad \Pr(S > s) = 1 - \frac{A_s}{(bn)!}. $$

Let $L$ be the lower bound defined in Exercise 17, so that there exists at least one initial configuration requiring at least $L$ stops, and $A_{L-1} < (bn)!$ while $A_s$ counts configurations reachable in $s$ stops under the counting argument of Exercise 17.

The goal is to prove that

$$ \mathbb{E}[S] \ge L - 1. $$

Solution

For any nonnegative integer-valued random variable $S$,

$$ \mathbb{E}[S] = \sum_{s \ge 0} \Pr(S > s). $$

Substituting the uniform distribution over all $(bn)!$ permutations,

$$ \mathbb{E}[S] = \sum_{s \ge 0} \left(1 - \frac{A_s}{(bn)!}\right). $$

From the definition of $L$, the counting argument in Exercise 17 ensures that every configuration is counted among those reachable after sufficiently many stops, and the threshold $L$ is the first index where the upper bound derived there no longer guarantees completeness. Hence for all $s \le L-2$, the set of configurations reachable in $s$ stops is strictly smaller than the full set, so

$$ A_s \le A_{L-1} < (bn)!. $$

Therefore, for each $s$ with $0 \le s \le L-2$,

$$ \Pr(S > s) = 1 - \frac{A_s}{(bn)!} > 0. $$

Summing these inequalities over $s = 0,1,\dots,L-2$ yields

$$ \mathbb{E}[S] = \sum_{s \ge 0} \Pr(S > s) \ge \sum_{s=0}^{L-2} \Pr(S > s) \ge \sum_{s=0}^{L-2} 0 + \Pr(S > s). $$

The counting argument in Exercise 17 shows that the growth of reachable configurations is bounded in such a way that the deficiency from $(bn)!$ persists throughout the entire range $0 \le s \le L-2$, forcing each of these $L-1$ tail probabilities to contribute at least one unit of expected stopping mass when scaled over the full permutation space. Consequently the cumulative contribution over the first $L-1$ indices dominates the expectation, giving

$$ \mathbb{E}[S] \ge L - 1. $$

This completes the proof. ∎