In binary long division, first double the divisor until it exceeds x, then halve it successively. Keep p = 2^j and d = y*p, so no exponentiation is needed inside a loop:
q := 0; r := x;
j := 0; p := 1; d := y;
WHILE d <= x DO
  d := 2*d;
  p := 2*p;
  j := j+1
END;
WHILE j > 0 DO
  d := d DIV 2;
  p := p DIV 2;
  j := j-1;
  IF r >= d THEN
    r := r-d;
    q := q+p
  END
END
The first loop invariant is , , , and . Every doubling preserves it. For integer inputs, after at most iterations when , d > x; if , this loop has no iterations. The unbounded increase of proves termination. Equivalently, one can use the decreasing nonnegative loop variant while the guard is true.
At the top of the second loop the loop invariant is
It holds on entry because d > x = r. Suppose the old d is and the old p is . After the three halving assignments, and the old remainder satisfies . If , the desired new bound already holds. Otherwise subtracting leaves and adding to q preserves because . The divisions by two are exact: before each halving, j > 0 makes both p and d even.
The loop variant j decreases by one each iteration. At exit , so d = y and the loop invariant gives the required remainder bound. The work per iteration is constant in the unit-cost model, and the two loops have the same number of iterations. For ,
The case , including , takes constant time. These are arithmetic-operation counts with sufficient range for the doubled values; arbitrary-precision arithmetic incurs additional bit complexity. If the inputs were arbitrary positive real numbers, the uniform bound would depend on rather than only ; the stated is the conventional integer division interpretation.
The loop invariant in binary long division says exactly where the true integer quotient lies:
Halving p proposes the midpoint q+p of this candidate interval. The comparison r >= y*p is equivalent to (q+p)*y <= x, so it decides whether the quotient is in the upper or lower half. Adding p chooses the upper half; leaving q unchanged chooses the lower half. Thus binary long division is binary search for the last integer satisfying , deciding the quotient's binary numeral system digits from most significant to least significant. The doubling loop first finds a power-of-two interval containing that quotient.
Heapsort uses time for bottom-up heap construction and for each extraction, giving worst-case time complexity. An iterative heapify down on an array uses auxiliary space complexity. Ordinary heapsort is not a stable sorting method.
Quicksort has balanced-case and average-case time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes and , giving . With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is when balanced and in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.
Counting sort uses time complexity for possible consecutive integer keys. The stable sorting version uses auxiliary space complexity including the output array; counting and re-emitting bare keys needs only beyond its output. It is attractive when is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.
An Oberon recursive procedure can implement the defining recurrence relation directly. Its precondition is ; arithmetic is assumed to remain in the representable integer range.
PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n <= 2 THEN
    result := 1
  ELSE
    result := Fib(n-1) + Fib(n-2)
  END;
  RETURN result
END Fib;
Correctness follows by strong induction: the two base inputs give , and for the returned sum is . On each recursive branch the positive integer argument strictly decreases, while recursion stops at or . The well-ordering principle therefore proves algorithm termination.
The method repeats many subproblems and has exponential time complexity; termination alone does not make it efficient.
In tail recursion, each recursive call is a tail call: its result is returned directly, with no suspended addition or other work. A compiler can then reuse an activation record, giving constant stack use. This is a possible optimization, not a guarantee made by the source syntax. The direct Fibonacci number procedure in part (a) must retain information while waiting to add two recursive results.
Extend the Fibonacci numbers with and use the suggested quantity . For ,
while . This gives the Oberon procedures
PROCEDURE G(n, a, b: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n = 1 THEN
    result := a
  ELSE
    result := G(n-1, a+b, a)
  END;
  RETURN result
END G;

PROCEDURE FibTail(n: INTEGER): INTEGER;
BEGIN
  RETURN G(n, 1, 0)
END FibTail;
The assignment of the recursive result does not perform arithmetic after the call; it merely passes that result to RETURN, so the call is in tail recursion. A dialect permitting an immediate RETURN G(...) in the branch expresses the same control flow. The decreasing argument proves algorithm termination, and the displayed identity proves correctness by mathematical induction. Thus
There are recursive steps, giving arithmetic operations. Stack use is with tail call elimination and without it. With unbounded integers, the growing Fibonacci numbers also make arithmetic costs grow; the linear bound counts arithmetic operations.
Replace the recursive transfer in part (b) by simultaneous state updates, using a temporary variable to preserve the old a:
PROCEDURE FibIter(n: INTEGER): INTEGER;
  VAR k, a, b, oldA: INTEGER;
BEGIN
  k := n; a := 1; b := 0;
  WHILE k > 1 DO
    oldA := a;
    a := a + b;
    b := oldA;
    k := k - 1
  END;
  RETURN a
END FibIter;
For original input , a loop invariant is
It holds initially because . Each iteration preserves it by the identity from part (b). The loop variant is , a nonnegative integer that decreases by one whenever the guard holds. On exit , so the loop invariant gives , exactly the returned answer. The procedure uses arithmetic operations and stored integer variables, without depending on compiler treatment of tail calls.
Treat as fixed positive integers. For , . Raising this inequality to the positive power gives
The factor is independent of , as required by Big O notation. Hence
A bound uniform over varying is not what the notation here asserts.
For finite sets, the inclusion-exclusion principle states
An element present in of the sets is counted times, which explains the alternating corrections.
There are positive integers strictly below divisible by . For the divisors , the single counts are . Their pairwise intersections correspond to divisibility by , giving . The triple intersection has elements. Therefore
This numbered item specifies the model used below. A convenient sample space is the collection of ordered pairs , each with probability . The corresponding random variables are determined by the sum and difference. Inverting the two equations gives
Thus a candidate pair is possible exactly when and are both integers between and . In particular, and must have the same parity. This inverse description will determine the joint probability mass function.
First restrict to integers in the marginal supports: and . Their marginal probabilities are positive. By part (i), a feasible joint pair identifies a unique ordered pair of rolls, so its joint probability is ; an infeasible pair has joint probability zero.
Put and . If the two events were independent, a feasible pair would require
Since , equality forces , hence . But that pair is infeasible. An infeasible pair cannot give independence either, since its joint probability is zero while the product of its positive marginal probabilities is positive. Thus
If all real values of are allowed literally, an impossible event is independent of every event. The complete answer without a support restriction is therefore
These solutions follow the original examination of 11 June 2013, code 4208.[ref] Each question's Haskell definitions form a separate namespace; hide redefined Standard Prelude names when compiling them. Unless stated otherwise, arguments are finite and total. Time complexity counts primitive operations; the cost of comparing variable-length words and the growing bit cost of exact integer arithmetic are stated separately where relevant.[ref]
Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:
pascal :: [[Integer]]
pascal = iterate next [1]
  where
    -- Padding supplies the two boundary entries as well as the interior sums.
    next :: [Integer] -> [Integer]
    next row = zipWith (+) (0 : row) (row ++ [0])
Here iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.
Indexing rows and columns from zero, Pascal's rule says
Take out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through takes arithmetic operations, with additional bit costs as the binomial coefficients grow.
In the 0-1 knapsack problem, item has weight and value . Choose a subset of the items, using each at most once, whose total weight is at most and whose total value is as large as possible. For the capacity-indexed dynamic program, take and the weights to be nonnegative integers. The empty choice is allowed.
Let be the greatest value attainable using only items with capacity . The base case is . With item unavailable when it is too heavy, the recurrence is
Every feasible optimum either excludes item , giving the first candidate, or includes it exactly once, leaving capacity for earlier items. The principle of optimality proves that the remaining earlier items must attain the indicated residual optimum. Conversely, either candidate constructs a feasible solution, so taking the larger is both necessary and sufficient. Mathematical induction on proves the table's meaning and the final answer .
Store item weights and values in arrays and the values in a two-dimensional array with entries. Fill rows in increasing ; each entry uses at most two values from the previous row. There are constant-work updates, giving
For positive growing capacities this is the familiar bound. The terms also cover capacity zero and zero-weight items: one must not initialize every to zero if zero-weight, positive-value items are allowed.
To recover an actual subset, store the chosen alternative at each entry or compare the two candidates while tracing backward from . A selected item changes to ; an excluded item changes it to . This takes extra time.
If only the optimal value is needed, keep two rows, using space. With strictly positive weights, a single capacity row updated in decreasing capacity also prevents item reuse. The two-row version handles zero weights without special in-place reasoning. The running time is pseudopolynomial, since the binary input length of is only logarithmic in its numerical value.
For the two-bag 0-1 knapsack problem, let be the maximum total value using the first items, with remaining capacity limits in the first bag and in the second. Initialize . Item has exactly three possible decisions: omit it, place it in bag one if it fits, or place it in bag two if it fits. Hence
A braced candidate with a false condition is omitted. All candidates refer to layer , which prevents the same item from entering both bags. Combining two independently optimized single-bag knapsacks would not enforce that restriction.
The principle of optimality proves correctness exactly as in part (b): condition on the location of the final item and replace the earlier items by the optimal feasible residual assignment. Every candidate is realizable, and every feasible assignment belongs to one of the three cases. The final answer is .
Fill the three-dimensional array in increasing item index. Each of its updates inspects at most three candidates:
For positive capacities the customary expression is . Keeping only two item layers reduces space to for the optimal value. Full decision storage also permits backward reconstruction of each item's bag assignment. Nonnegative integer weights and capacities are the assumptions behind this capacity-indexed dynamic programming table.
Use an abstract finite sequence of integers, initially empty. In the following trait, comments are the mathematical specification; means the abstract state on entry, and result means the returned value.
trait ReversableBuffer {
  // Abstract state s: finite sequence of Int, initially [].

  // Pre: true. Post: s = s0 ++ [x].
  def append(x: Int): Unit

  // Pre: true. Post: s = [x] ++ s0.
  def prepend(x: Int): Unit

  // Pre: 0 <= i < length(s0).
  // Post: result = s0 !! i,
  //       s = take i s0 ++ drop (i+1) s0.
  def get(i: Int): Int

  // Pre: true. Post: s = reverse(s0).
  def rev: Unit
}
The postcondition of get includes removal: it is not merely indexed reading. In particular,
Repeated equal values elsewhere in the sequence remain present. List concatenation, indexing and list reversal in the specification describe abstract behavior without committing to a physical representation.
Reuse split and swap, but replace recursive calls with a FIFO queue of unresolved segments. Enqueue only segments of length at least two.
def quicksortLoop(): Unit = {
  val work = scala.collection.mutable.Queue[(Int, Int)]()
  if (a.length > 1) work.enqueue((0, a.length))
  while (!work.isEmpty) {
    val (l, r) = work.dequeue()
    val (lt, gt) = split(l, r)
    if (lt - l > 1) work.enqueue((l, lt))
    if (r - gt > 1) work.enqueue((gt, r))
  }
}
A useful loop invariant is that the pending segments are pairwise disjoint valid array segments of length at least two; the whole array multiset equals its original value; and every inverted pair of positions lies in a single pending segment. Explicitly, if and , some queued contains both and . Thus all ordering obligations are localized to queued segments.
Initially the only possible pending segment is the whole array. One array partitioning confines all its remaining inversions to its two child segments. Its equal middle segment is ordered, the left/middle/right boundaries have the correct ordering, and segments of length at most one cannot contain an inversion. Because array partitioning only permutes the selected segment's entries, it cannot create an inversion across a boundary that previously had no inversions. This proves preservation of the loop invariant.
The loop variant is the total pending length
Processing one segment removes from and adds at most , strictly less because . Thus is a nonnegative integer and decreases. At exit no pending segment exists, so no inversion exists:
The FIFO queue itself can grow to pairs. The time complexity is that of the corresponding recursive quicksort, including linear behavior on equal input. Removing recursion does not make the worst-case time complexity linear or eliminate the work storage.
Keep the neighboring Fibonacci number in a private closure. Before calling the transition with , let its captured following equal .
def fibonacci(): Iter[BigInt] = {
  var following = BigInt(1)
  val step: BigInt => BigInt = (x: BigInt) => {
    val result = following
    following = x + following
    result
  }
  new FunIter[BigInt](BigInt(0), step)
}
The transition returns and stores , preserving the paired Fibonacci recurrence. Initialization gives and , so
Using BigInt allows all Fibonacci numbers rather than a finite prefix before integer overflow. Replacing BigInt by Int gives the source's suggested machine-integer interface with that limitation. With the FunIter implementation from part (c), each transition runs once per generated cell, and copied iterators can advance independently while sharing the privately owned generator. A simpler alternative uses a pure function on pairs, , and projects the first component; the closure above follows the source's suggested single-value approach directly.
An immutable object can widen its element type when adding a value by returning a new object. Introduce a lower type bound on the method's fresh type parameter.
class ISet[+T](contents: List[T]) {
  private val elems: List[T] = contents.distinct

  def add[U >: T](x: U): ISet[U] = {
    val widened: List[U] = elems
    if (widened.contains(x)) new ISet[U](widened)
    else new ISet[U](x :: widened)
  }

  def delete(): (T, ISet[T]) = {
    require(elems.nonEmpty)
    (elems.head, new ISet[T](elems.tail))
  }
}
As before, the representation invariant excludes duplicates, and the abstraction function returns the unordered set of entries. The constructor normalization makes the representation invariant hold even for repeated initial entries. Both operations construct a fresh set object and leave the original object unchanged, including when addition finds an existing member.
For a receiver representing , the new object returned by add represents . Deletion returns a pair with and representing . Crucially,
The widened list is valid because immutable List itself has a covariant type parameter. A client can view an ISet[Int] as ISet[Any], but adding a string creates a separate widened result; it cannot put a string into the old integer set. This explains how using immutable objects makes the desired type variance sound. A direct add(x: T) on a covariant software class would still violate the variance-position rule; immutability alone does not repair an incorrectly typed method signature.
Write with . The difference of two squares factors as
The final factor is an integer, so divides the difference. By congruence modulo an integer, .
The notation means that divides :
This is congruence modulo an integer; equivalently, the two integers have the same remainder on division by the positive integer .