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.
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 repeated squaring, including index zero:
b2[0] := b; top := 0;
WHILE b2[top]*b2[top] <= n DO
  b2[top+1] := b2[top]*b2[top];
  top := top+1
END;
The loop invariant is for , with for every stored entry except possibly the initial entry when . Squaring gives , proving preservation. The first failed guard identifies the first larger power outside the range. If , no power with needs storing.
Index zero is deliberately included. The original paper asks for indices but then claims that their products represent every allowable power. Taken without , that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.
Let be the largest representable positive integer. The worst case is , requiring indices through . Thus enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.
Store a second array weight with weight[k] = 2^k. Descending through the binary digits of the answer gives this greedy algorithm:
PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
    top, k, i, p: INTEGER;
BEGIN
  b2[0] := b; weight[0] := 1; top := 0;
  WHILE b2[top]*b2[top] <= n DO
    b2[top+1] := b2[top]*b2[top];
    weight[top+1] := weight[top]+weight[top];
    top := top+1
  END;
  i := 0; p := 1; k := top;
  WHILE k >= 0 DO
    IF p*b2[k] <= n THEN
      p := p*b2[k]; i := i+weight[k]
    END;
    k := k-1
  END;
  RETURN i
END FastLog;
For the second loop, write . Immediately before processing , its loop invariant is
Initially the failed squaring guard gives ; this also holds when , since then . The test succeeds exactly when . If successful, adding selects that binary digit; otherwise the upper bound tightens to . Either way the invariant holds for the next smaller . At , , so i = L.
There are squarings and descending tests. For fixed , this is arithmetic operations, hence logarithmic in the bit length of , and also within the weaker bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.
Let be the maximum positive machine integer. A positive product suffers integer overflow when . The vulnerable expressions are p*b in part (b), b2[top]*b2[top] in the table guard, and p*b2[k] in the descending search. Even a rejected candidate must be evaluated before its comparison with .
The table guard becomes dangerous as soon as its current entry exceeds : approximately for signed 32-bit integers, or for signed 64-bit integers. These are thresholds for the intermediate power, not for alone. For example, with 32-bit arithmetic, and reach the stored power and then try its overflowing square . If , even the initial square may overflow for a tiny . In part (b), the final test can overflow when the next power above exceeds ; at , this already happens for .
For positive operands, integer division gives the exact equivalence . Therefore replace the three guards respectively by
p <= n DIV b
b2[top] <= n DIV b2[top]
p <= n DIV b2[k]
and perform each multiplication only after its guard succeeds. Every accepted product is then at most . With these guarded products and sufficient table capacity, the algorithms work throughout , . The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.
Separate integer partitions according to whether they contain a part equal to . Removing one such part is a bijection to partitions of whose parts are at most . The alternatives are disjoint, giving
Use , because the empty integer partition is counted once, and for , with for . This Oberon implementation avoids negative recursive arguments:
PROCEDURE P(i, n: INTEGER): INTEGER;
VAR answer: INTEGER;
BEGIN
  IF n = 0 THEN answer := 1
  ELSIF i = 0 THEN answer := 0
  ELSIF i > n THEN answer := P(i-1, n)
  ELSE answer := P(i-1, n) + P(i, n-i)
  END;
  RETURN answer
END P;

PROCEDURE Partitions(n: INTEGER): INTEGER;
BEGIN
  RETURN P(n, n)
END Partitions;
The precondition is . Each recursive call reduces , proving algorithm termination. Every positive part of a partition of is at most , so the required one-argument count is . Counts require a sufficiently wide integer representation.
Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):
PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
    table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
  table[0,0] := 1; j := 1;
  WHILE j <= n DO table[0,j] := 0; j := j+1 END;
  i := 1;
  WHILE i <= n DO
    table[i,0] := 1; j := 1;
    WHILE j <= n DO
      table[i,j] := table[i-1,j];
      IF j >= i THEN
        table[i,j] := table[i,j] + table[i,j-i]
      END;
      j := j+1
    END;
    i := i+1
  END;
  RETURN table[n,n]
END CountPartitions;
Require . The outer loop invariant says all rows below equal . The inner loop invariant additionally says entries before column in the current row are correct. Its dependencies are the previous row and the earlier column , so no future entry is read. Each state is evaluated once, giving arithmetic operations and stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.
For a proposed loop invariant , initial condition , guard , body , and postcondition , establish these Hoare logic obligations:
The first establishes before the loop; the second preserves it after each iteration; the third derives the desired result when the guard is false. Together they prove partial correctness. For total correctness, also prove algorithm termination, for example by a nonnegative integer loop variant that strictly decreases whenever the body executes. The loop invariant need not be the postcondition: it generally describes completed and unfinished work together.
Use the convention , as required by the paper's rotation example. Follow each permutation cycle once. Temporarily encode a visited value as , and restore the whole permutation before returning:
PROCEDURE Permute(VAR p: ARRAY OF INTEGER);
VAR s, j, next: INTEGER; saved: T;
BEGIN
  s := 0;
  WHILE s < N DO
    IF p[s] >= 0 THEN
      IF p[s] = s THEN
        p[s] := -p[s]-1
      ELSE
        saved := a[s]; j := s;
        next := p[j]; p[j] := -next-1;
        WHILE next # s DO
          a[j] := a[next]; j := next;
          next := p[j]; p[j] := -next-1
        END;
        a[j] := saved
      END
    END;
    s := s+1
  END;
  s := 0;
  WHILE s < N DO p[s] := -p[s]-1; s := s+1 END
END Permute;
Require LEN(p) >= N and that p[0..N) is the stipulated permutation. Its cells must be writable and distinct from the data array. The marking map is reversible and fits whenever the original valid indices and fit in the signed integer type.
At each outer test, all marked indices belong to fully completed cycles; all unmarked cycles still contain their original data and permutation entries. Within a cycle the same shifting loop invariant as part (d) applies, with successor given by the original p: all previously filled positions have their final values, and saved preserves the overwritten first source. A permutation has no path into a different cycle, so every new successor is unmarked until it returns to s; no encoded negative value is used as a source index. At outer-loop exit every index is marked and correct. The restoration loop has decoded precisely the indices below s.
The procedure uses one extra value of type T, time, and at most data reads plus data writes, with no data access for fixed points. It returns p unchanged, though it marks it temporarily. If p must remain read-only even during execution, test whether each index is its cycle's smallest member by traversing p before moving that cycle. That preserves constant space and the same optimal data accesses, but can require index-array accesses.
Compare the two heads, emitting one copy of a tie and advancing both inputs in that case:
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
  | x < y     = x : merge xt ys
  | x > y     = y : merge xs yt
  | otherwise = x : merge xt yt
The emitted head is the smallest remaining value, so induction preserves strict order and removes duplicates. The extra empty-input cases also make the definition useful on finite lists.
There is a mathematical qualification to the unrestricted infinite-input claim: the union must be enumerable in this order. If one input increases to one from below and the other starts at two, no finite output position can contain two. Locally finite sorted-stream merge excludes this obstruction, and applies to the positive integer streams needed below.
Tie the three scaled streams back to the same shared lazy list:
hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming)
                    (merge (map (3*) hamming) (map (5*) hamming))
The resulting values are precisely the Hamming numbers for nonnegative integers . Every noninitial value has a smaller predecessor obtained by removing a factor, so the recursive demand can be supplied from earlier cells. This is the productivity argument for a sorted multiplicative closure stream. The merge algorithm removes duplicate representations such as , retaining strict order and every generated value.
Choose the representative . Since is prime and does not divide , their greatest common divisor is one. The extended Euclidean algorithm gives the Bezout identity
for some integers . Reducing modulo gives , so the residue class of is a multiplicative inverse of . The argument uses the nonzero condition to exclude the only residue with greatest common divisor .
First prove for every nonnegative integer by mathematical induction. The case is immediate. If it holds at , the binomial theorem and the stated divisibility of the middle binomial coefficients give
This establishes the induction. For an arbitrary integer , take a nonnegative representative of its residue class; then . When , part (b) supplies a multiplicative inverse modulo . Multiplying the congruence by that inverse proves Fermat's little theorem:
Use exponentiation by squaring, retaining the unprocessed exponent in k:
def eaBinary(n: Int): Double = {
  require(n > 0)
  var base = 1.0 + 1.0 / n.toDouble
  var k = n
  var result = 1.0
  while (k > 0) {
    if ((k & 1) != 0) result *= base
    k = k / 2
    if (k > 0) base *= base
  }
  result
}
Writing , the loop invariant is and . If the old exponent is , , multiplying the accumulator by and replacing the remaining power by preserves the invariant. When , the unused squaring may be omitted. The nonnegative integer k is a loop variant, since for . At exit the remaining power is one, giving . There are iterations, at most one accumulator multiplication and one squaring per iteration, hence multiplications and constant space.
First rearrange the ratios so that the intermediate powers remain moderate:
This avoids separately forming enormous powers such as . Perform the two instances of exponentiation by squaring in one while loop, using coupled binary exponentiation:
def ec(n: Int): Double = {
  require(n > 1)
  val dn = n.toDouble
  var x = 1.0 + 1.0 / dn
  var y = 1.0 + 1.0 / (dn - 1.0)
  var k = n
  var l = n - 1
  var p = 1.0
  var q = 1.0
  while (k > 0 || l > 0) {
    if (k > 0) {
      if ((k & 1) != 0) p *= x
      k /= 2
      if (k > 0) x *= x
    }
    if (l > 0) {
      if ((l & 1) != 0) q *= y
      l /= 2
      if (l > 0) y *= y
    }
  }
  (dn + 1.0) * p - dn * q
}
With and , the loop invariant is , , and . Each active branch preserves its own power identity by the parity argument in part (a)(ii), and an inactive branch changes nothing. The loop variant is the mathematical integer , which need not be computed in a fixed-width variable: it decreases whenever either exponent is positive. At exit , , proving the returned expression is . There are iterations, at most four loop multiplications each, and two final multiplications. Converting n before adding one avoids integer overflow at Int.MaxValue.
The rearrangement avoids floating-point overflow in the original powers, but subtraction still combines two quantities of order to obtain one of order one. Catastrophic cancellation can amplify their accumulated roundoff error. The mathematical approximation error therefore does not imply that the Double implementation improves indefinitely as n grows.
Return the lower-bound search boundary, permitting both zero and the array length:
def lowerBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) < x) lo = mid + 1
    else hi = mid
  }
  lo
}
The precondition includes nondecreasing order. The loop invariant is
Initially both excluded ranges are empty. If , sortedness justifies excluding every position through mid; otherwise it justifies excluding every position from mid onwards. The loop variant is a nonnegative integer that strictly decreases. When the old width is positive, mid is a valid array index. The midpoint expression avoids adding two potentially large indices. At exit , so lo satisfies the required partition, including when . Each new width is at most half the old width, rounded down; this gives time complexity and constant space, conventionally for nontrivial sizes.
A second binary search locates the first entry strictly greater than x:
def upperBound(a: Array[Int], x: Int): Int = {
  require(a != null) // a is nondecreasing
  var lo = 0
  var hi = a.length
  while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (a(mid) <= x) lo = mid + 1
    else hi = mid
  }
  lo
}

def equalRange(a: Array[Int], x: Int): (Int, Int) =
  (lowerBound(a, x), upperBound(a, x))
For upper-bound search, the loop invariant is , , and ; its loop variant is again . The same midpoint and sortedness arguments prove preservation, termination and time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.
Let the two boundaries be . There cannot be a value greater than before the first value at least , so . Every entry between them is simultaneously at least and at most , hence equals . Entries before are smaller and entries at or after are larger, so the interval cannot be extended at either end. This proves the equal-range search result is maximal. If x is absent, i == j, both equal to its insertion position; this can be zero, , or an interior gap. Two logarithmic searches still have logarithmic total time complexity. Computing an upper boundary as lowerBound(a, x+1) would introduce an unnecessary integer overflow bug at the largest integer.
Take the abstract state to be a finite sequence of integers, initially empty. Let denote the entry state, the empty sequence, and concatenation. A Scala trait presents the interface; its comments give the mathematical preconditions and postconditions:
trait DoubleEndedQueue {
  // Pre: true. Post: result == s0.isEmpty and s == s0.
  def isEmpty: Boolean
  // Pre: true. Post: s == [x] ++ s0.
  def addLeft(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.head, s == s0.tail.
  def getLeft(): Int
  // Pre: true. Post: s == s0 ++ [x].
  def addRight(x: Int): Unit
  // Pre: s0.nonEmpty. Post: result == s0.last, s == s0.init.
  def getRight(): Int
}
The double-ended queue has no abstract capacity limit in this first specification. Both removals require nonemptiness; the query leaves the state unchanged, an instance of command-query separation.
Programming language polymorphism means that one interface or program definition can be used with values of multiple types. In object-oriented programming, subtype polymorphism allows references with a common static type to denote instances of different concrete subclasses or implementers of a trait. An object method call uses dynamic dispatch to select the overriding implementation belonging to the receiver's runtime type. For example, different implementations of a playlist interface can respond to the same insert call without the client testing their concrete classes.
Parametric polymorphism uses type parameters, as in Sequence[A], so the same definition works uniformly for songs, integers, or other elements. Ad hoc polymorphism includes method overloading, where different parameter signatures share a name and the static types determine overload selection. These mechanisms are distinct: selecting an overloaded signature is not the same step as dispatching an override of that selected signature. Class inheritance can supply implementations, but the reusable interface and legal subtyping relationship determine what a polymorphic client may do.