Source paper: released examination archive, member 2018/T/a10098w1.pdf. The original cover identifies the Trinity Term examination of Wednesday 19 June 2019; the archive directory does not determine its year. All eight questions are covered. Code uses Scala 2 syntax.
Accumulate the prefix by Horner's method in base two. digit-'0' converts either permitted digit to its numerical value:
var i = 0
var integerPart = 0.0
while (i < bin.length && bin(i) != '.') {
  integerPart = 2.0 * integerPart + (bin(i) - '0')
  i += 1
}
The loop invariant, in exact arithmetic, is that i is the number of processed digits before the point and
(1)
Appending a digit shifts the old positional value by one binary place and adds that digit, which proves preservation. The loop variant is . At exit, i is the binary-point index or the length if no point occurs, and integerPart is the value of the integer prefix. An empty prefix contributes zero. There is one multiplication per processed digit, with no separate powers or repeated divisions. Short-circuit evaluation prevents an out-of-range access when the point is absent.
For Double, this exact-arithmetic invariant describes the intended value; the operational value is the rounded Horner recurrence. Very long prefixes can lose precision or overflow, as discussed in part (g). A fixed-width return type cannot represent every finite binary digit string exactly.
Let point be the known point index. Work backwards so that each step uses just one division, rather than separately computing positional weights:
var j = bin.length - 1
var fractionalPart = 0.0
while (j > point) {
  fractionalPart = (fractionalPart + (bin(j) - '0')) / 2.0
  j -= 1
}
The loop invariant, under exact arithmetic, is
(1)
Initially the suffix is empty. Incorporating digit and dividing by two gives exactly the same formula with replaced by . At exit , the result is . The loop variant is when a point exists. If a no-point input is handled by setting point=bin.length, the loop is skipped and the fractional contribution is zero; is a loop variant covering that convention too. Trailing zeroes and an empty fractional suffix require no special arithmetic. Floating-point rounding qualifies the exact formula for long inputs.
Represent zero by one digit. Since int_part is nonnegative, a logical right shift is exactly integer division by two:
var digits = 1
var scratch = int_part
while (scratch >= 2) {
  scratch = scratch >>> 1
  digits += 1
}
The loop invariant is and ; for positive int_part, also . The loop variant is scratch, strictly decreased whenever the guard holds. On exit, a positive input has , yielding . Therefore digits is the required width, including width one for zero. Shifting avoids an explicit multiplication or division in the code. This uses the supplied assumption that dec.toInt really is the mathematical floor; saturating or invalid conversions are not covered by that assumption.
Extract low bits and fill the integer positions from right to left:
var remaining = int_part
var pos = digits - 1
while (pos >= 0) {
  res(pos) = if ((remaining & 1) == 0) '0' else '1'
  remaining = remaining >>> 1
  pos -= 1
}
At the start of an iteration, the loop invariant says that positions contain the correct low bits and
(1)
The bitwise AND extracts the remainder modulo two; the shift supplies its quotient. These two facts preserve the loop invariant. The loop variant is . The width established in part (c) ensures that remaining is zero at exit, so the first digits entries encode the whole integer part. For zero the single entry becomes '0'. There are no explicit multiplications or divisions, and no extra digit array is needed.
Generate the fractional bits by repeated doubling, keeping only the unconverted residual:
res(digits) = '.'
var fraction = dec - int_part.toDouble
var out = digits + 1
while (out < res.length) {
  fraction = 2.0 * fraction
  if (fraction >= 1.0) {
    res(out) = '1'
    fraction -= 1.0
  } else res(out) = '0'
  out += 1
}
Let and . The loop invariant is , the first fractional digits have been written, and, in exact arithmetic,
(1)
Doubling exposes the next digit, and subtracting that digit leaves the next residual in . This proves preservation. The loop variant is . The loop fills the whole suffix, even when the residual has become zero; subsequent bits are zero. There is one multiplication per output bit. With fractional positions, the result is truncated, with exact-arithmetic error . An integer has an all-zero suffix. No rounding-up step is performed.
Equivalence partitioning divides the input domain into classes expected to exercise the same relevant behavior, then chooses representatives and boundary cases from each class. It is a way to select tests, not a proof that every member of a class must behave identically in a faulty implementation.
Useful classes for this parser include integer-only inputs, a leading point, a trailing point, and digits on both sides; all-zero inputs and inputs containing ones; leading or trailing zeroes; one-digit and longer blocks; and large integer or tiny fractional magnitudes near floating-point rounding, floating-point overflow and floating-point underflow boundaries. For instance, compare '1', '1.', '.1', '1.1', '0001.1000', and digit strings just beyond the exact integer precision of Double. Empty digit blocks have the zero convention used above. If a surrounding validator rejects an entirely empty representation or a bare point, test those as separate invalid-format classes. Unexpected digits and multiple points are likewise validator tests, since the conversion fragments assume well-formed input. Include representatives with independently calculated positional values, rather than relying only on inverse conversion.
The first proposed identity can fail even without numerical error because binary fractions have nonunique textual representations. Leading zeroes, optional points and trailing fractional zeroes are normalized differently by a fixed-width output convention. It also fails if the input has more significant bits than Double can preserve, more fractional places than the output buffer can hold, an integer part outside the assumed Int range, or a value that overflows or underflows during decoding. Array identity here must mean equal contents: a newly allocated Scala array is a different software object, so use sameElements rather than reference equality for a content test.
The second identity fails when the stored fractional precision truncates a nonzero bit; with two fractional places, becomes zero. It can also fail outside the finite nonnegative input and integer-conversion assumptions. Within those assumptions, enough fractional positions to encode the finite Double exactly can permit the round trip, but an arbitrary fixed small width does not guarantee it. Every finite Double has a finite binary expansion; saying that a decimal-looking Double necessarily has an infinite binary expansion would confuse the represented number with an exact decimal real.
The source's introductory example is internally inconsistent: the displayed digit string has value , whereas its shortened character array encodes . The conversion rules above follow the actual input digits. Round-trip testing needs an independent value oracle as well as the two compositions, because two mutually consistent but incorrect routines can conceal each other's errors.
Compare values directly, avoiding subtraction that could overflow:
def bestIndex(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  val first = l
  val middle = l + (r - l) / 2
  val last = r - 1
  if (a(first) <= a(middle)) {
    if (a(middle) <= a(last)) middle
    else if (a(first) <= a(last)) last
    else first
  } else {
    if (a(first) <= a(last)) first
    else if (a(middle) <= a(last)) last
    else middle
  }
}
Each branch returns an index whose value lies between the other two sampled values. Non-strict comparisons make ties harmless. The precondition is a nonempty valid segment, not a segment of at least three elements: for lengths one or two some sample indices coincide, but the code still returns a valid median of the sampled triple. This matters because selection can reach a two-element segment. With three distinct sample values, the pivot is not the minimum or maximum of the whole segment, but it need not be near the segment's true median. Median-of-three pivot selection is a heuristic, not a balance guarantee.
Set aside the selected pivot at the end, array partitioning the other entries, then move the pivot to the separation index:
def partition(l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  def swap(i: Int, j: Int): Unit = {
    val t = a(i); a(i) = a(j); a(j) = t
  }
  val chosen = bestIndex(l, r)
  val x = a(chosen)
  swap(chosen, r - 1)
  var p = l
  var j = l
  while (j < r - 1) {
    if (a(j) < x) {
      swap(p, j)
      p += 1
    }
    j += 1
  }
  swap(p, r - 1)
  p
}
The loop invariant is , , , and . The segment's multiset is unchanged and all entries outside it are unchanged. A low entry is swapped into the low segment; a high entry simply extends the high segment. The loop variant is . At exit, exchanging the reserved pivot with a(p) gives , , and . The displaced value at the old pivot position was already at least . Length one is handled by self-swaps and an empty loop. Duplicate pivot values belong to the high side. This costs time and auxiliary space.
Ranks are relative to the current segment. The pivot's rank is p-l, not its absolute index:
def select(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  if (r - l == 1) a(l)
  else {
    val p = partition(l, r)
    val rank = p - l
    if (k == rank) a(p)
    else if (k < rank) select(k, l, p)
    else select(k - rank - 1, p + 1, r)
  }
}
The array partitioning places exactly rank strictly smaller entries before the pivot, with all later entries at least the pivot. Thus the pivot is the element of sorted rank rank, even when equal values occur later. A requested earlier rank is unchanged in the left segment; a later rank loses the low entries and the pivot, accounting for the subtraction rank+1. The recursive segment is nonempty in either branch that takes it, and its length strictly decreases. Induction on segment length therefore proves the returned value is the requested order statistic, with at most one recursive call. Only the selected segment is permuted; all outside entries remain unchanged. This is Quickselect.
Replace the tail call by updates to local bounds and a local rank:
def selectIterative(k: Int, l: Int, r: Int): Int = {
  require(0 <= l && l < r && r <= a.length)
  require(0 <= k && k < r - l)
  var low = l
  var high = r
  var rank = k
  while (high - low > 1) {
    val p = partition(low, high)
    val pivotRank = p - low
    if (rank == pivotRank) return a(p)
    if (rank < pivotRank) high = p
    else {
      rank -= pivotRank + 1
      low = p + 1
    }
  }
  a(low)
}
The loop invariant says that , , and selecting rank rank in the active segment yields the originally requested order statistic. The original segment's multiset is preserved, and outside it no entries change. The updates are exactly the recursive reductions proved in part (c). The loop variant is ; a non-returning iteration strictly decreases it. A one-entry segment has only rank zero, establishing the final return. Auxiliary space is , rather than a potentially deep call stack.
Test singleton and two-element segments, first/last/interior requested ranks, nonzero segment offsets, already sorted and reversed inputs, random inputs, all-equal inputs and several patterns of duplicates. Include Int.MinValue and Int.MaxValue to expose overflow-prone comparisons. An independent sorted copy supplies the value oracle; also check preservation of the segment's multiset and of all outside entries. For speed tests, increase segment size and include deliberately unfavorable pivot arrangements, rather than timing random inputs alone.
Distinct entries do not guarantee linear worst-case time: the worst case is . A median of three can repeatedly be the second-smallest remaining value, leaving a segment of size when seeking its maximum. The quadratic median-of-three selection family gives explicit distinct inputs realizing this behavior for the implementation above; one six-entry member is . Its recurrence is , yielding a quadratic sum. Balanced reductions instead give . Randomized or suitable average-case analyses give expected linear selection, but this deterministic heuristic alone supplies no such worst-case guarantee. Unlike Quicksort, Quickselect explores only one side, so a balanced run is linear rather than .
The first three subtractions are negative or return the already-seen zero, so addition is used. The fourth subtraction gives a new positive two; the next subtraction is negative. Thus . These are the initial terms of Recamán's sequence.[ref]
Use the already-filled prefix itself for membership tests. Long intermediates avoid overflow in the candidate calculations, while a checked conversion respects the required output type:
def recaman(a: Array[Int]): Unit = {
  if (a.length == 0) return
  a(0) = 0
  var i = 1
  while (i < a.length) {
    val candidate = a(i - 1).toLong - i.toLong
    var j = 0
    while (candidate > 0L && j < i && a(j).toLong != candidate) {
      j += 1
    }
    val next =
      if (candidate > 0L && j == i) candidate
      else a(i - 1).toLong + i.toLong
    require(next <= Int.MaxValue.toLong, "Sequence value exceeds Int")
    a(i) = next.toInt
    i += 1
  }
}
The outer loop invariant is and for . The inner loop invariant says that and no processed entry before j equals the positive candidate. Its guard either reaches the end of the prefix, finds the candidate, or immediately rejects a nonpositive candidate. Its loop variant is . This establishes exactly the choice required by the recurrence, so the outer loop invariant is preserved. The outer loop variant is .
Extra storage is beyond the supplied result array. Membership scans give an upper bound for output entries. Addition, unlike the subtraction branch, is not required to avoid repeats: at indices and the value occurs twice. The code therefore does not try to enforce global distinctness. If an exact value eventually exceeds Int, the output interface cannot hold it; the check reports that limitation rather than wrapping the recurrence.
Regardless of which branch is taken, . Starting from zero and applying induction gives
(1)
For the inductive step, add to the bound for the previous value. The subtraction branch gives an even smaller result, and positivity is checked there. This bound need not describe the actual growth sharply; it is sufficient to size a finite membership representation for a requested prefix.
Let denote the entry state. A conventional meaning for the Boolean returned by add is whether the call changes the set:
// add(elem):
//   S' = S0 union {elem}
//   result == !S0.contains(elem)

// contains(elem):
//   S' = S0
//   result == S0.contains(elem)

// size:
//   S' = S0
//   result == cardinality(S0)
Initially . In particular, re-adding an existing element returns false and does not increase the size. All operations have the stated empty precondition at the abstract level. The comment that add adds an element does not itself completely specify its Boolean result; the explicit changed/not-changed convention above completes that contract. As with any Int-valued size operation, exact cardinalities are understood to be representable by that result type.
Represent the characteristic values of a bounded universe by one Boolean slot per possible member, a Boolean-array form of a bitset:
class BitMapSet(val MAXVALUE: Int) extends IntSet {
  require(MAXVALUE >= 0)
  private val bits = Array.fill(MAXVALUE)(false)
  private var count = 0

  def contains(elem: Int): Boolean =
    0 <= elem && elem < MAXVALUE && bits(elem)

  def add(elem: Int): Boolean = {
    require(0 <= elem && elem < MAXVALUE, "Outside bitmap universe")
    if (bits(elem)) false
    else {
      bits(elem) = true
      count += 1
      true
    }
  }

  def size: Int = count
}
The abstraction function is . The representation invariant is that bits.length==MAXVALUE, its entries are Boolean, and count equals the number of true entries. Initialization gives the empty set; changing a false entry to true adds exactly its index and increments the count once. A repeated addition preserves both. All three operations have time complexity after initialization; storage and explicit array initialization are .
The constructor requires , and add requires . contains remains total by returning false outside the representable universe; short-circuit evaluation protects the index. This finite representation cannot implement unrestricted addition of every Int while preserving the abstract contract. Its strengthened add precondition therefore makes it a restricted implementation, not a behaviorally substitutable implementation of the unrestricted trait for arbitrary clients. The sequence client below proves that it stays within the restricted universe.
For result entries the largest required index is , so the bound in part (a)(iii) permits universe size . Check that the chosen universe can itself be expressed as an array length:
def recamanBitmap(a: Array[Int]): Unit = {
  val n = a.length
  if (n == 0) return
  val capacity = n.toLong * (n.toLong - 1L) / 2L + 1L
  require(capacity <= Int.MaxValue.toLong, "Bitmap universe too large")
  val seen = new BitMapSet(capacity.toInt)
  a(0) = 0
  seen.add(0)
  var i = 1
  while (i < n) {
    val candidate = a(i - 1).toLong - i.toLong
    val next =
      if (candidate > 0L && !seen.contains(candidate.toInt)) candidate
      else a(i - 1).toLong + i.toLong
    a(i) = next.toInt
    seen.add(a(i))
    i += 1
  }
}
The loop invariant is that the result prefix contains exactly and the abstraction function of seen is their set of values. The universe bound ensures that each positive candidate being queried and each actual next value is less than capacity; values are nonnegative. Thus the conversions and the restricted add precondition are justified, rather than merely hoped to succeed. At a repeated addition, add returning false is harmless: the set of previously seen values is still updated correctly. The loop variant is . At return every result entry agrees with the original recurrence.
The original routine uses auxiliary space and at most membership work. A bitmap with universe size uses extra storage and work in the sequence-generation loop because membership and insertion each take constant time. Here the safe universal bound chooses , so extra storage is for growing .
Initialization must be accounted for separately: creating and clearing a Boolean array of length takes work in the usual array-initialization model. Consequently the complete one-shot routine takes , which is with this conservative universe bound. The faster lookup does not make that quadratic setup disappear. If the bitmap is already initialized, or the analysis explicitly charges only the generation phase, the remaining phase is linear. A tighter known bound on values can reduce the universe cost, but no unproved growth bound is needed here.
A fixed array containing the distinct seen integers needs capacity at most , because at most one new distinct value is introduced per result entry. Its auxiliary space is therefore , rather than the bitmap's universe storage. A size field identifies the occupied prefix; insertion first checks membership, and appends only when absent.
An unsorted occupied prefix needs linear membership scans, giving total work by the same summation as in the original version. Keeping it sorted permits binary search membership in , but inserting a new value can shift entries, so the overall worst-case upper bound remains quadratic. Unlike a bitmap, the space cost depends on the number of stored values rather than their largest possible numerical magnitude. Compared with part (a)(ii), this extra set array also duplicates information already present in the output prefix; its principal benefit is a separate set interface, not an automatic asymptotic speedup.
Check entries against their own indices, stopping on the first mismatch:
def isIdentity: Boolean = {
  var i = 0
  while (i < game.length && game(i) == i) {
    i += 1
  }
  i == game.length
}
The loop invariant is and for every . The loop variant is . A false guard means either every position has passed or the next position is wrong, so the returned Boolean is true exactly for the identity permutation. Neither the game nor its history is changed. Short-circuit evaluation protects the final indexed comparison.
Allocate a distinct game and copy every destination entry from the corresponding source position:
def flip(k: Int): Flip = {
  require(1 < k && k <= game.length)
  val result = new Flip(game.length)
  var i = 0
  while (i < game.length) {
    val source = if (i < k) k - 1 - i else i
    result.game(i) = game(source)
    i += 1
  }
  result.flips = k :: flips
  result
}
The loop invariant says that the receiver is unchanged and destination positions before i equal the reversal of the first source entries followed by the untouched suffix. The loop variant is . At exit the copying is complete. Reversal is a bijection on positions, so the destination remains a permutation. The returned object's array is independent of the receiver's array, while the immutable tail of its history list can safely be shared. The source's only supplied constructor randomizes the new array before the copy; that work is redundant but does not affect correctness. An additional private constructor could avoid it without changing the required result.
The history is built by prepending, so reverse it when displaying chronological moves:
override def toString: String =
  game.mkString("[", ", ", "]") +
    "    history of flips: " + flips.reverse.toString
Thus a reverse-stored history [3,2,4] is displayed as List(4, 2, 3). The initial empty history remains List(). Neither traversal mutates the game or the immutable history. Displaying the stored list without reversing it would describe the moves backwards.
Use breadth-first search with the supplied FIFO queue, taking one edge to mean one permitted prefix reversal:
def solve(puzzle: Flip): Flip = {
  val pending = scala.collection.mutable.Queue[Flip]()
  pending.enqueue(puzzle)
  while (!pending.isEmpty) {
    val current = pending.dequeue()
    if (current.isIdentity) return current
    var k = 2L
    while (k <= current.game.length.toLong) {
      pending.enqueue(current.flip(k.toInt))
      k += 1L
    }
  }
  throw new IllegalStateException("No solution")
}

val puzzle = new Flip(n)
println("Solving:")
println(puzzle)
val answer = solve(puzzle)
println("Solved:")
println(answer)
The FIFO queue holds pending paths in nondecreasing history length. Initially it holds only the zero-move path. Removing a path at depth and appending its children at depth preserves that order. The inner loop invariant says that precisely moves of the removed state have been appended; its loop variant is while the guard holds. The first identity state removed therefore has the minimum possible number of moves. A stack-based depth-first search does not generally have that property.
Termination does not rely on avoiding repeats in this first version. Every permutation can be sorted by prefix reversal sorting: place the largest misplaced value at the front if necessary, flip it into its final position, and repeat on the shorter prefix. This constructs a route of at most moves. Each search depth has finitely many paths, with at most children per path, so breadth-first search reaches some solution depth after finitely many expansions. This gives a finite bound on remaining expansions before the first solution even though the repeated-state path tree is infinite. The one-element game is already solved. Repeated paths can nevertheless make time and storage enormous; part (e) removes that waste.
Give each solving session a shared visited set keyed by immutable snapshots of permutation contents, for example game.toList, and insert the initial snapshot immediately. Have all successor objects refer to that same session's set. The refined flip first constructs the candidate state; if its key is present, return None. Otherwise add the key immediately and return Some(candidate). The search enqueues only Some results. Keys must compare contents rather than array identities, and a fresh solving session must start with a fresh visited set.
Marking at generation time prevents the same state from being queued repeatedly, including the immediate cycle made by applying the same reversal twice. First discovery in breadth-first search already has minimum depth, so discarding later discoveries cannot remove a shorter solution. The graph now has at most admitted states. If only cycles along one path were to be rejected, a path-local set would suffice, but it would still repeat states reached by different paths; the shared session-wide set avoids both kinds of repetition. Public game fields must not be externally mutated while their states are being searched.
The abstract state is a finite multiset of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent total order on T.
trait PriorityQueue[T] {
  // Pre: true. Post: Q' is the empty multiset.
  def clear(): Unit

  // Pre: true. Post: Q' = Q with one additional occurrence of x.
  def insert(x: T): Unit

  // Pre: Q is nonempty.
  // Post: result is a minimum of Q;
  //       Q' is Q with exactly one occurrence of result removed.
  def delMin(): T

  // Pre: true. Post: result iff Q is empty, and Q' = Q.
  def isEmpty(): Boolean
}
This abstract data type places no fixed-capacity bound on insertion. The only operation requiring a nonempty collection is delMin. The representation must preserve duplicates even if it uses a data structure commonly associated with sets.
Yes, provided balancing guarantees logarithmic height. In a suitably maintained balanced binary tree of height , insertion searches one root-to-leaf path and deletion of the minimum follows the leftmost path. Reconnecting the tree and performing the required rebalancing also costs at most a constant amount per level for the standard logarithmic-time schemes. Thus both operations take time, conventionally written for nontrivial sizes. Merely calling a tree approximately balanced would not prove that height bound; it is the balancing guarantee that matters. Without it, a binary search tree can have linear height.
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.
A minimum-oriented binary heap is an appropriate alternative. Store a complete binary tree in an array and maintain heap order. Insertion appends a value and moves it upward; removing the root replaces it by the last value and moves that value downward. Each path has levels, and equal values can be stored in separate slots. Both operations therefore take time when capacity is available.
Unlike a binary search tree, the heap does not maintain a complete search order, so finding an arbitrary specified value can require inspections. A simple array implementation also has a capacity issue: a fixed array can fill, and resizing a growable array occasionally costs , giving an amortized insertion guarantee unless allocation is otherwise managed. This capacity cost is an implementation tradeoff, not an inherent inability of heaps to represent the priority queue abstraction.
Use one real linked list node per occurrence, with a private reference to the first:
class Node(val value: Int, var next: Node)

// Inside the queue implementation:
private var first: Node = null
The representation invariant says that the reachable chain is finite, acyclic and nondecreasing in value, and is owned by the queue. Equal adjacent values are explicitly allowed. The abstraction function is the multiset containing one occurrence of v.value for every reachable real linked list node v. Initially first==null represents the empty multiset. No artificial smallest Int is needed as a sentinel, and Int.MinValue remains a valid real value.
Insert before the first entry that is at least the new value; equal values remain separate occurrences:
class ListPriorityQueue extends PriorityQueue[Int] {
  private var first: Node = null

  def clear(): Unit = { first = null }

  def isEmpty(): Boolean = first == null

  def insert(x: Int): Unit = {
    if (first == null || x <= first.value) {
      first = new Node(x, first)
    } else {
      var p = first
      while (p.next != null && p.next.value < x) {
        p = p.next
      }
      p.next = new Node(x, p.next)
    }
  }

  def delMin(): Int = {
    require(first != null, "Empty priority queue")
    val result = first.value
    first = first.next
    result
  }
}
In the scanning branch, the loop invariant says that p is reachable and all values from first through p are strictly smaller than x. The rest of the chain is unchanged and remains sorted. The loop variant is the number of nodes after p. At exit either the next value is at least x or there is no next node, so inserting between p and p.next preserves the representation invariant and adds exactly one occurrence under the abstraction function. The head branch covers an empty chain, a new minimum and equality with the old minimum. delMin returns the head's minimum value and removes exactly that occurrence.
Insertion is worst-case; delMin, isEmpty and the head-resetting clear are . Reclaiming an abandoned chain later is garbage-collection work, not an explicit traversal performed by clear. Storage is , including separate nodes for duplicate values. No fixed insertion-capacity precondition has been added.
The Iterator pattern gives clients a uniform way to inspect and consume the elements of a collection without exposing how that collection is stored. An iterator has a traversal state separate from the abstract collection interface, so the same client loop can process an array, a linked list or generated values. It preserves encapsulation and representation independence: changing the underlying data structure need not change the traversal client. Separate iterator instances can track separate traversals; two aliases of one consuming iterator instead share its progress.
The essential abstract methods are:
def hasNext: Boolean
def next(): T
hasNext reports whether another result is available. next() returns that result and advances; if exhausted, it throws NoSuchElementException. The other ordinary iterator operations are implemented using these primitives. An availability check must not silently discard a result visible to the client, although an adapter may need to fetch and cache underlying values in order to decide availability.[ref]
The plus marks a covariant type parameter: if , then Iterator[S] <: Iterator[T]. An iterator producing a subtype's values can be used where an iterator of the supertype is required. For example, a string iterator can be viewed as an iterator of AnyRef, because strings are reference values. The direction is appropriate for a producer: calling next() gives a value valid at the wider type. It would not be safe to expose an ordinary insertion method accepting arbitrary wider-type values into a subtype-only collection. This is a subtyping relationship, not a request to transform each produced value.[ref]
Use iterator concatenation and short-circuit the second availability test while the first iterator still has results:
class ConcatIterator[T](first: Iterator[T], second: Iterator[T])
    extends Iterator[T] {
  def hasNext: Boolean = first.hasNext || second.hasNext

  def next(): T = {
    if (first.hasNext) first.next()
    else second.next()
  }
}
The abstract remaining sequence is the remaining sequence of first followed by that of second. Each next() consumes the head of precisely this sequence. When both are exhausted, delegation to second.next() raises the required exception. Construction consumes no elements, and hasNext never calls either underlying next(). As usual, clients should not separately consume these iterators while relying on the adapter's traversal. Sharing one underlying iterator between both arguments also shares its state; it does not duplicate its elements.
The expression constructs a valid iterator object; it does not itself return the concatenated numeric or character values. The element types have a common supertype AnyVal, and covariance lets Iterator[Int] and Iterator[Char] serve as the two inputs to ConcatIterator[AnyVal]. In the ordinary Scala 2 typing of this expression, the common element type is AnyVal. One can make the intended widening explicit:
new ConcatIterator[AnyVal](
  List(1, 2, 3).iterator,
  List('a', 'b', 'c').iterator
)
Successive calls return 1, 2, 3, 'a', 'b', 'c', then exhaustion. Characters remain characters: viewing an existing iterator at a wider type does not convert its contents to integer character codes. No next() is invoked merely by constructing this adapter. The common-type argument uses subtype polymorphism and covariant type parameters, rather than requiring the two concrete input types to be equal.
Use one cached optional result. Only a request for availability or the next result fills that cache:
class FilterIterator[T](test: T => Boolean, iter: Iterator[T])
    extends Iterator[T] {
  private var cached: Option[T] = None

  private def prepare(): Unit = {
    while (cached.isEmpty && iter.hasNext) {
      val x = iter.next()
      if (test(x)) cached = Some(x)
    }
  }

  def hasNext: Boolean = {
    prepare()
    cached.nonEmpty
  }

  def next(): T = {
    prepare()
    cached match {
      case Some(x) =>
        cached = None
        x
      case None => throw new NoSuchElementException("Filtered iterator exhausted")
    }
  }
}
This is a demand-driven filtering iterator. When the cache is empty, its abstract remaining sequence is the filtered remaining input. When it holds Some(x), the abstract sequence is x followed by the filtered remaining input. The loop invariant for prepare says that all input elements consumed during the present search have failed test, except for the one cached passing value if one has been found. The first passing value stops the loop, so it cannot read past a result that the client has not yet consumed.
Construction performs no underlying reads, and repeated hasNext calls reuse a cached result. next also works without a preceding hasNext, clears only the result it returns, and does not prefetch its successor. Some(x), rather than Option(x), allows a passing null value to remain a genuine cached value. For finite remaining input, its length is a loop variant; for infinite input, availability can legitimately run forever if no further passing element exists. Deterministic terminating tests and exclusive ownership of the consuming input are assumed. One cache slot is extra storage.
Make two separate character iterators so that scanning uppercase letters does not consume the lowercase pass:
def upperLower(s: String): Iterator[Char] = {
  val upper = new FilterIterator[Char]((c: Char) => c.isUpper, s.iterator)
  val lower = new FilterIterator[Char]((c: Char) => c.isLower, s.iterator)
  new ConcatIterator[Char](upper, lower)
}
Each filtering iterator preserves the original order of its selected characters. Concatenation therefore yields all uppercase letters in source order, then all lowercase letters in source order, omitting other characters. The two s.iterator calls are essential: reusing a single consuming iterator would let the first pass discard lowercase characters before the second pass could return them. Construction remains lazy; an empty string yields an exhausted iterator without a special case.
Encapsulation exposes operations with contracts while hiding representation details and controlling changes to state. In a text editor, a document object can privately store text and cursor position and expose insert, delete and moveCursor. Clients cannot directly splice internal storage or set a cursor outside the document. The document's methods enforce its representation invariant, and the implementation can later replace a character array by a different text representation without changing the public editing interface. Merely declaring a field private is insufficient if an accessor returns the mutable representation itself.
Class inheritance defines a subclass by extending another class's behavior, often with method overriding and subtyping. An editor might have an abstract Command type with execute, and subclasses for insertion and deletion. The controller keeps commands through the common type and dynamic dispatch chooses each command's actual operation. Alternatively, a specialized document can extend a base document's documented behavior. An inheritance relationship used for substitution must preserve the superclass contract; borrowing its code alone does not justify exposing incompatible behavior. Commands exemplify the Command pattern without exposing document storage to the controller.
The constructor stores a reference, not a copy:
val d = new Dimension(3, 4)
val f = new Frame(d)
d.width = 10
Now f.area is still , but the product of its stored dimension fields is . Even without retaining d, a client can break the same invariant through f.dimension.height = 9, because the accessor exposes the same mutable object. This is representation exposure through reference aliasing. A val prevents reassigning the reference; it does not freeze the referenced object.
Make defensive copies on both entry and exit, while keeping the supplied Dimension class unchanged:
class Frame(d: Dimension) {
  require(d != null)
  private val saved = new Dimension(d.width, d.height)
  private val savedArea = saved.width * saved.height

  def area: Int = savedArea
  def dimension: Dimension = new Dimension(saved.width, saved.height)
  def isPortrait: Boolean = saved.height >= saved.width
}
The private stored dimensions have no aliases exposed to the caller and are never changed. Mutating the constructor argument affects only the caller's object; mutating a returned Dimension affects only a fresh copy. Consequently the stored area is calculated once and stays equal to the stored dimensions' product. This defensive copying is sufficient because Dimension contains only primitive fields; a more deeply nested mutable structure could require a deep copy or an immutable representation.
The multiplication above deliberately retains the supplied class's Int arithmetic and accessor type. If an exact mathematical area outside that range is required, compute once with saved.width.toLong * saved.height.toLong and expose Long instead; avoiding aliases and avoiding integer overflow are separate concerns.
Compare areas before and after each completed setter call. Widen before multiplication so all products of two Int dimensions are represented exactly:
class LoggedResizableFrame(h: Int, w: Int) extends ResizableFrame(h, w) {
  private var increases = BigInt(0)

  private def actualArea: Long = height.toLong * width.toLong

  override def height_=(h: Int): Unit = {
    val before = actualArea
    super.height_=(h)
    if (actualArea > before) increases += 1
  }

  override def width_=(w: Int): Unit = {
    val before = actualArea
    super.width_=(w)
    if (actualArea > before) increases += 1
  }

  def getIncreases: BigInt = increases
}
The history invariant is that increases counts exactly the completed dimension updates whose new area strictly exceeds their immediately preceding area. The constructor's starting area is a baseline, not an increase. Each overriding setter invokes the superclass setter once and increments precisely when its comparison succeeds. Equal-area changes do not count. The comparison is on area, not merely on which dimension increased; this also handles zero or signed dimensions without adding an unstated input restriction. An arbitrary-precision integer avoids eventual counter overflow.
Articles were limited to the first 100 out of 112 total.

Ancestors (9)

  1. 2019
  2. Past exam of the year 1 of the computer science course of the University of Oxford
  3. Year 1 of the computer science course of the University of Oxford
  4. Computer science course of the University of Oxford
  5. Undergraduate course of the University of Oxford
  6. Course of the University of Oxford
  7. University of Oxford
  8. List of universities
  9. Home

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version