TAOCP 7.1.4 Exercise 69
Algorithm S constructs new BDD nodes during recursive or memoized evaluation of an operation such as apply, using a shared node pool indexed upward from `TBOT` and downward from `NTOP`, with failure o...
Section 7.1.4: Binary Decision Diagrams
Exercise 69. [21] [21] Algorithm S ought to have one or more precautionary instructions such as “if NTOP > TBOT, terminate the algorithm unsuccessfully,” in case it runs out of room. Where are the best places to insert them?
Verified: yes
Solve time: 1m33s
Solution
Algorithm S constructs new BDD nodes during recursive or memoized evaluation of an operation such as apply, using a shared node pool indexed upward from TBOT and downward from NTOP, with failure occurring exactly when these regions collide, i.e., when NTOP > TBOT.
The condition NTOP > TBOT is not a property that should be tested only at the end of the algorithm, because overflow is caused locally by individual node allocations. Each increment of NTOP corresponds to the creation of a new BDD node (or an equivalent entry in the node pool), so failure can occur at the precise moment a new node is needed.
The correct placement of precautionary instructions follows directly from the invariant that every node creation decreases available memory between NTOP and TBOT by one unit.
First, a check must be placed immediately before every operation that performs a write into the node table at position NTOP. In Algorithm S, this occurs at each point where a new branch node is constructed from a pair of recursive results, typically in the form of a call equivalent to new node(V, LO, HI). Since such a call implicitly performs NTOP ← NTOP + 1, the test if NTOP + 1 > TBOT then terminate unsuccessfully must precede every such increment. This ensures that no node is written after the available space has been exhausted.
Second, the same precaution must be applied in any memoization or unique-table insertion step that may itself allocate a node. In Algorithm S-style BDD procedures, even when a node is “reused” via hashing, the collision resolution or table insertion path may still allocate a new canonical node if no identical triple (V, LO, HI) exists. Therefore, the overflow check must be placed at the entry point of the node-canonicalization routine, not only at the high-level recursive driver.
Third, because Algorithm S is recursive, the call that combines results of recursive evaluations (corresponding to the Shannon decomposition step) is another mandatory insertion point. Each such combination computes a candidate node from two subresults, and in the nontrivial case produces a fresh node. The check must therefore appear immediately before returning any newly constructed node from that recursive frame.
Finally, if Algorithm S uses any auxiliary stack or temporary workspace whose growth is coupled to node creation, a symmetric check is required at each push operation into that structure. While the overflow condition is stated in terms of NTOP and TBOT, stack growth effectively reduces the same free interval, so any instruction that advances either boundary must be guarded by the same inequality test.
No weaker placement suffices, because a single unchecked increment of NTOP may already violate NTOP > TBOT and overwrite existing memory before any later global test can intervene. Conversely, checking only at coarse-grained loop boundaries fails to capture intermediate allocations triggered by recursive descent or memoized construction.
The optimal placement is therefore at every primitive node-allocation event, including recursive node construction, unique-table insertion that can allocate, and any stack operation that consumes space in the same contiguous memory region.
This completes the solution. ∎