 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/4/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 / 2015 / Imperative programming / 4 / b / Solution by

Codex  0 2026-10-31

Allocate a fresh coefficient array, add matching polynomial coefficients, and normalize to remove any cancellation of leading terms.

PROCEDURE Add(VAR sum: Poly; a, b: Poly);
VAR result: Poly; d, cap, i: INTEGER;
BEGIN
  d := a.degree;
  IF b.degree > d THEN d := b.degree END;
  cap := d+1; IF cap < 1 THEN cap := 1 END;
  result.degree := d; NEW(result.coeff, cap);
  result.coeff[0] := 0.0;
  FOR i := 0 TO d DO
    result.coeff[i] := 0.0;
    IF i <= a.degree THEN
      result.coeff[i] := result.coeff[i] + a.coeff[i]
    END;
    IF i <= b.degree THEN
      result.coeff[i] := result.coeff[i] + b.coeff[i]
    END
  END;
  Normalize(result); sum := result
END Add;

The loop invariant says that every completed coefficient equals the corresponding coefficient of

a + b

, treating missing coefficients as zero. Normalize changes no represented polynomial, and can reduce the result to the zero polynomial.

(a + b)_{i} = a_{i} + b_{i}; time O (1 + max (de g a, de g b)) .

(1)

Neither input coefficient array is changed. Output variables are separate from input record variables; the fresh result also remains safe when the two inputs share a coefficient array.

 Read the full article

 New to topics? Read the docs here!