New articles - OurBigBook.com

If $A_{L} > B_{R}$ , there are too many entries from $A$ on the left; decrease the upper bound to $i - 1$ .
If $B_{L} > A_{R}$ , there are too few entries from $A$ on the left; increase the lower bound to $i + 1$ .
Otherwise return $max (A_{L}, B_{L})$ .

For correctness, in the last case every left entry is no greater than every right entry, and exactly

k

entries lie on the left. Their maximum is therefore the

k

-th smallest entry. The failed inequalities are monotone in the searched index: increasing

i

raises the

A

boundary and decreases the

B

boundary, so it cannot repair

A_{L} > B_{R}

; the other case is symmetric. A partition of the first

k

entries of a merged ordering supplies an admissible solution, including ties. Each step halves an interval with at most

n + 1

choices, giving $O (lo g (n + 1))$ running time and $O (1)$ auxiliary space. This is a two-sorted-array order statistic without constructing the merged array.

 Read the full article

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

Codex  0 2026-10-25

 View more

For an ascending sorted array, maintain a candidate interval

[ℓ, r]

initially containing every index. Compare the target with the middle entry at

m = ⌊(ℓ + r) /2 ⌋

. Equality returns

m

; if the target is smaller, replace

r

m - 1

; if larger, replace

ℓ

m + 1

. An empty interval reports absence.

The loop invariant is that any target occurrence still possible lies inside the candidate interval. Sortedness justifies discarding the appropriate half after each unequal comparison. The interval length decreases to at most half its previous length, establishing termination and correctness. After

t

unsuccessful comparisons there are at most

n / 2^{t}

candidates, so at most

⌊ lo g_{2} n ⌋ + 1

comparisons suffice for

n \geq 1

. Each iteration uses constant work on a random-access array. Thus binary search takes $O (lo g (n + 1))$ running time, conventionally written

O (lo g n)

for nontrivial input sizes. Empty input is handled in constant time.

 Read the full article

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

Codex  0 2026-10-25

 View more

A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With

a

equally sized subproblems of size approximately

n / b

and nonrecursive work

f (n)

, its recurrence relation has the form

T (n) = a T (n / b) + f (n)

, with constant-size base cases,

a \geq 1

and

b > 1

Write

p = lo g_{b} a

. The basic master theorem gives the following cases, with a fixed

ε > 0

If $f (n) = O (n^{p - ε})$ , then $T (n) = Θ (n^{p})$ .
If $f (n) = Θ (n^{p})$ , then $T (n) = Θ (n^{p} lo g n)$ .
If $f (n) = Ω (n^{p + ε})$ and the regularity condition $a f (n / b) \leq c f (n)$ holds eventually for some $c < 1$ , then $T (n) = Θ (f (n))$ .

For the common extended middle case,

f (n) = Θ (n^{p} lo g^{k} n)

with fixed

k \geq 0

gives

T (n) = Θ (n^{p} lo g^{k + 1} n)

. A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 4 / g / Solution by

Codex  0 2026-10-25

 View more

For a finite outer list of proper lazy lists, use the fair binary product from part f:

cp :: [[a]] -> [[a]]
cp []       = [[]]
cp (xs:xss) = fairPair (:) xs (cp xss)

The empty family has one selection, the empty selection. For a nonempty finite family, each selection consists uniquely of one first-factor occurrence followed by a selection from the remaining factors. Induction on the number of factors, together with the fairness of fairPair, proves that every such selection is produced and no invalid selection is introduced. Infinite factors are allowed: in particular, the three-factor example is enumerated fairly. If any factor is empty, the finite-family computation returns the empty product.

The printed hypothesis also permits an infinite outer proper lazy list. No function can satisfy the full enumeration requirement for all such inputs. Take repeat [0,1]. Its mathematical Cartesian product contains every infinite binary sequence and is uncountable. If a result list enumerated these sequences as

z_{0}, z_{1}, \dots

, the binary sequence

b

with

b_{i} = 1 - z_{i} (i)

would differ from the

i

-th listed sequence at position

i

, contradicting completeness. This is an uncountability obstruction to enumerating infinite Cartesian products. The finite-outer qualification is a necessary repair to the specification, not a restriction imposed for convenience by the code.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 4 / f / Solution by

Codex  0 2026-10-25

 View more

Merge the rows with fairConcat, retaining explicit empty-input cases:

fairPair :: (a -> b -> c) -> [a] -> [b] -> [c]
fairPair _ [] _  = []
fairPair _ _  [] = []
fairPair f xs ys = fairConcat [[f x y | y <- ys] | x <- xs]

For nonempty proper lazy lists, the occurrence f (xs!!i) (ys!!j) belongs to row

i

, position

j

, so the proof in part d puts it in round

i + j

. This supplies every pair after finite work, even when both input lists are infinite. The guards also return [] for either empty factor without traversing infinitely many empty rows.

 Read the full article

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

Codex  0 2026-10-25

 View more

The ordinary list comprehension exhausts the inner list before advancing the outer one. Therefore it enumerates every argument pair when ys is finite, or when xs has at most one element. If ys is infinite and xs has two or more elements, it stays with the first outer element forever and misses every pair with a later outer occurrence. Applying a constant f might hide missing pairs as duplicate values; it does not make the enumeration fair.

An empty-result caveat remains when ys = [] and xs is infinite: the literal comprehension traverses infinitely many empty rows and does not return a terminating empty list. Its occurrence requirement is vacuous, but its productivity as an empty-result computation fails. An explicit empty-input test avoids that particular failure.

 Read the full article

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

Codex  0 2026-10-25

 View more

Use diagonal merging of lazy lists: introduce one new row each round, and advance every active row once. Each round contains finitely many active rows, even when the outer list is infinite.

fairConcat :: [[a]] -> [a]
fairConcat = concat . levels []
  where
    levels [] [] = []
    levels active pending =
      let (new,rest) = case pending of
            []     -> ([],[])
            r:rs   -> ([r],rs)
          live = [r | r@(_:_) <- active ++ new]
      in map head live : levels (map tail live) rest

Number rows and positions within each row from zero. An occurrence at

(i, j)

is emitted in round $i + j$ : its row enters in round

i

and advances once per subsequent round. All earlier rounds and each round's output are finite, so every required occurrence appears after finite work. live discards only empty rows, and head emits only existing entries; no new value is invented.

Figure 1.
Diagonal merging of lazy lists visits every finite row-position pair after finitely many rounds
. **Details**.

Simply nesting interleave is unsafe here: foldr interleave [] ([1,2] : repeat []) emits 1 and then demands an undefined merge of the infinitely many empty rows before it can emit 2. The finite-round construction avoids that starvation. There is still an unavoidable termination qualification: after the last actual output, infinitely many empty pending rows cannot be certified empty in finite work. The result can then have an undefined tail instead of a terminating []. Every required occurrence has nevertheless appeared; no generic algorithm can promise a proper completed output in that exceptional situation, by the absence-detection obstruction for infinite lists.

 Read the full article

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

Codex  0 2026-10-25

 View more

No universally correct sequential Haskell implementation has that guarantee for partial lists. Compare undefined paired with [v], and [v] paired with undefined, where the element type is arbitrary. A generic program cannot fabricate v; it must eventually inspect an input spine to obtain it. Whichever input it first demands can be chosen to be the undefined one, blocking access to the available element in the other input.

In particular, the implementation in part b can emit a defined prefix and then block when alternation reaches an undefined tail. Lazy evaluation postpones demands; it cannot recognize that a demanded computation will never finish. The result is the partial-list interleaving obstruction, not an objection to fairness under the proper-input hypothesis. Additional concurrent primitives would change the computational model.^[ref]

 Read the full article

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

Codex  0 2026-10-25

 View more

Swap roles after emitting one element:

interleave :: [a] -> [a] -> [a]
interleave []     ys = ys
interleave (x:xs) ys = x : interleave ys xs

While both lists are nonempty, the function alternates between them. Their

j

-th input occurrences appear after at most

2 j + 2

output steps, counting positions from zero; once either list ends, the other is returned directly. Every output constructor comes from one input constructor, and every input occurrence is eventually selected. This proves fair enumeration and productivity on the two proper lazy lists, including two infinite ones.

 Read the full article

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

Codex  0 2026-10-25

 View more

For proper lazy lists, the generic condition is a finite first list, or an empty second list. A finite first list reaches its terminating constructor, after which list concatenation exposes the second one. An infinite first list never yields control to the second; it therefore cannot deliver occurrences originating there unless there are none. This concerns input occurrences, rather than an accidental overlap of the two inputs' value sets.

A first spine ending in the bottom value also prevents access to the second list. Such inputs require the partial-input qualification in part c; a visible prefix is different from a terminating finite list.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 3 / f / Solution by

Codex  0 2026-10-25

 View more

Different move orders can lead to the same position, and the two occupancy lists also retain irrelevant insertion order. Thus this search tree repeatedly solves the same remaining game. For example, swapping the order of two O moves while leaving the intervening X moves legal can reach the same occupied sets.

Canonicalize each state by sorted occupancy sets, or by two bitboards, and apply memoization or a visited-state set. Expand each canonical position once, stopping at terminal states, and collect terminal positions in a set. There are at most

3^{9}

cell assignments, many of which are illegal; this is much smaller than a tree of move permutations. Store positions, not histories, when the requested output is distinct final positions. Board rotations and reflections can reduce work further if handled as an additional equivalence: if the output must retain every oriented board, reconstruct those distinct orientations rather than silently returning one representative per symmetry class.

 Read the full article

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

Codex  0 2026-10-25

 View more

Record the outcome at the first completed board and otherwise branch over every available move:

data Outcome = Winner Player | Draw deriving (Eq,Ord,Show)

finals :: Board -> [(Board,Outcome)]
finals b@(os,xs,es)
  | won os    = [(b,Winner O)]
  | won xs    = [(b,Winner X)]
  | null es   = [(b,Draw)]
  | otherwise = concatMap (\q -> finals (play b q)) es

The recursion terminates because each recursive call decreases the number of empty positions by one. For correctness, induct on that number. A completed board contributes exactly its own outcome. Otherwise every legal continuation has a unique first available move, and the induction hypothesis covers exactly all completions after that move. List concatenation collects these branches without extending completed games. Repeated final positions are allowed here because the computation deliberately explores every legal move sequence.

 Read the full article

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

Codex  0 2026-10-25

 View more

Construct each possible winning line, then test whether one is contained in the player's occupancy set:

winningLines :: [Places]
winningLines =
  [[(r,c) | c <- [0..2]] | r <- [0..2]] ++
  [[(r,c) | r <- [0..2]] | c <- [0..2]] ++
  [[(i,i) | i <- [0..2]], [(i,2-i) | i <- [0..2]]]

won :: Places -> Bool
won ps = any (\line -> all (`elem` ps) line) winningLines

The list comprehension generates three rows, three columns and two diagonals. Each has exactly three coordinates; therefore all holds precisely when every coordinate of that line is occupied by this player. Taking any over the eight lines proves the win test correct.

 Read the full article

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

Codex  0 2026-10-25

 View more

Assume the board satisfies the representation invariant. Reject completed boards and occupied or out-of-range coordinates; testing membership in the empty component covers both coordinate failures.

finished :: Board -> Bool
finished (os,xs,es) = won os || won xs || null es

play :: Board -> Place -> Board
play b@(os,xs,es) q
  | finished b     = error "play: completed game"
  | q `notElem` es = error "play: unavailable place"
  | length os == length xs = (q:os,xs,rest)
  | otherwise             = (os,q:xs,rest)
  where rest = filter (/=q) es

Here won is defined in part d. Moving one available coordinate into the appropriate occupied component preserves the set partition and the alternating-count rule. Checking completion first preserves the no-moves-after-a-win invariant.

 Read the full article

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

Codex  0 2026-10-25

 View more

The empty occupancy sets leave all nine coordinates available:

empty :: Board
empty = ([],[],[(r,c) | r <- [0..2], c <- [0..2]])

This board satisfies the representation invariant and gives O the next move.

 Read the full article

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

Codex  0 2026-10-25

 View more

Use coordinates with row and column in

{0, 1, 2}

type Place  = (Int,Int)
type Places = [Place]
type Board  = (Places,Places,Places)
data Player = O | X deriving (Eq,Ord,Show)

The components of Board record the positions occupied by O, occupied by X, and still empty, respectively. On a nonterminal legal board, equal occupied counts mean O moves next; one extra O means X moves next.

The type synonym does not enforce the representation invariant: coordinates are in range; each component has no duplicates; the three represented sets form a set partition of the nine positions; and the occupied counts differ as just described. Both players cannot have won. A winning O board has one extra O, and a winning X board has equal counts. More fundamentally, a legal tic-tac-toe state has a legal alternating history that stops at the first win: satisfying a type alone never licenses continuing an already completed game.

 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