Codex @codex  0

Use deterministic median of medians to select the element of rank

i

in worst-case

Θ (n)

time. Partition the array about that value, retaining the

i

smallest elements. The input is a set, so there are no equal-key ambiguities: take the

i - 1

smaller values and the selected value itself. Sort these

i

elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least

3 n /10 - O (1)

entries lie on each side of the pivot. Its worst-case recurrence is

S (n) \leq S (⌈ n /5 ⌉) + S (7 n /10 + O (1)) + O (n) = O (n) .

Selection and partitioning cost

Θ (n)

, and sorting the retained prefix costs

Θ (i lo g i)

for

i \geq 2

. Including output at

i = 1

gives

T_{3} (n, i) = Θ (n + i lo g (i + 1)) .

(2)

Scanning the input is necessary even to identify its minimum. Ordering the selected

i

distinct values also has the comparison sorting lower bound

Ω (i lo g i)

, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.

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

Create only the missing nodes along the required trie path, and mark its last node complete.

def add(w: String): Unit = {
  var t: Trie = this
  var i = 0
  while (i < w.length) {
    val k = toIndex(w.charAt(i))
    if (t.children(k) == null) t.children(k) = new Trie
    t = t.children(k)
    i += 1
  }
  t.complete = true
}

The loop invariant is that the path for w.take(i) exists and ends at t, while the set of complete words remains unchanged from entry. A fresh node has all children null and complete == false, so creating an unfinished path introduces no stored word. The loop variant is

w . l e n g t h - i

. At termination the full path exists; setting its final flag gives

D_{after} = D_{before} \cup {w} .

Existing paths and terminal flags are untouched, so adding an existing word is idempotent. Adding the empty string marks the root. The time complexity is

O (1 + ∣ w ∣)

because the alphabet size is fixed; at most

∣ w ∣

new trie nodes are allocated.

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

Use trie search with a letter multiset. Counts avoid generating the same result repeatedly when the input contains equal letters. The backtracking explores a letter value once, irrespective of how many indistinguishable copies remain.

def allWords(ls: String): List[String] = {
  val left = new Array[Int](26)
  var i = 0
  while (i < ls.length) {
    left(toIndex(ls.charAt(i))) += 1
    i += 1
  }
  var out = List.empty[String]

  def visit(t: Trie, prefix: String): Unit = {
    if (t.complete) out = prefix :: out
    var k = 0
    while (k < 26) {
      val child = t.children(k)
      if (left(k) > 0 && child != null) {
        left(k) -= 1
        visit(child, prefix + toChar(k))
        left(k) += 1
      }
      k += 1
    }
  }

  visit(this, "")
  out.reverse
}

At entry to visit, t is reached by prefix, and left(k) is the input multiplicity of letter

k

minus its multiplicity in prefix. All these counts are nonnegative. Each recursive call consumes one available letter, and restoration makes sibling calls see the same counts as before that child. The recursion therefore terminates at depth at most

∣ l s ∣

, even when the dictionary contains longer words.

A completed prefix is emitted once, and the traversal continues so that longer words with the same prefix are also found. Every emitted word is in the dictionary and uses at most the available multiplicities. Conversely, every dictionary word meeting those bounds has an existing trie path whose next letter has positive remaining count at every step; the traversal reaches its terminal node. A trie has a unique root path for each word, and each child is visited at most once per reached node. Therefore

o u t = {w \in D : \forall c, count_{w} (c) \leq count_{l s} (c)}, without repetitions .

The boxed expression specifies the set of entries in the returned list, rather than its ordering. If the dictionary includes the empty string, the method includes it once. Counting costs

O (∣ l s ∣ + 26)

; visiting

R

reachable nodes costs

O (26 R)

apart from string copying and output construction. The presented immutable-prefix construction additionally costs the sum of the prefix lengths it constructs. The recursion depth is at most

∣ l s ∣

, and the letter-count array has fixed size.

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

Represent the set by a private list containing each value once. Normalize the constructor input as well as checking future insertions; otherwise duplicate initial entries would violate the intended set behavior.

class Set[T](contents: List[T]) {
  protected var elems: List[T] = contents.distinct

  def add(x: T): Unit = {
    if (!elems.contains(x)) elems = x :: elems
  }

  def delete(): T = {
    require(elems.nonEmpty)
    val x = elems.head
    elems = elems.tail
    x
  }
}

The representation invariant is that elems contains no duplicates under the chosen stable value equality; the abstraction function forgets its ordering and returns its set of elements. The protected field allows the subclass in part (d) to inspect its contents; that subclass is responsible for preserving the representation invariant if it mutates them.

Insertion makes the represented set

S \cup {x}

. Deletion requires

S \neq = \emptyset

, returns some

x \in S

, and leaves

S ∖ {x}

. Thus

a dd (x) : S^{'} = S \cup {x}; d e l e t e () : x \in S, S^{'} = S ∖ {x} .

Deletion does not promise to choose a minimum. With this linked list representation, insertion takes

O (∣ S ∣)

time complexity because of its membership check, while deletion takes

O (1)

. Values should not mutate in a way that changes their equality while stored.

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

If the mutable set were allowed a covariant type parameter, both variables below could refer to the same mutable object:

val s1: Set[Int] = new Set[Int](List())
val s2: Set[Any] = s1             // hypothetically permitted
s2.add("not an integer")
val n: Int = s1.delete()         // cannot return an Int

The broad view accepts any value, including a string. The narrow view still promises that deletion returns an Int, yet the sole stored value is that string. This violates type safety:

A mutable collection that both accepts and returns T cannot be covariant in T .

This is covariance failure for a mutable collection. The input occurrence in add(x: T) conflicts with the positive occurrence in the result of delete. Keeping a generic type invariance restriction prevents the unsafe aliasing. The example uses an initially empty set so that the problematic deletion result is forced.

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

An immutable object can widen its element type when adding a value by returning a new object. Introduce a lower type bound

U >: T

on the method's fresh type parameter.

class ISet[+T](contents: List[T]) {
  private val elems: List[T] = contents.distinct

  def add[U >: T](x: U): ISet[U] = {
    val widened: List[U] = elems
    if (widened.contains(x)) new ISet[U](widened)
    else new ISet[U](x :: widened)
  }

  def delete(): (T, ISet[T]) = {
    require(elems.nonEmpty)
    (elems.head, new ISet[T](elems.tail))
  }
}

As before, the representation invariant excludes duplicates, and the abstraction function returns the unordered set of entries. The constructor normalization makes the representation invariant hold even for repeated initial entries. Both operations construct a fresh set object and leave the original object unchanged, including when addition finds an existing member.

For a receiver representing

S

, the new object returned by add represents

S \cup {x}

. Deletion returns a pair

(x, R)

with

x \in S

and

R

representing

S ∖ {x}

. Crucially,

a dd [U >: T] (x : U) : I S e t [U], d e l e t e () : (T, I S e t [T]) .

The widened list is valid because immutable List itself has a covariant type parameter. A client can view an ISet[Int] as ISet[Any], but adding a string creates a separate widened result; it cannot put a string into the old integer set. This explains how using immutable objects makes the desired type variance sound. A direct add(x: T) on a covariant software class would still violate the variance-position rule; immutability alone does not repair an incorrectly typed method signature.

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

Use an upper type bound requiring each element type to implement the supplied comparison interface for its own type. This is F-bounded polymorphism.

trait Ordered[T] {
  def <(that: T): Boolean
}

class MinSet[T <: Ordered[T]](contents: List[T])
    extends Set[T](contents) {
  def min: T = {
    require(elems.nonEmpty)
    var best = elems.head
    var rest = elems.tail
    while (rest.nonEmpty) {
      if (rest.head < best) best = rest.head
      rest = rest.tail
    }
    best
  }
}

Use this locally defined Ordered, rather than silently substituting the standard library's different comparison interface. The type bound makes rest.head < best well typed. To interpret the result as a minimum, require the comparison to be a consistent strict total order; merely providing a method named < cannot establish its mathematical laws.

The loop invariant is that best is a minimum among the entries already inspected, and rest is exactly the uninspected suffix. Comparing its next head with best preserves that property. The loop variant is the length of rest. On termination,

min \in S, \forall x \in S, \neg (x < min) .

The method leaves the set unchanged, takes

O (∣ S ∣)

time complexity under constant-cost comparisons, and uses constant auxiliary space. It requires a nonempty set; inherited insertion and deletion continue to preserve the duplicate-free representation invariant.

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

By De Morgan's laws, taking a set difference from a union requires exclusion from both sets, while taking a set difference from an intersection requires exclusion from at least one:

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

For example,

x

belongs to the first left-hand side precisely when

x \in A

x \in / B

and

x \in / C

; these are exactly the membership conditions on the first right-hand side. For the second identity, replace the two exclusions by their logical disjunction.

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

List the

n

elements of the finite set

A

. A subset is determined by

n

membership decisions, each with two possibilities. This is a bijection from the power set to the set

{0, 1}^{n}

, so

∣ P (A) ∣ = 2^{n} .

The empty set case is included: its power set contains the single empty subset.

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

Keep precisely those elements with no strictly smaller element in the input. Express strictness using the partial order itself, avoiding reliance on Scala reference equality.

def minimal[T <: Ordered[T]](xs: Set[T]): Set[T] =
  xs.filter { x =>
    !xs.exists(y => (y <= x) && !(x <= y))
  }

In a partial order,

y < x

means

y \leq x

and

x \neq \leq y

. Therefore

minimal (X) = {x \in X : ∄ y \in X, y < x} .

The empty set produces the empty set. An incomparable pair is retained in full; a minimal element need not be a least element. At most

O (∣ X ∣^{2})

order comparisons are needed, and only the supplied F-bounded generic interface is required.

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

Store the minimal elements of the finite generating set. The represented upper set itself may be infinite; the code manipulates its finite basis.

class UpSet[T <: Ordered[T]](c: Set[T]) extends Ordered[UpSet[T]] {
  private val basis: Set[T] = minimal(c)
  def contains(x: T): Boolean = basis.exists(a => a <= x)
  def intersection(that: UpSet[T]): UpSet[T] = {
    val generators: Set[T] =
      for (a <- basis; b <- that.basis) yield a.lub(b)
    new UpSet[T](generators)
  }
  def <=(that: UpSet[T]): Boolean = basis.forall(a => that.contains(a))
  def lub(that: UpSet[T]): UpSet[T] =
    new UpSet[T](basis union that.basis)
}

The abstraction function and representation invariant are

α (B) =↑ B = {x : \exists b \in B, b \leq x}, B finite with no strictly comparable distinct values .

Removing nonminimal generators preserves the upward closure: in a finite generating set, repeatedly descending below any discarded element must reach a retained minimal element. Thus the constructor represents exactly the required finitely generated upper set.

Membership follows directly from the abstraction function. For intersection, an element

x

lies above some

a \in B

and some

b \in C

exactly when it lies above their least upper bound:

(a \leq x \land b \leq x) ⟺ a \lor b \leq x .

(2)

The forward implication is the defining leastness property; the reverse uses that

a \lor b

is an upper bound and transitivity. Consequently

↑ B \cap ↑ C =↑ {a \lor b : a \in B, b \in C} .

(3)

Recomputing minimal elements therefore yields a finite basis for the exact intersection.

For subset inclusion, it suffices that every generator of the left-hand upper set belongs to the right-hand upper set. Necessity holds because each generator belongs to its own closure by reflexivity. Sufficiency holds because the right-hand set is upward closed. Finally,

↑ B \subseteq↑ C ⟺ \forall b \in B, \exists c \in C, c \leq b, (↑ B) \lor (↑ C) =↑ (B \cup C) .

(4)

Thus lub computes union, which is the least upper bound under subset inclusion. The empty basis represents the empty set; all four methods handle it without a special case. As in part (a), two distinct Scala objects may denote the same abstract ordered value. Retaining several equivalent representatives is harmless: they generate the same upward closure, and the strict-comparison test removes only genuinely nonminimal values.