Section 2.3.3: Other Representations of Trees

Exercise 13. [M29] Give an informal proof that at the beginning of step A8 of Algorithm A we always have EXP(P) = EXP(Q) and CV(UP(P)) = CV(UP(Q)). (This fact is important to the proper understanding of that algorithm.)

Verified: yes
Solve time: 1m23s

---

Setup

Algorithm A adds two polynomials represented as trees. Let P and Q denote the current nodes in the two trees. The field EXP gives the exponent associated with a node, UP points to the parent node, and CV is the variable index stored in a header node.

The statement to be justified is:

At the beginning of step A8,

$$ \operatorname{EXP}(P)=\operatorname{EXP}(Q) $$

and

$$ \operatorname{CV}(\operatorname{UP}(P))

\operatorname{CV}(\operatorname{UP}(Q)). $$

The purpose is to explain why these equalities must hold whenever control reaches step A8.

Solution

Step A8 is reached only when Algorithm A has determined that the two terms currently under consideration correspond to the same power of the same variable, so that their coefficients must be combined recursively.

Consider first the exponents. During the comparison phase of the algorithm, the values EXP(P) and EXP(Q) are examined. If one exponent is larger than the other, the corresponding term is copied to the result and the algorithm advances without entering step A8. Therefore every path leading to A8 has already passed through the test that distinguishes the cases

$$ \operatorname{EXP}(P)>\operatorname{EXP}(Q), \qquad \operatorname{EXP}(P)<\operatorname{EXP}(Q), \qquad \operatorname{EXP}(P)=\operatorname{EXP}(Q). $$

The first two cases bypass A8. Hence arrival at A8 is possible only in the third case, and therefore

$$ \operatorname{EXP}(P)=\operatorname{EXP}(Q). $$

Now consider the variables. The nodes P and Q are descendants of header nodes whose variable indices are

$$ \operatorname{CV}(\operatorname{UP}(P)) \quad\text{and}\quad \operatorname{CV}(\operatorname{UP}(Q)). $$

Algorithm A compares polynomials only within corresponding levels of the recursive structure. Whenever a recursive call is made, it is made on coefficient subpolynomials that belong to the same variable level. The algorithm never compares a polynomial in one variable with a polynomial in another variable. Consequently the parent headers of the nodes currently being compared always represent the same variable.

This property is true initially, since the algorithm begins by adding two polynomials represented at the same top level. It is preserved whenever the algorithm descends to coefficient subpolynomials, because both descents are made simultaneously from terms having the same exponent. Thus every pair of nodes that can reach step A8 satisfies

$$ \operatorname{CV}(\operatorname{UP}(P)) = \operatorname{CV}(\operatorname{UP}(Q)). $$

Combining the two arguments, at the beginning of step A8 we necessarily have

$$ \operatorname{EXP}(P)=\operatorname{EXP}(Q) $$

and

$$ \operatorname{CV}(\operatorname{UP}(P)) = \operatorname{CV}(\operatorname{UP}(Q)). $$

This completes the proof.

∎

Verification

The only entries into step A8 occur after the exponent comparison has ruled out the cases

$$ \operatorname{EXP}(P)\ne\operatorname{EXP}(Q). $$

Hence equality of exponents is forced.

The algorithm maintains the invariant that P and Q lie at corresponding levels of the two polynomial trees. Since corresponding levels are headed by the same variable, the parent header nodes satisfy

$$ \operatorname{CV}(\operatorname{UP}(P)) = \operatorname{CV}(\operatorname{UP}(Q)). $$

Therefore both required equalities hold whenever execution reaches A8.

Notes

The statement is not an additional condition imposed on Algorithm A; it is an invariant created by the control structure of the algorithm itself. Step A8 is precisely the branch that handles the case of equal exponents at a common variable level.