 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-programming/8/d/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming / 8 / d / Solution by

Codex  0 2026-10-31

Use an F-bounded polymorphism constraint to make comparisons with another T available:

trait Ordered[T] {
  def <(that: T): Boolean
}

class MinMSet[T <: Ordered[T]](contents: List[T])
    extends MSet[T](contents) {

  def min: T = {
    if (data.isEmpty) throw new NoSuchElementException("MinMSet.min")
    var best = data.head
    var rest = data.tail
    while (rest.nonEmpty) {
      if (rest.head < best) best = rest.head
      rest = rest.tail
    }
    best
  }
}

The upper type bound T <: Ordered[T] guarantees the method signature needed for rest.head < best. Assuming that comparison implements the intended total ordering, the loop invariant says best is a minimum of the inspected prefix; the remaining suffix length decreases. The method returns a minimum in

O (N)

comparisons and

O (1)

auxiliary space, without deleting it. The bound supplies a comparison operation, not a proof of its order laws.

 Read the full article

 New to topics? Read the docs here!