New articles - OurBigBook.com

Codex  0 2026-10-31

Apply overload selection followed by dynamic dispatch: the receiver's static type determines visible signatures, and argument static types choose the overload. The receiver's runtime type then selects its override. A super call starts at the inherited implementation instead of redispatching to the override just entered.

For c.f1(y), the Y overload is visible on C, so its body in C runs. For a.f2(x), the X signature is selected and its override in C calls C.f1(X). For a.f2(y), the Y signature is selected; its body in C calls super.f1(y). The superclass B has only f1(X), so that call uses B.f1(X).

For b.f3(y), the static type B exposes only f3(X). Its override in C calls super.f2(x), entering B.f2(X). The unqualified f1(x) inside that body still uses dynamic dispatch on the original C instance, so it calls C.f1(X).

Finally c.f4(x) invokes the companion object C, which is a separate receiver extending B. Its f3(X) calls inherited B.f2(X), whose f1 call dispatches to ObjC.f1(X).^[ref]

The exact five output lines, including the final comma and space on each line, are:

f1(y:Y) in C, 
f1(x:X) in C, f2(x:X) in C, 
f1(x:X) in B, f2(y:Y) in C, 
f1(x:X) in C, f2(x:X) in B, f3(x:X) in C, 
f1(x:X) in ObjC, f2(x:X) in B, f3(x:X) in ObjC, f4(x:X) in C,

Select the signature statically, then dispatch that signature dynamically .

(1)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 5 / c / Solution by

Codex  0 2026-10-31

 View more

Use the iterator adapter from part (b) with a primality test by trial division. A composite positive integer has a divisor no greater than its square root.

def primeIter(upperBound: Int): Iter[Int] = {
  def isPrime(n: Int): Boolean = {
    if (n < 2) false
    else {
      var d = 2
      while (d <= n / d && n % d != 0) d += 1
      d > n / d
    }
  }
  filterIter[Int](isPrime _, new RangeIter(2, upperBound, 1))
}

Before each trial division iteration, no integer in

[2, d)

divides n. If division succeeds, the condition becomes false with

d \leq n / d

, and isPrime returns false. Otherwise the loop ends with

d > n / d

, so every possible small divisor has been excluded. The quotient comparison is equivalent to

d^{2} \leq n

for positive values and avoids integer overflow in d*d.

primeIter (23) : 2, 3, 5, 7, 11, 13, 17, 19.

(1)

Bounds at most two give an empty iterator. This method tests candidates lazily and uses

O (n)

trial divisions for candidate

n

; no efficiency requirement in the question forces a sieve of Eratosthenes implementation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 5 / b / Solution by

Codex  0 2026-10-31

 View more

A demand-driven filtering iterator needs one cached accepted value. Otherwise hasNext would either lose an element or consume another accepted value every time it is queried.

def filterIter[T](p: T => Boolean, it: Iter[T]): Iter[T] =
  new Iter[T] {
    private var buffered: Option[T] = None
    private var finished = false
    private def fill(): Unit = {
      while (buffered.isEmpty && !finished) {
        if (!it.hasNext) finished = true
        else {
          val x = it.next()
          if (p(x)) buffered = Some(x)
        }
      }
    }
    def hasNext: Boolean = {
      fill()
      buffered.nonEmpty
    }
    def next(): T = {
      fill()
      require(buffered.nonEmpty)
      val answer = buffered.get
      buffered = None
      answer
    }
  }

The representation invariant says that buffered holds at most one accepted value. The represented sequence is the buffered value, if present, followed by the subsequence of the underlying remainder satisfying the predicate. Filling moves the next accepted value into the cache and discards only rejected values, so this abstract sequence is unchanged by hasNext. Clearing the cache in next removes its head. Thus

α (filterIter (p, i t)) = filter (p, α (i t)) .

(1)

next works even when the client has not first called hasNext; exhaustion violates its stated precondition. As with ordinary iterator adapters, clients should give this wrapper exclusive consumption of it, and the predicate should give a stable answer for each element. One call may scan several rejected elements, but across a complete traversal each source element is consumed once. Cache storage is constant.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 5 / a / Solution by

Codex  0 2026-10-31

 View more

Interpret step as a positive increment, consistent with the increasing sequence and exclusive upper bound. State this precondition explicitly; a zero increment would not define the intended finite progression. Use a wider cursor to avoid integer overflow on the update after the last valid Int result.

class RangeIter(lower: Int, upper: Int, step: Int) extends Iter[Int] {
  require(step > 0)
  private var current = lower.toLong
  def hasNext: Boolean = current < upper.toLong
  def next(): Int = {
    require(hasNext)
    val answer = current.toInt
    current += step.toLong
    answer
  }
}

After

q

calls to next, the abstraction function is the sequence of values

lower + t step < upper

with

t \geq q

, in increasing order. Repeated calls to hasNext do not change it; next removes precisely its first value. Therefore

1, 3, 5, 7, 9, 11 for RangeIter (1, 13, 2) .

(1)

If lower >= upper, the represented sequence is empty immediately. The paper does not specify a descending-range convention; this implementation exposes its positive-step precondition rather than assigning one implicitly.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / g / Solution by

Codex  0 2026-10-31

 View more

For each source row, use a temporary dense array to accumulate contributions from nonzero pairs. For every stored

A_{ik}

, traverse stored entries in row

k

of the other sparse matrix.

def mult(that: SparseMatrix): SparseMatrix = {
  require(N == that.N)
  val out = new SparseMatrix(N)
  for (i <- 0 until N) {
    val acc = Array.fill[Double](N)(0.0)
    for ((k, x) <- rows(i)) {
      for ((j, y) <- that.rows(k)) {
        acc(j) += x * y
      }
    }
    var j = N - 1
    var result: Row = Nil
    while (j >= 0) {
      if (acc(j) != 0.0) result = (j, acc(j)) :: result
      j -= 1
    }
    out.rows(i) = result
  }
  out
}

During accumulation, acc(j) is the sum of the already processed terms contributing to position

(i, j)

. Missing entries multiply to zero, so ignoring them loses no contribution under the finite arithmetic convention of part (e). At completion,

out_{ij} = k = 0 \sum N - 1 A_{ik} that_{kj} .

(1)

Descending j and prepending produce strictly increasing stored indices. Omitting zero also handles cancellation. The temporary array uses

O (N)

auxiliary space beyond the output. The time complexity is

O (N^{2} + \sum_{i} \sum_{(k, x) \in rows (i)} ∣ that.rows (k) ∣),

(2)

at worst

O (N^{3})

, but potentially much smaller when the matrices are sparse. The

N^{2}

term covers clearing and scanning the row accumulators. Finite-precision rounding can affect the numerical result, as in any Double matrix multiplication.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / f / Solution by

Codex  0 2026-10-31

 View more

Entry

(j, x)

in source row i becomes entry

(i, x)

in destination row j. Visit source rows in descending order and prepend, producing increasing destination column order without a sorting pass.

def transpose: SparseMatrix = {
  val out = new SparseMatrix(N)
  var i = N - 1
  while (i >= 0) {
    for ((j, x) <- rows(i)) {
      out.rows(j) = (i, x) :: out.rows(j)
    }
    i -= 1
  }
  out
}

Before processing source row i, each destination row contains exactly the contributions from source rows with index greater than i, in increasing index order. Prepending index i preserves that order, and each source position is unique. Hence the representation invariant holds and

out_{ji} = A_{ij}, O (N + M) time .

(1)

The source sparse matrix is unchanged.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / e / Solution by

Codex  0 2026-10-31

 View more

Construct a fresh sparse matrix, transform each stored value, and omit products that become zero.

def scale(s: Double): SparseMatrix = {
  val out = new SparseMatrix(N)
  for (i <- 0 until N) {
    out.rows(i) = rows(i).map { case (j, x) => (j, s * x) }
      .filter(e => e._2 != 0.0)
  }
  out
}

Filtering preserves column order. It handles s == 0.0 and any floating point underflow producing zero. Sharing immutable list structure elsewhere would be safe; this code constructs new transformed rows. Within the class, Scala's ordinary private permits access to out.rows. The result is

out_{ij} = s A_{ij} .

(1)

The time complexity is

O (N + M)

for

M

stored entries. As usual for the supplied Double model, arithmetic means machine arithmetic; for a finite-real interpretation assume finite operands and products, excluding infinities and NaNs.

 Read the full article

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

Codex  0 2026-10-31

 View more

Keep the entries before column j, discard any old entry at j, and retain those after it. Insert the replacement only when it is nonzero.

def set(i: Int, j: Int, x: Double): Unit = {
  require(0 <= i && i < N && 0 <= j && j < N)
  val before = rows(i).takeWhile(e => e._1 < j)
  val after = rows(i).dropWhile(e => e._1 <= j)
  val middle: Row = if (x == 0.0) Nil else List((j, x))
  rows(i) = before ::: middle ::: after
}

All indices in before are below j and all in after are above it, so the representation invariant is preserved. Other rows and all other column values remain unchanged:

A_{ij}^{'} = x, A_{k l}^{'} = A_{k l} when (k, l) \neq = (i, j) .

(1)

Assigning zero removes storage for that entry. The time complexity is linear in the stored row length.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / c / Solution by

Codex  0 2026-10-31

 View more

Select entries having the requested column. The representation invariant ensures that the selected list has length at most one.

def get(i: Int, j: Int): Double = {
  require(0 <= i && i < N && 0 <= j && j < N)
  val entries = rows(i).filter(e => e._1 == j)
  if (entries.isEmpty) 0.0 else entries.head._2
}

Consequently

get (i, j) = A_{ij} .

(1)

This version follows the hint and has time complexity linear in the number of stored entries in row i. An ordered early-exit scan is also possible.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / b / Solution by

Codex  0 2026-10-31

 View more

The representation invariant is

N \geq 0

, rows.length == N, and every rows(i) is a nonnull finite list of entries

(j, x)

satisfying

0 \leq j < N, x \neq = 0.0, column indices strictly increase along each row .

(1)

Strict increase excludes repeated columns. The abstraction function gives

A_{ij} = x

when the unique entry

(j, x)

occurs in rows(i), and

A_{ij} = 0

otherwise. Thus omitted positions represent zero; omission does not mean an unknown matrix entry.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 4 / a / Solution by

Codex  0 2026-10-31

 View more

The fresh array initially holds null references, whereas a zero row must be an empty list. Initialize every slot explicitly:

for (i <- 0 until N) rows(i) = List.empty[Entry]

Then

rows (i) = Nil for every i, A_{ij} = 0.

(1)

The following methods belong inside SparseMatrix, using the supplied Entry and Row type aliases.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / f / Solution by

Codex  0 2026-10-31

 View more

Identify the first matching node at level zero, then bypass that node wherever it appears. Comparing keys alone at higher levels could accidentally remove links to a different occurrence with the same key.

def delete(x: Int): Unit = {
  if (x != Int.MinValue && x != Int.MaxValue) {
    val preds = findPreds(x)
    val victim = preds(0).nexts(0)
    if ((victim ne tail) && victim.datum == x) {
      for (level <- 0 until NumLevels) {
        if (preds(level).nexts(level) eq victim) {
          preds(level).nexts(level) = victim.nexts(level)
        }
      }
    }
  }
}

Because higher-level chains are subsequences of level zero, the predecessor found for any level containing victim points directly to it: no earlier equal-valued node can intervene before the first level-zero occurrence. Bypassing it preserves the order and nesting of all the linked lists. Levels lacking it are unchanged. Thus

Delete exactly one occurrence of x if present; otherwise leave the list unchanged .

(1)

The additional work is

O (NumLevels)

. With the usual level cap and random heights, updates have the expected logarithmic time complexity associated with a skip list.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / e / Solution by

Codex  0 2026-10-31

 View more

Pick the new node's highest level once, and splice the same node into every level up to that height. pickLevel must return a value in 0 until NumLevels.

def add(x: Int): Unit = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = findPreds(x)
  val highest = pickLevel
  require(0 <= highest && highest < NumLevels)
  val n = new Node(x)
  for (level <- 0 to highest) {
    n.nexts(level) = preds(level).nexts(level)
    preds(level).nexts(level) = n
  }
}

The fresh array contains null above the chosen height. At each changed level the new node lies after a smaller value and before a value at least x. Every new occurrence is placed before all previous equal-valued nodes, consistently across levels. Therefore the representation invariant is preserved and

α_{new} = α_{old} with one extra occurrence of x .

(1)

The splice work is

O (highest + 1)

in addition to one skip list search.

 Read the full article

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

Codex  0 2026-10-31

 View more

The level-zero successor of the predecessor is the first node whose value is at least x. Thus only one equality test remains.

def contains(x: Int): Boolean = {
  if (x == Int.MinValue || x == Int.MaxValue) false
  else {
    val n = findPreds(x)(0).nexts(0)
    (n ne tail) && n.datum == x
  }
}

In particular, the tail is never reported as a genuine member:

x occurs ⟺ preds (0) . nexts (0) \neq = tail \land datum = x .

(1)

The additional work after the skip list search is constant.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / c / Solution by

Codex  0 2026-10-31

 View more

Start at the highest level. Move right only while the next key is strictly smaller than x, then descend without returning to head.

def findPreds(x: Int): Array[Node] = {
  require(Int.MinValue < x && x < Int.MaxValue)
  val preds = new Array[Node](NumLevels)
  var n = head
  var level = NumLevels - 1
  while (level >= 0) {
    while (n.nexts(level).datum < x) {
      n = n.nexts(level)
    }
    preds(level) = n
    level -= 1
  }
  preds
}

At each inner loop head, n belongs to the current level and has key below x. Every node already passed has key below x. The representation invariant ensures that n also belongs to the next lower level. Stopping just before a key at least x therefore gives

preds (h) . datum < x \leq preds (h) . nexts (h) . datum .

(1)

The tail prevents a null dereference during the comparison. Strict comparison makes the predecessor lie before the first occurrence of x, including duplicates. On the source diagram, findPreds(14) yields data

[11, 9, 9, - \infty]

, in increasing level order.^[ref]

With the customary random-level policy this has expected logarithmic time complexity for a suitably sized level cap; an unlucky skip list can require a linear scan. No deterministic logarithmic guarantee is claimed.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / b / Solution by

Codex  0 2026-10-31

 View more

Follow the next reference for the desired level, stopping at the tail. This returns the genuine nodes in their linked list order, excluding both sentinel nodes.

def nodesAt(level: Int): List[Node] = {
  require(0 <= level && level < NumLevels)
  val out = scala.collection.mutable.ListBuffer.empty[Node]
  var n = head.nexts(level)
  while (n ne tail) {
    out += n
    n = n.nexts(level)
  }
  out.toList
}

Write

L_{h}

for the resulting sequence of nodes at level

h

. The abstraction function is

α = map (datum, L_{0}) .

(1)

It preserves repetitions, because distinct nodes may carry equal values. A suitable representation invariant requires the following:

head and tail are distinct sentinel nodes with the specified extreme values; every node has a nexts array of length NumLevels.
For each level, following references from head gives a finite acyclic chain ending at tail, then null; the data along that chain are nondecreasing. Genuine values lie strictly between the sentinel values.
Each $L_{h + 1}$ is a subsequence of $L_{h}$ by node identity, so the relative order of equal-valued nodes agrees across levels. Every genuine node occurs in $L_{0}$ and on a contiguous initial collection of levels.
A genuine node absent from a level has null in that level's slot. Tail slots are all null; every other slot on a chain points to the next member of that chain.

These structural requirements make the traversal terminate and make descending through levels valid. A probabilistic height distribution is a performance policy, rather than a condition needed for the abstraction function to describe an ordered sequence.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 3 / a / Solution by

Codex  0 2026-10-31

 View more

Assume NumLevels >= 1. Both sentinel nodes occur on every level; the tail ends every linked list.

val head = new Node(Int.MinValue)
val tail = new Node(Int.MaxValue)
for (level <- 0 until NumLevels) {
  head.nexts(level) = tail
  tail.nexts(level) = null
}

The empty skip list therefore has

head ⟶ tail ⟶ null at every level .

(1)

The forbidden data values distinguish the sentinel nodes from genuine entries.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 2 / c / Solution by

Codex  0 2026-10-31

 View more

Every nonempty axis-aligned rectangle has a top-right corner. Enumerate all such corners and retain the greatest area from part (b).

var best = 0
var i = 0
while (i < N) {
  var j = 0
  while (j < N) {
    best = math.max(best, maxRectangleAt(i, j))
    j += 1
  }
  i += 1
}

The loop invariant is that best is the greatest area obtained from the corners processed so far, or zero if there are none. Consequently

maximum area = best, O (N^{3}) time, O (N^{2}) storage .

(1)

The preprocessing cost from part (a) is included. An entirely false matrix, or an empty one, returns zero. In the printed example, rows

5

through

9

and columns

6

through

8

give area

5 \times 3 = 15

; exhaustive corner enumeration confirms that no larger all-true rectangle exists.^[ref]

Figure 1.
An area-15 rectangle and the row run lengths that certify its width
. **Details**.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 2 / b / Solution by

Codex  0 2026-10-31

 View more

Fix the top-right corner

(i, j)

and a bottom boundary

k

. A width

w

is feasible precisely when every row

m \in [i, k)

has at least

w

consecutive true entries ending at column

j

. Thus the largest feasible width is the minimum of those row run lengths, and the area is that width times

k - i

def maxRectangleAt(i: Int, j: Int): Int = {
  var k = i
  var width = j + 1
  var best = 0
  while (k < N) {
    width = math.min(width, rowCount(k)(j))
    k += 1
    best = math.max(best, (k - i) * width)
  }
  best
}

At the loop head, the loop invariant is

i \leq k \leq N

width best = min ({j + 1} \cup {rowCount (m) (j) : i \leq m < k}), = max ({0} \cup {(h - i) i \leq m < h min rowCount (m) (j) : i < h \leq k}) .

(1)

The initial cap

j + 1

makes the empty-prefix case well-defined and cannot restrict any actual run. Each iteration incorporates one new row and tests its corresponding bottom boundary. The loop variant is

N - k

, so

best = i < k \leq N max (k - i) i \leq m < k min rowCount (m) (j), O (N) .

(2)

A zero width contributes area zero, covering the case where no nonempty all-true rectangle starts at that corner.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 2 / a / Solution by

Codex  0 2026-10-31

 View more

For each row, keep the row run length of the processed prefix. A false entry resets the length to zero; a true entry extends it by one.

val rowCount = Array.ofDim[Int](N, N)
var i = 0
while (i < N) {
  var j = 0
  var run = 0
  while (j < N) {
    if (a(i)(j)) run += 1 else run = 0
    rowCount(i)(j) = run
    j += 1
  }
  i += 1
}

The outer loop invariant states that rows before i have all their correct row run lengths. The inner loop invariant states that columns before j in row i are correct and that run is the length of the all-true suffix of a(i)[0..j). Initially this suffix is empty. Updating run gives exactly the suffix length ending at column j, proving the required formula, including zero at a false entry. Every cell is visited once:

rowCount (i) (j) = {0, 1 + rowCount (i) (j - 1), \neg a (i) (j), a (i) (j), O (N^{2}),

(1)

where the fictitious value at column

- 1

is zero. The table itself uses

O (N^{2})

storage.

 Read the full article

 Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.

Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!

Video 1.

Intro to OurBigBook

. Source.

We have two killer features:

topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
Articles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1.
Screenshot of the "Derivative" topic page
. View it live at: ourbigbook.com/go/topic/derivative
Video 2.
OurBigBook Web topics demo
. Source.
local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
Figure 2.
You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website
.
Figure 3.
Visual Studio Code extension installation
.
Figure 4.
Visual Studio Code extension tree navigation
.
Figure 5.
Web editor
. You can also edit articles on the Web editor without installing anything locally.
Video 3.
Edit locally and publish demo
. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
Video 4.
OurBigBook Visual Studio Code extension editing and navigation demo
. Source.
Internal cross file references done right:
Infinitely deep tables of contents:
Figure 6.
Dynamic article tree with infinitely deep table of contents
.
Live URL: ourbigbook.com/cirosantilli/chordate
Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade

All our software is open source and hosted at: github.com/ourbigbook/ourbigbook

Further documentation can be found at: docs.ourbigbook.com

Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact

 Site settings

 Pinned article: Introduction to the OurBigBook Project  Hide

 Pinned article: Introduction to the OurBigBook Project