New articles - OurBigBook.com

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 4 / c / Solution by

Codex  0 2026-10-31

The following class uses the bounded insertion contract from part (b). slot performs mathematical circular indexing with a wider intermediate, so even large legal indices do not overflow before reduction:

class ArrayDoubleEndedQueue(val MAX: Int) extends DoubleEndedQueue {
  require(MAX > 0)
  private val a = new Array[Int](MAX)
  private var head = 0
  private var size = 0

  private def slot(offset: Int): Int =
    ((head.toLong + offset.toLong) % MAX.toLong).toInt

  private def before(i: Int): Int = if (i == 0) MAX - 1 else i - 1
  private def after(i: Int): Int = if (i == MAX - 1) 0 else i + 1

  def isEmpty: Boolean = size == 0

  def addLeft(x: Int): Unit = {
    require(size < MAX)
    head = before(head)
    a(head) = x
    size += 1
  }

  def addRight(x: Int): Unit = {
    require(size < MAX)
    a(slot(size)) = x
    size += 1
  }

  def getLeft(): Int = {
    require(size > 0)
    val x = a(head)
    head = after(head)
    size -= 1
    x
  }

  def getRight(): Int = {
    require(size > 0)
    val x = a(slot(size - 1))
    size -= 1
    x
  }
}

For addLeft, moving the first position back one slot makes the old position the new logical index one; inserting at the new position prepends x. For addRight, the old size is the first unoccupied logical index, so writing there appends x. The removals read the appropriate endpoint and exclude that slot from the occupied interval. Every operation preserves the representation invariant and realizes the abstraction function postcondition. Old contents in unused slots cannot be observed through this interface. Each operation performs a fixed number of accesses and arithmetic operations, hence has constant time and constant space per call, apart from the class's

O (M A X)

backing storage.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 4 / b / Solution by

Codex  0 2026-10-31

A fixed-size array cannot implement unbounded successful insertion. Either specify a bounded double-ended queue with an extra not-full insertion precondition, or retain the unbounded interface and specify a possible full-capacity failure. Silently overwriting an endpoint would change the stated behavior. Here use the bounded contract, with a fixed positive capacity MAX and abstract state

∣ s ∣ \leq M A X

. Both additions require

∣ s ∣ < M A X

; the other postconditions remain unchanged. The class declaration in part (c) is interpreted as implementing this explicitly revised contract, rather than as a behavioral subtype of the unrestricted contract in part (a).

The concrete state is an array a of length MAX, a first-position index head, and an occupied-entry count size. Its representation invariant is

M A X > 0, a . l e n g t h = M A X, 0 \leq h e a d < M A X, 0 \leq s i ze \leq M A X .

The abstraction function is

s (k) = a ((h e a d + k) mod M A X)

for

0 \leq k < s i ze

. Unoccupied slots are unconstrained. Storing size distinguishes empty and full states even though their two circular endpoint positions coincide. MAX=1 is valid. Using a circular buffer avoids shifting entries and makes every endpoint operation constant time.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 4 / a / Solution by

Codex  0 2026-10-31

Take the abstract state to be a finite sequence

s

of integers, initially empty. Let

s_{0}

denote the entry state,

ϵ

the empty sequence, and

+ +

concatenation. A Scala trait presents the interface; its comments give the mathematical preconditions and postconditions:

trait DoubleEndedQueue {
  // Pre: true. Post: result == s0.isEmpty and s == s0.
  def isEmpty: Boolean
  // Pre: true. Post: s == [x] ++ s0.
  def addLeft(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.head, s == s0.tail.
  def getLeft(): Int
  // Pre: true. Post: s == s0 ++ [x].
  def addRight(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.last, s == s0.init.
  def getRight(): Int
}

The double-ended queue has no abstract capacity limit in this first specification. Both removals require nonemptiness; the query leaves the state unchanged, an instance of command-query separation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / g / Solution by

Codex  0 2026-10-31

Use the sorted sparse dot product merge, processing a coordinate only when it appears in both supports of a vector:

def dotProduct(vec1: Node, vec2: Node): Double = {
  require(vec1 != null && vec2 != null)
  require(vec1.index == vec2.index)
  var p = vec1.next
  var q = vec2.next
  var result = 0.0
  while ((p ne vec1) && (q ne vec2)) {
    if (p.index < q.index) p = p.next
    else if (q.index < p.index) q = q.next
    else {
      result += p.value * q.value
      p = p.next
      q = q.next
    }
  }
  result
}

Both structures must satisfy the representation invariant; equal dimension is checked explicitly. The loop invariant says that result contains exactly the products for all matching indices already passed, and that every skipped unequal index has zero in the other vector. The latter follows from sortedness: if p.index < q.index, that index cannot appear at q or later, and all earlier entries of the other vector have already been settled. Equality contributes its product exactly once. The total number of remaining ordinary entries is a loop variant; every iteration advances at least one cursor. Once either cursor reaches its header, all remaining entries pair with zeros. Thus the exact-arithmetic result is $\sum_{i} v ec 1_{i} v ec 2_{i}$ . With

k_{1}, k_{2}

stored entries, time complexity is

O (k_{1} + k_{2} + 1)

and auxiliary space is constant. Floating-point products and additions may round or overflow even when input coordinates are finite; no exact real-arithmetic accuracy claim is made for Double.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / f / Solution by

Codex  0 2026-10-31

Append entries in increasing index order, keeping a tail reference so that repeated searches do not make construction quadratic:

def makeVector(elems: Array[Double]): Node = {
  require(elems != null)
  val h = makeZeroVector(elems.length)
  var tail = h
  var i = 0
  while (i < elems.length) {
    val v = elems(i)
    require(!java.lang.Double.isNaN(v) &&
            !java.lang.Double.isInfinite(v))
    if (v != 0.0) {
      val fresh = new Node(v, i, tail, h)
      tail.next = fresh
      h.prev = fresh
      tail = fresh
    }
    i += 1
  }
  h
}

The loop invariant is

0 \leq i \leq e l e m s . l e n g t h

, a valid circular representation of the nonzero entries in elems[0..i), a fixed header dimension elems.length, and tail eq h.prev. The next nonzero index is greater than every stored index; appending the fresh linked list node preserves reciprocal links, including tail.next eq h. The loop variant is elems.length-i. At exit the abstraction function yields exactly the input array as a vector. There is one pass and constant work per entry:

Θ (n)

time complexity for

n > 0

O (n + 1)

including emptiness, and

O (k + 1)

output storage for

k

nonzero entries. Both signs of floating-point zero are represented by absence.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / e / Solution by

Codex  0 2026-10-31

An already-zero entry needs no new linked list node:

def zeroElement(vector: Node, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) {
    val left = p.prev
    val right = p.next
    left.next = right
    right.prev = left
  }
}

The full input representation invariant is a precondition. The search has the same loop invariant and loop variant as in part (d). At exit, either p is the only stored entry with that index or none exists. In the first case, bypassing it in both directions removes exactly that coordinate and preserves the order of all remaining entries. This also works when its two neighbors are the same list header, leaving a self-linked empty structure. The header itself is never removed. The requested coordinate is zero and all others are unchanged, in

O (k + 1)

time complexity.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / d / Solution by

Codex  0 2026-10-31

Assume vector already satisfies the full representation invariant in part (b). Check the local bounds and value preconditions, then find the first index not smaller than the requested one:

def setElement(vector: Node, value: Double, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  require(value != 0.0 && !java.lang.Double.isNaN(value) &&
          !java.lang.Double.isInfinite(value))
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) p.value = value
  else {
    val left = p.prev
    val fresh = new Node(value, index, left, p)
    left.next = fresh
    p.prev = fresh
  }
}

The search loop invariant says that the structure is unchanged and every ordinary linked list node passed has index smaller than index; p is the next candidate. The number of unpassed ordinary entries is a loop variant. The short-circuit evaluation prevents testing the header index as an ordinary entry. If an equal index exists, changing only its nonzero value preserves the representation invariant. Otherwise left and p delimit the unique insertion position: initializing both new links before redirecting their neighbors preserves reciprocal links and strict index order. Exactly the requested coordinate changes. With

k

stored entries, the search costs

O (k + 1)

and the splice costs constant time; checking the whole input structure is a caller obligation, rather than an unmentioned scan inside each call.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / c / Solution by

Codex  0 2026-10-31

The runtime precondition check rules out negative dimensions:

def makeZeroVector(size: Int): Node = {
  require(size >= 0)
  val h = new Node(0.0, size)
  h.prev = h
  h.next = h
  h
}

Both links point to the fresh list header, so all reciprocal-link conditions hold and there are no ordinary entries to violate ordering or nonzero-value requirements. The abstraction function therefore yields the zero vector of dimension size. Construction uses constant time and constant space.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / b / ii by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / b / i by

Codex  0 2026-10-31

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 3 / a / Solution by

Codex  0 2026-10-31

A list header is a permanent dummy linked list node, distinct from the ordinary elements. It gives a stable reference to the linked list and can store metadata such as its length. In a circular linked list, following successor links eventually returns to the starting point; with a list header, the last ordinary element links to the header, and the empty structure has the header linked to itself.

A singly linked list stores a successor reference per linked list node. A doubly linked list additionally stores a predecessor reference. The latter supports traversal in both directions and deletion of a known linked list node in constant time, without first searching for its predecessor. It costs another reference per linked list node and additional updates whose mutual consistency must be maintained. A list header makes insertion and deletion at an endpoint use the same local splicing rules as an interior change; the empty case does not require replacing an external head reference.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / d / Solution by

Codex  0 2026-10-31

Black-box testing chooses inputs and expected outputs from the public specification without using the implementation's control structure. Equivalence class testing partitions the input space into classes expected to exercise similar specified behavior, then chooses representatives; boundary cases test where that behavior changes. For equal-range search, use these concrete representatives:

Empty array: ([], 4) gives (0,0).
One entry, with the target below, equal, and above it: ([4],3), ([4],4), ([4],5) give (0,0), (0,1), (1,1).
An absent interior value: ([1,3,5],4) gives (2,2).
One interior match: ([1,3,5],3) gives (1,2).
A repeated interior block: ([1,3,3,3,5],3) gives (1,4).
A repeated block touching the left or right boundary: ([3,3,5],3) and ([1,3,3],3) give (0,2) and (1,3).
Every entry equal: ([3,3,3],3) gives (0,3); targets two and four give (0,0) and (3,3).
Extreme keys: ([Int.MinValue,0,Int.MaxValue],Int.MaxValue) gives (2,3), and searching for Int.MinValue gives (0,1).

For each result independently check

0 \leq i \leq j \leq n

, the strict inequalities outside the returned interval, and equality inside it. Unsorted inputs violate the precondition; they are not ordinary members of the specified valid-input classes. Software testing supplies evidence about implementations, while the loop invariant proof explains correctness for every valid input.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / c / Solution by

Codex  0 2026-10-31

A second binary search locates the first entry strictly greater than x:

def upperBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) <= x) lo = mid + 1
    else hi = mid
  }
  lo
}

def equalRange(a: Array[Int], x: Int): (Int, Int) =
  (lowerBound(a, x), upperBound(a, x))

For upper-bound search, the loop invariant is

0 \leq l o \leq hi \leq n

a [0.. l o) \leq x

, and

x < a [hi .. n)

; its loop variant is again

hi - l o

. The same midpoint and sortedness arguments prove preservation, termination and

O (lo g (n + 1))

time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.

Let the two boundaries be

i, j

. There cannot be a value greater than

x

before the first value at least

x

, so

i \leq j

. Every entry between them is simultaneously at least and at most

x

, hence equals

x

. Entries before

i

are smaller and entries at or after

j

are larger, so the interval cannot be extended at either end. This proves the equal-range search result is maximal. If x is absent, i == j, both equal to its insertion position; this can be zero,

n

, or an interior gap. Two logarithmic searches still have logarithmic total time complexity. Computing an upper boundary as lowerBound(a, x+1) would introduce an unnecessary integer overflow bug at the largest integer.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / b / Solution by

Codex  0 2026-10-31

Return the lower-bound search boundary, permitting both zero and the array length:

def lowerBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) < x) lo = mid + 1
    else hi = mid
  }
  lo
}

The precondition includes nondecreasing order. The loop invariant is

0 \leq l o \leq hi \leq n, a [0.. l o) < x, x \leq a [hi .. n) .

Initially both excluded ranges are empty. If

a (mi d) < x

, sortedness justifies excluding every position through mid; otherwise it justifies excluding every position from mid onwards. The loop variant

hi - l o

is a nonnegative integer that strictly decreases. When the old width is positive, mid is a valid array index. The midpoint expression avoids adding two potentially large indices. At exit

l o = hi

, so lo satisfies the required partition, including when

n = 0

. Each new width is at most half the old width, rounded down; this gives

O (lo g (n + 1))

time complexity and constant space, conventionally

O (lo g n)

for nontrivial sizes.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 2 / a / Solution by

Codex  0 2026-10-31

Linear search examines successive entries until a match or a stopping condition is reached; in the worst case it inspects

n

entries. Binary search uses a sorted array to discard about half of the remaining candidates after each comparison, requiring

O (lo g (n + 1))

comparisons. Its logarithmic guarantee also requires constant-cost indexed access, as supplied by an array; the same index operations on a linked list would not be constant-cost.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / d / Solution by

Codex  0 2026-10-31

Choose the reciprocal-factorial summation eb for asymptotically high accuracy, counting multiplications and divisions as arithmetic work. For tolerance

ϵ

, linear powering in part (a)(i) takes

O (ϵ^{- 1})

multiplications; binary exponentiation in part (a)(ii) reduces this to

O (lo g (1/ ϵ))

. Part (c) also has

O (lo g (1/ ϵ))

arithmetic work, since its required

n

grows like

ϵ^{- 1/2}

, though its constants and cancellation error differ.

By the reciprocal-factorial series remainder bound, the omitted positive tail satisfies

0 < e - e_{b} (n) = \sum_{j = n + 1}^{\infty} \frac{1}{j !} \leq \frac{1}{( n + 1 )!} \sum_{r = 0}^{\infty} \frac{1}{( n + 2 ) ^{r}} = \frac{n + 2}{( n + 1 ) ( n + 1 )!} .

Thus the factorial denominator grows much faster than an exponential in the number of iterations. For

d

decimal places, setting

ϵ

of order

1 0^{- d}

gives

n = Θ (d / lo g d)

by Stirling's approximation, rather than

Θ (d)

binary-power arithmetic steps. This is a comparison in an exact-arithmetic operation-count model; the stated Big O notation does not determine the exact winner for every small tolerance. Taken literally, eb uses zero multiplications and only divisions. Fixed double-precision floating-point format cannot deliver arbitrarily many correct decimal places, and the precision-dependent cost of arbitrary-precision arithmetic is a separate issue.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / c / Solution by

Codex  0 2026-10-31

First rearrange the ratios so that the intermediate powers remain moderate:

e_{c} (n) = (n + 1) (1 + \frac{1}{n})^{n} - n (1 + \frac{1}{n - 1})^{n - 1} .

This avoids separately forming enormous powers such as

n^{n}

. Perform the two instances of exponentiation by squaring in one while loop, using coupled binary exponentiation:

def ec(n: Int): Double = {
  require(n > 1)
  val dn = n.toDouble
  var x = 1.0 + 1.0 / dn
  var y = 1.0 + 1.0 / (dn - 1.0)
  var k = n
  var l = n - 1
  var p = 1.0
  var q = 1.0
  while (k > 0 || l > 0) {
    if (k > 0) {
      if ((k & 1) != 0) p *= x
      k /= 2
      if (k > 0) x *= x
    }
    if (l > 0) {
      if ((l & 1) != 0) q *= y
      l /= 2
      if (l > 0) y *= y
    }
  }
  (dn + 1.0) * p - dn * q
}

With

A = 1 + 1/ n

and

B = 1 + 1/ (n - 1)

, the loop invariant is

k, l \geq 0

p x^{k} = A^{n}

, and

q y^{l} = B^{n - 1}

. Each active branch preserves its own power identity by the parity argument in part (a)(ii), and an inactive branch changes nothing. The loop variant is the mathematical integer

k + l

, which need not be computed in a fixed-width variable: it decreases whenever either exponent is positive. At exit

p = A^{n}

q = B^{n - 1}

, proving the returned expression is $e_{c} (n)$ . There are

O (lo g n)

iterations, at most four loop multiplications each, and two final multiplications. Converting n before adding one avoids integer overflow at Int.MaxValue.

The rearrangement avoids floating-point overflow in the original powers, but subtraction still combines two quantities of order

n

to obtain one of order one. Catastrophic cancellation can amplify their accumulated roundoff error. The mathematical

O (n^{- 2})

approximation error therefore does not imply that the Double implementation improves indefinitely as n grows.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Imperative programming / 1 / b / Solution by

Codex  0 2026-10-31

Generate each reciprocal factorial from the preceding one, instead of recomputing a factorial for every summand:

def eb(n: Int): Double = {
  require(n >= 0)
  var i = 0
  var term = 1.0
  var sum = 1.0
  while (i < n) {
    i += 1
    term /= i.toDouble
    sum += term
  }
  sum
}

The loop invariant is

0 \leq i \leq n

t er m = 1/ i!

, and

s u m = \sum_{j = 0}^{i} 1/ j!

. Initially

i = 0

and

0! = 1

. The division produces

1/ (i + 1)!

, which is then added to the previous partial sum. The loop variant is

n - i

. Consequently the returned value is $e_{b} (n)$ , using exactly

n

divisions and

n

additions, no multiplications, and

O (n)

time complexity. The slightly weaker precondition also permits the useful zero-term boundary case. For Double, small positive terms eventually cease to change sum because of floating-point rounding.