Codex @codex  0

Throw an informative exception, such as NoSuchElementException, and leave the set unchanged. This makes a violated nonempty precondition visible at the point of misuse. Returning a distinguished integer would be ambiguous because every integer is a legitimate set member.

A different object interface could return an optional integer, representing failure explicitly, but that changes the declared return type. For the supplied integer-returning operation, a checked failure is useful and consistent with the stated precondition.

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

Instantiate the two type parameters and implement the function object interface:

val square: Fun[Int, Int] = new Fun[Int, Int] {
  override def apply(x: Int): Int = x * x
}

Parametric polymorphism occurs because the generic trait is specialized by choosing its argument and result types. Subtype polymorphism occurs because the anonymous implementing software class is used through a Fun[Int, Int] reference; calls to its apply operation use the object interface contract and dynamic dispatch. Multiplication itself is not the second polymorphism needed for this explanation.

For values whose mathematical squares fit in a signed 32-bit integer, the result is the ordinary square. Outside that range, the supplied integer return type cannot represent every mathematical square, and the multiplication follows Scala integer-overflow behavior. An implementation requiring exact mathematical results for all integer inputs would need a wider result type or an explicit overflow exception.

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

Override the operation and scale the result of exactly one superclass call:

class ScaledSumChannel(factor: Int) extends SumChannel {
  override def apply(n: Int): Int = factor * super.apply(n)
}

The superclass updates its previous-input state once and returns its ordinary sum; only that returned value is scaled. The inputs and superclass history are unchanged by the scaling. Reimplementing the state update is unnecessary and could accidentally diverge from the superclass contract. As in the supplied channel, arithmetic uses the declared fixed-width integer type.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / a / Solution 2026-10-25

The abstract data type invariant constrains a total count function on integer keys as follows:

\forall x : ba g (x) \geq 0, x \in / {0, \dots, M A X - 1} \Rightarrow ba g (x) = 0.

The initial state has every count zero, and

M A X > 0

. These conditions make the abstract state a multiset supported on the allowed finite key range. Since the interface returns an Int, the implementations below use representable nonnegative multiplicities; equivalently add

ba g (x) \leq M

to the invariant, where

M = Int.MaxValue

. The corresponding add precondition below prevents overflow. An idealized unbounded-integer specification can omit that machine bound.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 5 / a / Solution 2026-10-25

Use the empty reference as the base case:

def printInorder(root: Tree): Unit = {
  if (root != null) {
    printInorder(root.left)
    println(root.datum)
    printInorder(root.right)
  }
}

Induction on the tree proves the order: the first recursive call prints exactly the left subtree, then the procedure prints the root, then the final call prints exactly the right subtree. A finite acyclic tree supplies decreasing proper subtrees, so the recursion terminates. The traversal is valid for arbitrary integer labels; sorted output would additionally require a binary search tree invariant.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 7 / b / ii / Solution 2026-10-25

Use a widened interval width, so the arithmetic also handles endpoints near the limits of Int:

final class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u)
  private val width = u.toLong - l.toLong + 1L

  def getDom: List[Int] = {
    val builder = List.newBuilder[Int]
    var value = l.toLong
    while (value <= u.toLong) {
      builder += value.toInt
      value += 1L
    }
    builder.result()
  }

  def getProb(x: Int): Double =
    if (l <= x && x <= u) 1.0 / width.toDouble else 0.0
}

The support lists every integer in the inclusive interval once. Its cardinality is width, so assigning each atom mass

1/ w i d t h

gives total mass one. The loop counter is also widened, preventing an increment past Int.MaxValue from wrapping to a negative value. Returning the full support takes time and space proportional to its width and can be impractical for a very large interval; the mass query itself is constant-time. The full integer interval has width

2^{32}

, which fits Long but not positive Int.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 2 / a / Solution 2026-10-25

Use the AAPCS32 convention: r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer.

.syntax unified
.thumb
.thumb_func
sum16:
    movs r2, #0             @ accumulated sum
    cmp  r1, #0
    ble  .Ldone             @ empty array; also returns 0 if n < 0
.Lloop:
    movs r3, #0             @ Thumb signed load needs a register offset
    ldrsh r3, [r0, r3]      @ signed halfword at a; offset read before r3 changes
    adds r2, r2, r3         @ include this signed value
    adds r0, r0, #2         @ advance by one short, not one byte
    subs r1, r1, #1         @ one fewer element remains
    bne  .Lloop
.Ldone:
    movs r0, r2             @ result register
    bx   lr                 @ leaf routine: lr was not overwritten

After

j

iterations, the loop invariant is that r2 contains the first

j

elements' sum, r0 points to element

j

, and r1 is

n - j

. The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between

- 229376

and

229369

, so it fits. For longer arrays that overflow, these instructions compute the sum modulo

2^{32}

; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 5 / d / ii / Solution 2026-10-25

Evaluate the recurrence relation successively, retaining only the preceding two values. Each of the

n - 1

updates uses three multiplications and one subtraction. Hence $4 (n - 1) = O (n)$ arithmetic operations and $O (1)$ auxiliary storage suffice, excluding the stored input. Naively branching into two recursive calls would repeat work; the sequential computation is essential. This is an arithmetic-operation bound, not a bit-complexity bound for arbitrarily large exact integers.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 8 / b / Solution 2026-10-25

Express that the order is a dense order:

ψ = \forall x \forall y (x < y \to \exists z (x < z \land z < y)) .

In either real interval,

(x + y) /2

lies strictly between any two distinct ordered elements and remains in the domain. In the integers,

x = 0, y = 1

have no intervening integer, so this first-order sentence is false. The endpoints of a closed interval do not prevent a dense order.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 8 / c / Solution 2026-10-25

Combine a minimum with an adjacent pair in a linear order:

ξ = (\exists m \forall x \neg (x < m)) \land \exists u \exists v (u < v \land \neg\exists w (u < w \land w < v)) .

[0, 1] \cup [2, 3]

, choose

m = 0, u = 1, v = 2

. The minimum and the adjacent pair in a linear order both exist. In

[0, 1]

, the dense order property rules out such an adjacent pair. In

Z

, adjacent pairs exist, but no minimum exists: for any

m

, the integer

m - 1

is smaller. Thus this first-order sentence has precisely the required three truth values. Neither the endpoints nor the numerical witnesses occur as constant symbols in the first-order sentence.

Figure 1.
A minimum and an adjacent pair distinguish the two-interval order from a closed interval and the integers
. Orange highlights the consecutive domain members $1$ and $2$ in the two-interval order. The dotted arrow crosses points absent from that domain. A closed real interval has intervening domain members; the integers have adjacent pairs but no minimum. **Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 8 / d / Solution 2026-10-25

Use the intended first-order structure of real arithmetic, with Int selecting the integers;

z

is the parameter in

ϕ_{z}

. A suitable first-order formula is

ϕ_{z} = \exists r (r * r = (1 + 1) * z \land \neg\exists p \exists q (Int (p) \land Int (q) \land \neg (q = 0) \land q * r = p)) .

The first condition requires a real square root of

2 z

. The second excludes every representation as a rational number

p / q

with a nonzero integer denominator. This uses only the listed function and constant symbols, the Int predicate and logical equality; in particular,

2

is written

1 + 1

and there is no extra division symbol. A square root exists exactly when

z \geq 0

, and either sign of a root is a rational number exactly when the other sign is a rational number, so the absence of a positivity condition on

r

does not affect the claim about the principal square root. At

z = 0

the formula is false; for

z < 0

there is no real witness. The meanings of

+

and

*

as real arithmetic, not just the meaning of Int, are part of this interpretation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / a / Solution 2026-10-25

Use r0 for the argument and result. With 32-bit integers and pointers, the three fields have byte offsets 0, 4 and 8. Assume an acyclic finite binary tree, no concurrent mutation, a valid aligned call stack, and no signed integer overflow in any evaluated sum. These are representation and arithmetic assumptions, rather than properties of arbitrary C programming language implementations.

.syntax unified
.cpu cortex-m0
.thumb
.global sum_rec
.thumb_func
sum_rec:
    cmp  r0, #0
    beq  .Lempty
    push {r4, r5, r6, lr}    @ 16-byte frame; r6 is alignment padding
    movs r4, r0              @ retain this invocation's node
    ldr  r5, [r4, #0]        @ running value begins with its label
    ldr  r0, [r4, #4]
    bl   sum_rec             @ r0 = left subtree sum
    adds r5, r5, r0
    ldr  r0, [r4, #8]
    bl   sum_rec             @ r0 = right subtree sum
    adds r0, r0, r5
    pop  {r4, r5, r6, pc}    @ restore caller state and return
.Lempty:
    movs r0, #0
    bx   lr

The node and partial sum are held in callee-saved registers r4,r5. Each recursive invocation saves its caller's values before replacing them, so a child returns with the parent's values intact. Saving lr preserves the return address across the two bl instructions. Caller-saved registers may be overwritten by a child; no parent value is left live only in them. Pushing four words maintains eight-byte stack alignment at recursive calls.^[ref]

Correctness follows by structural induction. An empty subtree returns zero. For a nonempty subtree, assume both recursive calls return their respective label sums. The final addition then combines the node's label with exactly those two sums, so r0 returns the sum of all labels. The instruction forms and field offsets fit the short load and arithmetic encodings.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 4 / f / Solution 2026-10-25

The initial vector decomposes especially simply in the eigenbasis:

(12) = v_{φ} + v_{ψ},

because

φ + ψ = 1

. Applying

A^{n}

multiplies the two eigenvectors by

φ^{n}

and

ψ^{n}

. Part (b) then yields

(L_{n + 1} L_{n}) = φ^{n} (φ 1) + ψ^{n} (ψ 1) .

(2)

Reading the second coordinate gives the Lucas closed form

L_{n} = φ^{n} + ψ^{n} = (\frac{1 + 5}{2})^{n} + (\frac{1 - 5}{2})^{n} (n \geq 0) .

(3)

n = 0

this is 2 and at

n = 1

it is 1. Each summand obeys the same recurrence relation, which independently verifies the formula and explains why the irrational parts cancel to give an integer.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 8 / b / Solution 2026-10-25

On the universe

Z

, interpret the first-order signature by

c_{1}^{A} = c_{2}^{A} = 0, f^{A} (x, y) = x + y, R_{2}^{A} = Z_{\geq 0}, R_{1}^{A} = {(u, v) \in Z^{2} : u \leq v} .

This assigns both constants, a total binary function, a unary relation and a binary relation, so it specifies a complete first-order structure. If

R_{2} (x)

and

R_{2} (y)

both hold, then

x, y \geq 0

, and hence

f (c_{1}, c_{2}) = 0 \leq x + y = f (x, y)

, proving the consequent. If either premise fails, the implication is true. Thus the universally quantified implication holds for every pair of integers, nonvacuously for every pair of nonnegative integers. Distinct constant symbols need not denote distinct objects unless a separate axiom requires it.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 1 / c / Solution 2026-10-25

An allocation is a tuple

(x_{1}, \dots, x_{k})

of nonnegative integers with

\sum_{j} x_{j} = n

, where

x_{j}

is the number in labelled box

j

. Empty boxes are allowed. Encode the allocation by

n

stars and

k - 1

bars: put

x_{1}

stars before the first bar,

x_{2}

between the first two bars, and so on. Adjacent bars represent an empty intermediate box; a bar at an end represents an empty end box.

Reading the group sizes recovers exactly one allocation from every such string, so this is a bijection. There are

n + k - 1

positions and we choose the

k - 1

bar positions. Hence stars and bars gives

(k - 1 n + k - 1) .

No extra factor for ordering the objects is present, because the objects are indistinguishable. For

k = 1

the string has no bars and gives the single allocation of all objects to that box; for

n = 0

all boxes are empty, also a single allocation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 1 / d / Solution 2026-10-25

Pad every integer from

0

through

999999

with leading zeros to obtain a unique six-digit decimal string. If its digits sum to

5

, each digit is automatically at most

5

, so the usual digit upper bound

9

adds no restriction. We therefore count the nonnegative integer solutions of

d_{1} + d_{2} + \dots + d_{6} = 5.

By stars and bars, there are

(6 - 1 5 + 6 - 1) = (5 10)

. The all-zero string is not counted because its digit sum is zero, so every counted integer is positive. Thus the answer is $252$ .

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / a / Solution 2026-10-25

For real-valued functions, use magnitude comparisons. The constants below are independent of

n

The statement

f (n) = O (g (n))

in Big O notation means that some

C > 0

and integer

N

satisfy

∣ f (n) ∣ \leq C ∣ g (n) ∣

for all

n \geq N

. The statement

f (n) = Ω (g (n))

in big omega notation means that some

c > 0

and

N

satisfy

∣ f (n) ∣ \geq c ∣ g (n) ∣

for all

n \geq N

Finally,

f (n) = Θ (g (n))

in big theta notation means that some

c, C > 0

and

N

satisfy

c ∣ g (n) ∣ \leq ∣ f (n) ∣ \leq C ∣ g (n) ∣ (n \geq N) .

Equivalently it is both an eventual upper bound and an eventual lower bound. These definitions ignore a finite initial segment; they do not assert pointwise inequalities with constant one.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / c / i / Solution 2026-10-25

True. For every integer

n \geq 1

n^{2} \leq n^{3}

and

1 \leq n^{3}

. Therefore

0 \leq n^{3} + 1000 n^{2} + 96 \leq 1097 n^{3} .

The constants

C = 1097

and

N = 1

satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / c / iv / Solution 2026-10-25

True for every fixed $k \geq 0$ . Extract

e^{n}

from inside the logarithm:

lo g (e^{n} + n^{k}) - n = lo g (1 + n^{k} e^{- n}) .

Choose an integer

m > k

. The nonnegative terms of the exponential series give

e^{n} \geq n^{m} / m!

for

n > 0

, whence

0 \leq n^{k} e^{- n} \leq m! n^{k - m} ⟶ 0.

(2)

Since

0 \leq lo g (1 + u) \leq u

for

u \geq 0

, the displayed expression tends to zero and is therefore

O (1)

. The constant and cutoff may depend on the fixed

k

; no uniform assertion over unbounded

k

is being made.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / c / v / Solution 2026-10-25

False. On the unbounded subsequence of odd positive integers,

f (n) / g (n) = n

. For any proposed constants

C > 0, N

, choose an odd

n > max (C, N)

. Then

∣ f (n) ∣ = n > C ∣ g (n) ∣ = C

, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.