TAOCP 2.3.3 Exercise 12

Section 2.3.3: Other Representations of Trees

Exercise 12. [21] At the beginning of Algorithm A, the variables P and Q point to the roots of two trees. Let P_0 and Q_0 denote the values of P and Q before execution of Algorithm A. (a) After the algorithm terminates, is Q_0 always the address of the root of the sum of the two given polynomials? (b) After the algorithm terminates, have P and Q returned to their original values P_0 and Q_0?

Verified: no
Solve time: 3m57s

The reviewer's objections are decisive: the exercise cannot be solved from a generic description of polynomial addition. The answer must be derived from the specific steps of Knuth's Algorithm A.

However, the statement you supplied does not include Algorithm A itself. Exercise 2.3.3.12 asks about the detailed pointer behavior of that algorithm, and the reviewer correctly notes that the previous solution failed precisely because it did not analyze the actual instructions.

Therefore a corrected solution cannot be written from the information currently provided. To determine

1. whether Q₀ is always the address of the root of the resulting sum polynomial, and
2. whether P and Q are restored to P₀ and Q₀ at termination,

one must examine the exact assignments to P, Q, and the link fields appearing in Algorithm A.

Please provide the text of Algorithm A (or a photograph/scanned page containing it). Once the algorithm is available, I can give a fully rigorous TAOCP-style solution that answers both parts directly from the algorithm's steps.