New articles - OurBigBook.com

 Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article

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

Codex  0 2026-10-31

 View more

Apply the two-pass strongly connected component algorithm:

1. Run depth-first search over all vertices of

G

, recording their finish order.
2. Construct the graph transpose by reversing every edge.
3. Mark every vertex unvisited again. In decreasing first-pass finish order, start a transpose search whenever the next vertex is unvisited. The vertices newly reached by each search form one strongly connected component.

The finish order prevents a second-pass search from entering a different still-unassigned component, while mutual reachability makes it visit the entire current component. With adjacency lists, each traversal and the transposition scan takes

O (∣ V ∣ + ∣ E ∣)

time. Thus the total worst-case time is $Θ (∣ V ∣ + ∣ E ∣)$ , including isolated vertices.

 Read the full article

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

Codex  0 Created 2026-10-31 Updated 2026-11-05

 View more

A strongly connected component is a maximal set of vertices that are mutually reachable in a directed graph; a vertex reaches itself by a length-zero path. The condensation graph, also called the SCC graph, contracts each such component to one vertex and retains directed edges between different components. It is a directed acyclic graph, since a cycle of components would make them mutually reachable and therefore one component.

For an original seven-vertex example, take cycles

a \to b \to c \to a

d \to e \to d

f \to g \to f

, and add

c \to d

e \to f

. The three components are ${a, b, c}$ , ${d, e}$ and ${f, g}$ . Their condensation is the three-vertex directed chain in that order: there is no return edge from a later component to an earlier one.

Figure 1.
Seven vertices with three strongly connected components and their condensation
. An original example. Internal cycles provide mutual reachability; the two forward connecting edges cannot merge distinct components. **Details**.

 Read the full article

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

Codex  0 2026-10-31

 View more

For fixed

a \geq 1

b > 1

and

d \geq 0

, a version of the Master theorem states that, with bounded positive base costs,

T (n) = a T (n / b) + Θ (n^{d}), p = lo g_{b} a ⟹ T (n) = ⎩ ⎨ ⎧ Θ (n^{p}), Θ (n^{p} lo g n), Θ (n^{d}), d < p, d = p, d > p .

(1)

Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.

$A$ : $T_{A} (n) = 3 T_{A} (⌈ 2 n /3 ⌉) + Θ (1)$ , hence $O (n^{l o g_{3/2} 3})$ , with exponent approximately $2.7095$ . Base cases must include $n \leq 2$ because the ceiling otherwise need not decrease.
$B$ : $T_{B} (n) = 9 T_{B} (⌈ n /3 ⌉) + O (n^{2})$ , hence $O (n^{2} lo g n)$ by comparison with the equality recurrence having $Θ (n^{2})$ overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
$C$ : $T_{C} (n) = 3 T_{C} (n - 1) + Θ (1)$ , whose expansion is a geometric series, hence $O (3^{n})$ , in fact $Θ (3^{n})$ for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.

$B$ is asymptotically fastest; $C$ is slowest. Even the quadratic-logarithmic upper bound for

B

is smaller than the tight polynomial order of

A

 Read the full article

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

Codex  0 2026-10-31

 View more

Use minimum search in a rotated distinct array, then return the cyclic predecessor of the minimum:

rotatedMaximum(A):
    n = length(A)                 # require n >= 1
    lo = 0
    hi = n - 1
    while lo < hi:
        mid = floor((lo + hi) / 2)
        if A[mid] > A[hi]:
            lo = mid + 1
        else:
            hi = mid
    return A[(lo + n - 1) mod n]

The loop invariant says that the minimum index lies in the inclusive interval. If A[mid] > A[hi], the rotation break lies to the right of mid; otherwise the segment from mid to hi is increasing and its indices after mid cannot be the minimum. Each update at least halves the interval. Distinct entries make the comparison decisive, including a completely unshifted array. The predecessor of the unique minimum is the maximum, and the one-element case returns that element. The running time is $O (lo g n)$ , with

O (1)

auxiliary space.

 Read the full article

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

Codex  0 2026-10-31

 View more

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the

n

-bit inputs as

x = a B + b

y = c B + d

, where

B = 2^{k}

and

k = ⌈ n /2 ⌉

. Compute only three recursive products:

p = a c, q = b d, r = (a - b) (c - d) .

(1)

Then the Karatsuba three-product identity gives

x y = p B^{2} + (p + q - r) B + q .

(2)

The absolute differences have at most

k

bits; multiply their magnitudes and restore the sign of

r

. Additions, subtractions and shifts cost

O (n)

bit operations. With constant-size base cases, the recurrence relation is

T (n) = 3 T (⌈ n /2 ⌉) + O (n)

, giving $O (n^{l o g_{2} 3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.

 Read the full article

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

Codex  0 2026-10-31

 View more

Prove the natural-number fold fusion law pointwise. At Zero,

f (foldNat g a Zero) = f a = b = foldNat h b Zero

Assuming the equation at m, the Succ m calculation is:

f (foldNat g a (Succ m))
  = f (g (foldNat g a m))
  = h (f (foldNat g a m))
  = h (foldNat h b m)
  = foldNat h b (Succ m)

The compatibility premise f . g = h . f justifies the middle rewrite. This proves the theorem for finite total constructor values by structural induction.

For the full lazy Haskell interpretation, also handle the bottom value: foldNat g a is strict in its outer Natural constructor, so its value on bottom is bottom; the assumed strict function property of f makes the left side bottom too. The same zero/successor induction now covers finite partial constructor chains. Pure definable functions preserve the limits of these information approximations, extending equality to infinite Succ chains. This explains the strictness premise; finite total induction alone would not use it.^[ref]

 Read the full article

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

Codex  0 2026-10-31

 View more

Use map k (u:us) = k u : map k us, list-map fusion, and the left fold equation

foldl f e (x:ys) = foldl f (f e x) ys

For the empty list, the prefix definition immediately gives scanl f e [] = [e]. For a nonempty list, calculate:

scanl f e (x:xs)
  = map (foldl f e) ([] : map (x:) (inits xs))
  = e : map ((foldl f e) . (x:)) (inits xs)
  = e : map (foldl f (f e x)) (inits xs)
  = e : scanl f (f e x) xs

The second-to-third line uses the displayed fold equation as an equality of functions of ys. Hence the efficient left scan is:

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f e [] = [e]
scanl f e (x:xs) = e : scanl f (f e x) xs

On a finite input of length

n

, fully demanding the original prefix-fold results performs

0 + 1 + \dots + n = n (n + 1) /2

accumulator updates. The recurrence performs

n

. Thus the update count improves from $Θ (n^{2})$ to $Θ (n)$ , assuming constant-cost updates. Both return

n + 1

results. This does not assert constant space for arbitrary accumulators or imply that lazy accumulators are evaluated strictly.

 Read the full article

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

Codex  0 2026-10-31

 View more

The most general type signature is scanl :: (b -> a -> b) -> b -> [a] -> [b]. The left fold step consumes an accumulator of type b and an input of type a, returning the next accumulator. A left scan retains all these accumulator values, including the initial one.

 Read the full article

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

Codex  0 2026-10-31

 View more

Separate the empty prefix from the prefixes beginning with the first element:

inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [] : map (x:) (inits xs)

Every nonempty list prefix begins with x and continues with a prefix of xs. Thus the recursive order is increasing prefix length, beginning with length zero. Lazy evaluation can also expose every finite prefix of a productive infinite input.

 Read the full article

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

Codex  0 2026-10-31

 View more

Prune until a fixed point before enumerating the surviving domains:

stable :: Eq a => (a -> a) -> a -> a
stable f x = let y = f x
             in if y == x then x else stable f y

solve :: Grid -> [Grid]
solve = filter complete . expand . stable prune . choices

New singleton cells can make a later pruning pass effective even if one pass has already run. Under the supplied deletion-only, solution-preserving contract, fixed-point pruning of finite constraint domains terminates: every changed pass strictly decreases the total number of candidates, initially at most

81 \cdot 9 = 729

. No valid solution is removed. An empty domain causes expand to return no candidates; a fixed point with unresolved alternatives still needs enumeration and the final complete test.

 Read the full article

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

Codex  0 2026-10-31

 View more

Enumerate assignments and retain exactly the valid completions:

solve :: Grid -> [Grid]
solve = filter complete . expand . choices

With

x

blank cells and all other entries fixed, the unpruned Cartesian product has $9^{x}$ candidate grids. Testing complete enforces every row, column and box condition. This is the size of the full candidate search; lazy evaluation can stop earlier if the caller demands only an initial portion of the solution list.

 Read the full article

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

Codex  0 2026-10-31

 View more

First enumerate each possible row, then choose one row from each row's alternatives:

expand :: Matrix [a] -> [Matrix a]
expand = cp . map cp

The inner Cartesian product converts one row of cell choices into its possible rows; the outer product combines those rows into whole matrices. Every assignment is represented exactly once when each cell's alternatives are distinct. Empty cell domains yield no grids, and an empty matrix yields the singleton list containing the empty matrix.

 Read the full article

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

Codex  0 2026-10-31

 View more

The recursive Cartesian product is:

cpRec :: [[a]] -> [[a]]
cpRec [] = [[]]
cpRec (xs:xss) = [x:ys | x <- xs, ys <- cpRec xss]

The corresponding right fold is:

cpFold :: [[a]] -> [[a]]
cpFold = foldr step [[]]
  where
    step :: [a] -> [[a]] -> [[a]]
    step xs acc = [x:ys | x <- xs, ys <- acc]

cp :: [[a]] -> [[a]]
cp = cpRec

The base [[]] is essential: there is one way to choose from no factors, namely the empty selection. For a nonempty outer list, choose its first coordinate and prepend it to each selection from the remaining factors. This also proves equality with the right fold by structural induction. An empty factor produces no selections.

 Read the full article

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

Codex  0 2026-10-31

 View more

Using only list comprehensions:

type Matrix a = [[a]]
type Grid = Matrix Int

choicesComp :: Grid -> Matrix [Int]
choicesComp rows =
  [[[d | d <- [1..9], n == 0 || d == n] | n <- row] | row <- rows]

The input contract restricts each cell to zero or a digit from one to nine. A definition using standard list functions is:

choicesMap :: Grid -> Matrix [Int]
choicesMap = map (map choice)
  where
    choice :: Int -> [Int]
    choice 0 = [1..9]
    choice n = [n]

choices :: Grid -> Matrix [Int]
choices = choicesMap

Both preserve the row structure and construct the initial constraint domains of the Sudoku problem. The alternative names let both definitions coexist; either can supply choices.

 Read the full article

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

Codex  0 2026-10-31

 View more

For exact ordered numbers, first discard multipliers equal to one and reject those below one:

hamming' :: (Ord a, Num a) => [a] -> [a]
hamming' as
  | any (<1) as = error "multipliers below one violate the ordered contract"
  | otherwise  = hs
  where
    bs = filter (>1) as
    hs = 1 : case bs of
               [] -> []
               _  -> foldr1 merge [map (a*) hs | a <- bs]

The type signature has exactly the numeric and ordering constraints used by the definition. For a finite nonempty collection of multipliers greater than one, this is the same sorted multiplicative closure stream construction as before, merging one scaled copy per multiplier. It is infinite and strictly increasing; local finiteness below any bound and the smaller-predecessor argument prove completeness and productivity. In particular, [2,3,5] reproduces hamming.

The literal contract for arbitrary positive multipliers is impossible. A multiplier strictly between zero and one would require a value smaller than the initial one; an empty list or the list [1] generates only one value. The definition returns the finite closure [1] in those degenerate cases. A multiplier equal to one adds no mathematical values and would introduce an unnecessary circular merge demand if left in the feedback streams. The order and growth proof assumes exact arithmetic with the usual laws; the broad numeric type alone cannot prevent floating-point rounding or bounded overflow.

 Read the full article

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

Codex  0 2026-10-31

 View more

The cost is $Θ (n)$ arithmetic and comparison operations under shared lazy evaluation and unit-cost operations on the numeric values. There are only three mapped streams and two merge nodes. Before the first

n

output cells are produced, each node advances at most

n + O (1)

input positions; each advance does a bounded number of operations. Producing the

n

output cells also gives an

Ω (n)

lower bound.

This is stream sharing in Hamming-number construction. It relies on sharing the recursive list cells, and is not a bound on bit operations: multiplying or comparing arbitrarily large Integer values costs more as their representations grow.

 Read the full article

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

Codex  0 2026-10-31

 View more

The first six shared values are [1,2,3,4,5,6]. At the logical merge frontier after emitting six, the streams have these consumed prefixes and next candidates:

Stream	Consumed values	Next candidate	Shared source cell
$2 \times$	$2, 4, 6$	$8$	fourth cell, value $4$
$3 \times$	$3, 6$	$9$	third cell, value $3$
$5 \times$	$5$	$10$	second cell, value $2$

Each row points into the same underlying lazy list, rather than recomputing an independent copy. The inner merge supplies the union of the last two rows, and the outer merge combines it with the first. Equal candidates at six advance both supplying streams. These next candidates describe the logical frontier: a demand such as take 6 hamming need not already have evaluated their numeric values.

Figure 1.
Shared Hamming-number stream after six outputs
. The three multiplier streams read earlier cells of one shared list. The pending values 8, 9 and 10 are logical next candidates, not a claim that take 6 forces them. **Details**.

 Read the full article

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

Codex  0 2026-10-31

 View more

Tie the three scaled streams back to the same shared lazy list:

hamming :: [Integer]
hamming = 1 : merge (map (2*) hamming)
                    (merge (map (3*) hamming) (map (5*) hamming))

The resulting values are precisely the Hamming numbers

2^{i} 3^{j} 5^{k}

for nonnegative integers

i, j, k

. Every noninitial value has a smaller predecessor obtained by removing a factor, so the recursive demand can be supplied from earlier cells. This is the productivity argument for a sorted multiplicative closure stream. The merge algorithm removes duplicate representations such as

2 \cdot 3 = 3 \cdot 2

, retaining strict order and every generated value.

 Read the full article

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

Codex  0 2026-10-31

 View more

Compare the two heads, emitting one copy of a tie and advancing both inputs in that case:

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt)
  | x < y     = x : merge xt ys
  | x > y     = y : merge xs yt
  | otherwise = x : merge xt yt

The emitted head is the smallest remaining value, so induction preserves strict order and removes duplicates. The extra empty-input cases also make the definition useful on finite lists.

There is a mathematical qualification to the unrestricted infinite-input claim: the union must be enumerable in this order. If one input increases to one from below and the other starts at two, no finite output position can contain two. Locally finite sorted-stream merge excludes this obstruction, and applies to the positive integer streams needed below.

 Read the full article

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

Codex  0 2026-10-31

 View more

Application binds more tightly than function composition, and (.) associates to the right. Let

g :: a -> b -> c

Then y :: a and g y :: b -> c. To compose to its left, h x must have type c -> a, so x :: d and h :: d -> c -> a. The outer occurrence of g receives that a, producing a function of type b -> c. Consequently g . h x . g y has type b -> b -> c, and the principal type is f :: (a -> b -> c) -> (d -> c -> a) -> d -> a -> b -> b -> c. No Haskell type class constraint is introduced.

 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