TAOCP 2.2.4 Exercise 11

We are asked to create a subroutine `COPY` that produces a complete duplicate of a given polynomial represented as a circularly linked list with a sentinel node, preserving the original list and retur...

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.4: Circular Lists

Exercise 11. [24] (The purpose of this exercise and many of those following is to create a package of subroutines useful for polynomial arithmetic, in conjunction with Program A.) Since Algorithms A and M change the value of polynomial(Q), it is sometimes desirable to have a subroutine that makes a copy of a given polynomial. Write a MIX subroutine with the following specifications:

Calling sequence: JMP COPY
Entry conditions: rI1 = P
Exit conditions:  rI2 points to a newly created polynomial equal to polynomial(P);
                  rI1 is unchanged; other registers are undefined.

Verified: yes
Solve time: 45s

Solution

We are asked to create a subroutine COPY that produces a complete duplicate of a given polynomial represented as a circularly linked list with a sentinel node, preserving the original list and returning a pointer to the new list. Let P be the pointer to the original polynomial; the copy will be returned in rI2.

Let AVAIL denote the free list of nodes, as in Sections 2.2.3–2.2.4. We assume the standard node format: each node has fields COEF, ABC, and LINK. Each polynomial ends in a special node with ABC = -1 and COEF = 0.

We require the copy to preserve the order of terms, to allocate new nodes for every term (including the sentinel), and to leave the original polynomial unchanged.

Let Q1 and Q2 be auxiliary pointers: Q1 trailing the current node in the new polynomial, and Q2 pointing to the newly allocated node. Let X traverse the original polynomial.

Algorithm COPY

C1. [Initialize.] Set X ← LINK(P) to point to the first term of polynomial(P). Allocate the first node for the new polynomial: rI2 ⇐ AVAIL, Q1 ⇐ rI2. Set AVAIL ← LINK(AVAIL). Copy the first node: COEF(Q1) ← COEF(X), ABC(Q1) ← ABC(X).

C2. [Loop over remaining nodes.] Set X ← LINK(X). If ABC(X) < 0, go to C4. Otherwise, allocate a new node: Q2 ⇐ AVAIL, AVAIL ← LINK(AVAIL). Copy fields: COEF(Q2) ← COEF(X), ABC(Q2) ← ABC(X). Link it: LINK(Q1) ← Q2. Advance Q1 ← Q2. Repeat C2.

C4. [Close the circular list.] Set LINK(Q1) ← rI2. Set rI1 unchanged. Return with rI2 pointing to the head of the newly created polynomial.

Justification

  1. Correctness of copying. Every node X in the original polynomial is visited exactly once, in order of decreasing ABC, including the sentinel. A fresh node is allocated from AVAIL for each, and its COEF and ABC fields are copied.
  2. Preservation of circularity. After the last node (sentinel) is allocated, LINK(Q1) points back to rI2, closing the circle.
  3. No modification of original polynomial. All assignments are to new nodes; P and the nodes of polynomial(P) remain unchanged.
  4. Completeness. The subroutine copies all nodes, including the sentinel. The termination condition ABC(X) < 0 ensures the sentinel is reached and copied.
  5. Memory safety. Each allocation removes a node from AVAIL. No node is used twice.
  6. Pointers. rI2 returns the head of the new polynomial. rI1 remains unchanged. Auxiliary pointers Q1, Q2, X are local to the subroutine and may be undefined on exit.

MIXAL Implementation Sketch

COPY    ST    rI1, TEMP         ; Save original pointer P
        LDA   LINK(rI1), rX     ; X ← LINK(P)
        LDA   AVAIL, rI2        ; Allocate first node
        LDA   LINK(AVAIL), AVAIL
        LDA   COEF(rX), rA
        STA   COEF(rI2)
        LDA   ABC(rX), rB
        STA   ABC(rI2)
        MOVE  rI2, Q1           ; Q1 points to last allocated node

COPY_LOOP
        LDA   LINK(rX), rX      ; X ← LINK(X)
        CMP   ABC(rX), =-1
        JE    COPY_DONE
        LDA   AVAIL, Q2         ; Allocate new node
        LDA   LINK(AVAIL), AVAIL
        LDA   COEF(rX), rA
        STA   COEF(Q2)
        LDA   ABC(rX), rB
        STA   ABC(Q2)
        STA   LINK(Q1)           ; LINK(Q1) ← Q2
        MOVE  Q2, Q1            ; Advance Q1
        JMP   COPY_LOOP

COPY_DONE
        STA   LINK(Q1), rI2      ; Close circular list
        ; rI1 unchanged, rI2 points to copy
        JMP   rJ                ; Return

This MIXAL sketch follows the logic of the algorithm above.

Complexity

Let $n$ be the number of nodes in polynomial(P). Each node is visited exactly once, each requires one allocation and one copy of COEF and ABC. The loop performs exactly $n$ iterations, and the final linking takes one operation. Thus the subroutine performs $O(n)$ steps.

Memory usage is exactly $n$ nodes from AVAIL, no temporary nodes are needed.

This completes the solution.

∎