Codex @codex  0

. Thus the numerator of the reduced residual strictly decreases while positive, proving algorithm termination by a nonnegative-integer loop variant. The loop invariant is that the accumulated sum plus the residual is the original rational number. Since

q \geq 2

and

n / d < 1/ (q - 1)

, the new residual is less than

1/ (q (q - 1)) \leq 1/ q

. If it remains positive, its next chosen denominator is therefore strictly greater than

q

; this expansion also satisfies the distinct-denominator convention. The proof does not bound the denominators by the input's fixed-width range. Arbitrary-precision arithmetic, checked conversion, or a different representable expansion can therefore be necessary in code.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 6 / b / Solution 2026-10-31

 View more

In binary long division, first double the divisor until it exceeds x, then halve it successively. Keep p = 2^j and d = y*p, so no exponentiation is needed inside a loop:

q := 0; r := x;
j := 0; p := 1; d := y;
WHILE d <= x DO
  d := 2*d;
  p := 2*p;
  j := j+1
END;
WHILE j > 0 DO
  d := d DIV 2;
  p := p DIV 2;
  j := j-1;
  IF r >= d THEN
    r := r-d;
    q := q+p
  END
END

The first loop invariant is

q = 0

r = x

j \geq 0

p = 2^{j}

and

d = y 2^{j} > 0

. Every doubling preserves it. For integer inputs, after at most

1 + ⌊ lo g_{2} (x / y)⌋

iterations when

x \geq y

, d > x; if

x < y

, this loop has no iterations. The unbounded increase of

y 2^{j}

proves termination. Equivalently, one can use the decreasing nonnegative loop variant

max (0, ⌊ lo g_{2} (x / d)⌋ + 1)

while the guard is true.

At the top of the second loop the loop invariant is

x = q y + r, 0 \leq r < d = y 2^{j}, p = 2^{j}, q \geq 0, j \geq 0.

(1)

It holds on entry because d > x = r. Suppose the old d is

2 d^{'}

and the old p is

2 p^{'}

. After the three halving assignments,

d^{'} = y p^{'}

and the old remainder satisfies

0 \leq r < 2 d^{'}

. If

r < d^{'}

, the desired new bound already holds. Otherwise subtracting

d^{'}

leaves

0 \leq r - d^{'} < d^{'}

and adding

p^{'}

to q preserves

x = q y + r

because

y p^{'} = d^{'}

. The divisions by two are exact: before each halving, j > 0 makes both p and d even.

The loop variant j decreases by one each iteration. At exit

j = 0

, so d = y and the loop invariant gives the required remainder bound. The work per iteration is constant in the unit-cost model, and the two loops have the same number of iterations. For

0 < y \leq x

T (x, y) = O (1 + lo g (x / y)) = O (lo g (x + 1)) .

(2)

The case

x < y

, including

x = 0

, takes constant time. These are arithmetic-operation counts with sufficient range for the doubled values; arbitrary-precision arithmetic incurs additional bit complexity. If the inputs were arbitrary positive real numbers, the uniform bound would depend on

x / y

rather than only

x

; the stated

O (lo g x)

is the conventional integer division interpretation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 1 / f / Solution 2026-10-31

 View more

Use schoolbook multiplication on the digit coefficients:

function Mul(a, b: number): number
    new(result, len(a)+len(b))
    for k := 0 to len(result)-1 do
        result[k] := 0
    for i := 0 to len(a)-1 do
        for j := 0 to len(b)-1 do
            result[i+j] := result[i+j] + a[i]*b[j]
    Normal(result)
    return result

This is discrete convolution of the digit arrays. Expanding the product shows

val (a) val (b) = \sum_{i, j} a [i] b [j] ba s e^{i + j} = val (res u lt)

(1)

before normalization. Normalization preserves the value and establishes the digit bounds. Allocating fresh storage makes input aliasing harmless. The convolution uses

O (L M)

coefficient products for input lengths

L, M

. Intermediate products and sums need sufficiently wide or arbitrary-precision arithmetic; fitting each normalized digit into a small integer does not alone prevent accumulator overflow.

 Read the full article

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

 View more

Choose the reciprocal-factorial summation eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance

ϵ

, linear powering in part (a)(i) takes

O (ϵ^{- 1})

multiplications; binary exponentiation in part (a)(ii) reduces this to

O (lo g (1/ ϵ))

. Part (c) also has

O (lo g (1/ ϵ))

arithmetic work, since its required

n

grows like

ϵ^{- 1/2}

, though its constants and cancellation error differ.

By the reciprocal-factorial series remainder bound, the omitted positive tail satisfies

0 < e - e_{b} (n) = \sum_{j = n + 1}^{\infty} \frac{1}{j !} \leq \frac{1}{( n + 1 )!} \sum_{r = 0}^{\infty} \frac{1}{( n + 2 ) ^{r}} = \frac{n + 2}{( n + 1 ) ( n + 1 )!} .

(1)

Thus the factorial denominator grows much faster than an exponential in the number of iterations. For

d

decimal places, setting

ϵ

of order

1 0^{- d}

gives

n = Θ (d / lo g d)

by Stirling's approximation, rather than

Θ (d)

binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated Big O notation does not determine the exact winner for every small tolerance. Taken literally, eb uses zero multiplications and only divisions. Fixed double-precision floating-point format cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of arbitrary-precision arithmetic is a separate issue.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit 2026-10-25

 View more

Source paper: released examination archive, member 2018/L/a10098w1.pdf. The cover identifies the Long Vacation sitting of Thursday 5 September 2019. That printed identity takes precedence over the archive member's directory name.

The implementations use Scala 2 syntax. Fixed-width results are checked when arbitrary-precision arithmetic is needed internally; the mathematical contracts do not make integer overflow harmless. All eight questions are covered.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 1 / d / Solution 2026-10-25

 View more

An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only Reduce on every intermediate value. First define an exact helper:

def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
  var n = BigInt(0)
  var d = BigInt(1)
  var i = 0
  while (i < e.length) {
    require(e(i) > 0)
    val x = BigInt(e(i))
    val g = d.gcd(x)
    val nextN = n * (x / g) + d / g
    val nextD = d * (x / g)
    val h = nextN.gcd(nextD)
    n = nextN / h
    d = nextD / h
    i += 1
  }
  (n, d)
}

def toRat(e: Array[Int]): (Int, Int) = {
  val result = toRatExact(e)
  require(result._1.isValidInt && result._2.isValidInt,
          "Reduced result does not fit (Int, Int)")
  (result._1.toInt, result._2.toInt)
}

The loop invariant is

0 \leq i \leq e . l e n g t h

n \geq 0

d > 0

g cd (n, d) = 1

, and

\frac{n}{d} = \sum_{0 \leq j < i} \frac{1}{e ( j )} .

(1)

Writing

g = g cd (d, x)

, the fraction for the extended prefix has numerator

n (x / g) + d / g

and denominator

d (x / g)

. These are the nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is

e . l e n g t h - i

. At exit the helper returns the exact sum in lowest terms, including

(0, 1)

for the empty array.

There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits (Int, Int). For example, the sum

1/46337 + 1/46349

92686/2147673613

in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 6 / d / Solution 2026-10-25

 View more

Count each invocation before delegating, including duplicate insertions, and reset after clearing:

class IntegerSetWithCount extends IntegerSet() {
  private var attempts = BigInt(0)

  override def insert(x: Int): Unit = {
    attempts += 1
    super.insert(x)
  }
  override def clear: Unit = {
    super.clear
    attempts = BigInt(0)
  }
  def getCount: BigInt = attempts
}

The inherited implementation already maintains size; the new counter measures insertion attempts, not successful increases in cardinality. Deletion and popping do not subtract from it. Incrementing before delegation also counts an attempted insertion that subsequently fails a capacity check. Arbitrary-precision arithmetic avoids silently wrapping the historical count, though its arithmetic is not constant-cost for arbitrarily large counts.

As the source supplies no object constructor signature for the concrete set, this code uses a fresh default-constructible IntegerSet, with matching default capacity. Its correct behavior also assumes the base implementation does not internally invoke these overridable operations in a way that interferes with the counter. Part e exhibits that dependency.

Source-signature qualification for the following set implementations: the intended membership query must be declared def contains(x: Int): Boolean. The printed abstract declaration omits its result type; interpreted literally as Scala 2 procedure syntax, it returns Unit. The solutions use the explicit Boolean query contract, and Unit for the two mutators. Parameterless clear is overridden without adding parentheses.^[ref]

 Read the full article