TAOCP 2.2.4 Exercise 9
Algorithm `A` does **not** work properly when `P = Q`.
Exercise 9. [23] Would Algorithm A work properly if P = Q (i.e., both pointer variables point at the same polynomial)? Would Algorithm M work properly if P = M, if P = Q, or if M = Q?
Verified: no
Solve time: 5m33s
Solution
Algorithm A does not work properly when P = Q.
At step A1, both variables are advanced:
$$ P \leftarrow LINK(P), \qquad Q \leftarrow LINK(Q). $$
Since initially $P=Q$, they continue to point to the same node. Therefore every comparison in step A2 yields
$$ ABC(P)=ABC(Q). $$
Execution always proceeds to step A3. There the assignment
$$ COEF(Q)\leftarrow COEF(Q)+COEF(P) $$
becomes
$$ COEF(P)\leftarrow 2,COEF(P), $$
because $P$ and $Q$ designate the same node. Hence every coefficient is doubled.
If a coefficient happens to be zero after doubling, step A4 deletes the corresponding node. Since the algorithm is simultaneously traversing the same list through both variables, the intended interpretation of one polynomial remaining unchanged while the other receives the sum is violated. The result is that the single polynomial is transformed into $2P$, not into $P+Q$ with $P$ preserved. Therefore Algorithm A is not correct for the case $P=Q$.
For Algorithm M, consider the three possible coincidences of pointer variables.
If $P=M$, the algorithm cannot work properly. Algorithm M uses the polynomial designated by $P$ as one multiplicand while building the product in the polynomial designated by $M$. During the computation, terms are inserted into and deleted from $M$. If $P$ and $M$ are the same polynomial, the multiplicand is altered while it is still being scanned. Consequently the algorithm no longer processes the original polynomial $P$, and the required multiplication is not performed correctly.
If $M=Q$, the same difficulty occurs. The polynomial designated by $Q$ serves as the second multiplicand, while $M$ is modified to accumulate the product. When $M$ and $Q$ are identical, changes made to the accumulating product simultaneously change one of the multiplicands. The algorithm therefore loses access to the original polynomial $Q$, so it is incorrect.
If $P=Q$, Algorithm M does work properly. The algorithm only reads the multiplicands $P$ and $Q$; it does not modify them. The same polynomial may therefore serve as both multiplicands. In that case the computation simply forms the square of the polynomial,
$$ P\cdot P. $$
Since neither traversal interferes with the other and the modifications are confined to $M$, no inconsistency arises.
Hence:
$$ \boxed{\begin{array}{c|c} \text{Case} & \text{Algorithm M correct?}\ \hline P=M & \text{No}\ P=Q & \text{Yes}\ M=Q & \text{No} \end{array}} $$
and Algorithm A is not correct when $P=Q$. ∎