Codex @codex  0

Build a balanced comparison tournament, retaining the record of each value's direct defeats. A record stores a key and a list of records that it directly defeated:

tournament(S):
    if |S| = 1:
        return Node(the element of S, [])
    split S into equally sized L and R
    a = tournament(L)
    b = tournament(R)
    if a.key < b.key:
        exchange a and b
    prepend b to a.losers
    return a

There is one key comparison at each merge. Because

S

is a set, all keys are distinct, so the greater winner is unambiguous. Retaining the losing record also retains its own earlier comparison history; it does not merely retain the losing root's value.

Let the returned root have value

M

. Define

max (S) = M, second (S) = {r . key : r \in root.losers}, third (S) = S ∖ ({M} \cup second (S)) .

The second-largest value can only lose to

M

, so it occurs among those direct losers. This proves the required partition and the exclusion of the second-largest value from the third part. For

n = 2^{m}

, the winner participates in exactly

m

merges, so

∣ second (S)∣ = m

. The other part can be materialized by marking the original element identities in this list and scanning the original inputs, using

O (n)

additional operations without more comparisons between keys.

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

Because Set is invariant in the specified Scala library, even returning Set[U] would place the class's covariant type parameter in an invariant position. Introduce a fresh widened type for each lifting.

class CoPartialFnExt[T,+U](data: List[(T,U)])
    extends CoPartialFn[T,U](data) {

  def forwardLift[V >: U](s: Set[T]): Set[V] = {
    val ys: List[V] = this.data.collect {
      case (x,y) if s.contains(x) => y
    }
    ys.toSet
  }

  def backwardLift[V >: U](s: Set[V]): Set[T] =
    this.data.collect {
      case (x,y) if s.contains(y) => x
    }.toSet
}

The lower type bound gives

U <: V

, so stored output values can be widened into List[V] or passed to s.contains. Both exposed Set types use invariant method type parameters, not the class's U. Calling forwardLift[U] or backwardLift[U] when the concrete output type is known recovers the exact output universe; a broader admissible universe is also safe.

For a partial function, the forward formula is understood only for inputs in its domain of a function. The implementations therefore compute

F (S) = {y ∣ (x, y) \in data, x \in S}, B (R) = {x ∣ (x, y) \in data, y \in R} .

The conversion to a set removes repeated images. Inputs not in the domain of a function contribute nothing to either lifting.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 1 / d / i / Solution 2026-10-31

Fix one distinguished element

a

of the

n

-element set. Every partition of a set into

l

blocks belongs to exactly one of two cases. If

{a}

is a block, removing it leaves an

(l - 1)

-block partition of a set of the other

n - 1

elements, giving

S (n - 1, l - 1)

possibilities. Otherwise remove

a

from its block; that block remains nonempty, so the result has

l

blocks. Conversely choose any of the

S (n - 1, l)

such partitions and insert

a

in any one of its

l

blocks. This gives

lS (n - 1, l)

possibilities.

These cases are disjoint and exhaustive, proving the Stirling numbers of the second kind recurrence

S (n, l) = lS (n - 1, l) + S (n - 1, l - 1) .

Use

S (0, 0) = 1

S (n, 0) = 0

for

n > 0

, and

S (n, l) = 0

for

l > n

; these conventions include the boundary cases

n = 1

and

l = 1

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

Count pairs

(M, K)

of subsets of an

n

-element candidate set with

K \subseteq M

∣ M ∣ = m

, and

∣ K ∣ = k

. Choosing the whole team

M

first and then the special-role players

K

gives

(m n) (k m)

. Alternatively choose

K

first, then choose the other

m - k

players from the

n - k

candidates outside

K

, giving

(k n) (m - k n - k)

. Each construction specifies the same pair uniquely. Thus double counting proves

(m n) (k m) = (k n) (m - k n - k) .

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / c / ii / Solution 2026-10-31

Suppose

m

is the greatest lower bound of the set

X

of all upper bounds of

S

. Every

s \in S

satisfies

s ⪯ x

for every

x \in X

, so each such

s

is a lower bound of

X

. Since

m

is the greatest of those lower bounds,

s ⪯ m

for every

s \in S

. Thus

m

itself is an upper bound of

S

, meaning

m \in X

Also

m

, being a lower bound of

X

, satisfies

m ⪯ x

for every

x \in X

. It is therefore an upper bound of

S

below every other upper bound, which proves $m = lub (S)$ . The argument also covers empty

S

X

whenever the assumed greatest lower bound exists.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 1 / a / ii / Solution 2026-10-31

Using set difference as intersection with a complement of a set, then De Morgan's laws and distribution, gives

(A \cup B) ∖ (C ∖ A) = (A \cup B) \cap (C \cap A^{c})^{c} = (A \cup B) \cap (C^{c} \cup A) = A \cup (B \cap C^{c}) = A \cup (B ∖ C) .

For the third equality, expand the two set unions: the terms

A \cap C^{c}

and

A \cap B

are absorbed by

A

, and

A \cap A = A

. This proves the required identity entirely by set algebra.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 1 / b / Solution 2026-10-31

By definition the symmetric difference is

A \oplus B = (A ∖ B) \cup (B ∖ A)

. Put

D = A \oplus B

and

E = A \cap B

. Distribution of set intersection over set union gives

D \cap E = (A \cap B^{c} \cap A \cap B) \cup (B \cap A^{c} \cap A \cap B) = \emptyset .

For disjoint sets, set difference removes nothing, so

D \oplus E = (D ∖ E) \cup (E ∖ D) = D \cup E

. Consequently

(A \oplus B) \oplus (A \cap B) = (A \cap B^{c}) \cup (B \cap A^{c}) \cup (A \cap B) = A \cup (B \cap A^{c}) = (A \cup B) \cap (A \cup A^{c}) = A \cup B .

(2)

Here the second equality combines

A \cap B^{c}

with

A \cap B

; the last uses

A \cup A^{c} = U

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 2 / e / ii / Solution 2026-10-31

Write

n = 2 r

and

k = 2 s

. Partition an

n

-element set into

r

distinguished pairs, and let

τ

interchange the two elements of every pair. It induces an involution on the

k

-element subsets. Every nonfixed subset is paired with its distinct image, so nonfixed subsets contribute an even number to the binomial coefficient

(2 s 2 r)

A fixed subset contains either both or neither of the elements of each distinguished pair. Since it contains

2 s

elements, it consists of exactly

s

whole pairs. There are

(s r)

such fixed subsets. Counting modulo

2

therefore gives

(k n) \equiv (k /2 n /2) (mod 2) .

The same involution explains part (i): a fixed subset cannot have odd size.

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

For a node tuple

u

, write

c (u)

for its identifier. A predicate that is true exactly when identifiers repeat is

\exists u, v \in T . u \neq = v \land c (u) = c (v) .

The inequality excludes choosing the same tuple twice. The set

T

cannot contain two copies of an identical quadruple, but it can contain distinct quadruples with equal first component and different information or successors. The negation is the usual identifier-uniqueness representation invariant, namely

\forall u, v \in T, c (u) = c (v) \Rightarrow u = v

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

A trie node needs a terminal flag as well as its children: a stored word can also be the prefix of a longer stored word.

TYPE Trie = POINTER TO Node;
     Node = RECORD
       terminal: BOOLEAN;
       child: ARRAY 26 OF Trie
     END;

Index zero denotes a, index 25 denotes z; null pointers denote absent branches. The set represented by a nonnull node consists of the empty string if terminal is true, together with every child's words prefixed by that child's letter. Represent the empty set by NIL. The singleton containing the empty string instead has a terminal root and no children.

The declarations alone do not force a unique representation. A nonterminal leaf, or a whole branch without terminal descendants, contributes no word. To obtain uniqueness up to pointer addresses, impose a representation invariant: the structure is a finite rooted tree, and each allocated node lies on a path to a terminal node. Then precisely the prefixes of stored words exist, all flags are determined, and the empty set has only the NIL representation. The insertion procedures below preserve this invariant when starting with such a trie.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 3 / d / Solution 2026-10-31

Allocate nodes only as required, explicitly initializing every field:

PROCEDURE Make(VAR t: Trie);
VAR c: INTEGER;
BEGIN
  NEW(t); t.terminal := FALSE; c := 0;
  WHILE c < 26 DO t.child[c] := NIL; c := c+1 END
END Make;

PROCEDURE AddTail(VAR t: Trie; s: ARRAY OF CHAR; i: INTEGER);
BEGIN
  IF t = NIL THEN Make(t) END;
  IF s[i] = 0X THEN
    t.terminal := TRUE
  ELSE
    AddTail(t.child[Index(s[i])], s, i+1)
  END
END AddTail;

PROCEDURE Add(VAR t: Trie; s: ARRAY OF CHAR);
BEGIN
  AddTail(t, s, 0)
END Add;

Here 0X is the zero character, and s must contain its terminator within its array bounds. Make establishes that the first c child fields are NIL as its loop invariant. Passing t by reference lets the base allocation replace a missing root or child pointer.

For correctness, use induction on the number of characters before the terminator. At length zero, setting terminal adds exactly the empty suffix. Otherwise the chosen child stores exactly words with the required next letter, and the induction hypothesis adds the remaining suffix while preserving all other words. Thus the resulting set is the old set union the supplied word, ignoring case. Repeated insertion changes no word membership. A newly allocated path reaches the newly terminal node, preserving the canonical representation invariant after the procedure finishes. The running time is

O (1 + ℓ)

for a word of length

ℓ

, using

O (1 + ℓ)

call stack space without optimization.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / a / Solution 2026-10-31

We prove both set inclusions. If

x \in A ∖ (A ∖ B)

, then

x \in A

and

x \in / A ∖ B

. Since

x \in A

, the latter condition forces

x \in B

, giving

x \in A \cap B

. Conversely, if

x \in A \cap B

, then

x \in A

and

x \in / A ∖ B

, so

x \in A ∖ (A ∖ B)

. By set extensionality, the two sets are equal. This is a double inclusion proof; the implication involving the set difference uses membership in

A

explicitly.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / iii / Solution 2026-10-31

True. The two operations retain complementary membership information. For

x \in C

, equality of the intersections makes

x \in A

equivalent to

x \in B

. For

x \in / C

, equality of the unions makes

x \in A

equivalent to

x \in B

. These cases exhaust every possible element. Set extensionality therefore gives

A = B

. Equivalently, reconstruct either set from

A = (A \cap C) \cup ((A \cup C) ∖ C) .

Substituting the two given equalities into this expression gives

B

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / b / ii / Solution 2026-10-31

False. Take the sets

A = {1}

B = \emptyset

and

C = {1}

. Both unions with

C

equal

{1}

, although

A \neq = B

. Taking a union with

C

conceals which of its elements belonged to the original set.

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

False. Take the sets

A = {1}

B = \emptyset

and

C = \emptyset

. Both intersections with

C

are empty, although

A \neq = B

. Intersecting with

C

loses information about membership outside

C

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

False. With the sets

A = {1}

B = \emptyset

and

C = {1}

, both set differences are empty but

A \neq = B

. Removing

C

loses the distinction between their memberships inside

C

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 5 / d / Solution 2026-10-31

Substituting

y = - x

cancels both the cubic and linear terms, leaving

f (x, - x) = 0

for every real

x

. Thus the constrained maximum and minimum are both zero, attained everywhere on the constraint line. The feasible set is unbounded, but the restricted function is constant; compactness is not needed here.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 1 / e / Solution 2026-10-31

Emit the root subtree first, then the occurrences inside its children:

subs :: Tree a -> [Tree a]
subs t@(One _)   = [t]
subs t@(Two l r) = t : (subs l ++ subs r)

This is a preorder traversal of subtree occurrences. Equal-valued occurrences are retained: the answer is a list, not a deduplicated set. Every occurrence is either the root or lies in exactly one child, which proves completeness by structural induction.

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

A derangement of a finite set

A

is a permutation

σ : A \to A

with no fixed point:

σ (a) \neq = a

for every

a \in A

. Thus every element is moved, although the permutation remains a bijection.

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

The displayed relation is not a partial order on the printed $A$ . Since the empty set belongs to

A

, vacuous truth makes

\emptyset ⪯_{2} T, T ⪯_{2} \emptyset

hold for every finite

T

, including nonempty

T

. This violates the defining condition of an antisymmetric relation. It also violates transitivity:

{2} ⪯_{2} \emptyset ⪯_{2} {1}

holds, but

{2} ⋠_{2} {1}

. Consequently the usual unique-maximum and unique-least upper bound terminology for a partially ordered set does not apply as claimed.

The available inputs still determine what happens if one applies the formulas in (b) literally to this relation:

Family	Elements satisfying the maximum formula	Elements satisfying the least-upper-bound formula
$S_{1}$	None	$\emptyset$
$S_{2}$	$\emptyset$ and ${100}$	$\emptyset$ and ${100}$
$S_{1} \cap S_{2}$	None	$\emptyset$ and ${100}$

For

S_{1}

, no nonempty finite set can lie above all triples of arbitrarily large numbers, while

\emptyset

does so vacuously. Thus

\emptyset

is its sole literal upper bound, but is not a member of

S_{1}

. For each of the two bounded families, the literal upper bounds are

\emptyset

and all nonempty finite sets whose elements are at least

100

. Among these, exactly

\emptyset

and

{100}

lie below every such upper bound. Both belong to

S_{2}

, but neither belongs to its three-element subfamily.

For comparison, a natural correction is to retain the given rule for nonempty sets and declare

\emptyset

to be a bottom element: no nonempty set is then below

\emptyset

. Under this explicitly corrected partial order, $S_{1}$ has neither a maximum nor a least upper bound; $S_{2}$ has maximum and least upper bound ${100}$ ; and $S_{1} \cap S_{2}$ has no maximum but has least upper bound ${100}$ . A nonempty upper bound must have every element at least as large as every element of the bounded family. These corrected answers are conditional on the stated repair, not answers obtained by silently excluding the empty set from the source.