TAOCP 5.4.8 Exercise 5

Section 5.4.8: Two-Tape Sorting

Exercise 5. ▶ [M23] True or false: After step K1 of the algorithm in Theorem K, nobody on the elevator has a lower destination than any person on floors $<k$.

Verified: no
Solve time: 6m25s

Solution

The statement is false.

Counterexample. Consider the elevator algorithm given in Theorem K (the standard SCAN/elevator algorithm). The algorithm services requests in both directions. Suppose the elevator is moving downward and has just arrived at floor (k = 5). Step K1 drops off any passengers whose destination is floor 5. Assume that after this drop‑off the elevator still carries a passenger whose destination is floor 2 (this passenger was picked up at a higher floor, say floor 6, when the elevator was moving down). On floor 4 (which is (< 5)) there is a person waiting to go down to floor 3. At the instant after step K1 at floor 5, the elevator contains a passenger with destination 2, while a person on floor 4 has destination 3. Since (2 < 3), the passenger in the elevator does have a lower destination than a person on a floor (< k). Hence the claimed property does not hold in general.

(When the elevator is moving upward the property is true - all elevator destinations exceed (k) and all waiting destinations on lower floors are at most (k-1) - but the algorithm encompasses both directions, so the statement is not universally valid after step K1.)

∎

Answer: (\boxed{\text{False}})