TAOCP 2.3.3 Exercise 15

**Problem restatement.

taocpmathematicsalgorithmsvolume-1project

Section 2.3.3: Other Representations of Trees

Exercise 15. [40] Design an algorithm to compute the product of two polynomials represented as in Fig. 28.

Verified: yes
Solve time: 2m39s

Exercise 2.3.3.15 [40]

Problem restatement. Let two polynomials be represented in the linked-tree sequential form of Fig. 28. That is, each polynomial is a tree in which a node contains fields:

  • COEFF, the coefficient of the term (possibly zero),
  • EXP, the exponent of the variable corresponding to this node,
  • LCHILD, a pointer to the first child (sub-polynomial for nested variables),
  • RLINK, a pointer to the next sibling node.

Let P and Q denote the roots of the two input polynomials. The goal is to compute the product polynomial

$$ R(x_1, x_2, \dots) = P(x_1, x_2, \dots) \cdot Q(x_1, x_2, \dots) $$

as a tree in the same representation, preserving the invariants of Fig. 28 and combining like terms.

Correct Solution

1. Recursive multiplication of trees

The key observation is that a node in the linked-tree representation may either be a terminal node (no LCHILD) or a nonterminal node (with LCHILD pointing to a sub-polynomial). Multiplication of two nodes must recursively multiply their subtrees.

Define the procedure

$$ \text{MULT}(P, Q) $$

which returns the root of the product polynomial of trees P and Q. The procedure proceeds as follows.

2. Algorithm T [Tree Polynomial Multiplication]

T1. [Base case: empty node.]

If P = null or Q = null, return null.

T2. [Initialize result.]

Set R <- null (empty tree).

T3. [Traverse P.]

For each node Pnode in the top-level list of P (follow RLINK):

  1. Let Pcoeff <- COEFF(Pnode) and Pexp <- EXP(Pnode).
  2. Let Pchild <- LCHILD(Pnode).

T4. [Traverse Q.]

For each node Qnode in the top-level list of Q (follow RLINK):

  1. Let Qcoeff <- COEFF(Qnode) and Qexp <- EXP(Qnode).
  2. Let Qchild <- LCHILD(Qnode).

T5. [Multiply nodes.]

  • Coefficient: $c \leftarrow Pcoeff \cdot Qcoeff$.

  • Exponent: $e \leftarrow Pexp + Qexp$.

  • Subtree:

  • If Pchild = null and Qchild = null, set Schild <- null.

  • Otherwise, recursively compute Schild <- MULT(Pchild, Qchild).

  • Create a new node S with fields:

$$ COEFF(S) = c, \quad EXP(S) = e, \quad LCHILD(S) = Schild, \quad RLINK(S) = null $$

T6. [Insert node into result.]

Insert S into the tree R in canonical order:

  1. Traverse the top-level nodes of R in increasing exponent order.
  2. If a node T exists with EXP(T) = e:
  • If LCHILD(T) = null and Schild = null, set COEFF(T) \leftarrow COEFF(T) + c.
  • If LCHILD(T) \neq null or Schild \neq null, recursively merge the subtrees:

$$ LCHILD(T) \leftarrow \text{ADD_TREES}(LCHILD(T), Schild) $$ 3. Otherwise, insert S at the correct exponent position in R (maintaining order).

T7. [Continue traversal.]

Repeat T4–T6 for all nodes of Q. Repeat T3–T6 for all nodes of P.

T8. [Return result.]

Return R as the root of the product polynomial.

3. Auxiliary procedure: ADD_TREES

The procedure

$$ \text{ADD_TREES}(A, B) $$

merges two trees representing polynomials in canonical form:

  1. If A = null, return B.
  2. If B = null, return A.
  3. Compare the EXP of the roots A and B:

  • If EXP(A) < EXP(B), set RLINK(A) <- ADD_TREES(RLINK(A), B) and return A.

  • If EXP(A) > EXP(B), set RLINK(B) <- ADD_TREES(A, RLINK(B)) and return B.

  • If EXP(A) = EXP(B):

  • Sum the coefficients: COEFF(A) <- COEFF(A) + COEFF(B).

  • Recursively merge children: LCHILD(A) <- ADD_TREES(LCHILD(A), LCHILD(B)).

  • Recursively merge siblings: RLINK(A) <- ADD_TREES(RLINK(A), RLINK(B)).

  • Return A.

This ensures that like terms at all levels are combined and canonical order is preserved.

4. Correctness argument

  1. Structural correctness:
  • Each node S is created with its coefficient, exponent, and subtree corresponding to the product of Pnode and Qnode.
  • The tree R is constructed by inserting nodes in exponent order and merging like terms recursively.
  • Therefore, R satisfies all invariants of the linked-tree representation of Fig. 28.
  1. Correctness of multiplication:
  • Every pair (Pnode, Qnode) is multiplied exactly once.
  • For nodes with subtrees, the recursive call MULT(Pchild, Qchild) correctly computes the product of sub-polynomials.
  • By induction on the depth of the tree, all coefficients and exponents are computed according to the distributive law for generalized polynomials.
  1. Combining like terms:
  • The ADD_TREES procedure ensures that nodes with the same exponent at any level are merged.
  • Zero coefficients can optionally be removed during insertion if desired, but the algorithm preserves them if required.
  1. Termination:
  • Each traversal of RLINK and recursive multiplication eventually reaches null nodes.
  • Depth of recursion is bounded by the maximum depth of the input trees.
  • Therefore, the algorithm terminates.
  1. Space and time complexity:
  • Let |P| and |Q| denote the number of nodes in the input trees.
  • In the worst case, the product has up to |P|*|Q| nodes before merging.
  • Recursive multiplication and tree insertion may take O(|P|*|Q|) time for sparse polynomials; merging subtrees incurs additional recursion proportional to subtree sizes.

5. Remarks

  • The algorithm is fully recursive and handles nested polynomial structures, unlike the previous flawed solution, which assumed flat monomials.
  • By using ADD_TREES, the algorithm preserves canonical form and merges like terms at all levels.
  • Zero-coefficient nodes may be retained or pruned according to the application.
  • This procedure generalizes naturally to multi-variable polynomials represented as trees with multiple variables corresponding to different levels.

$$ \boxed{R = \text{MULT}(P, Q) \text{ is the root of the product polynomial in linked-tree form}} $$