New articles - OurBigBook.com

Codex  0 2026-10-31

Use missing-value search by deficient value intervals: halve the candidate value interval, and apply array partitioning only to the array segment whose entries lie in that interval.

def missing(): Int = {
  require(N < Int.MaxValue)
  var lo = 0; var hi = N + 1
  var l = 0; var r = N
  while (hi - lo > 1) {
    val p = lo + (hi - lo) / 2
    val k = partition(l, r, p)
    if (k - l < p - lo) {
      hi = p; r = k
    } else {
      lo = p; l = k
    }
  }
  lo
}

The loop invariant is

0 \leq l \leq r \leq N

0 \leq l o < hi \leq N + 1

, and

a [l .. r) \subseteq [l o, hi), r - l < hi - l o .

(1)

More precisely, the segment contains all occurrences of original values in

[l o, hi)

, and the complete array remains a permutation of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original array.

After array partitioning, let

m = r - l

W = hi - l o

m_{L} = k - l

, and

W_{L} = p - l o

. If

m_{L} < W_{L}

, retain the left side. Otherwise the right side has

m_{R} = m - m_{L} < W - W_{L} = W_{R}

(2)

occurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive integer width

hi - l o

decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. Therefore

return l o, l o \in [0, N + 1), l o is absent from the original array .

(3)

For the time complexity, after

t

splits the width is at most

⌈(N + 1) / 2^{t} ⌉

, and the scan length is smaller than that width. Summing over the

O (lo g (N + 1))

levels gives a geometric series plus logarithmic overhead, hence

O (N + 1)

overall, conventionally

O (N)

for

N \geq 1

. This proof bounds the retained occurrence count by the retained value width; it does not assume that each array partitioning splits the number of occurrences in half. The

N = 0

case returns zero immediately.

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 Read the full article

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

Codex  0 2026-10-31

 View more

Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here a and N are the given array and its length.

def partition(l: Int, r: Int, p: Int): Int = {
  require(0 <= l && l <= r && r <= N)
  var k = l
  var j = l
  while (j < r) {
    if (a(j) < p) {
      val t = a(k); a(k) = a(j); a(j) = t
      k += 1
    }
    j += 1
  }
  k
}

The loop invariant is

l \leq k \leq j \leq r, a [l .. k) < p, a [k .. j) \geq p .

(1)

In addition, the active segment remains a permutation of its original contents, and every entry outside it remains unchanged. If a(j) < p, swapping it with a(k) extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The loop variant is

r - j

. At termination

j = r

, so

a [l .. k) < p \leq a [k .. r), return k .

(2)

There are exactly

r - l

iterations, giving

O (r - l + 1)

time complexity and constant auxiliary space.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / d / Solution by

Codex  0 2026-10-31

 View more

Build a maximum spanning tree

T

by the decreasing-weight version of Kruskal's algorithm. For the specified distinct endpoints

s, t

, find their unique graph path

P_{T}

T

by depth-first search, retaining predecessors to reconstruct it. Return that path and its minimum edge weight

b

For correctness, choose an edge

e

of weight

b

P_{T}

. Deleting it splits

T

into two connected components, separating

s

from

t

. No edge

f

across this cut of a graph can have

w (f) > b

: replacing

e

f

would give a spanning tree of greater total weight, contradicting maximality of

T

Every

s

–

t

graph path

P

must cross the same cut of a graph, so it contains a crossing edge

f

with

w (f) \leq b

. Therefore its minimum edge weight is at most

b

. The tree route attains

b

, proving

e \in P_{T} min w (e) = P : s ⇝ t max e \in P min w (e) .

(1)

This is precisely the widest path problem. The proof allows tied, zero and negative edge weights. It depends on maximizing the total tree weight, not on a shortest-distance algorithm.

Let

v = ∣ V ∣

and

e = ∣ E ∣

. Sorting and Kruskal's algorithm take

O (e lo g e + v)

time; the tree search adds

O (v)

. Hence

time O (e lo g e + v), auxiliary space O (e + v) .

(2)

For a connected simple graph with at least two vertices,

v - 1 \leq e \leq v (v - 1) /2

, so the time is also

O (e lo g v)

. The

O (e lo g e + v)

expression remains valid when parallel edges are permitted. If the two endpoints coincide, the empty path is returned, with bottleneck

+ \infty

under the usual empty-minimum convention; otherwise connectedness guarantees a nonempty route.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / c / Solution by

Codex  0 2026-10-31

 View more

Run Kruskal's algorithm in nonincreasing order of edge weight, accepting an edge exactly when its endpoints belong to different current connected components. Use a disjoint-set data structure to test and merge those components. Stop after accepting

∣ V ∣ - 1

edges.

Equivalently, apply ordinary Kruskal's algorithm to

w^{'} (e) = - w (e)

. For every spanning tree,

e \in T \sum w^{'} (e) = - e \in T \sum w (e),

(1)

so minimizing transformed total weight is exactly maximizing original total weight. Thus the output is a maximum spanning tree. Equal weights may be processed in any fixed order. Sorting dominates the time complexity, giving

O (∣ E ∣ lo g ∣ E ∣ + ∣ V ∣)

with the usual efficient disjoint-set data structure.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / b / Solution by

Codex  0 2026-10-31

 View more

A precise safe-extension form of the cut lemma for minimum spanning trees is as follows. Let

F \subseteq E

be contained in some minimum spanning tree. Let

S

be a nonempty proper subset of

V

, and suppose no edge of

F

crosses the cut of a graph

(S, V ∖ S)

. If

e

is any least-weight crossing edge, then

F \cup {e} is contained in some minimum spanning tree .

(1)

To prove it, choose a minimum spanning tree

T

containing

F

. If

e \in T

, it already certifies the claim. Otherwise inserting

e

creates a graph cycle. The other part of that graph cycle must cross the cut of a graph, so choose a crossing edge

f \in T

. It does not belong to

F

, and

w (e) \leq w (f)

. Then

T - f + e

is a spanning tree containing

F \cup {e}

, of weight no greater than the optimum. It is therefore also optimal.

With

F = \emptyset

, a lightest crossing edge belongs to at least one minimum spanning tree. If that edge is uniquely lightest, it belongs to every minimum spanning tree, the strict version of the minimum spanning tree cut property. With ties, “every” would be false: in an equal-weight triangle either crossing edge can be omitted from some optimum.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / a / Solution by

Codex  0 2026-10-31

 View more

For a finite connected graph

G = (V, E)

with undirected edges and edge weights

w

, a spanning tree is a connected, acyclic subgraph containing all vertices. It has

∣ V ∣ - 1

edges. A minimum spanning tree is one minimizing the sum of its edge weights:

T \in F \subseteq E (V, F) is a tree arg min e \in F \sum w (e) .

(1)

It minimizes total weight, rather than the distance of every route from a chosen root. Equal edge weights may permit more than one minimum spanning tree; negative weights do not invalidate the definition.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7 / d / Solution by

Codex  0 2026-10-31

 View more

Assume

1 \leq k \leq n

. Use bottom-up heap construction to make a max-heap of the first

k

input items. For each subsequent input value

x

, compare it with the root. If

x

is at least the root, discard it; otherwise replace the root by

x

and apply heapify down. Return the final root.

The loop invariant says the heap contains a multiset of the

k

smallest values seen so far. It holds after initialization. If

x

is at least the current largest retained value, the already retained

k

items are no larger, so discarding

x

preserves the invariant. If

x

is smaller, remove one largest retained value and keep

x

instead; precisely the

k

smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,

the heap root is the k th smallest input value .

(1)

Construction costs

O (k)

; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexity

O (n + (n - k) lo g k) = O (n lo g k) (k \geq 2), O (k) space .

(2)

For

k = 1

, the heap is a single running minimum and the time is

O (n)

. The uniform expression

O (n lo g (k + 1))

covers that boundary; interpreting the printed

O (n lo g k)

literally at

k = 1

would incorrectly make it zero.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7 / c / Solution by

Codex  0 2026-10-31

 View more

Count pairwise exchanges in the implementation from part (b), including the initial root/final-leaf exchange. For

n \geq 4

, the final leaf has a nonroot parent whose key is strictly larger than the leaf's key. That parent remains after deletion. If the moved leaf could stay at the root without a downward exchange, it would dominate both root children and hence every remaining descendant, contradicting that larger remaining parent. Thus at least one heapify down exchange is necessary.

One downward exchange suffices. The following level-order array is a max-heap on keys one through fifteen:

H = [15, 14, 13, 9, 8, 12, 11, 1, 2, 3, 4, 5, 6, 7, 10] .

(1)

Every parent is larger than both children. Exchange the root key fifteen with the final key ten, remove fifteen, then exchange ten with the larger root child fourteen. Ten now has children nine and eight, so repair stops. The final array is

[14, 10, 13, 9, 8, 12, 11, 1, 2, 3, 4, 5, 6, 7] .

(2)

Figure 1.
A fifteen-key max-heap achieving the minimum two pairwise exchanges during maximum deletion
. **Details**.

Hence the best-case maximum deletion in a binary heap is

two pairwise exchanges for n \geq 4 : one root/last exchange and one downward exchange .

(3)

This best case can be arranged at any such size: make the root child on the opposite side from the old final leaf the largest remaining key, the old leaf smaller than its own ancestors but larger than all descendants of that opposite child, and fill the remaining positions in decreasing order along each branch. The promoted child then allows the leaf to stop at depth one.

For sizes two and three, one initial exchange can suffice; for size one no exchange between distinct positions is needed. If only exchanges during heapify down are counted, the answer for

n \geq 4

is one. In the fifteen-key example the two exchanges involve three distinct keys, namely fifteen, ten and fourteen. An implementation that moves a hole by assignments need not perform literal swaps, so the count is explicitly tied to the exchange implementation. The worst-case time complexity remains logarithmic even though this best-case repair is constant.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7 / b / Solution by

Codex  0 2026-10-31

 View more

Store a complete binary tree in an array

H [0.. n)

, with children

2 i + 1, 2 i + 2

and parent

⌊(i - 1) /2 ⌋

. The max-heap invariant says every parent's key is at least its children's keys. Consequently the root is a greatest-key item, and the height is

⌊ lo g_{2} n ⌋

Here is a pairwise-exchange implementation of extractMax:

extractMax(H, n):
    if n == 0: error "empty priority queue"
    answer = H[0]
    swap(H[0], H[n-1])
    n = n - 1
    i = 0
    while 2*i + 1 < n:
        j = 2*i + 1
        if j + 1 < n and key(H[j+1]) > key(H[j]):
            j = j + 1
        if key(H[i]) >= key(H[j]): break
        swap(H[i], H[j])
        i = j
    return (answer, n)

Only the root can initially violate heap order. Each heapify down exchange promotes the larger child, making the previous position valid and moving the only possible violation down one level. It either stops at a valid position or reaches a leaf. The removed root is saved as answer, and reducing the active array length preserves the complete binary tree shape.

The binary heap operation costs, with existing positions available for handle operations, are:

Operation	Worst-case time
Empty initialization, `isEmpty`, `size`	$O (1)$
`maximum`	$O (1)$
`insert`, `increaseKey`	$O (lo g (n + 1))$
`extractMax`, deletion by handle	$O (lo g (n + 1))$
Build from $n$ arbitrary items by bottom-up heap construction	$O (n)$

Insertion into the binary heap places an item at the next leaf and moves it upward until heap order holds. Raising a key uses the same upward repair. Arbitrary deletion replaces its position by the final item and repairs upward or downward as necessary. A handle must be updated on exchanges; locating an item by value alone can require linear search. The boxed main bounds are

maximum : O (1), insert, extractMax : O (lo g (n + 1))

. Dynamic array resizing is usually amortized or avoided by reserving sufficient capacity.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 7 / a / Solution by

Codex  0 2026-10-31

 View more

A maximum priority queue is an abstract data type holding items with comparable priority keys and giving access to a greatest-key item. Equal priorities may occur; any one of the tied maximum items can be returned unless a tie rule is specified.

empty or initialization creates a queue with no items; isEmpty and size inspect its occupancy.
insert(item, key) adds an item with its priority.
maximum() returns a greatest-priority item without removing it.
extractMax() returns and removes a greatest-priority item.
When mutable priorities are supported, increaseKey(handle, newKey) raises an existing item's priority; the handle identifies its stored location.

The central behavior is

maximum (Q) \in x \in Q arg max key (x)

. Calling maximum or extractMax on an empty queue must report that no item exists. Raising a key is a common supported extension; arbitrary-key changes and deletion by handle can also be supplied.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / e / Solution by

Codex  0 2026-10-31

 View more

Store pred[j] = i whenever a strict improvement sets D[j] = D[i] + 1. Initialize predecessors to NONE. After the dynamic programming pass, return NONE if the final position is unreachable; otherwise follow predecessors backwards:

route = []
j = n - 1
while j != 0:
    route.append(j)
    j = pred[j]
route.append(0)
reverse(route)
return route

Every stored predecessor is smaller than the current index, so reconstruction terminates. Its stored distance is exactly one smaller, so the output has precisely

D [n - 1]

jumps and each jump satisfies its input bound. Therefore

store a minimizing predecessor; reverse the predecessor chain from n - 1 to 0

. Reconstruction takes

O (n)

additional time complexity and

O (n)

output space; the total dynamic programming bounds remain

Θ (n^{2})

time and

Θ (n)

space complexity. Keeping the first predecessor on ties selects one optimal route deterministically.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / d / Solution by

Codex  0 2026-10-31

 View more

Let

D [j]

be the minimum number of jumps from index zero to index

j

, with

\infty

denoting an unreachable position. The minimum forward-jump dynamic programming recurrence is

D [0] = 0, D [j] = 1 + 0 \leq i < j i + A [i] \geq j min D [i] (1 \leq j < n),

(1)

where the minimum of an empty set is

\infty

and

1 + \infty = \infty

. Compute it in increasing index order:

D[0] = 0
for j = 1, ..., n-1:
    D[j] = INFINITY
    for i = 0, ..., j-1:
        if D[i] != INFINITY and A[i] >= j-i:
            D[j] = min(D[j], D[i] + 1)
return D[n-1]

For algorithm correctness, classify any route to

j > 0

by its penultimate index

i

. Every jump advances, so

i < j

, and legality requires

A [i] \geq j - i

. By the principle of optimality, a shortest prefix to

i

can be used; this gives the lower bound represented by the recurrence. Conversely, a minimizing reachable predecessor supplies an actual route of length

D [i] + 1

, proving attainability. Mathematical induction on

j

therefore proves every stored value correct.

There are

n (n - 1) /2

predecessor tests, and two arrays are unnecessary when only the number is required. Thus

time Θ (n^{2}), auxiliary space Θ (n) .

(2)

For the source example, the computed array is

D = [0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4] .

(3)

When

n = 1

, zero jumps are needed even if the lone entry is zero. An unreachable final position returns

\infty

. Testing A[i] >= j-i also avoids forming a potentially overflowing sum i + A[i] in bounded implementations. A faster frontier-based algorithm is possible, but the displayed method directly supplies the requested dynamic programming solution.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / c / Solution by

Codex  0 2026-10-31

 View more

Dynamic programming solves related subproblems once, stores their results, and combines those results in an order consistent with their dependencies. The state must retain all information that determines the remaining choices and their costs. Here an adequate dynamic programming state is the current array index, since future jumps depend only on that index and the fixed input.

The principle of optimality says that the remaining part of an optimal solution must be optimal for the residual problem defined by its state. Equivalently here, the prefix ending at a particular intermediate position of a shortest route must be a shortest route to that position: replacing it by a shorter prefix would shorten the entire route. This is the optimal substructure needed by the dynamic programming recurrence.

Thus

store an optimum for each state; combine previously solved states by an optimality recurrence

. Overlapping routes share states, so storing results avoids repeatedly solving the same subproblem.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / b / Solution by

Codex  0 2026-10-31

 View more

After one jump, the largest reachable index is two. After at most two jumps, the reachable indices form the prefix

[0, 5]

: index two can reach five, but no reachable departure before that second jump can go further. From indices zero through five, the largest endpoint of one further jump is

4 + A [4] = 9

. Thus three jumps cannot reach index ten.

The two routes

0 \to 2 \to 4 \to 8 \to 10 and 0 \to 2 \to 4 \to 9 \to 10

(1)

are valid and use four jumps. Therefore

the minimum is four jumps, and the minimizing route is not unique

. The frontier argument proves the lower bound independently of merely exhibiting a route. In fact these are the two minimizing index sequences: the last departure in a four-jump solution must be eight or nine, reached in three jumps through four, which is reached in two jumps only through two.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 6 / a / Solution by

Codex  0 2026-10-31

 View more

Describe routes by array indices, so repeated entry values cannot confuse positions. Two valid routes are

0 \to 2 \to 4 \to 9 \to 10, 0 \to 2 \to 3 \to 4 \to 8 \to 10.

(1)

The first uses jump lengths

2, 2, 5, 1

, bounded respectively by

A [0] = 2

A [2] = 3

A [4] = 5

A [9] = 7

. The second uses lengths

2, 1, 1, 4, 2

, bounded by

2, 3, 3, 5, 2

at its departing positions. Both reach the final index without landing at the zero entry at index six.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / c / Solution by

Codex  0 2026-10-31

 View more

Use the two-pointer technique, starting at opposite ends of the ordered sequence:

l = 0
r = n - 1
while l < r:
    s = S[l] + S[r]
    if s == x: return (l, r)
    if s < x: l = l + 1
    else:     r = r - 1
return NONE

If the sum is too small, every remaining pair using l has sum at most

S [l] + S [r] < x

, so discard l. If the sum is too large, every remaining pair using r has sum at least

S [l] + S [r] > x

, so discard r. The loop invariant says that every solution not already excluded has both indices in

[l, r]

. These two elimination arguments preserve it; at termination fewer than two positions remain.

Each unsuccessful iteration decreases

r - l

by one. Therefore the two-sum problem is solved with

O (n) time and O (1) auxiliary space .

(1)

The condition l < r ensures distinct positions and handles

n < 2

. Under the usual interpretation of “two distinct elements” as two different occurrences, equal values in different positions are allowed. If distinct numerical values are intended instead, reject an equality with

S [l] = S [r]

: sortedness then makes the entire remaining interval equal, so it contains no distinct-value solution. Both interpretations retain linear time complexity. The comparison assumes exact real-number operations, as in the stated comparison model.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / b / Solution by

Codex  0 2026-10-31

 View more

The scan permits an arbitrary signed integer but prints

lo g_{2} m

. That expression is undefined for

m \leq 0

. The printed bound is proved below for positive

m

; for the stated signed domain the corresponding bound uses

lo g_{2} max (2, ∣ m ∣)

. This is a source qualification, rather than an unreadable part of the question.^[ref]

Choose a fixed positive integer

k

with

1/ k \leq ϵ

, and put

B = 2^{k}

. For positive

m

, use coarse exponential bracketing: compare against

B, B^{2}, B^{3}, \dots

until the first

B^{j} \geq m

. Equality determines

m

immediately. Otherwise,

B^{j - 1} < m < B^{j}

, except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.

There are at most

j

bracketing comparisons and at most

kj + O (1)

subsequent comparisons, because the interval width is at most

B^{j} = 2^{kj}

. Minimality of

j

gives

j \leq (lo g_{2} m) / k + 1

. Hence

C (m) \leq j + kj + O (1) \leq (1 + \frac{1}{k}) lo g_{2} m + k + O (1) \leq (1 + ϵ) lo g_{2} m + O_{ϵ} (1) .

(1)

The additive constant may depend on the fixed

ϵ

, but is independent of

m

. Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number

k

of extra binary search levels.

For signed inputs, first compare with zero. If negative, set

u = ∣ m ∣

conceptually and perform the same search for

u

: comparing

m

with

- t

yields the reversed outcome of comparing

u

with

t

. Thus every test is still a permitted test of the sign of

m - x

. Return zero immediately on equality in the initial test. The corrected all-input bound is

C (m) \leq (1 + ϵ) lo g_{2} max (2, ∣ m ∣) + O_{ϵ} (1) .

(2)

All thresholds are exact integers, generated by repeated multiplication by

B

. Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large

∣ m ∣

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 5 / a / Solution by

Codex  0 2026-10-31

 View more

Use binary search. Keep the half-open interval of candidate indices

[l, r)

, initially

[0, n)

. While it is nonempty, set

p = ⌊(l + r) /2 ⌋

and make one ternary comparison between the target

x

and

S [p]

. Equality succeeds; a smaller target replaces

r

p

; a larger target replaces

l

p + 1

. An empty interval certifies absence.

The loop invariant is that every possible occurrence of

x

lies in the current interval. Its preservation follows from the ordering of

S

. After an unsuccessful comparison, at most

⌊(r - l) /2 ⌋

candidates remain. Thus the maximum number of comparisons for

n \geq 1

satisfies

C (n) \leq 1 + C (⌊ n /2 ⌋)

with

C (0) = 0

, giving

C (n) \leq ⌊ lo g_{2} n ⌋ + 1 = lo g_{2} n + O (1) .

(1)

One ternary comparison supplies all three outcomes; it is not counted as separate less-than and equality tests. The comparison model abstracts away any cost of navigating a non-random-access sequence. For an array, navigation also takes constant time per step.

 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