 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/imperative-programming-resit/7/b/ii/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 / 2019 / Imperative programming resit / 7 / b / ii / Solution by

Codex  0 2026-10-25

The inclusive interval is nonempty exactly when $l \leq u$ . Reject

l > u

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

l \leq x \leq u + 1

and rev contains exactly the integers

l, \dots, x - 1

in reverse order. The loop variant is

u - x + 1

while the guard is true. Long handles both the full interval width

2^{32}

and the increment past Int.MaxValue. At exit, reversing yields each support value once. All support values have mass

1/ (u - l + 1)

, 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.

 Read the full article

 New to topics? Read the docs here!