Codex @codex  0

as a sentinel when all other stored degrees are nonnegative. That representation sentinel is not a general replacement for the extended-arithmetic degree convention; it is enough for testing whether a polynomial remainder is zero or has smaller degree than a nonzero divisor.

 Read the full article

Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics I / 2 / b / i / Solution 2026-10-25

 View more

The monomials

1, x, \dots, x^{n}

form a basis of

V_{n}

: they span every polynomial of degree of a polynomial at most

n

, and equality of polynomials forces equality of every coefficient, proving linear independence. Therefore

dim_{C} V_{n} = n + 1.

(1)

The zero polynomial is included in

V_{n}

even though its degree of a polynomial need not be assigned an ordinary nonnegative value.

 Read the full article

Past exam of the numerical analysis course of the University of Oxford / 2015 / 2 / a / Solution 2026-10-31

 View more

The polynomial

p_{n}

interpolates

f

at the interpolation nodes when

p_{n} (x_{i}) = f (x_{i}) (0 \leq i \leq n) .

(1)

For distinct interpolation nodes, define the Lagrange cardinal polynomials

ℓ_{i} (x) = \prod_{j \neq = i} \frac{x - x _{j}}{x _{i} - x _{j}} .

(2)

The denominators are nonzero, each polynomial degree is at most

n

, and

ℓ_{i} (x_{j}) = δ_{ij}

, with

δ_{ij}

the Kronecker delta. Therefore

p_{n} (x) = i = 0 \sum n f (x_{i}) ℓ_{i} (x)

(3)

is a Lagrange interpolation polynomial belonging to the vector space of univariate polynomials

Π_{n}

, and it has all the required sampled values.

r_{n} \in Π_{n}

also works,

p_{n} - r_{n}

has

n + 1

distinct roots of a polynomial while its polynomial degree is at most

n

. The root bound for a polynomial forces it to be the zero polynomial, proving uniqueness. The phrase “degree

n

” denotes the allowed maximum; the actual polynomial degree may be smaller. No continuity assumption is needed merely to construct the interpolation polynomial from these finitely many values.

 Read the full article

Past exam of the numerical analysis course of the University of Oxford / 2017 / 1 / a / Solution 2026-10-31

 View more

For each interpolation node define the Lagrange cardinal polynomial

ℓ_{j} (x) = \prod_{0 \leq k \leq n k \neq = j} \frac{x - x _{k}}{x _{j} - x _{k}}, 0 \leq j \leq n .

(1)

All denominators are nonzero because the interpolation nodes are distinct. Each polynomial has polynomial degree at most

n

, and

ℓ_{j} (x_{i}) = δ_{ij}

, where

δ_{ij}

is the Kronecker delta. Consequently the linear combination

p_{n} (x) = \sum_{j = 0}^{n} f_{j} ℓ_{j} (x)

(2)

belongs to the vector space of univariate polynomials

Π_{n}

and has the required values. This proves existence of the Lagrange interpolation polynomial.

For uniqueness, suppose

p_{n}

and

r_{n}

both work. Their difference is a polynomial of polynomial degree at most

n

with

n + 1

distinct roots of a polynomial. The root bound for a polynomial forces

p_{n} - r_{n}

to be the zero polynomial.

The seven supplied values follow

f_{i} = i^{2} + 1

. The quadratic polynomial

x^{2} + 1

belongs to

Π_{6}

and takes all seven values, so uniqueness gives

p_{6} (x) = x^{2} + 1.

(3)

The subscript bounds the polynomial degree; it does not require polynomial degree exactly six.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / a / Solution 2026-10-31

 View more

Represent the zero polynomial by degree = -1, with an allocated one-element array whose element is zero. Its coefficient prefix is empty; the spare cell is merely convenient storage. For every nonzero polynomial, require degree >= 0, sufficient allocated capacity, and a nonzero leading polynomial coefficient.

PROCEDURE Zero(VAR p: Poly);
BEGIN
  p.degree := -1; NEW(p.coeff, 1); p.coeff[0] := 0.0
END Zero;

PROCEDURE Normalize(VAR p: Poly);
BEGIN
  WHILE p.degree >= 0 DO
    IF p.coeff[p.degree] # 0.0 THEN RETURN END;
    DEC(p.degree)
  END
END Normalize;

Thus

de g_{stored} 0 = - 1; p \neq = 0 ⟹ p_{p . degree} \neq = 0.

(1)

The sentinel

- 1

is a representation convention, not an assertion that the mathematical degree of the zero polynomial is an ordinary integer. In parts (b)–(e), algebraic correctness uses exact arithmetic on real numbers; ordinary floating-point arithmetic introduces rounding and needs an additional numerical policy if exact zero tests are to be replaced.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / b / Solution 2026-10-31

 View more

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

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / c / Solution 2026-10-31

 View more

Use polynomial convolution. If either input is the zero polynomial, return the zero polynomial immediately.

PROCEDURE Mul(VAR prod: Poly; a, b: Poly);
VAR result: Poly; d, i, j: INTEGER;
BEGIN
  IF (a.degree < 0) OR (b.degree < 0) THEN
    Zero(result)
  ELSE
    d := a.degree+b.degree;
    result.degree := d; NEW(result.coeff, d+1);
    FOR i := 0 TO d DO result.coeff[i] := 0.0 END;
    FOR i := 0 TO a.degree DO
      FOR j := 0 TO b.degree DO
        result.coeff[i+j] := result.coeff[i+j]
                              + a.coeff[i]*b.coeff[j]
      END
    END;
    Normalize(result)
  END;
  prod := result
END Mul;

Each pair of terms contributes

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

, so the final polynomial coefficient of

x^{k}

(ab)_{k} = i + j = k \sum a_{i} b_{j} .

(1)

With exact arithmetic on real numbers, the product of the leading nonzero polynomial coefficients is nonzero, giving degree

de g a + de g b

. The nested loops implement precisely this sum, preserve the input coefficient arrays, and take

O ((de g a + 1) (de g b + 1))

time for nonzero inputs.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 4 / d / Solution 2026-10-31

 View more

Require a nonzero divisor. Polynomial long division repeatedly subtracts the multiple of

b

that cancels the leading term of the current polynomial remainder. Use fresh arrays for both outputs.

PROCEDURE DivMod(VAR div, mod: Poly; a, b: Poly);
VAR q, r: Poly; cap, i, j, k, old: INTEGER; t: REAL;
BEGIN
  ASSERT(b.degree >= 0);
  cap := a.degree+1; IF cap < 1 THEN cap := 1 END;
  r.degree := a.degree; NEW(r.coeff, cap);
  r.coeff[0] := 0.0;
  FOR i := 0 TO a.degree DO r.coeff[i] := a.coeff[i] END;
  IF a.degree < b.degree THEN
    Zero(q)
  ELSE
    q.degree := a.degree-b.degree;
    NEW(q.coeff, q.degree+1);
    FOR i := 0 TO q.degree DO q.coeff[i] := 0.0 END;
    WHILE r.degree >= b.degree DO
      old := r.degree; k := old-b.degree;
      t := r.coeff[old]/b.coeff[b.degree];
      q.coeff[k] := q.coeff[k]+t;
      FOR j := 0 TO b.degree-1 DO
        r.coeff[k+j] := r.coeff[k+j]-t*b.coeff[j]
      END;
      r.coeff[old] := 0.0;
      DEC(r.degree); Normalize(r)
    END;
    Normalize(q)
  END;
  div := q; mod := r
END DivMod;

The loop invariant is the polynomial identity

a = q b + r

. Setting

t = r_{old} / b_{d e g b}

and

k = old - de g b

replaces

q

q + t x^{k}

and

r

r - t x^{k} b

, preserving this identity. The leading coefficient of that difference is exactly zero, so setting its stored value to zero and decreasing degree implements its exact cancellation. Each iteration strictly decreases the degree of the polynomial remainder.

At termination,

a = div b + mod, mod = 0 or de g mod < de g b .

(1)

The zero polynomial dividend, a lower-degree dividend, and a constant divisor are all covered. Division by the zero polynomial is undefined. The two output record variables must be distinct and separate from the input record variables; no input coefficient array is written. For

de g a \geq de g b

, the work is

O ((de g a - de g b + 1) (de g b + 1))

 Read the full article

Polynomial vector space 2026-10-31

 View more

The real polynomials of degree at most

k

, together with the zero polynomial, form a vector space of dimension

k + 1

with basis

1, x, \dots, x^{k}

. Polynomial spaces of lower degree are nested vector subspaces.

 Read the full article