Source paper: released examination archive, member 2018/L/a10098w1.pdf. The cover identifies the Long Vacation sitting of Thursday 5 September 2019. That printed identity takes precedence over the archive member's directory name.
The implementations use Scala 2 syntax. Fixed-width results are checked when arbitrary-precision arithmetic is needed internally; the mathematical contracts do not make integer overflow harmless. All eight questions are covered.
Use the remainder form of the Euclidean algorithm to compute the greatest common divisor, then divide both components of the fraction by it:
def Reduce(num: Int, den: Int): (Int, Int) = {
  require(0 <= num && num < den)
  var a = den
  var b = num
  while (b != 0) {
    val r = a % b
    a = b
    b = r
  }
  (num / a, den / a)
}
The loop invariant is , , and . Initially it holds by symmetry of the greatest common divisor. For , the integer division identity , with , shows that and have exactly the same common integer divisors. Thus the update preserves the loop invariant. The loop variant is the nonnegative integer , which strictly decreases on each iteration. At exit , so . Dividing by preserves the rational number and makes the returned components coprime. In particular, zero is returned as . No multiplication is needed, and all remainders remain within the original nonnegative Int range.
For a positive remaining fraction , the condition is equivalent to . Since decreases as the positive integer increases, choose . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.
The remaining fraction is
(1)
The defining inequalities give . Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.
Maintain an accumulated array of denominators and an exact remaining fraction. The usual greedy algorithm can require a denominator larger than Int.MaxValue, even for an input with Int components. The following implementation uses arbitrary-precision integers internally. If that representational limit is reached, it returns the always-valid alternative consisting of num copies of . Repeated denominators are permitted by the given Egyptian fraction representation.
def fromRat(num: Int, den: Int): Array[Int] = {
  require(0 <= num && num < den)
  val start = Reduce(num, den)
  var n = BigInt(start._1)
  var d = BigInt(start._2)
  var e = Array.empty[Int]
  while (n > 0) {
    val q = (d + n - 1) / n
    if (!q.isValidInt) return Array.fill(num)(den)
    e = e :+ q.toInt
    val nextN = n * q - d
    val nextD = d * q
    val g = nextN.gcd(nextD)
    n = nextN / g
    d = nextD / g
  }
  e
}
The loop invariant is , , all entries of e are positive, and
(1)
Appending and replacing the residual by preserves this equality; division by the greatest common divisor preserves the residual's value. The loop variant is , by the proof in part (b). If nextN is zero, its greatest common divisor with nextD is nextD, giving residual . On normal exit the residual is zero and the returned array has exactly the required value. On the early-return branch, num copies of have that same value directly; the partial greedy Egyptian fraction expansion is discarded. num=0 returns an empty array.
The fallback is a correctness provision for the fixed result type, not an efficiency claim: a large repeated-term array can be impractical. An array of arbitrary-precision integers would retain the greedy Egyptian fraction expansion without this fallback. Allocation, as with any output-producing program, requires enough available memory. The BigInt remainder, greatest common divisor and checked conversion operations are documented in [ref].
An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only Reduce on every intermediate value. First define an exact helper:
def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
  var n = BigInt(0)
  var d = BigInt(1)
  var i = 0
  while (i < e.length) {
    require(e(i) > 0)
    val x = BigInt(e(i))
    val g = d.gcd(x)
    val nextN = n * (x / g) + d / g
    val nextD = d * (x / g)
    val h = nextN.gcd(nextD)
    n = nextN / h
    d = nextD / h
    i += 1
  }
  (n, d)
}

def toRat(e: Array[Int]): (Int, Int) = {
  val result = toRatExact(e)
  require(result._1.isValidInt && result._2.isValidInt,
          "Reduced result does not fit (Int, Int)")
  (result._1.toInt, result._2.toInt)
}
The loop invariant is , , , , and
(1)
Writing , the fraction for the extended prefix has numerator and denominator . These are the nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is . At exit the helper returns the exact sum in lowest terms, including for the empty array.
There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits (Int, Int). For example, the sum is in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.[ref]
Print separators before all but the first term, so there is neither a leading nor a trailing plus sign:
def printRat(num: Int, den: Int): Unit = {
  print(num.toString + "/" + den.toString)
}

def printEgypt(e: Array[Int]): Unit = {
  if (e.isEmpty) print("0")
  var i = 0
  while (i < e.length) {
    if (i > 0) print(" + ")
    print("1/" + e(i).toString)
    i += 1
  }
}
The loop invariant says that exactly the first unit fractions have been printed in order, separated by + , with no trailing separator. The loop variant is . The empty array is displayed as zero. Since and , the output is 5/7 = 1/2 + 1/5 + 1/70. The source's earlier example with middle denominator and final denominator contains the arithmetic typo; its final printing example is correct. Indeed , so no positive final term could repair that particular prefix. The printing routine reports the generated terms rather than imposing a particular expansion.
Let a be the given enclosing array. A two-way array partition needs only one scan, and does not require the pivot to occur in the array:
def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= a.length)
  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 , every entry of is less than , every entry of is at least , and the segment's multiset is unchanged. Entries outside are unchanged. When a(j)<p, swapping it into position k extends the low part; if k<j, the displaced entry was in the high part and remains there after j advances. If k==j, the self-swap is harmless. The other branch simply extends the high part. The loop variant is . At exit , so the returned has the required separation property, including empty segments and arbitrarily many duplicate entries. The time complexity is and auxiliary space complexity is .
For an integer pivot , exactly entries lie in . That interval contains possible integers. If , the pigeonhole principle implies that some value in is missing. Counting occurrences rather than distinct entries only strengthens this argument: occurrences cannot cover more than distinct values.
For completeness, if the lower side contains the entire permitted value range, which already has a missing value. If , the condition is impossible. Thus the general conclusion is a missing permitted value below ; an internal pivot gives useful localization.
There are entries in , which contains possible integers. If , then . Therefore some value in is missing, again by the pigeonhole principle. This is an existence conclusion in the chosen interval, not a claim that all missing values lie there; both sides can contain missing values when duplicates occur.
If , the upper side contains the whole permitted range and hence a missing value. If , the condition is impossible. Outside the internal-pivot range this conclusion therefore supplies no improved localization.
Keep a deficient interval of possible values and only the array segment containing occurrences from that interval. This is missing-value search by deficient value intervals:
def missing(): Int = {
  val n = a.length
  var lo = 0L
  var hi = n.toLong + 1L
  var l = 0
  var r = n
  while (hi - lo > 1L) {
    val p = lo + (hi - lo) / 2L
    val k = partition(l, r, p.toInt)
    if ((k - l).toLong < p - lo) {
      hi = p
      r = k
    } else {
      lo = p
      l = k
    }
  }
  lo.toInt
}
The precondition is that every original entry lies in . The loop invariant is
(1)
together with: every active entry lies in , and every original occurrence with a value in that interval is in the active segment. The whole array remains a permutation of its initial contents. Initially these assertions follow from the precondition and .
After array partitioning, the low subinterval has occurrences and possible values. If it is deficient, retaining it preserves the loop invariant. Otherwise , while the original active count is strictly less than ; subtraction gives
(2)
Thus the high subinterval is deficient and retaining it also preserves the loop invariant. Discarded occurrences lie outside the new candidate interval. The loop variant is the positive integer , which strictly decreases because the midpoint is strictly internal. At exit the interval has one possible value and fewer than one occurrence, so lo is absent from the entire original array. For the loop is skipped and zero is returned. The Long value bounds avoid overflowing ; every internal pivot is at most , so its checked mathematical range fits Int.
For the time complexity, let be the interval width and its active occurrence count before iteration . The loop invariant gives , and binary search gives . Each two-way array partition costs . Until the width reaches one, the widths are bounded by , so the total scan work is bounded by a geometric series plus loop overhead: overall, hence for positive . Partitioning the full array again at every iteration would instead lose this bound. Auxiliary space complexity is .
The abstract state is a finite partial function from strings to strings, initially empty. Names and numbers below are non-null mathematical strings. store replaces an old binding if present; delete reports whether a binding existed.
trait Book {
  // Abstract state B: finite partial map String -> String; initially empty.

  // Pre: name != null && number != null.
  // Post: B' = B updated at name with number.
  def store(name: String, number: String): Unit

  // Pre: name != null && name is in dom(B).
  // Post: result = B(name), and B' = B.
  def recall(name: String): String

  // Pre: name != null.
  // Post: result iff name is in dom(B), and B' = B.
  def isInBook(name: String): Boolean

  // Pre: name != null.
  // Post: result iff name was in dom(B); B' = B with name removed.
  def delete(name: String): Boolean
}
These preconditions and postconditions specify an abstract data type, independently of any linked list. In particular, a failed deletion leaves the abstract state unchanged, and recalling a missing name is outside the operation's specified domain.
The linked list node needs mutable fields for changing a stored number and rearranging links:
class Node(var name: String, var number: String, var next: Node)
The implementation will keep its real linked list nodes private to the Book object and will not return linked list node references to clients.
A permanent dummy header node gives even the first real linked list node a predecessor. Insertion into an empty linked list and deletion or movement of its first real linked list node then use the same link updates as internal cases. The header itself represents no contact, so it also removes the need to use a real name as a special end marker. A search still needs a null-end check.
Start with a private permanent header whose next is null. Its two string fields are ignored. For a concrete state satisfying the representation invariant, define the abstraction function
(1)
The representation invariant says that the header exists, the reachable real linked list is finite and acyclic, the header is not a real reachable linked list node, all real name/number fields are non-null strings, and real names are pairwise distinct. The real linked list nodes are owned by the book, so clients cannot mutate their fields through exposed references. Distinct names ensure that the displayed relation is a partial function. The initial empty linked list has abstraction . Reordering real linked list nodes changes the representation but not the abstract book.
Search for the predecessor of the matching linked list node, or for the last linked list node if there is no match. This helper makes deletion uniform:
class LinkedBook extends Book {
  private val header = new Node("", "", null)

  // Pre: name != null.
  // Post: result is header or a real node.
  // All real nodes through result have names different from name.
  // result.next is null or has name equal to name.
  // No state is changed.
  private def findPrev(name: String): Node = {
    require(name != null)
    var p = header
    while (p.next != null && p.next.name != name) {
      p = p.next
    }
    p
  }

  def store(name: String, number: String): Unit = {
    require(name != null && number != null)
    val p = findPrev(name)
    if (p.next == null)
      p.next = new Node(name, number, null)
    else
      p.next.number = number
  }

  def recall(name: String): String = {
    require(name != null)
    val p = findPrev(name)
    require(p.next != null, "Name is not in the book")
    p.next.number
  }

  def isInBook(name: String): Boolean = {
    require(name != null)
    findPrev(name).next != null
  }

  def delete(name: String): Boolean = {
    require(name != null)
    val p = findPrev(name)
    if (p.next == null) false
    else {
      p.next = p.next.next
      true
    }
  }
}
The search loop invariant says that p is the header or a reachable real linked list node, and every real linked list node from the start through p has a name different from the requested name. The linked list has not been changed. Short-circuit evaluation protects p.next.name when the end is reached. The loop variant is the number of real linked list nodes strictly after p; finiteness and acyclicity make it a nonnegative decreasing integer. Consequently the helper's stated postcondition holds.
For store, a found name changes only its number; an absent name adds exactly one fresh binding at the end, maintaining uniqueness. For delete, unlinking the found linked list node removes exactly the requested binding; absence returns false without mutation. Both query operations preserve the abstraction function. Non-null preconditions are checked at entry; recall additionally checks membership using the one completed search, avoiding a redundant whole-list membership scan. The helper is the only additional operation and its complete behavioral contract is stated above.
Let be the number of real contacts, and suppose the requested name is at position , counting from one. The implementation above makes exactly name-equality comparisons, including the successful comparison; null checks are not string comparisons. Thus the minimum is one, when the first real contact is requested, and the maximum is , when the last is requested. The precondition excludes unsuccessful recalls and recalls on an empty book. This counts calls to string equality, not individual character inspections within each call.
Use the move-to-front heuristic. Replace only recall in LinkedBook by:
def recall(name: String): String = {
  require(name != null)
  val p = findPrev(name)
  require(p.next != null, "Name is not in the book")
  val found = p.next
  if (p ne header) {
    p.next = found.next
    found.next = header.next
    header.next = found
  }
  found.number
}
The search has the same loop invariant and loop variant as before. Detach the existing linked list node before inserting it immediately after the dummy header node. The branch for an already-first linked list node avoids linking it to itself. Every real contact still occurs exactly once with the same name/number binding, so the representation invariant and abstraction function are preserved at return. No new linked list node is allocated, and an immediate repeated recall needs one name comparison. The present recall still pays its original search cost; the gain is for later repeated access.
Treat a null reference as the empty binary tree and perform the visit before descending:
def preorderRecursive(t: Tree): Unit = {
  if (t != null) {
    println(t.datum)
    preorderRecursive(t.left)
    preorderRecursive(t.right)
  }
}
By structural induction, the empty binary tree produces the empty output. A nonempty binary tree prints its root label, then the complete preorder traversal of the left subtree, then that of the right subtree. These are exactly the required output positions. The recursion terminates on a finite binary tree because each recursive call has strictly fewer vertices. For the three-node example, the output order is . The time complexity is linear in the number of vertices, with call stack depth bounded by the height of a binary tree plus a constant.
Store the bottom of the stack at index zero and the top at the last occupied index:
class Stack {
  private val MAX = 1000
  private val data = new Array[Tree](MAX)
  private var used = 0

  // Pre: used < MAX.
  def push(t: Tree): Unit = {
    require(used < MAX, "Stack full")
    data(used) = t
    used += 1
  }

  // Pre: used > 0.
  def pop: Tree = {
    require(used > 0, "Stack empty")
    used -= 1
    val result = data(used)
    data(used) = null
    result
  }

  // Pre: true.
  def isEmpty: Boolean = used == 0
}
The representation invariant is that data.length==MAX, , and unused slots from used onwards contain null references. Occupied slots contain the stored Tree references; the stack itself need not forbid null values. The abstraction function, written with the first sequence element at the top, is
(1)
Initially this is the empty sequence. push prepends its argument, pop removes and returns the first abstract element, and isEmpty reports whether the abstract sequence is empty. These postconditions follow directly from the index changes. Clearing a popped slot avoids retaining an otherwise unused tree reference. All three operations take time. No loops are needed.
Push the right child before the left child so that the LIFO stack exposes the left child first:
def preorderIterative(t: Tree): Unit = {
  val pending = new Stack
  if (t != null) pending.push(t)
  while (!pending.isEmpty) {
    val u = pending.pop
    println(u.datum)
    if (u.right != null) pending.push(u.right)
    if (u.left != null) pending.push(u.left)
  }
}
Let be the sequence of labels in the preorder traversal of . If the abstract pending stack, top first, is , the loop invariant is that the output already printed, followed by , is the required full output. Each pending root is non-null, and its subtree is still unvisited. This is the pending-work form of explicit-stack depth-first tree traversal.
One iteration discharges the first root's own label and replaces its remaining obligation by the left subtree followed by the right subtree. The push order makes that precisely the new top-first pending order. Thus the loop invariant is preserved. The loop variant is the sum of the numbers of vertices in all pending subtrees; it decreases by exactly one per iteration, even if the number of stack entries increases. When the stack is empty there is no remaining output obligation, proving correctness and termination. This assumes a finite genuine binary tree and, as permitted, sufficient stack capacity. Each vertex is pushed and popped once, giving time and pending references for binary tree height .
For Chomp, one representation is a Boolean array occupied(y)(x) with one entry per cell. The initial board has every entry true. For the noninitial board in the figure, the sets of occupied column indices in successive rows are , , , , , ; all other entries are false.
A more compact representation is the monotone boundary representation of a grid order ideal: an array row(y) giving the number of occupied cells in row . Occupied cells in a row always form a left prefix. The initial representation is , and the illustrated noninitial representation is , indexed upwards from row zero. Its total is . These descriptions use the same coordinate orientation as the original figure; no source image is needed in the solution.
Let the abstract state be the set of occupied coordinate pairs. For the Boolean array, the abstraction function is . Its representation invariant requires an Boolean array and the downward-closure property
(1)
Thus is an order ideal for the coordinatewise partial order. Removing an upper-right rectangle preserves this property. The empty set is allowed after the losing move.
For the row-boundary array, the abstraction function and representation invariant are
(2)
The array has length . Removing at replaces each row(j) for by . Earlier rows are unchanged. This both implements the abstract removal and preserves the nonincreasing boundary.
Without a cached count, the Boolean representation takes for Count, for Legal, worst-case for Move, and for a full-grid Display. The boundary representation takes for Count, for Legal, worst-case for Move, and for the same full-grid Display. Their space complexities are respectively and . A scalar cached total makes Count in either representation if each move updates it consistently. The implementation below uses that cache with the boundary array, so it achieves constant-time Count and Legal, linear worst-case Move, and linear storage. Full-grid output still takes quadratic time because it emits quadratic many cell positions.
Use the row boundary and cache its sum. The restriction on the initial total makes the fixed Int return type of Count meaningful; Display separately checks the requested single-digit coordinate range.
class Chomps(N: Int) {
  require(N > 0 && N.toLong * N.toLong <= Int.MaxValue.toLong)
  private val row = Array.fill(N)(N)
  private var remaining = N * N

  def Count(): Int = remaining

  def Legal(x: Int, y: Int): Boolean =
    0 <= x && x < N && 0 <= y && y < N && x < row(y)

  def Move(x: Int, y: Int): Unit = {
    require(Legal(x, y))
    var j = y
    while (j < N) {
      val next = math.min(row(j), x)
      remaining -= row(j) - next
      row(j) = next
      j += 1
    }
  }

  def Display(): Unit = {
    require(N < 10)
    var y = N - 1
    while (y >= 0) {
      print(y.toString + " ")
      var x = 0
      while (x < N) {
        print(if (x < row(y)) "* " else "  ")
        x += 1
      }
      println()
      y -= 1
    }
    print("  ")
    var x = 0
    while (x < N) {
      print(x.toString + " ")
      x += 1
    }
    println()
  }
}
The additional representation invariant is . It initially holds. For Move, write for the boundary at entry. The loop invariant says that rows before are unchanged, rows from through equal , rows from onwards still equal , and remaining equals the sum of the current entries. The loop variant is . Each iteration subtracts exactly the newly removed number of cells from the cache. At exit all affected rows are truncated as required, and the nonincreasing boundary is restored. During a partially completed update it need not be nonincreasing; only the stated loop invariant, not the full externally visible representation invariant, is required internally.
For Display, the outer loop invariant says that exactly the rows with indices greater than have been printed correctly; its loop variant is . The inner loop invariant says that the current row's first cells have been emitted correctly; its loop variant is . The final labels loop has the same decreasing loop variant, and prints exactly the first column labels before each iteration. Short-circuit evaluation in Legal checks both coordinates before indexing. An illegal Move fails before changing the board.
Keep the same player until an occupied, in-range cell is supplied:
val board = new Chomps(6)
var player = 1
while (board.Count() > 0) {
  board.Display()
  var x = -1
  var y = -1
  while (!board.Legal(x, y)) {
    println("Player " + player + ": enter x, then y")
    try {
      x = scala.io.StdIn.readInt()
      y = scala.io.StdIn.readInt()
    } catch {
      case _: NumberFormatException =>
        x = -1
        y = -1
    }
    if (!board.Legal(x, y)) println("Choose an occupied cell")
  }
  board.Move(x, y)
  if (board.Count() == 0)
    println("Player " + player + " loses; player " + (3 - player) + " wins")
  else player = 3 - player
}
The outer loop invariant is that player is the next player's number, either one or two, and the board is the result of the accepted moves. The inner loop invariant says that the board and player have not changed; rejected inputs do not consume a turn. Assuming the input source continues and eventually supplies a legal coordinate pair, the inner loop finishes. No program can guarantee that a user stops entering illegal moves, so that interaction assumption is necessary.
Every accepted move removes at least its selected token, so the outer loop variant is Count(), a decreasing nonnegative integer. In a nonempty order ideal, is occupied. Removing it removes the entire board, whereas a move at any other cell leaves it. Therefore the player making the final move is exactly the loser; the code reports that player before changing the turn. At most legal moves occur.
The return types suggest an immutable sequence implementation: insertion and deletion return a new Sequence[A], while the receiver can remain unchanged. A mutable implementation would more naturally return Unit for in-place edits, though it could return itself. Thus the signatures are evidence of an intended immutable object implementation, not a logical guarantee. For the snapshot solution below, require that returned and retained Sequence values really are immutable. The owning SlideSuite can still have a mutable variable referring to its current immutable sequence.
Represent an applied edit by a command pattern object with undo and redo. Use zero-based positions. For move(from,to), define to as the slide's index in the resulting sequence; it is in for a presentation of length . Removing the slide first and then inserting at that index implements this convention in either direction.
trait Change {
  // Pre: this is the most recent applied change not yet undone.
  def undo(): Unit
  // Pre: this is the next change on the redo history.
  def redo(): Unit
}

class SlideSuite(initial: Sequence[Slide]) {
  private var slides = initial

  private def insertRaw(i: Int, x: Slide): Unit = {
    slides = slides.insert(i, x)
  }

  private def deleteRaw(i: Int): Unit = {
    slides = slides.delete(i)
  }

  private def moveRaw(from: Int, to: Int): Unit = {
    val x = slides.elementAt(from)
    slides = slides.delete(from).insert(to, x)
  }

  def insert(i: Int, x: Slide): Change = {
    insertRaw(i, x)
    new Change {
      def undo(): Unit = deleteRaw(i)
      def redo(): Unit = insertRaw(i, x)
    }
  }

  def delete(i: Int): Change = {
    val x = slides.elementAt(i)
    deleteRaw(i)
    new Change {
      def undo(): Unit = insertRaw(i, x)
      def redo(): Unit = deleteRaw(i)
    }
  }

  def move(from: Int, to: Int): Change = {
    moveRaw(from, to)
    new Change {
      def undo(): Unit = moveRaw(to, from)
      def redo(): Unit = moveRaw(from, to)
    }
  }
}
Sequence and Slide are the supplied external types. Valid insertion positions are , deletion positions are , and both move positions are valid indices of the original length. These are the permitted unchecked argument preconditions. The private raw operations perform exactly their named state transformation and do not create history entries. A move to the same index is a legitimate no-op.
The deleted slide must be saved because its index alone cannot reconstruct it. By contrast, insertion already receives the slide to retain. For a move, the inverse of moving the slide from from to its final index to is to remove it at to and reinsert it at from; all other slides retain their relative order. Thus each returned object satisfies undo restores the state immediately before the edit, and redo restores the state immediately after it, under the stated history protocol.
A controller can enforce the protocol with two stacks. This code records changes that have already been executed:
class History {
  private var done = List.empty[Change]
  private var undone = List.empty[Change]

  // Pre: c is a fresh, already-applied change of this history's suite.
  def record(c: Change): Unit = {
    done = c :: done
    undone = Nil
  }

  def undo(): Unit = {
    require(done.nonEmpty)
    val c = done.head
    c.undo()
    done = done.tail
    undone = c :: undone
  }

  def redo(): Unit = {
    require(undone.nonEmpty)
    val c = undone.head
    c.redo()
    undone = undone.tail
    done = c :: done
  }
}
For example, history.record(suite.move(i,j)) executes and records one move. The representation invariant says that done contains applied changes in reverse application order, while undone contains undone changes in the next-redo order, all belonging to the same suite. A fresh edit clears the redo branch. Undo and redo transfer one command between the two heads, so they neither skip intervening edits nor generate new history records. Unrecorded external edits and out-of-order use of old command objects are excluded by this protocol.
Replace edit-specific inverse information by before/after snapshots implementing the Memento pattern. The same Change and History interfaces still work. A complete alternative suite is:
class SnapshotSlideSuite(initial: Sequence[Slide]) {
  private var slides = initial

  private def changeTo(after: Sequence[Slide]): Change = {
    val before = slides
    slides = after
    new Change {
      def undo(): Unit = { slides = before }
      def redo(): Unit = { slides = after }
    }
  }

  def insert(i: Int, x: Slide): Change =
    changeTo(slides.insert(i, x))

  def delete(i: Int): Change =
    changeTo(slides.delete(i))

  def move(from: Int, to: Int): Change = {
    val x = slides.elementAt(from)
    changeTo(slides.delete(from).insert(to, x))
  }
}
By-value evaluation computes after without changing slides, then changeTo captures the still-current before and installs the new value. The val bindings inside each call are stable snapshots, rather than later reads of a mutable variable. Under the same chronological history preconditions, undo and redo are constant-time reference assignments. This is the Memento pattern applied to an immutable sequence. Retaining a reference to an in-place-mutated sequence would not save its old state. The snapshot covers slide order and membership; it does not promise to undo unrelated mutations inside a Slide object.
Not necessarily: structural sharing can make snapshots cheap, but the trait alone gives no storage guarantee. With a persistent data structure, unchanged portions of old and new sequences can be shared safely. Saving two root references costs additional space per edit, and adjacent history entries commonly refer to the same intermediate version. With an appropriate balanced persistent tree, each positional edit may add only new vertices, giving approximately storage for retained edits of comparable presentation size, plus references to slides.
There are important qualifications. A fully copied immutable array may allocate per edit and use across its history. A persistent linked list shares suffixes but may copy a long prefix for a late positional edit. Moreover, snapshot history keeps old versions alive that an edit-specific inverse representation might otherwise release. Consequently a significant increase is possible with some implementations or workloads; it is not forced by saving Sequence references, and it cannot be ruled out from the interface alone.
Programming language polymorphism lets one expression or operation work with values of different types or concrete representations. In object-oriented programming, subtype polymorphism lets a reference of an interface or superclass type designate instances of different implementing software classes. A call through that reference uses dynamic dispatch to select the receiver's overriding object method. For example, a routine taking Book can invoke recall on a linked-list or an array-based implementation while depending only on the common abstract contract.
Parametric polymorphism is another form: the type parameter in FiniteDist[T] lets the same interface describe distributions over Booleans, integers or characters. A generic method introduces a further type parameter when its output type differs. Method overloading, in contrast, supplies several statically selected signatures with one name; it should not be confused with receiver-dependent dynamic dispatch. Correct substitutability also requires implementations to respect the common behavioral contract, not merely to share method names.
Implement the Bernoulli distribution, taking special care that a zero-mass outcome is excluded from the support of a probability distribution:
class Flip(p: Double) extends FiniteDist[Boolean] {
  require(!p.isNaN && 0.0 <= p && p <= 1.0)

  def getDom: List[Boolean] =
    if (p == 0.0) List(false)
    else if (p == 1.0) List(true)
    else List(true, false)

  def getProb(x: Boolean): Double =
    if (x) p else 1.0 - p
}
The precondition excludes NaN and all values outside , including infinities. The two masses are nonnegative and sum mathematically to one. Endpoint domains are singleton lists, while an interior parameter lists both outcomes exactly once. Treating getDom as always containing both Booleans would violate its positive-support contract at the endpoints.
The inclusive interval is nonempty exactly when . Reject with a failed precondition, rather than assigning a nonexistent normalization to an empty interval. Compute its width in Long before taking a reciprocal:
class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u, "Empty uniform interval")
  private val width = u.toLong - l.toLong + 1L
  private val mass = 1.0 / width.toDouble

  def getProb(x: Int): Double =
    if (l <= x && x <= u) mass else 0.0

  def getDom: List[Int] = {
    var x = l.toLong
    var rev = List.empty[Int]
    while (x <= u.toLong) {
      rev = x.toInt :: rev
      x += 1L
    }
    rev.reverse
  }
}
The loop invariant says that and rev contains exactly the integers in reverse order. The loop variant is while the guard is true. Long handles both the full interval width and the increment past Int.MaxValue. At exit, reversing yields each support value once. All support values have mass , so their exact sum is one; Double approximates that rational number. Very large valid domains require correspondingly large lists and sufficient memory; that resource issue does not make the mathematical endpoint values invalid.
Use relative character frequencies, an empirical distribution. A nonempty string is required because an empty sample has no normalized frequency distribution:
class DistFromString(s: String) extends FiniteDist[Char] {
  require(s != null && s.nonEmpty, "A nonempty string is required")
  private val chars = s.toList
  private val domain = chars.distinct

  def getDom: List[Char] = domain

  def getProb(c: Char): Double =
    chars.count(_ == c).toDouble / s.length.toDouble
}
distinct removes repeated support entries without changing which characters occur. Every returned domain element has positive frequency, and every absent character has frequency zero. The occurrence counts partition the string's character positions, so their total is s.length, establishing normalization. For Scala, the masses are for a and each for S, c and l. The character units here are exactly the Char values supplied by s.toList; the interface does not specify a different notion of displayed text characters. The code has no explicit loop beyond the specified library traversals.
Add the following concrete method inside FiniteDist[T]. It forms a pushforward of a finite probability distribution, adding the masses of outcomes that map to the same result:
def map[U](f: T => U): FiniteDist[U] = {
  val source = getDom
  val weighted = source.map(x => (f(x), getProb(x)))
  val target = weighted.map(_._1).distinct
  new FiniteDist[U] {
    def getDom: List[U] = target
    def getProb(y: U): Double =
      weighted.filter(pair => pair._1 == y).map(_._2).sum
  }
}
The input finite probability distribution is assumed to satisfy its interface, with stable masses during construction, and f must be a total deterministic pure function on its finite support. Output values need stable equality consistent with the mathematical equality being modeled; mutating equality-relevant fields afterwards would undermine any finite-support implementation. Computing weighted once also prevents later queries from re-evaluating f inconsistently.
Every source support element appears once in weighted. The distinct operation lists each image value once; every such image has a positive mathematical mass because it has a positive-mass preimage. For each , filtering selects exactly those with , so getProb(y) is the required sum, with an empty sum of zero off the image. The fibers form a set partition of the original support, giving
(1)
Thus colliding images have their probabilities added, not overwritten. For a concrete check, mapping a uniform distribution on by parity gives probability to each of ; mapping every source value to one constant gives a singleton domain with total mass one. Floating-point rounding can make a computed total differ slightly from one; the proof is for exact mathematical masses, and the representation uses Double approximations.
Test-driven development interleaves three small steps: write a test expressing the next required behavior and observe that it fails, implement enough behavior to make it pass, then improve the code's structure while keeping the tests passing. The retained tests become a regression suite. For example, before implementing a book deletion, test that deleting an existing contact removes it and returns true; later add the absent-name case. Each test guides a small implementation step rather than waiting for a finished component.[ref]
Compared with a traditional write-the-component-then-test workflow, tests guide the design before each increment is implemented. This does not imply that all non-TDD testing is postponed until a whole product is finished, or that TDD eliminates broader integration testing.
The test-first behavioral core is naturally black-box testing: expected outcomes come from the operation's contract. Later tests can use internal control flow or representation cases, becoming white-box testing. Thus a complete practice can use a mixture, with mainly contract-based black-box tests driving the next behavior. The classification depends on how test cases are chosen, not on whether the programmer personally knows the implementation. Passing a finite suite is not a proof of universal correctness.
In the Observer pattern, a subject maintains subscriptions through a common observation interface. Interested observers register and unregister; when a relevant state change occurs, the subject sends a notification, and each observer runs its own reaction. Notifications can carry the new information directly or prompt the observer to query the subject's coherent updated state.
This fits an event-driven programming interface in which one model can have several independently changing views: a displayed conversion, a chart or a status indicator can react to the same model change. It avoids hard-coding calls to every concrete view inside the subject, which would couple domain logic to presentation details and require editing the subject whenever another view is added. The subject depends on the observer interface rather than every concrete observer class.
The design still needs subscription cleanup and an update policy. Mutual notifications can create a feedback loop or a reentrant event handler, while an observer that reacts halfway through a state change can see inconsistent data. Publishing only coherent changes and controlling derived display updates address those problems; the pattern alone does not automatically solve them.
In Scala Swing, a Publisher is the observable subject and a Reactor supplies an observer's reactions. A reactor calls listenTo(pounds, euros, rate) to subscribe to the relevant publishing components. It adds a partial function from events to actions with reactions += { case ... => ... }; unmatched event types need no action. When a publisher calls publish(e), subscribed reactions that handle that event are notified. Calling deafTo removes subscriptions that are no longer wanted.[ref]
The publisher does not need to know the concrete frame or its currency-conversion code. A TextField supplies the relevant editing events, and the frame's reaction distinguishes the source field using EditDone(source). Both registration and a matching reaction are needed: installing a case handler without subscribing does not establish the notification path. The observer logic should update the conversion model once and then refresh the other fields from that coherent state.
Let the committed model be amounts and an exchange rate , with invariant . Editing pounds keeps the rate and computes euros; editing euros keeps the rate and computes pounds; editing the rate keeps pounds and computes euros. A usable rate must be strictly positive, and every accepted floating-point number and derived result must be finite. Negative amounts are allowed. Rejecting invalid text preserves the last committed model.
Insert the following members inside the supplied MainFrame, after the three fields have been initialized. Its existing layout can remain as written:
private var p = 10.0
private var e = 11.5
private var r = 1.15
private var refreshing = false

private def finite(x: Double): Boolean = !x.isNaN && !x.isInfinity

private def showModel(): Unit = {
  refreshing = true
  try {
    pounds.text = java.lang.String.format(java.util.Locale.ROOT, "%.2f", Double.box(p))
    euros.text = java.lang.String.format(java.util.Locale.ROOT, "%.2f", Double.box(e))
    rate.text = r.toString
  } finally {
    refreshing = false
  }
}

private def edit(source: TextField): Unit = {
  try {
    val v = source.text.trim.toDouble
    if (finite(v)) {
      var nextP = p
      var nextE = e
      var nextR = r
      if (source eq pounds) {
        nextP = v
        nextE = v * r
      } else if (source eq euros) {
        nextE = v
        nextP = v / r
      } else if (source eq rate) {
        nextR = v
        nextE = p * v
      }
      if (nextR > 0.0 && finite(nextP) && finite(nextE) && finite(nextR)) {
        p = nextP
        e = nextE
        r = nextR
      }
    }
  } catch {
    case _: NumberFormatException => ()
  }
  showModel()
}

listenTo(pounds, euros, rate)
reactions += {
  case EditDone(source) if !refreshing => edit(source)
}
The invariant is interpreted with the usual floating-point rounding in multiplication and division. All candidate values are calculated before committing any of them, so invalid text, zero/negative rates, NaN, infinity and floating-point overflow leave the old model intact. The committed r remains positive, so euro-to-pound division is defined. Using a fixed formatting locale keeps the decimal separator compatible with toDouble. The displayed amounts are rounded to two decimal places, while the model retains their full available precision. The rate is not forcibly rounded to two places, which could otherwise turn a valid small positive rate into displayed zero.
The refreshing guard prevents synchronous derived-field notifications from recursively committing another edit. EditDone is an edit-completion event, not a request to react to every partial keystroke; pressing the field's completion action is enough to trigger the conversion. If a particular UI additionally needs live updates, it can subscribe to the appropriate text-change events with the same validation and authoritative-source policy. The supplied API and archived Scala Swing documentation suffice for the requested completion-event implementation; no unidentified practical library is required.[ref]

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