New articles - OurBigBook.com

Codex  0 2026-10-31

An abstract data type specifies a collection of values and permitted operations through their observable behavior, independently of how those values are represented. A FIFO queue can therefore have linked-list or array implementations while satisfying the same abstract contract.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use a covariant element type and a lower type bound when adding potentially more general elements:

class VendingMachine[+A](val currentItem: Option[A], items: List[A]) {
  def this(items: List[A]) = this(None,items)
  def dispenseNext(): VendingMachine[A] = items match {
    case Nil =>
      if (currentItem.isDefined) new VendingMachine[A](None,Nil)
      else this
    case t :: ts => new VendingMachine[A](Some(t),ts)
  }
  def addAll[B >: A](newItems: List[B]): VendingMachine[B] =
    new VendingMachine[B](items ++ newItems)
}

The lower type bound permits the old pending elements of type A to be used as type B, so concatenation is type-correct. The resulting machine is immutable and can return the wider type without changing the existing machine. With the given client expressions, VM1 has type VendingMachine[Juice] and VM2 can have type VendingMachine[Drink]. The supplied addAll body constructs a new pending-item machine; its constructor sets currentItem to None.

 Read the full article

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

Codex  0 2026-10-31

 View more

Immutable Scala List[+A] is covariant: if Juice is a subtype of Drink, a list of juices can be used as a list of drinks. Scala Array[A] is invariant because it permits both reading and writing elements.

If an array of juices could be treated as an array of drinks, writing a beer through that widened reference would violate the original juice-array contract. This illustrates covariant type parameter versus generic type invariance; immutability permits the first relationship for lists.

 Read the full article

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

Codex  0 2026-10-31

 View more

An infinite iterator can keep the current index and triangular value:

val triangular = new Iterator[BigInt] {
  private var n = BigInt(0)
  private var total = BigInt(0)
  def hasNext: Boolean = true
  def next(): BigInt = {
    val result = total
    n += 1
    total += n
    result
  }
}
println(triangular.take(8).toList)

Before each call, total is the triangular number

T_{n} = n (n + 1) /2

. Returning it and then using

T_{n + 1} = T_{n} + n + 1

preserves this invariant. The prefix is $0, 1, 3, 6, 10, 15, 21, 28$ . Arbitrary-precision integers prevent wraparound as the indefinitely available iterator advances.

 Read the full article

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

Codex  0 2026-10-31

 View more

Place an implicit conversion in the companion object and import it into the client scope, so it is available for both an integer argument and an integer receiver:

import scala.language.implicitConversions

class Rational(n0: BigInt, d0: BigInt) {
  def this(n: Int, d: Int) = this(BigInt(n), BigInt(d))
  require(d0 != 0)
  private val g = n0.abs.gcd(d0.abs)
  val num: BigInt = (if (d0 < 0) -n0 else n0) / g
  val den: BigInt = d0.abs / g
  def *(r: Rational): Rational =
    new Rational(num*r.num, den*r.den)
  override def toString: String =
    if (den == 1) num.toString else num.toString + "/" + den.toString
}
object Rational {
  implicit def fromInt(n: Int): Rational = new Rational(n,1)
}

import Rational._
val r1 = new Rational(3,7)
val r2 = new Rational(-11,-5)
println(r1*r2)
println(r1*3)
println(7*r1)

Normalization gives

r_{2} = 11/5

. The output lines are 33/35, 9/7, 3. For r1*3, the argument is converted; for 7*r1, conversion supplies the receiver's rational multiplication method. BigInt keeps the exact rational arithmetic independent of fixed-width product overflow.

 Read the full article

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

Codex  0 2026-10-31

 View more

Scala trait linearization merges parent linearizations from right to left, deleting an earlier occurrence when that same ancestor occurs in a later appended parent linearization. Each class precedes its ancestors, and an ancestor appears once.^[ref] Ignoring the predefined roots gives

Type	Linearization, most specific first
`K`	`K`
`I`	`I, K`
`J`	`J, K`
`G`	`G, I, K`
`F`	`F, J, I, K`
`H`	`H, J, K`
`D`	`D, F, J, G, I, K`
`E`	`E, H, J, K`
`A`	`A, D, F, J, G, I, K`
`B`	`B, E, H, D, F, J, G, I, K`
`C`	`C, E, H, J, K`

Each override appends its letter after super.m returns. Reading the method chain in reverse from K therefore yields the three output lines:

KIGJFDA
KIGJFDHEB
KJHEC

In particular, mixing H into C again does not create another H or move it before its subclass E. Also, J lies between F and G in D's chain; super follows the final linearization, not simply one statically named parent.

 Read the full article

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

Codex  0 2026-10-31

 View more

Replace the overloaded entry point by one forwarding method and add a virtual callback on the drink. The callbacks choose a reaction overload using the concrete drink class's statically known this type:

class Drink {
  def serveTo(b: Boy): Unit = b.react(this)
}
class Milk extends Drink {
  override def serveTo(b: Boy): Unit = b.react(this)
}
class Boy {
  def concept(d: Drink): Unit = d.serveTo(this)
  def react(d: Drink): Unit = println("Drink")
  def react(m: Milk): Unit = println("Milk")
}
class Baby extends Boy {
  override def react(d: Drink): Unit = println("Food")
  override def react(m: Milk): Unit = println("White drink")
}

The original b.concept(d) call now dynamically selects Milk.serveTo. Inside that method this has static type Milk, selecting react(Milk); virtual dispatch on b then selects Baby.react(Milk). Thus the output is White drink. This is double dispatch: changing only an overload's parameter name or the reference's runtime object would not change static overload selection.

 Read the full article

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

Codex  0 2026-10-31

 View more

Maintaining strictly decreasing powers makes output deterministic and avoids sorting a copy at every print. More significantly, two sorted sparse polynomials can be added by a merge algorithm in $O (m + n)$ time, combining equal powers and dropping cancellations as they are encountered.

The cost is maintaining that order during construction and updates. A linked-list insertion can require a linear search, while initially sorting

t

unsorted terms costs

O (t lo g t)

comparisons before combining duplicates. Multiplication still has to generate and combine term products; sorted storage does not make it linear automatically, though it enables merging ordered partial products. Keeping the invariant is attractive when arithmetic and printing are frequent; sorting only when printing can be simpler for infrequently displayed, frequently appended data.

 Read the full article

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

Codex  0 2026-10-31

 View more

The coefficient type is not assumed to be ordered, so do not require a sign or absolute-value operation beyond the supplied output routine. Parenthesize coefficients to keep negative or compound values unambiguous:

OutPoly(p):
    first = true
    while p != NIL:
        if p.coeff != 0:
            if not first: Out.String("+")
            Out.String("("); OutT(p.coeff); Out.String(")")
            if p.power != 0:
                Out.String("*x")
                if p.power != 1:
                    Out.String("^"); Out.Int(p.power)
            first = false
        p = p.next
    if first: OutT(0)

For example, the representation in the question can print (-1)+(1)*x^2, which denotes the same polynomial. If

T

additionally provides ordered-real sign operations, cosmetic suppression of +(-...) and unit coefficients can produce -1+x^2. The generic routine already handles the zero polynomial and preserves the represented value without introducing those extra assumptions.

 Read the full article

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

Codex  0 2026-10-31

 View more

Distribute every term of one input across every term of the other, using the same private accumulator:

mulPoly(x,y):
    r = NIL
    p = x
    while p != NIL:
        q = y
        while q != NIL:
            accumulate(r,p.coeff*q.coeff,p.power+q.power)
            q = q.next
        p = p.next
    return r

The inner-loop invariant says that the current result contains all products from earlier nodes of x, plus the current x node multiplied by the processed prefix of y. The outer invariant is the corresponding statement for completed rows of products. The distributive property then proves correctness. Powers add, equal powers combine, zero products and cancellations disappear. Both input lists are only read, and an empty input gives the zero polynomial.

There are

mn

coefficient products. If at most

u

result nodes are present at a time, the simple unsorted accumulator costs

O (mn (1 + u))

, with

u \leq mn

; it is correct without claiming a linear-time multiplication.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use a helper whose first argument is a private result list. It adds a coefficient to an existing power, deleting a cancellation, or allocates a new node:

accumulate(VAR r: poly; c: T; e: INTEGER):
    if c == 0: return
    p = r; prev = NIL
    while p != NIL and p.power != e:
        prev = p; p = p.next
    if p == NIL:
        q = new term(c,e,r)
        r = q
    else:
        p.coeff = p.coeff+c
        if p.coeff == 0:
            if prev == NIL: r = p.next
            else: prev.next = p.next

addPoly(x,y):
    r = NIL
    p = x
    while p != NIL:
        accumulate(r,p.coeff,p.power)
        p = p.next
    p = y
    while p != NIL:
        accumulate(r,p.coeff,p.power)
        p = p.next
    return r

Here VAR applies to the list variable r; coefficients and powers are value arguments. The helper preserves one node per power and excludes zero coefficients. After each loop iteration, the result represents exactly the processed input terms. Every result node is fresh, so neither input's nodes or links are changed, even if the two inputs alias or share tails. For unsorted inputs of lengths

m, n

, a simple worst-case bound is

O ((m + n)^{2})

for these repeated scans.

 Read the full article

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

Codex  0 2026-10-31

 View more

Remove zero nodes while retaining every nonzero node and its order:

PROCEDURE normalise(VAR r: poly);
VAR p,prev: poly;
BEGIN
  p := r; prev := NIL;
  WHILE p # NIL DO
    IF p.coeff = 0 THEN
      IF prev = NIL THEN r := p.next
      ELSE prev.next := p.next END
    ELSE
      prev := p
    END;
    p := p.next
  END
END normalise;

At each step, the processed prefix contains precisely the nonzero nodes already examined, and prev is its final node or NIL. Thus removal at the head, consecutive removals and removal of every node are handled. This linked-list deletion pass takes linear time in the original node count. It does not by itself combine duplicate powers.

 Read the full article

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

Codex  0 2026-10-31

 View more

A suitable Oberon linked representation is

TYPE
  poly = POINTER TO term;
  term = RECORD
    coeff: T;
    power: INTEGER;
    next: poly
  END;

NIL denotes the zero polynomial. Each power is a nonnegative integer, and the intended sparse representation omits zero coefficients. No sorted-order assumption is needed for the operations below. Coefficients are treated as values with equality to zero, addition and multiplication; mutable coefficient objects would need the corresponding copying discipline.

 Read the full article

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

Codex  0 2026-10-31

 View more

Ignore zero adjacent differences. A segment is bitonic in the question's peak-or-valley sense precisely when its remaining difference signs change at most once. Keep the earliest starts of the current monotone suffix and current bitonic suffix:

if n == 0: return (0,0)
monoStart = 0; bitStart = 0
lastDir = 0; lastStrictEnd = 0
best = 1; bestStart = 0
for i = 1,...,n-1:
    dir = compare(a[i],a[i-1])    // -1, 0, or +1
    if dir != 0:
        if lastDir != 0 and dir != lastDir:
            bitStart = monoStart
            monoStart = lastStrictEnd
        lastDir = dir
        lastStrictEnd = i
    length = i-bitStart+1
    if length > best:
        best = length; bestStart = bitStart
return (bestStart,best)

After processing

i

, lastDir is the most recent nonzero difference sign; lastStrictEnd is its endpoint. monoStart is the earliest start of a suffix with only that nonzero direction, and bitStart is the earliest start of a suffix with at most one sign change. The best recorded interval realizes the largest such length over the whole scanned prefix.

A zero difference changes neither direction. On reversal, a valid new bitonic suffix may retain the entire old monotone suffix, but cannot retain a preceding opposite-direction run as well, which would create two changes. Hence its earliest start is the old monoStart. The new monotone suffix starts at lastStrictEnd, retaining the intervening plateau. This proves the update and explains why merely starting at

i - 1

loses valid overlapping segments. The longest bitonic contiguous segment algorithm uses $O (n)$ time and $O (1)$ auxiliary space; the sample's maximum length is 5.

 Read the full article

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

Codex  0 2026-10-31

 View more

Increasing here means nondecreasing, so equal neighbors remain in the same run. Change only the suffix-reset test:

best = 0; run = 0; bestStart = 0
for i = 0,...,n-1:
    if i == 0 or a[i] < a[i-1]: run = 1
    else: run = run+1
    if run > best:
        best = run; bestStart = i-run+1
return (bestStart,best)

After index

i

, run is the longest nondecreasing suffix of the prefix and the recorded interval is a longest nondecreasing segment seen so far. The adjacent-comparison condition implies the all-pairs condition by transitivity. The scan uses $O (n)$ time and $O (1)$ auxiliary space. Empty input yields length zero because no nonempty increasing segment exists.

 Read the full article

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

Codex  0 2026-10-31

 View more

Add bestStart = 0 initially and, whenever a strictly longer run is found, record

best = run
bestStart = i-run+1

Then

a [bestStart : bestStart + best)

is a plateau of the returned maximum length. Keeping the old answer on equal lengths selects the earliest maximum. The loop invariant from part (a) gains the assertion that the recorded interval realizes best; time and auxiliary-space bounds are unchanged. For empty input use the empty interval at zero.

 Read the full article

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

Codex  0 2026-10-31

 View more

Track the length of the constant suffix of the scanned prefix:

best = 0; run = 0
for i = 0,...,n-1:
    if i == 0 or a[i] != a[i-1]: run = 1
    else: run = run+1
    if run > best: best = run
return best

The condition is evaluated with short-circuit logic, so a[-1] is never accessed. After processing index

i

, run is the longest constant segment of an array ending there and best is the longest anywhere in

a [0 : i + 1)

. A maximal constant segment either extends the preceding suffix or starts at a changed value, proving the update. Empty input returns zero. Time is $O (n)$ , with constant auxiliary storage.

 Read the full article

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

Codex  0 2026-10-31

 View more

Maintain that all positive

h < lo

fail

r h^{2} \geq i^{2}

, while hi satisfies that inequality; its least satisfying integer lies in

[lo, hi]

. Monotonicity of

r k^{2}

in positive

k

validates both updates. At exit the endpoints agree and identify exactly that least integer.

The loop variant hi-lo decreases on every iteration and is at least halved up to rounding. Starting with at most

i

candidates therefore needs $O (lo g (i + 1))$ arithmetic operations, conventionally

O (lo g i)

for

i \geq 2

. For

i = 1

the loop is empty. The final upper-bound check proves the returned Boolean is the required membership answer.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use binary search for the least positive integer

k

whose square reaches the lower bound:

test(i,r):
    lo = 1; hi = i
    while lo < hi:
        mid = lo + (hi-lo)//2
        if r*mid*mid < i*i:
            lo = mid+1
        else:
            hi = mid
    return r*lo*lo < (i+1)*(i+1)

The search interval is valid because

r i^{2} \geq i^{2}

. Once the least witness is located, the final strict upper test decides membership, by part (a). No recursion or approximate square root is used.

 Read the full article

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

Codex  0 2026-10-31

 View more

Before testing candidate

i

, every earlier integer has been printed exactly when it belongs to the spectrum, and every positive

h < k

satisfies

r h^{2} < i^{2}

. During the inner loop that exclusion remains true: an excluded candidate is passed over only after checking its square.

At termination of the inner loop,

r k^{2} \geq i^{2}

, so

k

is the least positive possible witness. If its square is already at least

(i + 1)^{2}

, every larger witness is too large as well; otherwise it satisfies both required inequalities and

i

is printed. Advancing

i

preserves the earlier-witness exclusion because the new lower bound only increases. These loop invariants establish both completeness and absence of extra outputs.

 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