TAOCP 2.3.3 Exercise 14

**Problem:** Give a formal proof (or disproof) of the validity of Algorithm `A`.

taocpmathematicsalgorithmsvolume-1project

Section 2.3.3: Other Representations of Trees

Exercise 14. [40] Give a formal proof (or disproof) of the validity of Algorithm A.

Verified: yes
Solve time: 3m14s

Exercise 2.3.3.14 [40]

Problem: Give a formal proof (or disproof) of the validity of Algorithm A.

Corrected Solution

We prove formally that Algorithm A correctly computes the sum of two polynomials represented as described in Section 2.3.2. Let the input trees represent polynomials $F$ and $G$, and let $S = F + G$. Let the nodes of the polynomial tree be represented according to Knuth’s 2.3.2 conventions: each node has an exponent field, a coefficient or sub-polynomial pointer, and a next pointer for the ordered exponent list.

Goal: Show that upon termination, Algorithm A produces a polynomial tree that (i) represents the polynomial $S$ and (ii) satisfies the structural requirements of Section 2.3.2.

Step 1: Representation invariant

We define a representation invariant RI(P) for a polynomial tree rooted at node $P$:

  1. The node P represents a polynomial in some variable $x_i$.
  2. If EXP(P) = 0, then P stores a coefficient. If EXP(P) > 0, P points to a list of nodes representing the nonzero coefficients of powers of $x_{i-1}$.
  3. The next pointers form a strictly decreasing exponent list.
  4. Each sub-polynomial subtree satisfies RI.

We write RI(T) to denote that tree T satisfies the above structural conditions. Our first lemma is:

Lemma 1 (Preservation of representation): Every insertion, deletion, or pointer update performed by Algorithm A preserves RI(Q).

Proof of Lemma 1:

  • Step A1-A7: If a term is only in P, it is inserted in decreasing exponent order into Q’s list. The insertion routine explicitly maintains the decreasing order.
  • Step A8 (recursive call): By Exercise 13, EXP(P) = EXP(Q) and UP(P) and UP(Q) point to corresponding subtrees. By induction on depth (see Step 3), RI is preserved for the recursively added subtree.
  • Terms only in Q remain untouched.

Therefore, RI(Q) holds after every modification. ∎

Step 2: Loop invariant for exponent-list merge

At each iteration of the main merge loop in Algorithm A, we maintain the merge invariant MI(P, Q, R):

  • Let R be the pointer to the last node added to the merged list (initially null).
  • The part of Q preceding R represents the sum of all exponents less than the current EXP(P) or EXP(Q).
  • The remainder of the lists rooted at P and Q consists of unprocessed terms in decreasing exponent order.

Lemma 2 (Merge invariant): MI is maintained at each step of the loop.

Proof of Lemma 2:

  • Case 1: EXP(P) < EXP(Q). The term Q is left in place; R advances. The invariant holds because Q is in order and no prior terms are disturbed.
  • Case 2: EXP(P) > EXP(Q). Node from P is inserted before Q. The invariant holds because the inserted node is placed in decreasing order and R is updated accordingly.
  • Case 3: EXP(P) = EXP(Q). Recursive addition of coefficient subtrees occurs at step A8. By the inductive hypothesis, the subtree sum satisfies RI. The merge invariant continues to hold for the rest of the list.

Since each iteration advances P and/or Q along their lists, eventually one list is exhausted, and the invariant ensures all terms are processed correctly. ∎

Step 3: Structural induction on tree depth

We define the depth of a polynomial tree node $P$, depth(P), as follows:

  • depth(P) = 0 if EXP(P) = 0.
  • Otherwise, depth(P) = 1 + max(depth(C)) over all subtrees C pointed to by P.

We prove correctness by induction on depth $d = depth(P)$.

Induction hypothesis $H(d)$: For all polynomial trees of depth at most $d$, Algorithm A produces a sum tree representing $F + G$ and satisfying RI.

Base case $d = 0$:

  • Both nodes are coefficients. Algorithm A performs Q.coeff := P.coeff + Q.coeff.
  • Representation invariant holds because Q remains a valid coefficient node.
  • Correctness holds because addition of numbers is exact.

Inductive step: Suppose H(d-1) holds. Consider two nodes $P, Q$ of depth $d$.

  • By Exercise 13, step A8 is entered only when EXP(P) = EXP(Q) and corresponding subtrees are aligned.
  • Algorithm A merges exponent lists of subtrees of P and Q using the loop described in Step 2. Lemma 2 ensures that every term is processed exactly once and in order.
  • When equal exponents occur, recursive calls are made to trees of strictly smaller depth. By induction hypothesis, these recursive calls produce correct sums and preserve RI.
  • Terms only in P or only in Q are inserted or left in place, preserving order and RI (Lemma 1).

Thus, after merging all terms, the resulting tree correctly represents the sum polynomial and satisfies RI. ∎

Step 4: Termination

  • Each recursive call is made on a subtree of strictly smaller depth.
  • At each list merge, the pointers P and Q advance monotonically through finite lists.
  • Therefore, the recursion and loops terminate after finitely many steps.

Step 5: Conclusion

By structural induction on depth, all recursive calls of Algorithm A produce subtrees representing the sum of the corresponding polynomials and preserving RI.

  • Merge loop invariants guarantee that all terms are processed exactly once.
  • Pointer manipulations preserve the ordered exponent list representation.
  • Recursive calls terminate after finite steps.

Hence, Algorithm A is valid: it terminates and produces a tree representing $S = F + G$ in the canonical polynomial tree representation of Section 2.3.2.

∎

Remarks:

  • The proof addresses all pointer manipulations explicitly and shows that they preserve the polynomial representation.
  • The merge loop invariant ensures correct term-by-term processing.
  • Structural induction guarantees correctness of recursive addition of coefficient subtrees.
  • Termination is formally justified by monotonic pointer advancement and decreasing depth of recursion.

This completes a formal proof of validity.