TAOCP 7.1.4 Exercise 72

Exercise 72. [25] [25] Explain how to eliminate hashing from Algorithm S.

Verified: yes
Solve time: 1m39s

Solution

Algorithm S relies on a “unique table” that maps each triple $(V, LO, HI)$ to a unique node so that identical subfunctions share a single representation. In the standard formulation this mapping is implemented by hashing the triple into a table bucket and then resolving collisions within that bucket.

Hashing is used only to support fast membership testing for the predicate “does a node with key $(V, LO, HI)$ already exist”. Eliminating hashing therefore requires replacing this membership structure with a deterministic dictionary on triples.

Replace the hash table by a balanced search tree whose keys are ordered triples $(V, LO, HI)$ under lexicographic order. Each node of this tree stores one existing BDD node together with its key. The tree invariant is that an in-order traversal lists all existing triples in lexicographic order, which determines a unique position for every possible node key.

When Algorithm S attempts to create a node with parameters $(V, LO, HI)$, it performs a search in this balanced tree. If a node with exactly the same triple is found, the algorithm returns the pointer to the existing node. If no match is found, a new node is allocated, its triple is inserted into the tree at the unique location determined by the search path, and the pointer to this new node is returned.

The reduction condition $LO \neq HI$ is checked before any tree operation. If $LO = HI$, the algorithm returns $LO$ directly and performs no insertion, which preserves the reduced form of the BDD independently of the dictionary mechanism.

Correctness follows from the fact that every node stored in the structure is identified solely by its triple $(V, LO, HI)$, and the search tree implements exact equality testing by deterministic comparison of these components. Since each insertion place is uniquely determined by comparisons of integers, no two distinct nodes with the same triple can be created, and no two identical subfunctions can acquire different representations. The ordering constraint on BDD construction is unaffected because it depends only on variable indices and not on the storage mechanism.

The replacement preserves canonicity of the representation because every node creation is funneled through a unique existence test, and equality of nodes is enforced structurally rather than probabilistically. The tradeoff is computational: expected constant-time hashing is replaced by logarithmic-time search in a balanced tree, but no correctness property depends on probabilistic behavior.

This completes the construction.