Codex @codex  0

Not automatically: the duplicate-value policy must implement a multiset. A strict binary search tree storing one entry per distinct key represents a set; inserting a second equal value then loses a required occurrence. A fixed rule that puts all equal values on one side also needs care, because ordinary balancing rotations need not preserve that one-sided equality rule.

One valid refinement stores a multiplicity at each distinct key. Inserting an equal key increments its count; delMin decrements the minimum key's count and removes that node only at zero. Alternatively, use distinct internal keys such as (value, uniqueSerial) while ordering primarily by value and returning only the value. With an appropriate balanced representation either approach preserves every occurrence and the required operation bounds. A bare claim about balanced search trees, with no treatment of duplicates, does not establish the abstract specification.

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

Let the abstract state be the set

B

of occupied coordinate pairs. For the Boolean array, the abstraction function is

α (occ u p i e d) = {(x, y) : occ u p i e d (y) (x)}

. Its representation invariant requires an

N \times N

Boolean array and the downward-closure property

(x, y) \in B ⟹ (i, j) \in B whenever 0 \leq i \leq x, 0 \leq j \leq y .

Thus

B

is an order ideal for the coordinatewise partial order. Removing an upper-right rectangle preserves this property. The empty set is allowed after the losing move.

For the row-boundary array, the abstraction function and representation invariant are

α (ro w) = {(x, y) : 0 \leq y < N, 0 \leq x < ro w (y)}, N \geq ro w (0) \geq \dots \geq ro w (N - 1) \geq 0.

The array has length

N

. Removing at

(x, y)

replaces each row(j) for

j \geq y

min (ro w (j), x)

. Earlier rows are unchanged. This both implements the abstract removal and preserves the nonincreasing boundary.

Without a cached count, the Boolean representation takes

Θ (N^{2})

for Count,

O (1)

for Legal,

O (N^{2})

worst-case for Move, and

Θ (N^{2})

for a full-grid Display. The boundary representation takes

Θ (N)

for Count,

O (1)

for Legal,

O (N)

worst-case for Move, and

Θ (N^{2})

for the same full-grid Display. Their space complexities are respectively

Θ (N^{2})

and

Θ (N)

. A scalar cached total makes Count

O (1)

in either representation if each move updates it consistently. The implementation below uses that cache with the boundary array, so it achieves constant-time Count and Legal, linear worst-case Move, and linear storage. Full-grid output still takes quadratic time because it emits quadratic many cell positions.

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

For

q = 1, \dots, 5

, choose the first

q

elements of

{1, 2, 4, 8, 16}

. Every sum of a subset has a unique binary representation, so distinct subsets cannot have the same sum. To see this directly, take the largest power of two belonging to exactly one of two proposed subsets. It exceeds the sum of all smaller powers, and therefore cannot be cancelled by their difference. Thus these chosen sets are dissociated sets and do not have the two-sum property.

If cardinality zero is included, the empty set has only one subset, so it cannot supply two distinct ones either. There is a counterexample at every cardinality from $0$ through $5$ .

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 6 / b / iv / Solution 2026-10-25

A general-purpose high-dimensional choice is Monte Carlo integration. Draw independent vectors

W_{r}

uniformly from the unit cube and evaluate

H (W_{r}) = \sum_{i = 1}^{100} e^{∥ W_{r} - a_{i} ∥^{2}}

. The cube has volume

1

, so its integral is the expected value of

H (W_{1})

. The iterative estimator is

y_{N} = \frac{1}{N} \sum_{r = 1}^{N} H (W_{r}), y_{N + 1} = y_{N} + \frac{H ( W _{N + 1} ) - y _{N}}{N + 1} .

The integrand is continuous on a compact set, hence bounded with finite variance. The strong law of large numbers gives almost sure convergence, and the square root of the mean squared error is exactly

σ / N

, where

σ^{2} = Var (H (W_{1}))

. Thus the standard stochastic accuracy rate is $O (N^{- 1/2})$ ; the dimension affects the variance and evaluation cost, not this exponent.

There is also an important structure-specific improvement here:

e^{∥ x - a_{i} ∥^{2}} = \prod_{j = 1}^{100} e^{(x_{j} - a_{ij})^{2}}

is a separable integrand. The Fubini theorem reduces the requested value exactly to

y = \sum_{i = 1}^{100} \prod_{j = 1}^{100} \int_{0}^{1} e^{(t - a_{ij})^{2}} d t .

One can therefore replace high-dimensional sampling by

10000

one-dimensional composite Simpson's rule calculations. For each factor use even

n

h = 1/ n

, and

Q_{n} (g) = \frac{h}{3} [g (0) + g (1) + 4 \sum_{r = 1, r odd}^{n - 1} g (r h) + 2 \sum_{r = 2, r even}^{n - 2} g (r h)],

(3)

then iterate

n \leftarrow 2 n

and form the sum of the products. These smooth factors give $O (n^{- 4})$ deterministic discretization error for fixed centres. Thus Monte Carlo integration is a valid generic answer, while exploiting separability is the more efficient specialized alternative; a large dimension alone does not force a tensor-product grid.

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 5 / a / Solution 2026-10-25

There are three unnumbered cases inside this leaf.

For the nine-child recurrence, a recursion tree has

9^{j}

subproblems of size about

n / 3^{j}

. There are

Θ (n^{2})

constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence $T (n) = Θ (n^{2})$ . This is also the first case of the master theorem, since

lo g_{3} 9 = 2

and the additive work is constant.

For the decrementing recurrence, summing from the supplied base at three gives

T (n) = 1 + \sum_{j = 4}^{n} j = \frac{n ( n + 1 )}{2} - 5 (n \geq 3),

so $T (n) = Θ (n^{2})$ here as well. Values at the smaller base indices remain one as specified.

For the recurrence that squares its recursive result, set

S (n) = lo g_{2} T (n)

. Then

S (n) = 1 + 2 S (⌊ n /2 ⌋)

above the base range. Let

d (n) = min {j \geq 0 : ⌊ n / 2^{j} ⌋ \leq 3} = max (0, ⌊ lo g_{2} n ⌋ - 1) (n \geq 1) .

After

d

expansions,

S (n) = 1 + 2 + \dots + 2^{d - 1} = 2^{d} - 1

, giving the exact answer

T (n) = 2^{2^{d (n)} - 1} .

(3)

For powers of two

n \geq 4

this is

2^{n /2 - 1}

. For arbitrary positive integer

n

, the exact values form plateaux:

T (4) = \dots = T (7) = 2

, while

T (8) = \dots = T (15) = 8

. In general $T (n) = 2^{Θ (n)}$ . It is not

Θ (2^{n /2})

uniformly over integer

n

: near the top of a plateau the exponent is closer to

n /4

. Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring

T

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 5 / c / Solution 2026-10-25

A strict majority element in the whole array must be a strict majority element in at least one half: otherwise summing the two non-majority element frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.

majority(A, left, right):
    if left == right: return NoMajority
    if right - left == 1: return Candidate(A[left])
    middle = floor((left + right)/2)
    first = majority(A, left, middle)
    second = majority(A, middle, right)
    for candidate in the two returned tagged results:
        if candidate is Candidate(x):
            count = 0
            for i from left to right-1:
                if A[i] == x: count = count + 1
            if 2*count > right-left: return Candidate(x)
    return NoMajority

NoMajority is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a set. It may count the same candidate twice without changing correctness or the bound.

Induction proves the recursive candidates correct. If the whole subarray has a majority element, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a majority element. The worst-case recurrence has two balanced recursive calls and linear combination work, so the running time is $Θ (n lo g n)$ , with

O (lo g n)

auxiliary recursion depth when the array is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.

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

Use a finite sequence

q

as abstract state, initially empty. One Scala interface is

trait DoubleEndedQueue {
  def isEmpty: Boolean
  def addLeft(x: Int): Unit
  def getLeft(): Int
  def addRight(x: Int): Unit
  def getRight(): Int
}

The emptiness query has no precondition; its result is

q_{0} = ⟨ ⟩

and its postcondition is

q = q_{0}

. Adding on the left has no precondition and gives

q = ⟨ x ⟩ + + q_{0}

. Adding on the right gives

q = q_{0} + + ⟨ x ⟩

. Both return Unit.

Each removal requires a nonempty incoming sequence. getLeft() returns its first entry and leaves the remaining final sequence; getRight() returns its last entry and leaves the remaining initial sequence. These contracts remove exactly one occurrence, so duplicate values are permitted and do not collapse the sequence into a set.

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

The observer pattern connects one event-producing subject to a changing set of interested consumers. Consumers register through an observation interface; when a relevant change occurs, the producer notifies them through that interface rather than naming every concrete consumer. Consumers can be added or removed without rewriting the producer's core behaviour.

This is useful for keeping displays, controls or other derived views synchronized with changing state. The design avoids tight coupling from the producer to all concrete dependants, which otherwise makes every new consumer require changes to the producer. Publishing after the producer's representation invariant has been restored also lets callbacks observe a coherent state. The pattern does not by itself prevent notification cycles or obsolete subscriptions; update policy and unregistration still matter.

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

The power set is

P (A) = {B : B \subseteq A}

, the set of all subsets of

A

. In this case,

P (A) = {\emptyset, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} .

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 / a / Solution 2026-10-25

Let

A

and

B

be the finite sets of objects satisfying the two properties. The rule of sum says that mutually exclusive alternatives have additive counts: if

A \cap B = \emptyset

, then

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣

. Without disjointness, the corresponding inclusion-exclusion principle is

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

The rule of subtraction counts objects satisfying the first property but not the second:

∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣.

In particular, if the objects with the second property form a subset of those with the first, the count is

∣ A ∣ - ∣ B ∣

. These conditions prevent either double counting an overlap or subtracting objects that were not counted initially.

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 / b / Solution 2026-10-25

The rule of product says that if a construction has

r

stages, with exactly

a_{j}

choices at stage

j

after every permitted earlier history, then it has

\prod_{j = 1}^{r} a_{j}

possible outcomes. The later choices need not be identical sets after different histories; their numbers must have the stated values.

For a permutation of

n

distinct objects, choose the first object in

n

ways, the second in

n - 1

ways, and continue until only one remains. Thus the number is

n (n - 1) \dots 1 = n! .

Every ordered arrangement is produced exactly once by its successive choices, so this counts permutations without omissions or repetitions. For

n = 0

, the unique empty arrangement agrees with

0! = 1

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

The pigeonhole principle states that if more than

r

objects are placed in

r

boxes, with

r \geq 1

, at least one box contains two or more objects. Equivalently, a function from a finite set of more than

r

elements to a set of

r

elements cannot be injective: if every box held at most one object, there would be at most

r

objects altogether.

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

Prove the stronger statement with a nonempty subset. Order the

n \geq 1

integers as

a_{1}, \dots, a_{n}

, and form the prefix sums

s_{0} = 0, s_{j} = \sum_{k = 1}^{j} a_{k} (1 \leq j \leq n) .

There are

n + 1

such sums but only

n

residue classes modulo

n

. The pigeonhole principle gives indices

0 \leq i < j \leq n

with

s_{i} \equiv s_{j} (mod n)

. Their difference satisfies

s_{j} - s_{i} = a_{i + 1} + \dots + a_{j} \equiv 0 (mod n) .

The selected elements form a nonempty subset of

S

, proving the claim. Neither positivity nor distinct values in a general ordered sequence are needed for the consecutive sum divisible by the sequence length argument; distinctness merely makes the present input a set.

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

The nonempty simple graphs having an independent vertex cover of size at most two. The witnesses

x, y

select the cover. The clause

\neg E (x, y)

makes the selected vertices nonadjacent; the universal clause forbids every edge whose two endpoints both lie outside the selected set.

The witnesses need not be distinct, so a one-vertex cover is permitted by choosing

x = y

. A nonempty edgeless graph also satisfies the formula. The empty graph does not, because the existential quantifiers have no witnesses. Here independent vertex cover has its standard vertex cover meaning; 8(b)'s differing parenthetical definition is addressed separately below.

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

The source's explicit parenthetical condition is domination: every unselected vertex has a neighbour in the selected set. Together with independence this defines an independent dominating set. A first-order sentence expressing that definition with size at most three is

\exists x_{1} \exists x_{2} \exists x_{3} (1 \leq i < j \leq 3 ⋀ (x_{i} = x_{j} \lor \neg E (x_{i}, x_{j})) \land \forall v (i = 1 ⋁ 3 v = x_{i} \lor i = 1 ⋁ 3 E (v, x_{i}))) .

The finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a first-order formula. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected vertices. The last clause says that every vertex is selected or adjacent to a selected vertex. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.

For the standard meaning of independent vertex cover, replace the domination clause by

\forall u \forall v (E (u, v) \to (⋁_{i = 1}^{3} u = x_{i} \lor ⋁_{i = 1}^{3} v = x_{i})) .

This instead demands that every edge has a selected endpoint. These interpretations differ: in a triangle in a graph, any singleton is an independent dominating set, but no independent vertex cover exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 4 / c / Solution 2026-10-25

Choose the middle element as the root:

build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
  where
    (ls,x:rs) = splitAt (length xs `div` 2) xs

The input is a finite, strictly ascending list, as required for distinct elements of a set. The two child lengths differ by at most one. Applying the same argument recursively gives a balanced binary tree of logarithmic height. All values on each side retain their original order, proving the binary search tree property. With linked lists, the repeated splitting gives

O (n lo g n)

time; it does not repeatedly insert values into a skewed tree.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 4 / f / Solution 2026-10-25

Insert down the unique search route, leaving equal elements unchanged:

insert :: Ord a => a -> Tree a -> Tree a
insert q Empty = Tree Empty q Empty
insert q t@(Tree l x r) = case compare q x of
  LT -> Tree (insert q l) x r
  EQ -> t
  GT -> Tree l x (insert q r)

The binary search tree ordering determines the only child in which a missing query can belong. The recursive call preserves that child's ordering bounds, and the other child is shared. Thus the output represents the original set with q added, with duplicates suppressed. Its time complexity and newly allocated route length are

O (h + 1)

; it makes no balancing guarantee.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 3 / f / Solution 2026-10-25

For each table index

b

, let

C_{b} = L (t ab l e (b))

be the set of non-null nodes reachable by following next. A sufficient representation invariant is:

The array has exactly $N > 0$ buckets, and every bucket heads a finite acyclic linked list.
The sets $C_{b}$ are pairwise disjoint, so one physical node cannot belong to two buckets.
Every reachable node has a valid user identity, lies in bucket hash(node.user), and has both counters between zero and Int.MaxValue.
User identities are unique among all reachable nodes, not merely within a single chain.

The abstraction function maps these nodes to the total functions of part (a): if the unique node for

u

exists,

I (u)

and

O (u)

are its fields; otherwise both are zero. A stored record with two zero counters is harmless and has the same observable meaning as an absent record. This intentionally permits multiple concrete representations of the same abstract program state.

Initially every bucket is null, so the representation invariant holds and the abstraction function yields all zeros. The successful-update branch preserves every structural condition; the insertion branch creates a fresh node with a previously absent identity in its correct bucket. Both branches realize exactly the incoming-increment postcondition, demonstrating correct operations through an abstraction function.

Path in a transition system 2026-10-31

A finite or infinite sequence of states in which

s_{i} \to s_{i + 1}

for each consecutive pair. In infinite-path linear temporal logic semantics, paths are infinite; an initial path must also start in the specified initial set. Repeated states are allowed, unlike conventions for a simple path in a graph.

Perfect subsequence lemma 2026-10-14

Every infinite sequence in a well-quasi-ordering has an infinite subsequence all of whose earlier terms precede its later terms. Some term must have infinitely many later terms above it: otherwise choose each new index outside the finitely many upper-cone index sets of the terms already chosen, producing a bad sequence. Apply the same observation successively inside the infinite upper-cone subsequence. Each restriction preserves all earlier inequalities, proving the assertion.