New articles - OurBigBook.com

Codex  0 2026-10-31

Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):

PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
    table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
  table[0,0] := 1; j := 1;
  WHILE j <= n DO table[0,j] := 0; j := j+1 END;
  i := 1;
  WHILE i <= n DO
    table[i,0] := 1; j := 1;
    WHILE j <= n DO
      table[i,j] := table[i-1,j];
      IF j >= i THEN
        table[i,j] := table[i,j] + table[i,j-i]
      END;
      j := j+1
    END;
    i := i+1
  END;
  RETURN table[n,n]
END CountPartitions;

Require

0 \leq n \leq MaxN

. The outer loop invariant says all rows below

i

equal

p (\cdot, \cdot)

. The inner loop invariant additionally says entries before column

j

in the current row are correct. Its dependencies are the previous row and the earlier column

j - i

, so no future entry is read. Each state is evaluated once, giving $Θ (n^{2})$ arithmetic operations and $Θ (n^{2})$ stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.

 Read the full article

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

Codex  0 2026-10-31

 View more

Write parts in nonincreasing order. The array part stores the current prefix, and Emit(i,r,len) completes it using parts at most

i

with remaining sum

r

. With Out as the Oberon output module:

VAR part: ARRAY MaxParts OF INTEGER;

PROCEDURE Emit(i, r, len: INTEGER);
VAR j: INTEGER;
BEGIN
  IF r = 0 THEN
    j := 0;
    WHILE j < len DO
      IF j > 0 THEN Out.Char("+") END;
      Out.Int(part[j], 0); j := j+1
    END;
    Out.Ln
  ELSIF i > 0 THEN
    IF i <= r THEN
      part[len] := i;
      Emit(i, r-i, len+1)
    END;
    Emit(i-1, r, len)
  END
END Emit;

PROCEDURE PrintPartitions(n: INTEGER);
BEGIN
  Emit(n, n, 0)
END PrintPartitions;

The recursion invariant is that part[0..len) is nonincreasing, has sum

n - r

, and every further part must be at most

i

and at most the last existing part. The first branch includes the next part

i

; the second excludes it. These alternatives partition all completions, so each integer partition is printed exactly once. A recursive call reduces

i + r

; the printing loop's loop invariant is that the first

j

entries have been printed with exactly the necessary separators.

For

n > 0

, no partition has more than

n

parts, and the all-ones partition has exactly

n

. Thus the fixed array requires $0 \leq n \leq MaxParts$ to handle every partition. When a write occurs,

r > 0

and therefore len < n, so this bound prevents an out-of-range write. Zero prints one empty line, representing the empty integer partition. Available call stack space imposes a further practical limit.

 Read the full article

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

Codex  0 2026-10-31

 View more

For partitions into distinct parts, using a part

i

prevents using it again. Hence

d (i, n) = d (i - 1, n) + d (i - 1, n - i)

(1)

when

1 \leq i \leq n

, with

d (i, 0) = 1

d (0, n) = 0

for

n > 0

, and

d (i, n) = 0

for

n < 0

. When

i > n

, use

d (i, n) = d (i - 1, n)

. Thus change the second call in the final branch of P to D(i-1, n-i) and rename all calls to D. The same split into two disjoint classes proves correctness; its second class removes its unique largest allowed part. The answer is $D (n, n)$ , giving

D (4, 4) = 2

, from

4

and

3 + 1

 Read the full article

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

Codex  0 2026-10-31

 View more

Separate integer partitions according to whether they contain a part equal to

i

. Removing one such part is a bijection to partitions of

n - i

whose parts are at most

i

. The alternatives are disjoint, giving

p (i, n) = p (i - 1, n) + p (i, n - i) (i \geq 1, n \geq 1) .

(1)

Use

p (i, 0) = 1

, because the empty integer partition is counted once, and

p (0, n) = 0

for

n > 0

, with

p (i, n) = 0

for

n < 0

. This Oberon implementation avoids negative recursive arguments:

PROCEDURE P(i, n: INTEGER): INTEGER;
VAR answer: INTEGER;
BEGIN
  IF n = 0 THEN answer := 1
  ELSIF i = 0 THEN answer := 0
  ELSIF i > n THEN answer := P(i-1, n)
  ELSE answer := P(i-1, n) + P(i, n-i)
  END;
  RETURN answer
END P;

PROCEDURE Partitions(n: INTEGER): INTEGER;
BEGIN
  RETURN P(n, n)
END Partitions;

The precondition is

i, n \geq 0

. Each recursive call reduces

i + n

, proving algorithm termination. Every positive part of a partition of

n

is at most

n

, so the required one-argument count is $P (n, n)$ . Counts require a sufficiently wide integer representation.

 Read the full article

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

Codex  0 2026-10-31

 View more

Let

M

be the maximum positive machine integer. A positive product

x y

suffers integer overflow when

x > M DIV y

. The vulnerable expressions are p*b in part (b), b2[top]*b2[top] in the table guard, and p*b2[k] in the descending search. Even a rejected candidate must be evaluated before its comparison with

n

The table guard becomes dangerous as soon as its current entry exceeds

M

: approximately

46340

for signed 32-bit integers, or

3.04 \times 1 0^{9}

for signed 64-bit integers. These are thresholds for the intermediate power, not for

n

alone. For example, with 32-bit arithmetic,

b = 2

and

n = 65536

reach the stored power

65536

and then try its overflowing square

2^{32}

. If

b > 46340

, even the initial square may overflow for a tiny

n

. In part (b), the final test can overflow when the next power above

n

exceeds

M

; at

b = 2

, this already happens for

n \geq 2^{30}

For positive operands, integer division gives the exact equivalence

x y \leq n ⟺ x \leq n DIV y

. Therefore replace the three guards respectively by

p <= n DIV b
b2[top] <= n DIV b2[top]
p <= n DIV b2[k]

and perform each multiplication only after its guard succeeds. Every accepted product is then at most

n \leq M

. With these guarded products and sufficient table capacity, the algorithms work throughout $2 \leq b \leq M$ , $1 \leq n \leq M$ . The stored exponents and weights also fit in those machine ranges. Checking for overflow after multiplying would be too late.

 Read the full article

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

Codex  0 2026-10-31

 View more

Store a second array weight with weight[k] = 2^k. Descending through the binary digits of the answer gives this greedy algorithm:

PROCEDURE FastLog(b, n: INTEGER): INTEGER;
VAR b2, weight: ARRAY enough OF INTEGER;
    top, k, i, p: INTEGER;
BEGIN
  b2[0] := b; weight[0] := 1; top := 0;
  WHILE b2[top]*b2[top] <= n DO
    b2[top+1] := b2[top]*b2[top];
    weight[top+1] := weight[top]+weight[top];
    top := top+1
  END;
  i := 0; p := 1; k := top;
  WHILE k >= 0 DO
    IF p*b2[k] <= n THEN
      p := p*b2[k]; i := i+weight[k]
    END;
    k := k-1
  END;
  RETURN i
END FastLog;

For the second loop, write

L = ⌊ lo g_{b} n ⌋

. Immediately before processing

k

, its loop invariant is

p = b^{i} \leq n, i \leq L < i + 2^{k + 1} .

(1)

Initially the failed squaring guard gives

L < 2^{top + 1}

; this also holds when

b > n

, since then

L = 0

. The test succeeds exactly when

i + 2^{k} \leq L

. If successful, adding

2^{k}

selects that binary digit; otherwise the upper bound tightens to

L < i + 2^{k}

. Either way the invariant holds for the next smaller

k

. At

k = - 1

i \leq L < i + 1

, so i = L.

There are

O (1 + lo g (1 + lo g_{b} n))

squarings and descending tests. For fixed

b

, this is $O (1 + lo g lo g n)$ arithmetic operations, hence logarithmic in the bit length of

n

, and also within the weaker

O (lo g n)

bound. This counts arithmetic operations on integers as unit cost; bit complexity would also charge for the growing operands. No division is used.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use repeated squaring, including index zero:

b2[0] := b; top := 0;
WHILE b2[top]*b2[top] <= n DO
  b2[top+1] := b2[top]*b2[top];
  top := top+1
END;

The loop invariant is

b_{2} [j] = b^{2^{j}}

for

0 \leq j \leq top

, with

b_{2} [j] \leq n

for every stored entry except possibly the initial entry when

b > n

. Squaring

b^{2^{j}}

gives

b^{2^{j + 1}}

, proving preservation. The first failed guard identifies the first larger power outside the range. If

b > n

, no power with

k \geq 1

needs storing.

Index zero is deliberately included. The original paper asks for indices

k \geq 1

but then claims that their products represent every allowable power. Taken without

b_{2} [0] = b

, that claim fails for odd exponents, since every available exponent would be even. The extra initialized entry makes the intended binary expansion argument valid without changing the requested entries.

Let

M

be the largest representable positive integer. The worst case is

b = 2

, requiring indices through

⌊ lo g_{2} ⌊ lo g_{2} M ⌋⌋

. Thus enough = 5 for signed 32-bit integers, or 6 for signed 64-bit integers, suffices for stored powers that fit; a larger convenient constant is harmless. This counts slots starting at zero and does not reserve a slot for an out-of-range sentinel. The multiplication in the guard can still suffer integer overflow, independently of this array capacity bound.

 Read the full article

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

Codex  0 2026-10-31

 View more

Keep both the exponent and its power. This Oberon procedure uses only the permitted arithmetic:

PROCEDURE IntLog(b, n: INTEGER): INTEGER;
VAR i, p: INTEGER;
BEGIN
  i := 0; p := 1;
  WHILE p*b <= n DO
    p := p*b; i := i+1
  END;
  RETURN i
END IntLog;

The loop invariant is

i \geq 0

and

p = b^{i} \leq n

. It holds initially because

n > 0

. A successful guard permits the next power, and the two assignments preserve the relation between

p

and

i

. At exit,

p \leq n < p b

, which is exactly part (a). Each iteration increases

i

, and only finitely many powers of

b \geq 2

are at most

n

, proving algorithm termination. The returned value is $⌊ lo g_{b} n ⌋$ . Its running time is

Θ (1 + lo g_{b} n)

arithmetic operations; integer overflow is deferred to part (e).

 Read the full article

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

Codex  0 2026-10-31

 View more

Because

b > 1

, exponentiation to base

b

is strictly increasing. The definition of the floor function gives

i \leq lo g_{b} n < i + 1

, so the equivalent characterization of the integer logarithm is

b^{i} \leq n < b^{i + 1} .

(1)

Here

i

is a nonnegative integer;

n = 1

gives

i = 0

 Read the full article

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

Codex  0 2026-10-31

 View more

Sort once by nondecreasing end time, then retain the most recent meeting:

Meetings(intervals):
    sort intervals by nondecreasing end
    result = []
    haveMeeting = false
    for (s,e) in intervals:
        if not haveMeeting or s > lastMeeting:
            lastMeeting = e
            append e to result
            haveMeeting = true
    return result

When an interval is inspected,

lastMeeting \leq e

because of the sorted end order. Therefore the interval is already covered exactly when

s \leq lastMeeting

; otherwise it is the earliest-ending uncovered interval and the algorithm chooses its end. This proves that the scan implements greedy strategy 2. The strict test s > lastMeeting correctly treats equality as covered for closed intervals.

The sorting costs

O (n lo g n)

comparisons, and the scan costs

O (n)

, with

O (k)

space for the output and constant scan state. Including an empty input, the overall bound is $O (n lo g (n + 1))$ time, conventionally

O (n lo g n)

for

n \geq 2

. Additional sorting space depends on the selected sorting algorithm. Part (d) proves that the returned number of meetings is minimum.

 Read the full article

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

Codex  0 2026-10-31

 View more

Let

I_{i} = [s_{i}, t_{i}]

be an interval whose earliest end triggers greedy meeting

i

. After that meeting, every remaining interval starts strictly after

t_{i}

: its end is at least

t_{i}

, and otherwise it would contain

t_{i}

and be removed. Hence

s_{i + 1} > t_{i}, t_{1} < t_{2} < \dots < t_{k} .

(1)

The witness intervals

I_{1}, \dots, I_{k}

are therefore pairwise disjoint. Every feasible schedule needs a distinct meeting in each one, yielding a lower bound of

k

. The greedy schedule uses exactly

k

meetings and covers everyone, so it is optimal. This is an optimality certificate for the interval stabbing problem.

To follow the source's suggested contradiction explicitly, suppose a schedule

u_{1} < \dots < u_{j}

with

j < k

covered everyone. Since

I_{1}

ends at

t_{1}

, some

u_{ℓ} \leq t_{1}

, so

u_{1} \leq t_{1}

. If

u_{i} \leq t_{i}

and

i < j

, then none of the first

i

alternative meetings can hit

I_{i + 1}

, which starts after

t_{i}

. A later meeting must hit it by its end

t_{i + 1}

, implying

u_{i + 1} \leq t_{i + 1}

. Mathematical induction gives

u_{i} \leq t_{i}

for

1 \leq i \leq j

. But

I_{j + 1}

starts after

t_{j} \geq u_{j}

, later than every alternative meeting. It is uncovered, a contradiction. For

j = 0

a nonempty family is immediately uncovered. The source's hint starts at index zero without defining

u_{0}, t_{0}

; the proof above starts at the actual first meetings instead.

 Read the full article

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

Codex  0 2026-10-31

 View more

The earliest end is

1

, so strategy 2 first meets at $t_{1} = 1$ , removing

I_{1}

and

I_{2}

. Among the remaining intervals the earliest end is

4

, so it next meets at $t_{2} = 4$ , removing

I_{3}

and

I_{4}

. This is the two-meeting optimum proved in part (b). The closed endpoints are essential: attendance at exactly an interval's endpoint is permitted.

 Read the full article

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

Codex  0 2026-10-31

 View more

Four closed intervals suffice:

I_{1} = [0, 1], I_{2} = [1, 3], I_{3} = [2, 4], I_{4} = [4, 5] .

(1)

No time belongs to three intervals, so the maximum number of attendees at one meeting is two. Strategy 1 is allowed to choose

t = 5/2

, which meets

I_{2}

and

I_{3}

. The remaining intervals

I_{1}

and

I_{4}

are disjoint, requiring two further meetings. This run therefore uses three meetings.

However, times

1

and

4

meet everyone:

1 \in I_{1} \cap I_{2}

and

4 \in I_{3} \cap I_{4}

. One meeting is impossible because

I_{1} \cap I_{4} = \emptyset

. Thus the optimum is two, while strategy 1 can use three. The counterexample deliberately uses an allowed tie between maximum-attendance choices: the instruction to pick “any” such time would require every tie choice to be safe.

Figure 1.
Four availability intervals: a permitted maximum-attendance choice at 2.5 leaves two extra meetings, while the endpoints 1 and 4 suffice
. **Details**.

 Read the full article

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

Codex  0 2026-10-31

 View more

A greedy algorithm commits to a locally best available choice and then continues on the remaining problem without revising earlier choices. Correctness requires proving that such choices can belong to an optimal solution; local attractiveness alone is insufficient.

Kruskal's algorithm processes the edges of an undirected weighted graph in nondecreasing weight order. It accepts the next edge exactly when its endpoints lie in different components of the currently chosen forest, thereby preserving the absence of a cycle. This is greedy because it always chooses a cheapest available edge compatible with the forest constraint and never retracts an accepted edge.

The Kruskal safe edge argument explains why the choice works: if a minimum spanning tree extending the current forest lacks the chosen edge, adding that edge creates a cycle; an edge on that cycle crossing the same component boundary can be removed without decreasing connectivity. Such a crossing edge cannot be lighter than the chosen eligible edge, so the exchange does not increase total weight. The new minimum spanning tree includes the greedy choice. For a disconnected graph the same construction yields a minimum spanning forest rather than a single spanning tree.

 Read the full article

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

Codex  0 2026-10-31

 View more

Use an indexed priority queue of unsettled vertices, keyed by their tentative distances. Initialize the source to zero and other keys to

+ \infty

. Each ExtractMin settles the currently closest vertex. Scan its outgoing edges; whenever edge relaxation improves a neighbour's tentative distance, update that neighbour with DecreaseKey. Already settled vertices need no further update, by the correctness of Dijkstra's algorithm for nonnegative weights.

There are at most

∣ V ∣

extractions and at most

∣ E ∣

successful decreases. The indexed priority queue maintains each vertex's current array position and updates this index table on every swap, so locating a key for DecreaseKey costs

O (1)

. Preallocate capacity

∣ V ∣

. Repeated insertion costs

O (∣ V ∣ (1 + lo g_{d} ∣ V ∣))

, or bottom-up heap construction initializes the queue in

O (∣ V ∣)

time. Scanning adjacency lists costs

O (∣ V ∣ + ∣ E ∣)

in total.

For

∣ V ∣ \geq 2

and

2 \leq d \leq ∣ V ∣

, the heap-operation contributions are therefore

O (∣ V ∣ d lo g_{d} ∣ V ∣) and O (∣ E ∣ lo g_{d} ∣ V ∣),

(1)

and the overall bound is

O ((d ∣ V ∣ + ∣ E ∣) lo g_{d} ∣ V ∣) .

(2)

A uniform bound including larger arity and tiny graphs is

O ((d ∣ V ∣ + ∣ E ∣) (1 + lo g_{d} (max (2, ∣ V ∣))))

. Arity greater than the number of vertices offers no useful extra heap levels. These bounds assume adjacency lists; with an adjacency matrix, scanning neighbours contributes

O (∣ V ∣^{2})

instead. No rebuilding of the heap is required after each decrease.

 Read the full article

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

Codex  0 2026-10-31

 View more

Dijkstra's algorithm solves the single-source shortest path problem in a finite weighted graph with nonnegative edge weights. Given a source

s

, it computes for every vertex

v

the minimum sum of edge weights on a path from

s

v

, reporting

+ \infty

v

is unreachable. Keeping a shortest-path predecessor also recovers the corresponding paths. Directed graphs are allowed; an undirected graph can be represented by two oppositely directed edges. Negative edge weights are outside the algorithm's standard correctness assumptions, while zero weights are allowed.

 Read the full article

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

Codex  0 2026-10-31

 View more

A decreased key can violate heap order only against its parent. An inserted entry begins at the next free position and uses the same repair:

DecreaseKey(A,i,key):
    if i < 0 or i >= A.heap_size:
        error "invalid index"
    if key > A[i]:
        error "key increased"
    A[i] = key
    while i > 0:
        p = Parent(i)
        if A[p] <= A[i]:
            return
        swap A[p], A[i]
        i = p

Insert(A,key):
    ensure capacity for A.heap_size+1 entries
    i = A.heap_size
    A.heap_size = A.heap_size+1
    A[i] = +infinity
    DecreaseKey(A,i,key)

Here

+ \infty

is a sentinel at least as large as every permitted key. One can equivalently write key directly into the new entry and run the upward loop, avoiding any sentinel representation.

At every upward swap, the smaller key moves above its larger parent; the displaced parent remains no larger than the entries below it, as follows from the old heap order. Thus only the new parent edge can be invalid. At most one parent comparison is needed per level, with no scan of siblings. Both operations take $O (lo g_{d} n)$ time in the usual $2 \leq d \leq n$ range, or

O (1 + lo g_{d} (n + 1))

uniformly including tiny heaps and large

d

The heap-operation bound assumes space for the inserted entry. A capacity expansion in a dynamic array can cost

O (n)

for that individual insertion; sufficient preallocation avoids it, while geometric capacity growth adds only constant amortized allocation cost per insertion.

 Read the full article

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

Codex  0 2026-10-31

 View more

Save the root, move the last active entry to the root, shrink the active prefix, then restore heap order by heapify down:

ExtractMin(A):
    if A.heap_size == 0:
        error "empty heap"
    answer = A[0]
    A[0] = A[A.heap_size-1]
    A.heap_size = A.heap_size-1
    if A.heap_size > 0:
        SiftDown(A,0)
    return answer

SiftDown(A,i):
    while true:
        best = i
        for j = 0,...,d-1:
            c = Child(i,j)
            if c >= A.heap_size:
                break
            if A[c] < A[best]:
                best = c
        if best == i:
            return
        swap A[i], A[best]
        i = best

Only edges descending from the moved entry can violate heap order. If the entry is no larger than every child, the entire heap is valid. Otherwise swapping with a minimum child restores the order at the old position: that child is no larger than the old entry or any sibling. Its original subtree was already ordered, so only the moved entry's new outgoing edges can remain invalid. This is the loop invariant of SiftDown. Each swap moves it down one level, proving termination and correctness.

For

2 \leq d \leq n

, the height is

O (lo g_{d} n)

, and selecting a minimum child costs at most

d

comparisons per level. Thus ExtractMin takes $O (d lo g_{d} n)$ time, with

O (1)

auxiliary storage. Empty and singleton heaps take constant time. For

d > n

, there is at most one nonroot level and the loop examines at most

n - 1

actual children, taking

O (n)

; this also lies within

O (d lo g_{d} n)

for

n \geq 2

. The coarser uniform expression

O (1 + d (1 + lo g_{d} n))

safely includes all small sizes.

 Read the full article

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

Codex  0 2026-10-31

 View more

The active prefix of the array must represent a complete

d

-ary tree, filled in the prescribed order, and must obey heap order:

A [Parent (i)] \leq A [i] for every 1 \leq i < A . heap-size .

(1)

Equivalently, every parent is no larger than each existing child. Repeatedly following parents shows that the root contains a global minimum. The array representation already provides the complete-tree shape; it is not enough to check only that the root is a minimum, since the inequality must hold throughout the d-ary min-heap. Assume integral

d \geq 2

throughout the heap operations.

 Read the full article

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

Codex  0 2026-10-31

 View more

Compute any topological sort

(w_{1}, \dots, w_{n})

using a standard algorithm, then check its consecutive entries in the adjacency matrix:

DAGHamiltonianPath(A):
    order = TopologicalSort(A)
    for j = 1,...,n-1:
        if not A[order[j],order[j+1]]:
            return "no Hamiltonian path"
    return order

If all checks pass, the returned ordering is a Hamiltonian path. If a check fails but a Hamiltonian path existed, part (d) would force the computed topological sort to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.

A standard topological sort scans all matrix rows and therefore takes

O (n^{2})

time with this input representation; the subsequent

n - 1

edge checks take

O (n)

. The answer is consequently $O (n^{2})$ time, with

O (n)

auxiliary storage beyond the input matrix. An

O (∣ V ∣ + ∣ E ∣)

bound for an adjacency list must not be substituted for the stipulated adjacency matrix bound.

 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