New articles - OurBigBook.com

Codex  0 2026-10-25

The coefficient assumptions imply a nonconstant polynomial with

p (0) < 0

and a positive leading coefficient. Thus

p (x) \to + \infty

x \to + \infty

: dividing by its leading power of

x

leaves the positive leading coefficient plus terms tending to zero. There is some

B > 0

with

p (B) > 0

. A polynomial is continuous, so the intermediate value theorem supplies at least one positive root of a polynomial in

(0, B)

This gives neither uniqueness nor monotonicity. Multiple crossings are possible. If the degree of a polynomial is an even integer, the same leading-term argument gives

p (x) \to + \infty

x \to - \infty

, so there is also a negative root of a polynomial. For an odd integer degree of a polynomial no negative root of a polynomial is forced; a linear polynomial with negative constant coefficient and positive slope is a counterexample.

 Read the full article

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

Codex  0 2026-10-25

 View more

Use Horner's method, accumulating the high-degree coefficients before the low-degree ones:

def eval(x: Double): Double = {
  var i = a.length
  var value = 0.0
  while (i > 0) {
    i -= 1
    value = a(i) + x * value
  }
  value
}

At each while loop head the loop invariant is

0 \leq i \leq n, value = \sum_{j = i}^{n - 1} a (j) x^{j - i} .

(1)

The initial sum is empty. Decreasing i and replacing the accumulator by a(i) + x * value extends that sum by one coefficient with the required powers shifted. The loop variant is i; on exit it is zero, so the accumulator equals

p (x)

. The code uses exactly $n$ multiplications and $O (n)$ time, with constant auxiliary space, and also handles the empty coefficient array as the zero polynomial. Initializing from the last coefficient instead would save one multiplication for nonempty arrays.

The invariant is an exact-arithmetic specification. With Double, each arithmetic operation rounds; consequently the code evaluates the Horner expression in floating-point arithmetic, rather than guaranteeing the exact real value for arbitrary coefficients.

 Read the full article

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

Codex  0 2026-10-25

 View more

Choose the following explicit policy: an edit of pounds recomputes euros; an edit of euros recomputes pounds; an edit of the rate keeps pounds fixed and recomputes euros. Amounts may be any finite signed values, while a rate must be finite and strictly positive. Invalid text, non-finite numbers and overflowing conversions leave the last accepted state intact and restore its display.

import scala.swing._
import scala.swing.event.EditDone
import scala.util.Try

object CurrencyConverter extends SimpleSwingApplication {
  def top: Frame = new MainFrame {
    title = "Currency converter"
    val pounds = new TextField(8)
    val euros = new TextField(8)
    val rate = new TextField(8)
    private var poundsValue = 10.0
    private var rateValue = 1.15
    private var updating = false

    private def finite(x: Double): Boolean =
      java.lang.Double.isFinite(x)

    private def money(x: Double): String =
      java.lang.String.format(java.util.Locale.ROOT, "%.2f",
                              java.lang.Double.valueOf(x))

    private def showValues(): Unit = {
      updating = true
      try {
        pounds.text = money(poundsValue)
        euros.text = money(poundsValue * rateValue)
        rate.text = java.lang.Double.toString(rateValue)
      } finally updating = false
    }

    private def commit(field: TextField): Unit = {
      if (!updating) {
        val proposed = Try(field.text.trim.toDouble).toOption
          .filter(finite).map { value =>
            if (field eq pounds) (value, rateValue)
            else if (field eq euros) (value / rateValue, rateValue)
            else (poundsValue, value)
          }
        proposed.foreach { case (newPounds, newRate) =>
          if (finite(newPounds) && finite(newRate) && newRate > 0.0 &&
              finite(newPounds * newRate)) {
            poundsValue = newPounds
            rateValue = newRate
          }
        }
        showValues()
      }
    }

    contents = new FlowPanel {
      contents += new Label("Pounds")
      contents += pounds
      contents += new Label("Euros")
      contents += euros
      contents += new Label("Euros per pound")
      contents += rate
    }
    listenTo(pounds, euros, rate)
    reactions += {
      case EditDone(source) if source eq pounds => commit(pounds)
      case EditDone(source) if source eq euros => commit(euros)
      case EditDone(source) if source eq rate => commit(rate)
    }
    showValues()
  }
}

The numeric state has the invariant

e u ros Va l u e = p o u n d s Va l u e \cdot r a t e Va l u e

and

r a t e Va l u e > 0

; euros are derived instead of being stored independently. A proposal is validated before either stored value changes. The update flag prevents a synchronous programmatic display update from recursively committing another edit. Currency amounts display two decimal places, while the rate retains its parsed precision; display rounding is not repeatedly fed back into the numeric model. Locale.ROOT ensures that formatted decimal points match the input parser.

The code handles the EditDone events used by the paper rather than trying to parse every intermediate keystroke. It uses Scala 2 style and Java 8-or-newer numeric helpers. No Scala compiler or Swing runtime execution was available in the checking environment; the state transitions were checked independently, and the API usage was compared with the supplied contract and official Scala/Swing documentation.^[ref]

 Read the full article

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

Codex  0 2026-10-25

 View more

A widget or model implementing Publisher is the subject. It calls publish(event) when an observable change occurs. An interested Reactor subscribes with listenTo(subject), and adds a partial function to reactions that handles the event types it understands. deafTo(subject) ends that subscription when it is no longer needed.

The connection is therefore made through publisher and reactor interfaces rather than through a hard-coded list of particular application classes. A reactor may observe several publishers and inspect an event's source to distinguish them. The implementation's registration machinery delivers published events to interested reactions; registering a reaction alone is not a substitute for subscribing to the source.^[ref]

For the converter, the three text fields are publishers and the frame is a reactor. Register the three fields once, then handle their edit-completion events to update the stored numeric state and refresh the appropriate displayed values.

 Read the full article

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

Codex  0 2026-10-25

 View more

The observer pattern connects one event-producing subject to a changing set of interested consumers. Consumers register through an observation interface; when a relevant change occurs, the producer notifies them through that interface rather than naming every concrete consumer. Consumers can be added or removed without rewriting the producer's core behaviour.

This is useful for keeping displays, controls or other derived views synchronized with changing state. The design avoids tight coupling from the producer to all concrete dependants, which otherwise makes every new consumer require changes to the producer. Publishing after the producer's representation invariant has been restored also lets callbacks observe a coherent state. The pattern does not by itself prevent notification cycles or obsolete subscriptions; update policy and unregistration still matter.

 Read the full article

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

Codex  0 2026-10-25

 View more

Test-driven development uses a repeating sequence: write a small test for the next required behaviour, observe it fail for the expected reason, add enough implementation to make it pass, and refactor while keeping the tests passing. The initial failure checks that the test can actually detect the absent behaviour. This differs from writing a whole implementation first and only then constructing tests for it; it also uses the tests to guide interface and design decisions rather than only to inspect a finished program.^[ref]

A mixture of test-selection styles is possible; the defining test-first step is normally behaviour-driven. Choosing inputs and expected results from a public contract is black-box testing with respect to the implementation, even if the developer writes the test. Knowing the internal branches can then motivate white-box tests for boundary paths or exceptional cases. TDD specifies the order of development activities, not a rule forbidding either source of test cases. It therefore does not guarantee branch coverage, and passing the growing test suite is not a proof of correctness for untested inputs.

 Read the full article

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

Codex  0 2026-10-25

 View more

Add a generic mapping method inside the supplied trait. Snapshot the finitely many source masses, and sum masses when different entries have the same image:

def map[U](f: T => U): FiniteDist[U] = {
  val entries = getDom.map(x => (f(x), getProb(x)))
  val support = entries.map(_._1).distinct

  new FiniteDist[U] {
    def getDom: List[U] = support
    def getProb(y: U): Double =
      entries.foldLeft(0.0) { case (sum, (image, mass)) =>
        if (image == y) sum + mass else sum
      }
  }
}

Here the mapping is a mathematical function, and keys are assumed to have stable equality consistent with their intended identity. Each source atom is evaluated once when the new distribution is constructed. The distinct image list is exactly the finite support because all listed source atoms have positive mass. Summing collisions, rather than overwriting a previous mass, implements the probability pushforward.

The sets of source atoms with a fixed image partition the original support. Hence nonnegativity is preserved and, in exact probability arithmetic,

\sum_{y} p_{2} (y) = \sum_{y} \sum_{x : f (x) = y} p_{1} (x) = \sum_{x} p_{1} (x) = 1.

(1)

Thus the result is a finite probability distribution. For a constant mapping, every atom merges into one outcome of mass one. Floating-point additions in the implementation can introduce rounding error, so numerical tests of normalization should use a suitable tolerance rather than demand exact equality of Double sums.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 7 / b / iii 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) / 7 / b / 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) / 7 / b / 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) / 7 / a / Solution by

Codex  0 2026-10-25

 View more

Programming language polymorphism lets a common interface or operation apply to values of more than one type. In subtype polymorphism, a variable typed by a base class or trait can refer to instances of different implementing classes. A method call is checked through that common interface, then dynamic dispatch selects the receiver's overriding implementation. For example, a consumer using Iterator[Int] can accept either a filtering iterator or a concatenating iterator without knowing its concrete class.

Inheritance can establish a subtype relationship, while method overriding provides distinct implementations of a shared method signature. The classes must still honour the common behavioural contract; sharing a name alone does not establish substitutability. Parametric polymorphism is different: the type parameter in Iterator[T] or FiniteDist[T] lets a definition work uniformly over element types. Method overloading is a further form of software polymorphism in which the compiler selects a signature using the static argument types; it should not be confused with runtime receiver dispatch.

 Read the full article

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

Codex  0 2026-10-25

 View more

For the implementations above the value is

List('1', '3', '5', '7', '9')

The first half-iterator returns the odd-position characters while consuming the even-position characters as its required skips. By the time it is exhausted, it has consumed the entire shared underlying iterator. The second half-iterator consequently has no entries left when concatenation reaches it. Sharing one source does not create two independent traversals. Neither constructor consumes anything, so it also does not shift the first output before iteration begins. The source's implementation references here should be read as parts (d) and (e); the printed reference to (c) and (d) is a cross-reference slip.

 Read the full article

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

Codex  0 2026-10-25

 View more

Use short-circuit evaluation so that even an availability test of the second iterator is delayed until the first is exhausted:

class ConcatIterator[T](first: Iterator[T], second: Iterator[T])
    extends Iterator[T] {
  def hasNext: Boolean = first.hasNext || second.hasNext

  def next(): T = {
    if (first.hasNext) first.next()
    else if (second.hasNext) second.next()
    else throw new java.util.NoSuchElementException("empty concatenation")
  }
}

Each successful call returns from the first producer while it has entries, then from the second. There is no constructor-time request or element prefetch. This implements concatenation of the producers' remaining sequences, subject to their ordinary iterator contracts.

 Read the full article

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

Codex  0 2026-10-25

 View more

Delay both initial skipping and every later skipped entry until a caller actually requests availability or an output:

class HalfIterator[T](iter: Iterator[T], odd: Boolean)
    extends Iterator[T] {
  private var needSkip = !odd

  def hasNext: Boolean = {
    if (needSkip && iter.hasNext) {
      iter.next()
      needSkip = false
    }
    iter.hasNext
  }

  def next(): T = {
    if (!hasNext)
      throw new java.util.NoSuchElementException("empty half iterator")
    val result = iter.next()
    needSkip = true
    result
  }
}

The state flag means that the next underlying entry, if present, must be skipped before the next selected entry can be exposed. It is initially false for odd positions and true for even positions. Returning a selected entry reinstates that obligation.

Construction does not call the underlying iterator at all. A successful availability check may discard the one required intervening entry, but does not fetch the selected entry. It then clears the flag, so repeated availability checks cannot skip again. To decide whether a second entry exists through this interface, consuming the preceding discarded entry is necessary. After next() returns, it does not eagerly request the following skipped entry. This gives the intended laziness while retaining correct exhaustion behaviour, including an even-position iterator over a singleton input.

 Read the full article

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

Codex  0 2026-10-25

 View more

Yes in special cases; an ordinary finite iterator that progresses through its input needs changing consumption state. For a genuine immutable counterexample, an iterator over an infinite constant sequence needs no changing fields:

final class Ones extends Iterator[Int] {
  def hasNext: Boolean = true
  def next(): Int = 1
}

Removing the first entry of that sequence leaves the same sequence, so this satisfies the iterator behaviour without changing object state. A permanently empty iterator is another example.

For a normal finite nonempty traversal, however, repeated next() calls must eventually change the returned entry or availability, so the implementation needs mutable cursor state somewhere. Declaring only val fields is not a proof of deep immutability: those fields can refer to another mutable iterator, an array, or a stateful closure. The standard API's description of iterators as mutable captures the usual consuming case, rather than enforcing a mutable field in every possible implementation.

 Read the full article

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

Codex  0 2026-10-25

 View more

The two abstract methods are

def hasNext: Boolean
def next(): T

The first reports availability; the second returns and consumes the next entry, or throws a NoSuchElementException if none exists. Other standard iterator operations are supplied in terms of this interface. Repeated availability checks must not lose entries, although they may perform preparatory internal work.^[ref]

 Read the full article

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

Codex  0 2026-10-25

 View more

The iterator pattern exposes sequential traversal through a small interface while hiding the representation of the underlying data. A client asks whether another entry is available and requests the next entry; it need not know whether the producer uses an array, linked list, tree or generated sequence.

The key design benefit is encapsulation of traversal state and representation. The same consuming algorithm can work through the interface for different producers, and each traversal can keep its own cursor state when a fresh iterator is supplied. This independence requires separate consumption states; two references to one iterator share a cursor.

 Read the full article

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

Codex  0 2026-10-25

 View more

For a remaining tree

T

, define the potential

L (\emptyset) = 0, L (T) = ∣ T . l e f t ∣ + L (T . r i g h t) .

(1)

This counts the nodes not on the right spine, so

0 \leq L (T) \leq ∣ T ∣

. Consider a right rotation with old root

y

, left child

x

, and three untouched subtrees

A, B, C

. Before the rotation the potential is

1 + ∣ A ∣ + ∣ B ∣ + L (C) .

(2)

After the rotation it is

∣ A ∣ + ∣ B ∣ + L (C)

, so each rotation decreases $L$ by exactly one while preserving the number of remaining nodes. This supplies a nonnegative decreasing bound for the inner loop.

When the root has no left child, printing it and advancing to its right child leaves

L

unchanged and decreases the remaining node count by one. Thus

∣ T ∣ + L (T)

decreases on every rotation and every removal, proving termination of the whole procedure. Over the entire execution there are exactly

N

printed nodes and exactly

L (T_{0})

rotations, since the final potential is zero. Both quantities are at most

N

, so the running time is $Θ (N)$ for a nonempty tree, with constant auxiliary space. The nested syntax does not imply quadratic time: it is the total potential decrease across all iterations that bounds the inner work. The potential is a proof device and is not computed by the running program.

 Read the full article

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

Codex  0 2026-10-25

 View more

Repeated right rotations expose the next inorder entry without a recursion stack:

def printDestructively(input: Tree): Unit = {
  var root = input
  while (root != null) {
    while (root.left != null) {
      val child = root.left
      root.left = child.right
      child.right = root
      root = child
    }
    println(root.datum)
    root = root.right
  }
}

A right rotation replaces a local shape with inorder order

A, x, B, y, C

by another shape with exactly that same order. The inner loop therefore preserves the inorder sequence of the remaining tree while moving its next output closer to the root. When the left child is null, the root is exactly the first remaining inorder entry. Printing it and advancing to its right child removes that entry from the remaining traversal.

The outer-loop invariant is that the output already produced, followed by the inorder sequence of the current root, equals the original inorder sequence. Consequently the procedure prints every original entry once in order. It stores only a constant number of node references and uses $O (1)$ auxiliary space. It changes the original links, as permitted; clients must not rely on the input tree retaining its earlier shape.

Figure 1.
A right rotation preserves inorder order and decreases the traversal potential by one
. Original seven-node example. Orange edges mark the right spine; nodes off that spine contribute to the left-size potential. The inorder labels remain 1 through 7 before and after the rotation. **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) / 5 / b / Solution by

Codex  0 2026-10-25

 View more

Split the index range at its middle:

def MakeTree(u: Array[Int], a: Int, b: Int): Tree = {
  require(0 <= a && a <= b && b <= u.length)
  if (a == b) null
  else {
    val middle = a + (b - a) / 2
    new Tree(u(middle),
             MakeTree(u, a, middle),
             MakeTree(u, middle + 1, b))
  }
}

For

N = b - a > 0

, the child sizes are

⌊ N /2 ⌋

and

N - 1 - ⌊ N /2 ⌋

, differing by at most one. Induction gives the same property at every descendant, so the result is nearly balanced. Its inorder traversal is the initial subrange, then

u (mi dd l e)

, then the final subrange, reproducing exactly

u [a .. b)

with every occurrence retained.

There is one nonempty recursive call per constructed node and one constant-time base call per empty child position. Therefore construction takes $Θ (N)$ time for $N \geq 1$ , or

Θ (N + 1)

including the empty case, and allocates exactly

N

nodes. The balanced recursion has logarithmic stack depth. The input array need not be sorted: the required property concerns subtree sizes and inorder order, not a search-tree ordering.

 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