Codex @codex  0

Traverse the trie along the input string, stopping as soon as the required child is absent. All words and letter collections in this question are assumed to use only lowercase letters a through z; this is the alphabet represented by the given child array. Put the following methods inside the supplied Trie class.

def contains(w: String): Boolean = {
  var t: Trie = this
  var i = 0
  while (i < w.length && t != null) {
    t = t.children(toIndex(w.charAt(i)))
    i += 1
  }
  t != null && t.complete
}

The loop invariant is that t is the trie node reached by the prefix w.take(i), or null if that prefix has no path, with

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

. If t is null, no extension can be a stored word. Otherwise, following the next character preserves the loop invariant. The loop variant is

w . l e n g t h - i

. At exit,

co n t ain s (w) ⟺ the full path exists and its terminal flag is true .

A prefix that exists but is not complete must return false. The empty string is present exactly when the root's complete flag is true. The time complexity is

O (1 + ∣ w ∣)

, with constant auxiliary space.

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

These operations consume the receiver, as expected for this destructive iterator interface. exists stops immediately after the first successful test.

trait RichIter[T] extends Iter[T] {
  def foreach(f: T => Unit): Unit = {
    while (hasNext) f(next())
  }

  def exists(p: T => Boolean): Boolean = {
    while (hasNext) {
      if (p(next())) return true
    }
    false
  }

  def foldLeft[U](x: U)(f: (U, T) => U): U = {
    var acc = x
    while (hasNext) acc = f(acc, next())
    acc
  }
}

For foreach, after

k

iterations the supplied function has been applied in order to exactly the first

k

entries. For exists, every consumed entry has failed the predicate unless the method is returning true. For the left fold, the loop invariant after consuming

k

entries is

a cc = f (\dots f (f (x, a_{1}), a_{2}) \dots, a_{k}) .

Each iteration extends the expression by the next entry on the right. For a finite remaining sequence, its unconsumed length is a common loop variant. Thus

f ore a c h visits in order; e x i s t s short-circuits; f o l d L e f t associates to the left .

An empty iterator invokes no callback, gives false for exists, and returns

x

from the left fold. On an infinite iterator, exists can terminate when it finds a match; the other two operations ordinarily do not terminate. With constant-cost callbacks, finite input of length

n

takes

O (n)

time complexity and constant auxiliary space.

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 / Digital systems, linear algebra, introduction to formal proof / 1 / c / i / Solution 2026-10-31

Use byte addresses, so adjacent 32-bit array elements are four bytes apart. The following MIPS instructions include harmless sll $zero,$zero,0 instructions in every branch delay slot; the second load is followed by another independent instruction before its value is consumed, also accommodating an early MIPS architecture with a load-use delay. All mnemonics here denote individual machine instructions.

        beq   $t3,$zero,done  # n=0: do not access any array
        sll   $zero,$zero,0
loop:
        lw    $t4,0($t0)      # current a element
        lw    $t5,0($t1)      # current b element
        addiu $t0,$t0,4       # advance a; also separates lw from its use
        subu  $t6,$t4,$t5     # current difference, modulo 2^32
        sw    $t6,0($t2)      # store current c element
        addiu $t1,$t1,4
        addiu $t2,$t2,4
        addiu $t3,$t3,-1      # one fewer element remains
        bne   $t3,$zero,loop
        sll   $zero,$zero,0
done:

A loop invariant at the head of the loop, after

k

completed iterations, is that the three addresses point to elements

k

, the count is

n - k

, and every output element before

k

equals the corresponding difference. One iteration reads element

k

, stores its difference and advances to

k + 1

, preserving the loop invariant. The remaining count is a nonnegative loop variant decreasing by one, so the loop ends with

k = n

The code uses subu to avoid signed-overflow traps: the suffix does not restrict the operands to unsigned values. Its precise result is

c_{i} \equiv a_{i} - b_{i} (mod 2^{32}) (0 \leq i < n) .

For representable signed differences this is exactly

c_{i} = a_{i} - b_{i}

. If trapping signed arithmetic is required instead, use sub and assume all differences are representable. The arrays must occupy valid word-aligned storage with no address wrap; the usual separate output array avoids overwriting unread inputs.

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

Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here a and N are the given array and its length.

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= N)
  var k = l
  var j = l
  while (j < r) {
    if (a(j) < p) {
      val t = a(k); a(k) = a(j); a(j) = t
      k += 1
    }
    j += 1
  }
  k
}

The loop invariant is

l \leq k \leq j \leq r, a [l .. k) < p, a [k .. j) \geq p .

In addition, the active segment remains a permutation of its original contents, and every entry outside it remains unchanged. If a(j) < p, swapping it with a(k) extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The loop variant is

r - j

. At termination

j = r

, so

a [l .. k) < p \leq a [k .. r), return k .

There are exactly

r - l

iterations, giving

O (r - l + 1)

time complexity and constant auxiliary space.

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

Fix the top-right corner

(i, j)

and a bottom boundary

k

. A width

w

is feasible precisely when every row

m \in [i, k)

has at least

w

consecutive true entries ending at column

j

. Thus the largest feasible width is the minimum of those row run lengths, and the area is that width times

k - i

def maxRectangleAt(i: Int, j: Int): Int = {
  var k = i
  var width = j + 1
  var best = 0
  while (k < N) {
    width = math.min(width, rowCount(k)(j))
    k += 1
    best = math.max(best, (k - i) * width)
  }
  best
}

At the loop head, the loop invariant is

i \leq k \leq N

width best = min ({j + 1} \cup {rowCount (m) (j) : i \leq m < k}), = max ({0} \cup {(h - i) i \leq m < h min rowCount (m) (j) : i < h \leq k}) .

The initial cap

j + 1

makes the empty-prefix case well-defined and cannot restrict any actual run. Each iteration incorporates one new row and tests its corresponding bottom boundary. The loop variant is

N - k

, so

best = i < k \leq N max (k - i) i \leq m < k min rowCount (m) (j), O (N) .

A zero width contributes area zero, covering the case where no nonempty all-true rectangle starts at that corner.

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

Implement staircase matrix search from the top-right corner. In the following Oberon-style code, & denotes short-circuit conjunction; all guarded accesses respect array bounds.

PROCEDURE Staircase(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
VAR r, c: INTEGER;
BEGIN
  r := 0; c := N-1;
  WHILE (r < M) & (c >= 0) DO
    IF f[r,c] = x THEN i := r; j := c; RETURN TRUE
    ELSIF f[r,c] < x THEN INC(r)
    ELSE DEC(c)
    END
  END;
  RETURN FALSE
END Staircase;

The loop invariant is that every occurrence not yet returned lies in

[r, M) \times [0, c + 1) .

Initially this is the whole array. If

f [r, c] < x

, every entry of row

r

in the candidate rectangle is smaller than

x

, so increasing

r

discards no possible answer. If

f [r, c] > x

, every entry of column

c

in that rectangle is greater than

x

, so decreasing

c

is safe. These conclusions follow from monotonicity even when repeated values occur.

The loop variant

(M - r) + (c + 1)

decreases on every unsuccessful iteration. If a dimension becomes empty, the loop invariant proves absence. For positive dimensions the path inspects at most

M + N - 1

entries; an initially empty dimension causes no inspection. Thus

Time O (M + N), auxiliary space O (1) .

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

Let

s (T)

be the number of nodes and let the left-size potential of a binary tree be

L (\emptyset) = 0, L (T) = s (T . l e f t) + L (T . r i g h t) .

Equivalently

L (T)

counts nodes outside the right spine, so

0 \leq L (T) \leq s (T)

; for a nonempty binary tree of

n

nodes,

L (T) \leq n - 1

For the right tree rotation in part (f), write the old shape as

((A, x, B), y, C)

. Before and after,

L_{before} = s (A) + 1 + s (B) + L (C), L_{after} = s (A) + s (B) + L (C) .

Thus each inner iteration decreases

L

by exactly one, making

L

an inner loop variant. Removing a root with empty left subtree leaves

L

unchanged and decreases

s

by one. Therefore

s + L

decreases on every rotation or visit, while

s

decreases on every completed outer iteration. These are bounds used for proof; the program never computes them.

There are exactly

n

visits and exactly

L (T_{0})

rotations, since the final empty binary tree has potential zero. Counting constant-cost p,

rotations + visits = n + L (T_{0}) \leq 2 n - 1 (n > 0), T (n) = Θ (n + 1) .

(3)

The nested loops therefore have linear total running time, despite one outer iteration potentially making many rotations.

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

Track the length r of the trailing constant segment of an array, and the best length m anywhere in the processed prefix:

i := 1; r := 1; m := 1;
WHILE i < n DO
  IF a[i] = a[i-1] THEN r := r+1 ELSE r := 1 END;
  IF r > m THEN m := r END;
  i := i+1
END;

The loop invariant is:

1 \leq i \leq n

; r is the length of the longest constant suffix of

a [0.. i)

; and m is the length of the longest constant segment of an array within

a [0.. i)

. Initially all three lengths are one, using

n \geq 1

When the next entry equals its predecessor, the trailing constant segment extends by one; otherwise its new length is one. Every new plateau either was already in the old prefix or ends at the new entry, so taking the larger of the old m and the new r preserves the loop invariant. The loop variant is

n - i

, a nonnegative integer decreased by one. At termination

i = n

, so

m = max {q - p : 0 \leq p < q \leq n, a [p .. q) is constant}, T (n) = Θ (n) .

The auxiliary space is

O (1)

, and

n = 1

correctly returns one without entering the loop.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 2 / b / Solution 2026-10-31

Use binary search on an interval with unequal endpoint values. The array need not be sorted:

l := 0; r := n;
WHILE r-l > 1 DO
  m := l + (r-l) DIV 2;
  IF b[l] # b[m] THEN r := m ELSE l := m END
END;
k := l;

The loop invariant is

0 \leq l < r \leq n, b [l] \neq = b [r] .

It holds initially by the given endpoint inequality, which also implies

n \geq 1

. When

r - l > 1

l < m < r

. If

b [l] \neq = b [m]

, replacing

r

maintains unequal endpoints. Otherwise

b [m] = b [l] \neq = b [r]

, so replacing

l

maintains them. This does not require monotonicity or even just two possible values.

The positive integer width

r - l

is a loop variant, reduced to at most its old half rounded up. On exit

r = l + 1

, giving

0 \leq k < n, b [k] \neq = b [k + 1], T (n) = Θ (1 + lo g n) .

There are at most

⌈ lo g_{2} n ⌉

iterations. The additive constant handles

n = 1

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

Return the exclusive endpoint of the maximal initial run:

PROCEDURE Run(a, b: INTEGER): INTEGER;
VAR c: INTEGER;
BEGIN
  IF a = b THEN RETURN b END;
  c := a+1;
  WHILE c < b DO
    IF u[c-1] > u[c] THEN RETURN c END;
    c := c+1
  END;
  RETURN c
END Run;

The loop invariant is

a < c \leq b

and

u [a .. c)

is nondecreasing. An unsuccessful adjacent-order test extends the run by one; a strict descent at

c

prevents any extension across it. If

c = b

, the whole segment is a run. The loop variant is

b - c

u [a .. Run (a, b)) is the maximal initial run .

For a run of length

s > 0

, the running time is

Θ (s)

, including at most one failed extension test; an empty segment takes

Θ (1)

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

Use a merge algorithm with one unread index in each run. Here u is the module's array; the destination

[d, d + c - a)

is disjoint from the source and lies within the array bounds:

PROCEDURE Merge(a, b, c, d: INTEGER);
VAR i, j, k: INTEGER;
BEGIN
  i := a; j := b; k := d;
  WHILE (i < b) & (j < c) DO
    IF u[i] <= u[j] THEN
      u[k] := u[i]; i := i+1
    ELSE
      u[k] := u[j]; j := j+1
    END;
    k := k+1
  END;
  WHILE i < b DO
    u[k] := u[i]; i := i+1; k := k+1
  END;
  WHILE j < c DO
    u[k] := u[j]; j := j+1; k := k+1
  END
END Merge;

Let

A, B

denote the original two runs. The first loop invariant says

k - d = (i - a) + (j - b)

and

u [d .. k)

is the sorted merge of

A [0.. i - a)

and

B [0.. j - b)

; moreover each emitted value is at most every unread value. Choosing the smaller head preserves that condition. Equal heads are taken from the first run, giving stable sorting within this merge. The loop variant is

(b - i) + (c - j)

For each copying loop, the output remains the sorted merge of the consumed prefixes, at least one source run is exhausted, and only the indicated suffix remains. The respective loop variants are

b - i

and

c - j

. At exit both source runs are exhausted:

u [d .. d + c - a) = merge (A, B), T = Θ (c - a + 1) .

The destination's multiset is the sum of the two source multisets.

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

Let

S

be the original sequence and

n = b - a

. The loop invariant is

0 \leq c \leq d \leq N, d - c = n, bag (u [c .. d)) = bag (S) .

Here

bag

denotes the multiset of entries. The capacity condition uses the question's assumption of sufficient space. Removing two runs of combined length

z

and appending their merge preserves the length and multiset. It also leaves all live values in one contiguous segment.

For a nonempty live sequence, let

R

be its number of maximal initial runs obtained by repeatedly cutting at strict adjacent descents. The loop variant is

R - 1

. If x = d, there is one run and the procedure returns a sorted permutation. Otherwise the iteration removes two runs and appends one; it cannot create a new descent inside that appended run. The appended run may join the last old run, further reducing

R

, so

R

decreases by at least one. There are at most

R_{0} - 1 \leq n - 1

merges.

Preserved length and multiset, plus decreasing run count, imply total correctness .

For

n = 0

, the loop is skipped and the empty segment is already sorted. No global stability claim is needed: moving a merged run behind other runs can change the order of equal-labelled occurrences.

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

If the merge algorithm from part (b) is retained with a disjoint destination, use a circular buffer of

2 n

cells. Represent the live segment by its start modulo

2 n

and its length

n

. The other

n

cells are free; the next merge needs at most

n

output cells. Appending its output and advancing the live start releases exactly as many obsolete source cells. Logical run boundaries and copying indices are reduced modulo

2 n

. The final sorted sequence may wrap, in which case an array rotation makes it contiguous. Thus

2 n cells suffice while retaining the disjoint-output merge .

This is also the worst-case requirement if all source cells must be retained until a whole disjoint merge has been written: the final two runs can have combined length

n

Under the question's literal wording, however, no running time requirement or disjoint-output restriction is imposed on the modified implementation. The absolute smallest array is

n cells, with O (1) auxiliary scalar storage .

To achieve this, replace the disjoint-output merge by an in-place merge: compare the next unread values of the two adjacent runs; when the second is smaller, save it in one scalar, shift the intervening first-run block right by one, and insert it before that block. This is a sorted merge using no extra array. Its loop invariant is that the finished prefix is the sorted merge of the consumed portions and the two remaining runs stay sorted. Each step consumes one value, proving termination.

After merging the first two runs in place, rotate the merged prefix behind the untouched suffix. Three array reversals implement this rotation with one scalar: reverse the merged prefix, reverse the suffix, then reverse the whole segment. The resulting live sequence is exactly the one produced in part (c). Repeat the same run schedule until sorted. The shift and reversal loops respectively preserve the copied block and exchanged end pairs; their loop variants are the unshifted length and half the unreversed length. The modification can be substantially slower, but preserves the loop invariant and decreasing run count from part (d). Fewer than

n

cells cannot even hold the specified

n

input entries. Thus

2 n

is the natural circular-workspace answer for the original merge primitive, while

n

is attainable when minimizing storage over all implementations allowed by the stated time-free specification.

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

Keep u[0..len) sorted, with the coupling invariant

0 \leq len \leq N, len = length (x s), u [0.. len) = sort (x s) .

The abstract list retains insertion order, while the concrete array retains its sorted multiset. Initially both are empty.

PROCEDURE Add(x: INTEGER);
VAR i: INTEGER;
BEGIN
  ASSERT(len < N);
  i := len;
  WHILE i > 0 DO
    IF u[i-1] <= x THEN EXIT END;
    u[i] := u[i-1];
    i := i-1
  END;
  u[i] := x;
  len := len+1
END Add;

PROCEDURE Get(k: INTEGER): INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  RETURN u[k]
END Get;

For insertion, conceptually treat index i as a hole. If

U

is the old sorted prefix of length

n

, the loop invariant is

0 \leq i \leq n

u [0.. i) = U [0.. i)

and

u [i + 1.. n + 1) = U [i .. n)

, with every shifted value strictly greater than

x

. The loop variant is

i

. The exit condition gives either no left neighbour or a left neighbour at most

x

; filling the hole establishes sortedness and adds exactly one occurrence, preserving the coupling invariant.

get : Θ (1), add : O (n) and worst-case Θ (n) .

When the new entry is smaller than every old entry, all

n

old values must move in this contiguous sorted-prefix representation. Binary search can reduce comparisons to locate the insertion point, but cannot remove that linear movement cost. Appending a new largest value takes constant time in this implementation.

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

The original page permits

m = r

, but also indexes

a [m]

. The meaningful pivot-position contract is the stronger

l \leq m < r

, with

a [l .. m) < a [m]

and

a [m .. r) \geq a [m]

. Implement this two-way array partition by reserving the last entry as pivot:

PROCEDURE Partition(l, r: INTEGER): INTEGER;
VAR pivot, i, j, tmp: INTEGER;
BEGIN
  ASSERT(l < r);
  pivot := a[r-1];
  i := l; j := l;
  WHILE j < r-1 DO
    IF a[j] < pivot THEN
      tmp := a[i]; a[i] := a[j]; a[j] := tmp;
      i := i+1
    END;
    j := j+1
  END;
  tmp := a[i]; a[i] := a[r-1]; a[r-1] := tmp;
  RETURN i
END Partition;

The loop invariant is

l \leq i \leq j \leq r - 1, a [l .. i) < pivot, a [i .. j) \geq pivot, a [r - 1] = pivot .

The segment's multiset is preserved and entries outside

[l, r)

are unchanged. The unclassified part is

[j, r - 1)

. A smaller entry is swapped into the left group; if

i < j

, the displaced entry belongs to the greater-or-equal group. Otherwise the entry simply joins that group. The loop variant is

r - 1 - j

At exit the final swap installs the pivot at i, giving

m = i \in [l, r), a [l .. m) < a [m] \leq a [m .. r), T = Θ (r - l) .

A singleton segment is handled without loop iterations. Equality belongs on the pivot's right side, as required by the printed strict left inequality.

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

Store the current multiset in an unsorted prefix a[0..len); Add appends exactly as in part (a). The coupling invariant is equality of length and multiset with abstract xs, rather than equality of insertion order. Get applies quickselect:

PROCEDURE Get(k: INTEGER): INTEGER;
VAR l, r, m: INTEGER;
BEGIN
  ASSERT((0 <= k) & (k < len));
  l := 0; r := len;
  LOOP
    m := Partition(l, r);
    IF k = m THEN RETURN a[m]
    ELSIF k < m THEN r := m
    ELSE l := m+1
    END
  END
END Get;

The loop invariant is

0 \leq l \leq k < r \leq len

, the complete array has its original multiset, every discarded entry on the left is at most every active entry, and every active entry is at most every discarded entry on the right. Thus the desired global order statistic is the local one of rank

k - l

. The two-way array partition result either identifies it or excludes the pivot and the irrelevant side. The positive loop variant

r - l

strictly decreases unless the procedure returns.

Balanced pivots give

T (n) \leq T (⌈ n /2 ⌉) + c n

, whose geometric series is

O (n)

. More generally, choosing a uniformly random pivot before each call, by swapping a random active entry into a[r-1], gives expected

Θ (n)

running time on distinct keys: with constant probability, the pivot is in the middle half and the retained side has size at most

3 n /4

. Expected work over these shrinking stages is a convergent geometric series.

add : Θ (1); get : expected Θ (n) under suitable pivot assumptions, worst-case Θ (n^{2}) .

The particular last-entry pivot in the displayed code has no unconditional expected guarantee without an input distribution. Its worst case repeatedly discards one entry. Duplicate keys require further care: on an all-equal segment, the strict partition always returns

l

, so selecting the last rank costs

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

even with randomized pivot positions. A three-way array partitioning that groups all keys equal to the pivot restores the usual randomized linear expectation with duplicates; alternatively the stated expectation assumes distinct keys. This is a qualification to the bound, not to the algorithm correctness of the displayed code.

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

The first matching entry must be retained, and copying an already-started prefix-dropping iterator must not restart the search. Use a private initial buffer together with the underlying iterator snapshot:

class DropUntil[T] private (
    p: T => Boolean, iter: Iter[T],
    saved: Option[T], alreadyStarted: Boolean) extends Iter[T] {

  def this(p: T => Boolean, iter: Iter[T]) =
    this(p, iter, None, false)

  private var pending: Option[T] = saved
  private var started: Boolean = alreadyStarted

  private def prepare(): Unit = {
    if (!started) {
      var found = false
      while (!found && iter.hasNext) {
        val x = iter.next()
        if (p(x)) {
          pending = Some(x)
          found = true
        }
      }
      started = true
    }
  }

  def hasNext: Boolean = {
    prepare()
    pending.nonEmpty || iter.hasNext
  }

  def next(): T = {
    prepare()
    pending match {
      case Some(x) => pending = None; x
      case None =>
        if (!iter.hasNext) throw new NoSuchElementException("DropUntil.next")
        iter.next()
    }
  }

  def copy(): Iter[T] =
    new DropUntil[T](p, iter.copy(), pending, started)
}

Before preparation, the iterator still represents the original remaining sequence. During the search, the loop invariant says that every discarded entry fails the predicate, and pending is either empty or contains the first satisfying entry just consumed. For a finite input, the number of unread entries is a loop variant. After preparation, the abstract remaining sequence is pending.toList followed by the underlying iterator's remaining sequence. Repeated hasNext calls do not discard or test more entries after the first match.

The iterator snapshot copies both the cached entry and the started flag. In particular, copying after the matching entry has been returned continues with the remaining suffix, including later entries that fail p. Restarting new DropUntil(p, iter.copy()) at that point would wrongly drop another prefix.

remaining = dropWhile (\neg p, input) initially; copies preserve the current suffix .

As usual, assume a deterministic predicate without shared mutable effects. On an infinite input having no match, the first demand cannot terminate: no finite inspection establishes absence. Independence here concerns cursor state; arbitrary mutation of shared element objects is outside the iterator contract.

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

Implement the three consumers directly with while loops. These methods consume the receiver; exists stops immediately after the first witness:

trait RichIter[T] extends Iter[T] {
  def foreach(f: T => Unit): Unit = {
    while (hasNext) f(next())
  }

  def exists(p: T => Boolean): Boolean = {
    while (hasNext) {
      if (p(next())) return true
    }
    false
  }

  def foldLeft[U](x: U)(f: (U, T) => U): U = {
    var result = x
    while (hasNext) result = f(result, next())
    result
  }
}

For foreach, the loop invariant is that f has been called once, in order, on exactly the consumed prefix. For exists, provided it has not returned, every consumed entry fails the predicate; a returned true has a witness, while exhaustion proves there is none. For foldLeft, after

j

consumed entries the loop invariant is

result = f (\dots f (f (x, a_{1}), a_{2}) \dots, a_{j}),

with result = x at

j = 0

. Thus initialization, one further application, and exhaustion prove the required left fold. On finite inputs, the remaining length is a loop variant for each loop. Callbacks are assumed not to mutate this iterator independently.

foreach : ordered consumption; exists : short-circuit search; foldLeft : left-associated accumulation .

With constant-cost callbacks and iterator operations, full consumption costs

Θ (n + 1)

; exists may return earlier. Empty inputs respectively do nothing, return false, and return x. Infinite inputs need not terminate, except that exists terminates upon reaching a witness.