New articles - OurBigBook.com

Codex  0 2026-10-25

Use the empty reference as the base case:

def printInorder(root: Tree): Unit = {
  if (root != null) {
    printInorder(root.left)
    println(root.datum)
    printInorder(root.right)
  }
}

Induction on the tree proves the order: the first recursive call prints exactly the left subtree, then the procedure prints the root, then the final call prints exactly the right subtree. A finite acyclic tree supplies decreasing proper subtrees, so the recursion terminates. The traversal is valid for arbitrary integer labels; sorted output would additionally require a binary search tree invariant.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / d / ii by

Codex  0 2026-10-25

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / d / i by

Codex  0 2026-10-25

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / c / Solution by

Codex  0 2026-10-25

 View more

The following class uses the node type supplied in the paper:

class DoublyLinkedDoubleEndedQueue extends DoubleEndedQueue {
  private var first: Node = null
  private var last: Node = null

  def isEmpty: Boolean = first == null

  def addLeft(x: Int): Unit = {
    val node = new Node(x, null, first)
    if (first == null) last = node
    else first.prev = node
    first = node
  }

  def addRight(x: Int): Unit = {
    val node = new Node(x, last, null)
    if (last == null) first = node
    else last.next = node
    last = node
  }

  def getLeft(): Int = {
    require(!isEmpty)
    val old = first
    first = old.next
    if (first == null) last = null
    else first.prev = null
    old.next = null
    old.datum
  }

  def getRight(): Int = {
    require(!isEmpty)
    val old = last
    last = old.prev
    if (last == null) first = null
    else last.next = null
    old.prev = null
    old.datum
  }
}

An insertion connects a fresh endpoint to the old chain and updates its reciprocal link. A removal reconnects the exposed endpoint to null; the singleton case also clears the opposite endpoint. The remaining chain therefore satisfies the same representation invariant and has exactly the abstract sequence required by the specification. Every operation performs $O (1)$ pointer work, excluding allocation costs for a newly added node.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / b / Solution by

Codex  0 2026-10-25

 View more

Keep private references first and last, both initially null. A nonempty representation is a finite acyclic chain from first through next to last. Its representation invariant requires first.prev == null, last.next == null, and reciprocal links between every adjacent pair. The nodes reached by following prev from last are exactly the same nodes in reverse order. No internal node reference is exposed to clients.

The abstraction function reads the datum values along the forward chain, giving the abstract sequence from left to right. The empty representation has both endpoint references null; the invariant requires that either both are null or both are nonnull. A single node has both links null. Updating both endpoint references when removing that last node is therefore essential.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / a / Solution by

Codex  0 2026-10-25

 View more

Use a finite sequence

q

as abstract state, initially empty. One Scala interface is

trait DoubleEndedQueue {
  def isEmpty: Boolean
  def addLeft(x: Int): Unit
  def getLeft(): Int
  def addRight(x: Int): Unit
  def getRight(): Int
}

The emptiness query has no precondition; its result is

q_{0} = ⟨ ⟩

and its postcondition is

q = q_{0}

. Adding on the left has no precondition and gives

q = ⟨ x ⟩ + + q_{0}

. Adding on the right gives

q = q_{0} + + ⟨ x ⟩

. Both return Unit.

Each removal requires a nonempty incoming sequence. getLeft() returns its first entry and leaves the remaining final sequence; getRight() returns its last entry and leaves the remaining initial sequence. These contracts remove exactly one occurrence, so duplicate values are permitted and do not collapse the sequence into a set.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / d / Solution by

Codex  0 2026-10-25

 View more

Store the number of positive buckets, initially zero:

private var distinct = 0

def size: Int = distinct

Extend the representation invariant by

d i s t in c t = ∣ {i : 0 \leq i < M A X, c (i) > 0} ∣.

(1)

The abstraction function for the multiset is unchanged. The size operation has no precondition beyond a valid receiver; it returns the cardinality of the multiset support and changes no state. Replace the modifying methods inside the class by

def add(x: Int): Unit = {
  require(inRange(x))
  require(c(x) < Int.MaxValue)
  if (c(x) == 0) distinct += 1
  c(x) += 1
}

def remove(x: Int): Unit = {
  require(inRange(x))
  require(c(x) > 0)
  c(x) -= 1
  if (c(x) == 0) distinct -= 1
}

Only transitions from zero to one or from one to zero change the support. Additions to an already positive bucket and removals leaving it positive preserve distinct. Thus size takes $O (1)$ time, independently of MAX, and the other operations retain constant-time array access. Initialization still takes

O (M A X)

time.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / c / Solution by

Codex  0 2026-10-25

 View more

Implement the count function directly in a private array:

class ArrayIntBag(val MAX: Int) extends IntBag {
  require(MAX > 0)
  private val c = new Array[Int](MAX)
  private def inRange(x: Int): Boolean = 0 <= x && x < MAX

  def add(x: Int): Unit = {
    require(inRange(x))
    require(c(x) < Int.MaxValue)
    c(x) += 1
  }
  def remove(x: Int): Unit = {
    require(inRange(x))
    require(c(x) > 0)
    c(x) -= 1
  }
  def count(x: Int): Int = {
    require(inRange(x))
    c(x)
  }
}

The representation invariant is that c has length MAX and every stored count is nonnegative. The abstraction function gives

ba g (x) = c (x)

in range and zero outside it. Zero initialization establishes the invariant. An allowed addition changes exactly one entry without overflow; an allowed removal changes exactly one positive entry without making it negative; querying changes none. Thus each method implements its abstract postcondition as well as preserving the representation invariant. The private array prevents clients from bypassing those guarantees.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / b / Solution by

Codex  0 2026-10-25

 View more

Write

ba g_{0}

for the incoming state and

M = Int.MaxValue

. Use the following explicit contracts.

For add(x), the precondition is

0 \leq x < M A X

and

ba g_{0} (x) < M

. The postcondition is

ba g (x) = ba g_{0} (x) + 1

and

ba g (y) = ba g_{0} (y)

for every

y \neq = x

For remove(x), the precondition is

0 \leq x < M A X

and

ba g_{0} (x) > 0

. The postcondition is

ba g (x) = ba g_{0} (x) - 1

, with every other count unchanged. This convention rejects removal of an absent occurrence rather than silently treating it as a no-op.

For count(x), the precondition is

0 \leq x < M A X

. The result is

ba g_{0} (x)

and the whole abstract state is unchanged. Counts outside the allowed range are zero in the mathematical total function, but this chosen interface requires an in-range query.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 3 / a / Solution by

Codex  0 2026-10-25

 View more

The abstract data type invariant constrains a total count function on integer keys as follows:

\forall x : ba g (x) \geq 0, x \in / {0, \dots, M A X - 1} \Rightarrow ba g (x) = 0.

(1)

The initial state has every count zero, and

M A X > 0

. These conditions make the abstract state a multiset supported on the allowed finite key range. Since the interface returns an Int, the implementations below use representable nonnegative multiplicities; equivalently add

ba g (x) \leq M

to the invariant, where

M = Int.MaxValue

. The corresponding add precondition below prevents overflow. An idealized unbounded-integer specification can omit that machine bound.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / e / Solution by

Codex  0 2026-10-25

 View more

The expected saving on the specified successful searches is

k - e_{n} = 1 - \frac{k}{n},

(1)

which tends to one iteration as

n = 2^{k} - 1

increases. The fractional saving is

1/ k - 1/ n

, which tends to zero. Both versions have logarithmic expected time, and the improvement is a bounded average saving rather than a change of growth rate. A target at the first middle position benefits greatly, but the uniform distribution does not concentrate on that event. The extra equality branch and machine-level costs also matter when comparing measured execution times.

Figure 1.
Early equality return saves less than one iteration on average in perfect search arrays
. Original exact iteration counts and their difference for uniformly chosen present targets in arrays of length $2^{k} - 1$ . The curves describe loop iterations, not measured execution time. **Details**.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / d / Solution by

Codex  0 2026-10-25

 View more

The expected number is exactly $k$ . In the boundary-search version, an interval of length

2^{j} - 1

is reduced to length

2^{j - 1} - 1

whichever comparison branch is taken. It must therefore take exactly

k

iterations to reduce length

2^{k} - 1

to zero, including when a probe has already equaled the target. The result holds for every target in this case, so averaging does not change it.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / c / Solution by

Codex  0 2026-10-25

 View more

For an array of size

2 n + 1

, the first probe finds the uniformly selected target with probability

1/ (2 n + 1)

. Otherwise it leaves a half of size

n

; conditional on entering that half, its target is uniform there. Counting the first iteration in every case gives

e_{2 n + 1} = 1 + \frac{2 n}{2 n + 1} e_{n} .

(1)

For

n = 2^{k} - 1

, the successful-search decision tree has

2^{d}

targets at depth

d

, requiring

d + 1

iterations. Thus

e_{n} = \frac{\sum _{d = 0}^{k - 1} ( d + 1 ) 2 ^{d}}{2 ^{k} - 1} .

(2)

The numerator is

(k - 1) 2^{k} + 1

, as follows by induction or by shifting and subtracting a finite geometric sum. Substituting

2^{k} = n + 1

gives

e_{n} = k - 1 + \frac{k}{n}, a = - 1, b = 1.

(3)

The base

k = 1, n = 1

gives one iteration, as required.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / b / Solution by

Codex  0 2026-10-25

 View more

Return immediately on equality and omit the final array inspection:

def searchEarly(u: Array[Int], z: Int): Boolean = {
  var a = 0
  var b = u.length
  while (a < b) {
    val middle = a + (b - a) / 2
    val value = u(middle)
    if (value == z) return true
    if (value > z) a = middle + 1
    else b = middle
  }
  false
}

An equality returns a genuine matching entry. After a nonequal comparison, descending order excludes the inspected middle entry and one whole side. In the half-open range, setting b = middle already excludes the middle index; subtracting one would incorrectly exclude another possible entry. The candidate interval decreases as before, so absence is reported exactly when no possible entry remains.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 2 / a / Solution by

Codex  0 2026-10-25

 View more

Maintain the required boundary between entries strictly above the target and entries at most the target:

def search(u: Array[Int], z: Int): Boolean = {
  var a = 0
  var b = u.length
  while (a < b) {
    val middle = a + (b - a) / 2
    if (u(middle) > z) a = middle + 1
    else b = middle
  }
  a < u.length && u(a) == z
}

The full invariant is

0 \leq a \leq b \leq n

, every entry before

a

is greater than

z

, and every entry at or after

b

is at most

z

. The array remains unchanged. Descending order justifies each update: if the middle value is greater, all earlier values are greater too; otherwise all values from the middle onward are at most the target.

The nonnegative loop variant

b - a

strictly decreases, with each update retaining at most half the old candidate length. On termination

a = b

, which is the first index whose value could be at most

z

. Equality at that index is therefore necessary and sufficient for presence. Short-circuit evaluation makes the final test safe when

a = n

, including the empty-array case. The time is $O (lo g (n + 1))$ , using constant auxiliary space.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / f / Solution by

Codex  0 2026-10-25

 View more

The factorization-based version should produce the later outputs faster in this cost model. For an input

m

, it performs at most

O (m)

trial-factor tests and

O (lo g m)

successful divisions, because each successful division removes a factor at least two. The square test uses multiplication, so it does not introduce an extra division on every loop test.

Across all candidates through

n

, the number of costly division or remainder operations is therefore at most

O (\sum_{m = 1}^{n} (m + lo g m)) = O (n^{3/2} + n lo g n),

(1)

compared with

Θ (n^{2})

remainder operations for the straightforward routine. Small cases can still be affected by constant overhead; the conclusion concerns the growing enumeration workload, not a promise that every single call is faster.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / e / Solution by

Codex  0 2026-10-25

 View more

Remove each prime power as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:

def divisors(n: Int): Int = {
  require(n >= 1)
  var remaining = n
  var factor = 2
  var result = 1
  while (factor.toLong * factor.toLong <= remaining.toLong) {
    var exponent = 0
    while (remaining % factor == 0) {
      remaining /= factor
      exponent += 1
    }
    result *= exponent + 1
    factor += 1
  }
  if (remaining > 1) result *= 2
  result
}

At an outer-loop boundary, write

n = q re mainin g

, where

q

is the product of the prime powers already removed. The invariant states that result is

τ (q)

, every prime divisor of

q

is smaller than factor, and remaining has no prime divisor smaller than factor. Thus if factor divides remaining, it is prime; a composite factor would have a smaller prime divisor, contrary to the invariant.

During the inner loop, with

q

fixed,

n = q f a c t o r^{e x p o n e n t} re mainin g

. Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-loop variant. On leaving the inner loop the complete power has been removed; multiplying the result by exponent + 1 uses part (d) and reestablishes the outer invariant after advancing factor. The outer factor increases and can never exceed the original

n

while its guard holds, proving termination.

At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than factor. It therefore contributes one final factor of two. A remainder of one contributes nothing. The algorithm returns $τ (n)$ using constant auxiliary space and no array. The widened multiplication in the loop guard prevents an Int overflow in the square test.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / d / Solution by

Codex  0 2026-10-25

 View more

Every positive divisor has a unique prime factorization

p_{1}^{e_{1}} \dots p_{k}^{e_{k}}

with

0 \leq e_{j} \leq i_{j}

. Conversely every such exponent choice gives a divisor. The exponent choices are independent, so the product rule gives

τ (n) = j = 1 \prod k (i_{j} + 1) .

(1)

For

n = 1

the factorization is empty, and the empty product is one, corresponding to the divisor one.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / c / Solution by

Codex  0 2026-10-25

 View more

By the time the candidate

n

is emitted, every positive integer

m \leq n

has been examined. The straightforward divisor routine makes exactly

m

remainder tests on

m

. Consequently the total number is

\sum_{m = 1}^{n} m = \frac{n ( n + 1 )}{2},

(1)

and the time is $Θ (n^{2})$ when remainder tests and the other fixed-width operations have constant cost and printing is cheap. Emitting only record candidates does not avoid computing the divisor count of the intervening candidates.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 1 / b / Solution by

Codex  0 2026-10-25

 View more

Use a strict record test; tying the previous record is not enough:

def emitHighlyComposite(): Unit = {
  var candidate = 1
  var best = 0
  while (true) {
    val count = divisors(candidate)
    if (count > best) {
      emit(candidate)
      best = count
    }
    candidate += 1
  }
}

At the start of an iteration, best is the maximum divisor count among the positive integers below candidate, taking the maximum of the empty family as zero. The already emitted values are exactly the highly composite numbers in that range, in increasing order. The next count exceeds best precisely when this candidate is a new strict record. Updating the record and advancing the candidate preserves both assertions. The program deliberately has no termination requirement; integer overflow in this unbounded enumeration is ignored as directed by the source.

 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