TAOCP 2.2.2 Exercise 7

Step `G4` of Algorithm `G` sets \alpha \leftarrow 0.

taocpmathematicsalgorithmsvolume-1simple

Section 2.2.2: Sequential Allocation

Exercise 7. [12] Step G4 of Algorithm G indicates a division by the quantity INC. Can INC ever be zero at that point in the algorithm?

Verified: no
Solve time: -

Solution

Step G4 of Algorithm G sets

$$ \alpha \leftarrow 0.1 \times \frac{\text{SUM}}{n},\qquad \beta \leftarrow 0.9 \times \frac{\text{SUM}}{\text{INC}}. $$

The quantity INC was computed in step G2 as

$$ \text{INC} \leftarrow \sum_{j=1}^{n} D[j],\quad \text{where } D[j] = \begin{cases} \text{TOP}[j] - \text{OLDTOP}[j], & \text{if } \text{TOP}[j] > \text{OLDTOP}[j];\[2mm] 0, & \text{otherwise}. \end{cases} $$

Thus INC is the total increase in occupied space for all stacks since the previous memory allocation.

By construction, step G2 sets D[j] nonnegative for each j. Therefore, INC = 0 exactly when D[j] = 0 for all 1 \le j \le n. In other words, INC = 0 occurs if and only if

$$ \text{TOP}[j] \le \text{OLDTOP}[j] \quad \text{for all } j = 1, \dots, n. $$

Now consider the situation in which INC = 0. Step G2 also computes

$$ \text{SUM} \leftarrow L_\infty - L_0 - \sum_{j=1}^{n} (\text{TOP}[j] - \text{BASE}[j]). $$

If INC = 0, then no stack has grown since the previous allocation. Step G3 checks whether SUM < 0, i.e., whether the total remaining memory is negative. If SUM \ge 0, then there is still free memory. In this case, the algorithm can proceed to allocate new entries without repacking any stack upward, because step G4 will compute \beta as 0.9 × SUM / INC, which is division by zero.

Therefore, INC can be zero at step G4 if none of the stacks has grown since the previous allocation. Algorithm G must handle this case explicitly to avoid division by zero. A practical approach is to define \beta arbitrarily or to skip the redistribution of memory, since no stack expansion has occurred and all required allocations fit within SUM.

Hence, INC = 0 is possible, and it corresponds precisely to the case where no stack has increased its size since the last allocation. This completes the proof.

∎