 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2005/functional-programming-data-structures-and-algorithms-procedural-programming-and-digital-hardware/8/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 8 / b / Solution by

Codex  0 2026-10-31

Add polynomials by adding equal-power coefficients, interpreting a missing coefficient as zero. Compute into a local record before assigning the output, so the result may safely be the same actual record as either input.

PROCEDURE Add(VAR p, q, result: Polynomial);
  VAR t: Polynomial; i: INTEGER; u, v: REAL;
BEGIN
  t.len := p.len;
  IF q.len > t.len THEN t.len := q.len END;
  i := 0;
  WHILE i < t.len DO
    u := 0.0; v := 0.0;
    IF i < p.len THEN u := p.coeff[i] END;
    IF i < q.len THEN v := q.coeff[i] END;
    t.coeff[i] := u+v;
    i := i+1
  END;
  result := t
END Add;

With

L = max (p . len, q . len)

, the loop invariant is

0 \leq i \leq L

and, for

0 \leq k < i

, t.coeff[k] is the sum of the two extended input coefficients at

k

. The loop variant is

L - i

. The inputs remain unchanged throughout the loop, and at exit every active coefficient is correct. The time complexity is

O (L)

for the active arithmetic; assigning the fixed-capacity record can additionally copy its full capacity.

For the product, each pair of input terms contributes

a_{i} b_{j} x^{i + j}

. Initialize the active result to zero, then accumulate these pairwise contributions:

PROCEDURE Multiply(VAR p, q, result: Polynomial);
  VAR t: Polynomial; i, j, k: INTEGER;
BEGIN
  t.len := 0;
  IF (p.len > 0) & (q.len > 0) THEN
    t.len := p.len + q.len - 1
  END;
  (* Precondition: t.len <= Capacity. *)
  k := 0;
  WHILE k < t.len DO
    t.coeff[k] := 0.0; k := k+1
  END;
  IF t.len > 0 THEN
    i := 0;
    WHILE i < p.len DO
      j := 0;
      WHILE j < q.len DO
        t.coeff[i+j] := t.coeff[i+j]
                          + p.coeff[i]*q.coeff[j];
        j := j+1
      END;
      i := i+1
    END
  END;
  result := t
END Multiply;

The input representation invariants and the capacity precondition are assumed. No coefficient is accessed when either input is the zero polynomial. The initialization loop invariant says coefficients below

k

are zero; its loop variant is t.len-k.

For positive input lengths

m, n

, the outer loop invariant says that

0 \leq i \leq m

and each coefficient

t_{k}

equals

\sum_{0 \leq u < i} \sum_{0 \leq v < n u + v = k} a_{u} b_{v} .

(1)

The inner loop invariant adds the contributions with

u = i

and

0 \leq v < j

to that sum, while

0 \leq j \leq n

. The update adds exactly the next missing term at index

i + j

, preserving the inner loop invariant. The loop variants are

m - i

for the outer loop and

n - j

for the inner loop. On exit all pairs have contributed, yielding

(p + q)_{k} = a_{k} + b_{k}, (pq)_{k} = i + j = k \sum a_{i} b_{j} .

(2)

The product uses

O (mn + m + n)

arithmetic operations and a temporary coefficient array of capacity Capacity. Both operations allow trailing zeros; no extra normalization loop is required. Only the active coefficients are meaningful, so inactive record entries are never read by these operations. As in part (a), floating-point coefficients implement these formulas subject to rounding.

 Read the full article

 New to topics? Read the docs here!