Source paper: released examination archive, member 2015/T/a10098w1.pdf; original cover dated 2016-06-15. The archive member's directory is not the examination year.
Use two array indices, advancing only the smaller current entry. Here and in Questions 1–4, code is structured Oberon-style pseudocode: RETURN exits a procedure, Some(x) and None distinguish success and absence, and AND short-circuits from left to right. Arithmetic is exact where the source asks us to ignore integer overflow.
PROCEDURE common(a, N, b, M): INTEGER;
VAR i, j: INTEGER;
BEGIN
  i := 0; j := 0;
  WHILE a[i] # b[j] DO
    IF a[i] < b[j] THEN i := i + 1
    ELSE j := j + 1
    END
  END;
  RETURN a[i]
END common;
Let be the smallest common value, and let . Existence implies . A useful loop invariant is , , with no common value among the discarded prefixes and . Initially the prefixes are empty. If , then cannot equal any entry of because that sorted array is increasing; it cannot be a common value in the discarded prefix either. Moreover would imply , a contradiction. Thus and incrementing is safe. The other branch is symmetric.
Every guard and return therefore uses valid array indices, even without explicit bounds tests. The loop variant decreases on each iteration. At exit the equal entries form a common value no larger than , hence equal . There are at most increments and constant work per increment. The procedure returns the smallest common value in time and auxiliary space.
Replace the existence-dependent bounds proof with explicit bounds tests. Neither input array is changed or copied.
PROCEDURE commonOrNone(a, N, b, M);
VAR i, j: INTEGER;
BEGIN
  i := 0; j := 0;
  WHILE (i < N) AND (j < M) DO
    IF a[i] = b[j] THEN RETURN Some(a[i])
    ELSIF a[i] < b[j] THEN i := i + 1
    ELSE j := j + 1
    END
  END;
  RETURN None
END commonOrNone;
The loop invariant is , , and every common value of the original arrays lies in both remaining suffixes and . Equivalently neither discarded prefix contains a common value. Advancing the smaller current value preserves this for the same ordering reason as in part (a).
Both array bounds are checked before any element is read. If the remaining heads are equal, all later entries are larger, so the returned value is the smallest. If either suffix becomes empty, the loop invariant proves there is no common value. The loop variant decreases on each unsuccessful comparison. The result is Some(smallest common value) or None, with time and auxiliary space, including empty-input cases. A language without short-circuit operators can use nested tests; the guard here itself contains no array reads.
The cyclic strict comparisons in the hint identify a head that cannot be the answer:
PROCEDURE common3(a, N, b, M, c, L): INTEGER;
VAR i, j, k: INTEGER;
BEGIN
  i := 0; j := 0; k := 0;
  WHILE (a[i] # b[j]) OR (b[j] # c[k]) DO
    IF a[i] < b[j] THEN i := i + 1
    ELSIF b[j] < c[k] THEN j := j + 1
    ELSE k := k + 1
    END
  END;
  RETURN a[i]
END common3;
Let be the smallest common value. The loop invariant is , , , and every discarded entry is not common to all three arrays. If , the entry cannot occur in the unprocessed part of , so discard it. The branch has the analogous justification. If neither comparison holds but the heads are not all equal, the hint guarantees , so discard .
A pointer at its target position cannot be advanced: for example and would imply . Thus all reads stay within array bounds. The loop variant decreases. At exit all heads equal . The cost is time and auxiliary space.
Maintain one array index per input and a candidate value. Cycle through the arrays, counting consecutive agreements with that candidate; when a larger head is encountered, start counting agreements again. p is an auxiliary array of indices, not a copy of any input.
PROCEDURE commonMany(as, n, m);
VAR p: ARRAY m OF INTEGER;
    j, candidate, agree, x: INTEGER;
BEGIN
  FOR j := 0 TO m-1 DO
    p[j] := 0;
    IF n[j] = 0 THEN RETURN None END
  END;
  candidate := as[0][0];
  j := 0; agree := 0;
  WHILE agree < m DO
    IF p[j] = n[j] THEN RETURN None END;
    x := as[j][p[j]];
    IF x < candidate THEN
      p[j] := p[j] + 1
    ELSIF x = candidate THEN
      agree := agree + 1;
      j := (j + 1) MOD m
    ELSE
      candidate := x;
      agree := 1;
      j := (j + 1) MOD m
    END
  END;
  RETURN Some(candidate)
END commonMany;
The loop invariant has three parts. All indices satisfy ; no discarded entry is common to every input; and every original common value is at least candidate. Additionally, the agree cyclically consecutive arrays immediately preceding index j have heads equal to candidate. These facts are true initially, with an empty agreement run.
A head below candidate is not globally common, by the lower-bound clause, so advancing its pointer is safe. A head above candidate gives a new lower bound: every globally common value lies in this array's unprocessed suffix and so is at least its head. Only this array is yet certified to agree with the new candidate. An equal head extends the run by one. An exhausted suffix proves absence; a run of agreements covers every array exactly once and proves that candidate is common, and the lower-bound clause proves minimality. The exhaustion test precedes each dereference, including after the last entry of a suffix is discarded.
For algorithm termination and time complexity, charge comparisons to the pair (j,p[j]). A fixed entry is discarded at most once, can raise the candidate at most once, and can be counted as an agreement at most once: before the same array is revisited, either the algorithm has finished or the candidate has strictly increased. Thus there are at most three comparisons per input entry, besides the initialization. The result is the smallest common value or None in time and auxiliary space. For , the first head immediately gives the answer.
Evaluate the supplied function once at each positive integer, retaining its largest value so far. In particular do not initialize the maximum to zero: might be negative everywhere.
PROCEDURE record(f, emit);
VAR n, best, y: INTEGER;
BEGIN
  best := f(1);
  emit(1);
  n := 2;
  WHILE TRUE DO
    y := f(n);
    IF y > best THEN
      emit(n);
      best := y
    END;
    n := n + 1
  END
END record;
At the loop head the loop invariant is , best , and precisely the record values with argument less than have been emitted, in increasing argument order. The first argument is a record because its comparison set is empty. The strict test correctly excludes ties. Updating best only on a strict increase preserves the loop invariant.
Exactly one call of f is made per processed argument. For an arbitrary supplied function, an unexamined argument can have a value larger than all previous values, so skipping its evaluation cannot be correct in general. This assumes is a total, deterministic function; the requested infinite computation ignores integer overflow.
Test each possible positive divisor directly:
PROCEDURE divisors(n: INTEGER): INTEGER;
VAR i, count: INTEGER;
BEGIN
  i := 1; count := 0;
  WHILE i <= n DO
    IF n MOD i = 0 THEN count := count + 1 END;
    i := i + 1
  END;
  RETURN count
END divisors;
For , the loop invariant is and count . Testing adds exactly the next possible divisor. The loop variant decreases, and the divisor in MOD is always positive. At exit the interval contains every positive divisor. This computes the divisor function using remainder operations, time, and auxiliary space.
By the time print(n) is called, record has evaluated divisors(i) once for every . In the unit-cost model, the total number of remainder tests is
(1)
The record values comparisons add only work, and output is cheap by assumption. The elapsed time is . This measures time to reach a given highly composite number, rather than time as a function of the number of printed records.
By unique prime factorization, a positive divisor has precisely the form
(1)
There are independent choices for each prime exponent; different choices give different divisors, and every divisor occurs. The multiplication principle therefore gives . For , the empty product is , giving its one positive divisor.
Use trial division on a shrinking residual. Once the trial divisor exceeds its square root, any residual larger than one is itself prime.
PROCEDURE divisors(n: INTEGER): INTEGER;
VAR residual, trial, exponent, answer: INTEGER;
BEGIN
  residual := n; trial := 2; answer := 1;
  WHILE trial * trial <= residual DO
    exponent := 0;
    WHILE residual MOD trial = 0 DO
      residual := residual DIV trial;
      exponent := exponent + 1
    END;
    answer := answer * (exponent + 1);
    trial := trial + 1
  END;
  IF residual > 1 THEN answer := 2 * answer END;
  RETURN answer
END divisors;
For the outer loop invariant, let be the set of primes below trial and their exponents in the original . Then
(1)
and residual has no prime factor below trial. If trial divides the residual it must therefore be prime: a composite trial value would have a smaller prime factor, contradicting this clause. If it does not divide, the zero exponent contributes the factor .
For the inner loop invariant, let be the residual on entry. Then . Each exact division reduces the positive residual by at least a factor of two, so this loop terminates. At exit the exponent is the full multiplicity of trial; multiplying by exponent+1 preserves the outer loop invariant. The outer loop terminates because trial increases and residual never increases. When it exits, a composite residual would have a prime factor at most its square root, yet every smaller trial factor has already been excluded. Hence the residual is or a single remaining prime of exponent .
The procedure computes in unit-cost time and auxiliary space, with the separate successful divisions bounded by . No array or table of primes is needed, and correctly returns .
The second procedure should reach large outputs faster, because the first makes exactly expensive MOD operations when processing argument , whereas the second tries only up to the square root of a shrinking residual, with at most successful DIV operations. Each successful division also requires a successful MOD test; each outer iteration adds one final unsuccessful MOD test. Thus its expensive-operation count is per argument, and at most cumulatively through argument , compared with for direct counting.
The speedup is not an assertion that every single call uses fewer divisions: for , the second code makes three MOD tests and two DIV operations, while the first makes four MOD tests. Small constant costs can go either way. The many small prime factors in highly composite numbers also shrink the residual early, which often helps further; the cumulative comparison includes every preceding argument, not only the printed records.
Print a prefix while following the linked list, counting how many closing parentheses remain. The final reciprocal can be printed without parentheses.
PROCEDURE printCF(f: fraction);
VAR p: fraction; opened: INTEGER;
BEGIN
  p := f; opened := 0;
  Out.Int(p.head, 0);
  p := p.tail;
  WHILE p # NIL DO
    IF p.tail = NIL THEN
      Out.String("+1/"); Out.Int(p.head, 0)
    ELSE
      Out.String("+1/("); Out.Int(p.head, 0);
      opened := opened + 1
    END;
    p := p.tail
  END;
  WHILE opened > 0 DO
    Out.String(")"); opened := opened - 1
  END
END printCF;
The first loop invariant says that p is the next unprinted linked list node, the printed text is the correct expression prefix, and opened counts its unmatched opening parentheses. The final node contributes no opening parenthesis; the second loop invariant says that precisely opened closing parentheses remain. Thus [1,2,3,4,5] produces 1+1/(2+1/(3+1/(4+1/5))). A singleton prints just its head. If the first head is negative, its leading minus remains a valid prefix; subsequent heads are positive.
The precondition is a finite nonempty continued fraction list. Every dereference is made only for a nonnull pointer. The procedure uses auxiliary space and time linear in the number of nodes, apart from printing their digits. The source's claimed strict upper bound has an exception under its stated definition: [x0,1] represents . None of these algorithms relies on that incorrect strict bound.
Use the Euclidean algorithm with floor quotient and nonnegative remainder, including for a negative numerator:
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
  q := n DIV d; r := n MOD d;
  NEW(p); p.head := q; p.tail := NIL;
  IF r # 0 THEN p.tail := rat2cf(d, r) END;
  RETURN p
END rat2cf;
For , Euclidean division gives with . If , the singleton [q] is exact. Otherwise
(1)
so the recursive tail represents . Its numerator is positive and greater than its denominator, so every tail head is a positive integer. The new denominator is strictly smaller than , proving algorithm termination by descent through the positive integers.
The returned list represents exactly . For example gives [-3,1,2]; truncating negative division toward zero would violate the required positivity of the tail. There are Euclidean algorithm steps, with output allocation and recursive stack depth linear in the number of generated nodes.
Append each quotient directly to the output linked list, retaining a pointer to its last node. The nodes are required output; auxiliary variables remain simple integers and pointers.
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR first, last, p: fraction; q, r: INTEGER;
BEGIN
  first := NIL; last := NIL;
  REPEAT
    q := n DIV d; r := n MOD d;
    NEW(p); p.head := q; p.tail := NIL;
    IF first = NIL THEN first := p
    ELSE last.tail := p
    END;
    last := p;
    n := d; d := r
  UNTIL d = 0;
  RETURN first
END rat2cf;
At the start of each iteration, d is positive, and the output prefix consists exactly of the quotients already obtained by the Euclidean algorithm. last points to its final node, or both first and last are null when the prefix is empty. The current ratio n/d is the unexpanded tail of the original continued fraction. The quotient/remainder step extends that prefix by the same value as the recursive version, then replaces the unexpanded ratio by its reciprocal residual tail. If the remainder is zero, no tail remains and the loop stops before another division.
The loop variant is the positive current denominator, which strictly decreases after each nonfinal iteration. The input denominator is positive, so at least one node is allocated, including for zero or an integral ratio. This is the same exact conversion with auxiliary space, excluding the returned list, and no input mutation.
Convert the tail first and apply the reciprocal identity. Two output parameters hold the rational number's numerator and denominator.
PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR u, v: INTEGER;
BEGIN
  IF f.tail = NIL THEN
    n := f.head; d := 1
  ELSE
    cf2rat(f.tail, u, v);
    n := f.head * u + v;
    d := u
  END
END cf2rat;
The singleton case is immediate. If the recursive call returns the tail as , then because every tail head is positive. The full value is
(1)
Structural induction on the finite nonempty linked list proves correctness, and the denominator is always positive even if the first head is negative. If the tail pair is coprime, then ; the base pair is coprime, so the result is in lowest terms. Return (head*u+v,u) after converting the tail, using linear node-processing time and linear recursive stack space.
Accumulate the product of the matrices from left to right, which matches forward linked list traversal.
PROCEDURE cf2rat(f: fraction; VAR n, d: INTEGER);
VAR p: fraction; a, b, c, e, x: INTEGER;
BEGIN
  a := 1; b := 0; c := 0; e := 1;
  p := f;
  WHILE p # NIL DO
    x := p.head;
    a, b, c, e := a*x+b, a, c*x+e, c;
    p := p.tail
  END;
  n := a; d := c
END cf2rat;
The four-value assignment is simultaneous, as permitted by the source. With , the loop invariant after reading the prefix is
(1)
with the empty product initialized to the identity matrix. Multiplication on the right by produces exactly the four assignments above. The associativity of matrix multiplication allows this left-to-right accumulation even though the recursive conversion groups operations from the right.
At completion, the first column is the numerator/denominator pair for the whole continued fraction: the last factor sends to , and each earlier factor applies the recurrence from part (d). The vector is an algebraic device, not a finite input ratio requiring division by zero. For a nonempty list the resulting is positive; for a singleton it is . The product has determinant , so its first-column entries are coprime. Return in linear node-processing time and auxiliary space, without changing the list.
Assume every indicated segment lies within array bounds, and lengths are nonnegative. Use a temporary value of element type T:
PROCEDURE swap(i, j: INTEGER);
VAR x: T;
BEGIN
  x := m[i]; m[i] := m[j]; m[j] := x
END swap;

PROCEDURE blockswap(i, j, n: INTEGER);
VAR t: INTEGER;
BEGIN
  t := 0;
  WHILE t < n DO
    swap(i+t, j+t);
    t := t + 1
  END
END blockswap;
The first procedure even works for . For the second, disjointness ensures that each swap exchanges the two original entries at offset t without disturbing any other pair. Its loop invariant says that offsets below t have been exchanged, offsets from t through retain their original values, and everything outside the two segments is unchanged. The loop variant proves algorithm termination. A block exchange uses swaps and auxiliary space. The stray wp printed after this source subpart is not an additional requirement.
Exchange symmetric pairs, stopping before the middle:
PROCEDURE reverse(i, n: INTEGER);
VAR t: INTEGER;
BEGIN
  t := 0;
  WHILE t < n DIV 2 DO
    swap(i+t, i+n-1-t);
    t := t + 1
  END
END reverse;
Writing for the pre-call array, the loop invariant says that the first and last t positions of the segment already satisfy , all positions between them retain their original values, and positions outside the segment are unchanged. Each swap fixes the next symmetric pair. The loop variant decreases; the two indices are distinct and in bounds whenever the body executes. Exactly swaps reverse the segment, with the odd-length middle element left in place and no accesses for .
Write the segment as , where and . The desired array rotation is . Reverse each block, then the whole segment:
PROCEDURE rotate(i, n, k: INTEGER);
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  reverse(i, n-k);
  reverse(i+n-k, k);
  reverse(i, n)
END rotate;
The state changes are , using the list reversal identity supplied in the paper and reversal being an involution. Three reversals implement the right rotation in time and auxiliary space. The initial return covers empty and identity rotations.
Let and be the lengths of the left and right blocks. Exchange the smaller block with the equally long block at the opposite end.
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  a := n-k; b := k;
  IF a = b THEN
    blockswap(i, i+a, a)
  ELSIF a < b THEN
    blockswap(i, i+b, a);
    rotate(i, b, b-a)
  ELSE
    blockswap(i, i+a, b);
    rotate(i+b, a, b)
  END
END rotate;
If , split with . The first block swap sends to ; is now in its final suffix. Rotate the remaining prefix of length right by to send to . If , split with . The swap sends to ; the fixed prefix is , and rotating the remaining length- suffix right by restores . In both cases the exchanged segments are disjoint.
The remaining length strictly decreases, so induction on proves algorithm termination and correctness. This implements the block-exchange rotation. It uses only simple explicit variables, but its recursive call stack can have depth when one block has length ; the iterative version removes that extra storage.
Replace the sole recursive call by updates to the current segment's parameters:
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
  WHILE (k > 0) AND (k < n) DO
    a := n-k; b := k;
    IF a = b THEN
      blockswap(i, i+a, a);
      RETURN
    ELSIF a < b THEN
      blockswap(i, i+b, a);
      n := b; k := b-a
    ELSE
      blockswap(i, i+a, b);
      i := i+b; n := a; k := b
    END
  END
END rotate;
The loop invariant is that every position outside the current unresolved segment already has its final value, while rotating the current segment by the current k completes the original array rotation. The block decompositions in part (ii) prove preservation. The positive unresolved length decreases in each continuing branch; the equal-block branch finishes immediately. The same rotation now uses auxiliary space, including control storage, and leaves the rest of the array untouched.
Save the last entry, shift the others right in descending index order, and put the saved value at the left. Descending order prevents overwriting an unread entry.
PROCEDURE rotate(i, n, k: INTEGER);
VAR x: T; step, t: INTEGER;
BEGIN
  IF (k = 0) OR (k = n) THEN RETURN END;
  step := 0;
  WHILE step < k DO
    x := m[i+n-1];
    t := n-1;
    WHILE t > 0 DO
      m[i+t] := m[i+t-1];
      t := t-1
    END;
    m[i] := x;
    step := step+1
  END
END rotate;
For one pass, after the shifts at offsets greater than t, those positions contain the original preceding entries; offsets through t are still available, and x retains the original last entry. The loop variant t decreases to zero. The outer loop invariant is that the segment has been rotated right by step places relative to its initial state. Repeating a one-step cyclic permutation times therefore gives the required array rotation. The method uses one extra T variable and time, with auxiliary space. The early return avoids all accesses for an identity rotation.
Count element reads and writes, ignoring simple-variable operations. A swap of distinct entries makes two reads and two writes, hence four expensive accesses. For , the three-reversal method therefore costs
(1)
Here if and are both even, and otherwise.
For either block-exchange version, let , , and let count element swaps. The recurrence is and, when the lengths differ,
(2)
The Euclidean algorithm preserves under this subtraction. Induction on therefore yields
(3)
Thus both block-exchange methods cost accesses, no more than the three-reversal method. Their element-access counts are identical; the iterative one avoids the recursive stack. For example a half-length rotation uses swaps instead of approximately reversal swaps.
Each single-place pass in part (iv) reads every entry once and writes every entry once, costing accesses. For , its accesses beat the block method's for and tie for . For the block method costs strictly less than . All three methods as written return without accesses for or . Repeated shifting can take quadratic time; the reversal and block methods take linear time. These comparisons concern the specified implementations, not a more general cycle-decomposition rotation using several disjoint cycles.
The standard output is three lines:
A
2.3
B
This is program output, excluding any interactive interpreter's display of returned values. The calls a.m(1) and b.m(5.6) compute squares without printing. In A, the concrete m(Int) wins over the generic method at argument 1; the string and 2.3 use m[T] and print their arguments.
For b: B[Any], the class type parameter has already become Any, so the two alternatives are m(Any) and m(Double), rather than a method with its own freely inferred type parameter. The Double alternative is more specific. It accepts 4 by numeric widening, so b.m(4) computes 16.0 without printing; b.m("B") prints B; b.m(5.6) computes a square without printing. These are applications of the Scala 2.11 method overloading rules, with the arithmetic return values discarded in statement position.[ref]
The output is YY, with no newline. The variable a has static type A, although its runtime type is B. Both c.m(a) and d.m(a) therefore select the signature m(A) at compile time. The m(B) alternative is not applicable to an argument whose static type is merely A.
Both receivers refer to the same D object. Dynamic dispatch then invokes D's override of the already selected m(A) signature, printing Y twice. The static type C of c changes the visible member set, but both signatures are visible through either receiver in this example. Overload selection followed by dynamic dispatch does not select an overload from the argument's runtime type.
An abstract data type specifies a set of abstract values and the operations on them, including their observable behavior, independently of their concrete representation. Its operation signatures say what can be requested; its laws or preconditions and postconditions say what those requests mean.
For example a stack can be specified by an empty value, push, pop, and isEmpty, with pop(push(x,s)) returning x and leaving s. A linked list and an array can implement the same abstract data type if clients observe the same specified behavior. Encapsulation hides the representation, while a representation invariant describes which internal states are valid and an abstraction function explains which abstract value each valid internal state represents. An abstract class is a language mechanism; it is not by itself a full abstract data type specification.
For a node tuple , write for its identifier. A predicate that is true exactly when identifiers repeat is
(1)
The inequality excludes choosing the same tuple twice. The set cannot contain two copies of an identical quadruple, but it can contain distinct quadruples with equal first component and different information or successors. The negation is the usual identifier-uniqueness representation invariant, namely .
Define the directed successor relation by . Then the required predicate is
(1)
where denotes the natural-number information component of node . In the source's indexed notation this is .
This formulation checks both successor links against every node with the corresponding identifier, so it does not silently assume part (d)'s uniqueness condition. It checks existing successors; if every identifier must denote an actual node, add the separate referential integrity condition , or exempt an explicitly designated null identifier. The source specifies no null convention. Indeed a nonempty finite structure with two actual successors at every node cannot have strictly increasing values along all edges: following successors would eventually create a directed cycle. The implication above remains meaningful for leaves represented by absent or null successors.
Read as the existence of a directed successor path from to . Then the property says every reachable ordered pair of even-valued nodes admits a connecting route through an odd-valued node. More exactly, for all even-valued with reaching , there is an odd-valued such that reaches and reaches .
The two reachability witnesses concatenate to a directed walk through . In an acyclic graph this yields an intervening node on a path. In a graph with directed cycles, the concatenation may revisit vertices. The existential witness does not say that every connecting path contains an odd-valued node, or even that an even-to-even edge is forbidden. For example edges , , , with even endpoints and odd , satisfy the property for this pair despite the direct even-to-even edge.
There are two source-notation qualifications. The displayed outer universal quantifier binds both symbols appearing as formal arguments to prop, so the whole formula is a global property of , rather than a genuinely free two-node predicate. Also the indexed ellipsis defining prop3 does not formalize path length zero. With positive-length reachability, even nodes on a cycle impose additional requirements; with reflexive reachability, choosing also imposes a requirement, and an isolated even-valued node would fail. The usual intended reading here is positive-length successor reachability. No uniqueness, acyclicity or specific path-length convention is proved by the displayed formula alone.
The output is 1, with no newline. The Any in class B[Any] and class C[Any] is a type parameter name that shadows the standard type scala.Any inside those class bodies. Renaming it to T preserves the program's meaning. Thus new B[Int] has an inherited m(Double) and its own m(Int); obj1.m(1) selects the latter and prints 1. The call with 2.3 can only use the inherited m(Double), which computes a sum without printing.
For new C[Any], the supplied type argument is the standard scala.Any, so the overloads are m(Double) and m(scala.Any). The more-specific Double alternative accepts 4 by numeric widening, and accepts 5.6 directly. Both return sums without printing. A computed result is not automatically screen output. This reasoning uses the Scala 2.11 overload conventions of Question 5(a); type erasure does not turn either class's generic-argument overload into an method overriding of m(Double).
Programming language polymorphism permits one interface or piece of code to work with values of several types, while providing the behavior appropriate to those values. For example a routine that calls play through a Player reference can use a Regular, Optimistic, or House object without knowing its concrete software class.
Use programming language polymorphism when clients should depend on a common contract while concrete behavior varies, or when an algorithm is independent of the element type. It avoids duplicating client logic or repeatedly inspecting concrete runtime types, and supports extensions behind the same interface. A shared interface must still have meaningful behavioral guarantees: merely giving unrelated operations the same name does not establish that implementations can safely replace one another.
With subtype polymorphism, a trait or abstract class declares an operation and concrete subclasses implement or override it. A Player reference holding a House object invokes House.play through dynamic dispatch. The client is written against the common contract.
With parametric polymorphism, a software class or generic method has a type parameter, such as List[T] or def identity[T](x: T): T = x. The same definition works for many supplied type arguments, with static relationships between input and output types. Method overloading is another mechanism, usually called ad hoc polymorphism: alternatives share a name but are selected from their parameter signatures at compile time.
Each play call should make at most one hit and return true exactly when it did so; the supplied while loop invokes it again to decide whether another hit is needed. Add these accessors inside Player:
def cards: List[Int] = _cards
def cards_=(cs: List[Int]): Unit = { _cards = cs }
def visibleValue: Int = _visibleValue
def visibleValue_=(v: Int): Unit = { _visibleValue = v }
The Scala assignment temp.cards = cs calls the setter, and visibleValue += cards.head uses the getter followed by the setter. The list getter exposes an immutable list value; updating the player's field still goes through the setter. The supplied initialization and hit maintain the hidden card at the last list position and visibleValue == cards.init.sum for each nonempty dealt hand.
The concrete software classes implement the supplied strategies literally:
class Regular extends Player {
  def play(visibleCards: List[Int]): Boolean = {
    require(visibleCards.length == 1)
    val total = value
    if (total < 21 && total <= 21 - visibleCards.head) {
      hit
      true
    } else false
  }
}

class Optimistic extends Player {
  def play(visibleCards: List[Int]): Boolean = {
    if (value != 21) {
      hit
      true
    } else false
  }
}

class House extends Player {
  def play(visibleCards: List[Int]): Boolean = {
    val total = value
    if (total < 21 && visibleCards.forall(v => total <= 21 - v)) {
      hit
      true
    } else false
  }
}
House receives all other players' final visible totals, whereas a non-house player receives the singleton containing the house's first visible card. The universal test implements “for each other player,” including the vacuously true case of no other players. Subtype polymorphism gives the common player list a Player interface, and dynamic dispatch chooses the appropriate play implementation.
These are the literal missing methods, but the printed specification does not guarantee a terminating game. An optimistic player with total who draws reaches ; every further positive card keeps the total above , so value != 21 remains true. The claim that only finitely many further cards are requested is therefore inconsistent with the optimistic strategy on such executions, in the intended arithmetic model without overflow. If the intended rule is “stop on reaching or exceeding 21,” the necessary correction is to replace its test by value < 21; that changes the printed strategy and is not silently made here.
There is a second printed mismatch: nextInt(10) yields , so 1 + nextInt(10) yields , not . Preserve the supplied hit when filling its missing pieces; generating every value from through would require an explicit change to nextInt(11) in both dealing and hitting.[ref] No winner-computation code is requested; the supplied loop only deals and requests cards.
Creational patterns organize object creation; behavioral patterns organize interactions and responsibility for behavior. A creational pattern controls how concrete software objects are selected, instantiated, or shared, so clients need not hard-code the entire construction policy. Examples include the factory method pattern and the singleton pattern.
A behavioral pattern describes how objects collaborate, receive requests, or distribute an algorithm's behavior. For example the observer pattern lets a subject notify dependants after its state changes, and the strategy pattern supplies interchangeable implementations of an operation. This distinction concerns the pattern's principal responsibility; a system can use both kinds together.
The UML class diagram below uses dashed hollow-triangle arrows for trait realization and ordinary arrows for stored references or navigable associations. Visibility is + for public and - for private.
Figure 1.
Gym equipment classes and observer associations
. Details.
GymEquipment implements Equipment. Performance and Prediction implement Functionality, each retaining one GymEquipment reference and registering itself with that equipment. Each equipment keeps a list of zero or more Functionality references; one functionality can in principle be registered with multiple equipment objects through the public method, although the supplied constructors register it only with their own equipment. Hence the generic registration association does not imply exclusive ownership or composition in UML.
There are two traits, one concrete equipment software class, and two concrete observer software classes. GymEquipment implements name, age, and weight as read-only values and overrides updateUserMeasures; the mutable measurement state and observer list are defined privately in Equipment. The diagram reflects the source, including deleteFunctionality returning a new list rather than mutating the stored list.
The system uses the observer pattern with a pull-style update. Equipment provides the subject interface and stores registered observers; GymEquipment is the concrete subject. Functionality is the observer interface, with Performance and Prediction as concrete observers. Their constructors subscribe them with addFunctionality(this).
When GymEquipment.updateUserMeasures is called, it first updates both measurements through super, then calls notifyFunctionalities. Every subscribed observer receives update() and reads the new measurements from its stored equipment reference. Performance calculates the current score; Prediction calculates the score at time time+5, keeping the other quantities fixed. Since observers are prepended to a list, notification follows reverse registration order.
The source has two independent implementation defects. deleteFunctionality(f) computes _functionalities diff List(f) but does not assign it back, so it does not actually unsubscribe anything. The prediction message also contains a physical newline inside an ordinary quoted Scala string in the PDF; executable code must join that string, concatenate pieces, or use a multiline string. Neither issue changes the intended observer pattern. The source's score is treated as the specified arithmetic expression, not as an independently validated physiological model.
Introduce one shared GymStandings singleton object. It stores the latest current-performance score for every participating GymEquipment, using the equipment reference as key, and returns every equipment object tied for the maximum score. Performance.update sends each freshly computed score to this object. The previous observer pattern and its prediction observer remain in use.
Figure 1.
Observer system extended with a singleton for gym-wide standings
. Details.
The added Performance -> GymStandings dependency means “reports to,” while GymStandings -> GymEquipment represents the equipment keys in its stored score map. GymStandings is an software object, so clients share its unique instance instead of constructing one standings object per machine. The singleton pattern centralizes the current scores and the maximum-score query. Equipment objects, rather than user names, are the keys because two users can have the same name. Scores are current readings, not an accumulation of all historical notifications; the largest reported score wins, with all ties retained.
Use a Scala object for the singleton pattern, and replace Performance with a version that reports to it. This code plugs into the source's Equipment, GymEquipment, and Functionality definitions; Prediction can remain an independent observer once its displayed string line break is made executable.
object GymStandings {
  private var scores = Map.empty[GymEquipment, Int]

  def record(e: GymEquipment, calories: Int): Unit = {
    scores = scores.updated(e, calories)
  }

  def remove(e: GymEquipment): Unit = {
    scores = scores - e
  }

  def leaders: List[(GymEquipment, Int)] = {
    if (scores.isEmpty) Nil
    else {
      val best = scores.values.max
      scores.toList.filter { case (_, score) => score == best }
        .sortBy { case (equipment, _) => equipment.name }
    }
  }
}

class Performance(e: GymEquipment) extends Functionality {
  private def calories: Int =
    ((e.age - e.weight + e.heartRate) * e.time) / 10

  e.addFunctionality(this)
  GymStandings.record(e, calories)

  def update(): Unit = {
    val current = calories
    GymStandings.record(e, current)
    println("Your current performance is: " + current + " calories burned.")
  }
}
For example, new Performance(treadmill) and new Performance(bike) attach two observers; later GymStandings.leaders returns the leading equipment/score pairs. Initial registration records the equipment's present score, even before its first subsequent update. Recording replaces the same equipment's previous score, so repeated notifications do not multiply its contribution. The explicit remove supports taking an equipment object out of the comparison; detaching its observer when its session ends also prevents later re-registration through another notification. In the original single-threaded event model no extra synchronization is needed.
All equipment observers report to the same standings software object, and leaders returns every maximum or Nil if empty. The query takes to find/filter scores for active equipment objects, plus sorting the tied names for deterministic presentation by name; equal names may remain in either order and still denote distinct equipment. This uses the exact supplied integer score formula and its integer division; it does not substitute a different performance metric. A functioning unsubscribe operation, if required, must explicitly correct the source to _functionalities = _functionalities diff List(f).
Use the iterator pattern when clients need sequential access to a collection's elements without depending on its internal representation. A collection supplies a traversal object with operations such as hasNext and next; the client uses the same traversal interface whether the collection is an array, linked list, or another data structure.
The iterator keeps the traversal state separate from both the collection and client, so several independent traversals can coexist and the representation can change without rewriting traversal logic. It can also support incremental or lazy evaluation of elements. Exhaustion must have defined behavior, and a mutable collection must define how updates during traversal are handled. The pattern does not by itself promise that arbitrary concurrent modifications are safe.
The two patterns are the factory method pattern and the decorator pattern. Manufacturer.build is the factory operation specialized by the two national manufacturer software classes. Option and its subclasses wrap a Car to add configurable behavior.
For the factory method pattern, Manufacturer is the abstract creator and declares build(carType): Car; UKManufacturer and USManufacturer are concrete creators. Car is the abstract product interface, and Convertible, Family, and Sports are concrete products. Each national creator selects one product software class from carType and configures the national settings. The diagram does not contain distinct families of national product interfaces or several abstract product-creation operations, so abstract factory pattern is not the most precise identification of this single-operation design.
For the decorator pattern, Car is also the component interface. Convertible, Family, and Sports are concrete components; Option is the abstract decorator, both a subtype of Car and associated with a wrapped Car. DieselEngine, AlarmSystem, and AutomaticTransmission are concrete decorators. Each delegates baseline behavior to its wrapped car, augments description, and adds its surcharge to price. National properties should delegate unchanged through decorators.
A customer can compose options, for example new AlarmSystem(new DieselEngine(baseCar)). Every layer remains usable through the Car interface; each layer adds its own description and price contribution. Factory methods choose/configure the base car, and decorators compose optional additions without requiring a subclass for every option combination. If applying each option at most once is required, enforce that as a separate ordering constraint; unrestricted decorator nesting alone permits repeated options.
The diagram omits the type of carType and the concrete constructors. Choose String selectors "convertible", "family", and "sports", no-argument concrete car constructors, and writable temperatureScale and driverSide properties on a fresh Car. Under this explicit interface convention the two methods are:
abstract class Manufacturer {
  def build(carType: String): Car
}

class UKManufacturer extends Manufacturer {
  override def build(carType: String): Car = {
    val car: Car = carType match {
      case "convertible" => new Convertible
      case "family"      => new Family
      case "sports"      => new Sports
      case _ => throw new IllegalArgumentException("Unknown car type: " + carType)
    }
    car.temperatureScale = "Celsius"
    car.driverSide = "left"
    car
  }
}

class USManufacturer extends Manufacturer {
  override def build(carType: String): Car = {
    val car: Car = carType match {
      case "convertible" => new Convertible
      case "family"      => new Family
      case "sports"      => new Sports
      case _ => throw new IllegalArgumentException("Unknown car type: " + carType)
    }
    car.temperatureScale = "Fahrenheit"
    car.driverSide = "right"
    car
  }
}
UK products use Celsius and left-side road traffic; US products use Fahrenheit and right-side road traffic. Here driverSide denotes the side of the road, matching the wording of the source. If the field instead means the side occupied by the steering wheel/driver inside the car, its values must be reversed: right for UK, left for US. The diagram does not resolve that naming ambiguity. With constructor-only immutable properties, pass these same settings to the concrete constructors instead of assigning setters; that is a different interface convention, not a different national policy.
Each branch allocates a fresh concrete Car; it does not reuse mutable cars across orders. Invalid selectors fail explicitly rather than returning null. The base price and description come from the chosen concrete product. Options are applied afterward by wrapping the returned car; build(carType) has no option-list parameter and therefore cannot infer which options a customer wants.

Ancestors (9)

  1. 2016
  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