TAOCP Vol 1: Overflowing multiple stacks proof

Question

I am self-studying TAOCP and trying to make sense of the solution to the following problem from Chapter 2.2.2 Linear Lists: Sequential Allocation.

17. [30] If σ is any sequence of insertions and deletions such as (12), let s0 (σ) be the number of stack overflows that occur when the simple method of Fig. 4 is applied to σ with initial conditions (11), and let s1 (σ) be the corresponding number of overflows with respect to other initial conditions such as (13). Prove that s0 (σ) ≤ s1 (σ)+L∞ − L0.

For s0, the initial conditions are that BASE[j] = TOP[j] = L0 for 1 <= j <= n (11), and BASE[n+1]=L∞. In other words, initially all space (L∞ − L0) is given to the last stack (the n-th stack), and all stacks are empty. s1 can be any other initial condition, such as, for example, evenly dividing all space among the n empty stacks.

Note that when stack i overflows, the algorithm is to find the nearest subsequent stack that is not at full capacity, and "move things up one notch." If all subsequent stacks (with respect to i) are at full capacity, then find the nearest previous stack (with respect to i) that is not full, and "move things down one notch." Lastly, if we cannot find any room for the new stack entry, then we must give up.

Our intuition is the following:

It is clear that many of the first stack overflows that occur with this method could be eliminated if we chose our initial conditions wisely, instead of allocating all space initially to the nth stack as suggested in (11). ... No matter how well the initial allocation is set up, it can save at most a fixed number of overflows, and the effect is noticeable only in the early stages of a program run.

The given solution is this:

17. First show that BASE[j]0 ≤ BASE[j]1 at all times. Then observe that each overflow for stack i in s0(σ) that does not also overflow in s1(σ) occurs at a time when stack i has gotten larger than ever before, yet its new size is not more than the original size allocated to stack i in s1(σ).

I don't think that the "larger than ever before" part of the statement is true. A stack's capacity can shrink as result of another stack overflowing. Say stack i is full, then a deletion from stack i occurs, then stack i shrinks, and lastly an insertion into stack i occurs. In this case an overflow occurs in stack i when stack i grows larger, but not "larger than ever before." For this reason, I do not understand the solution, or see what I am supposed to see, I suppose.

I am trying to figure out a way to prove that s0 (σ) will encounter at most L∞ − L0 more overflows than s0 (σ) will, but am currently stumped. Any help would be appreciated :-)

Answer 1

I think you might have a valid objection, but I’m not near my copy of TAoCP, and I’m not sure that I have correctly implemented the algorithm (see Python below).

Let’s suppose we have n = 4 stacks. We start the “bad” initial conditions (s0) where stacks 0, 1, 2 each have capacity 0 and stack 3 has capacity 4, and the “good” initial conditions (s1) where each stack has capacity 1.

A bad sequence is: push stack 2, pop stack 2, push stack 1, pop stack 1, push stack 0, push stack 1, push stack 2. Each push overflows s0 but not s1.

import random


def push(L, U, i):
    if U[i] < L[i + 1]:
        U[i] += 1
        return False
    for k in range(i + 1, len(U)):
        if U[k] < L[k + 1]:
            for j in range(k, i, -1):
                U[j] += 1
                L[j] += 1
            U[i] += 1
            return True
    for k in range(i - 1, -1, -1):
        if U[k] < L[k + 1]:
            for j in range(k + 1, i):
                L[j] -= 1
                U[j] -= 1
            L[i] -= 1
            return True
    return False


def pop(L, U, i):
    if L[i] < U[i]:
        U[i] -= 1


def test():
    for t in range(1000000):
        n = 4
        cap = 1
        L0 = [0] * n + [n * cap]
        U0 = L0[:n]
        L1 = list(range(0, (n + 1) * cap, cap))
        U1 = L1[:n]
        c0 = 0
        c1 = 0
        ops = []
        for r in range(7):
            i = random.randrange(n)
            if random.randrange(2):
                c0 += push(L0, U0, i)
                c1 += push(L1, U1, i)
                ops.append("push {}".format(i))
            else:
                pop(L0, U0, i)
                pop(L1, U1, i)
                ops.append("pop {}".format(i))
        assert L0[-1] == n * cap == L1[-1]
        assert all(U0[i] - L0[i] == U1[i] - L1[i] for i in range(n))
        assert c0 <= c1 + L1[-1], "\n".join(ops + [str(c0), str(c1)])


if __name__ == "__main__":
    test()