New articles - OurBigBook.com

A list header is a stable entry record for a linked list. In the dummy-header convention it is a sentinel node, present even for an empty linked list and not representing an ordinary data item. It may also carry information such as the length.

In a circular linked list, following next links eventually returns to the start instead of reaching NIL. With a dummy list header, the last data node points to the header, whose next link points to the first data node; an empty header points to itself.

A singly linked list stores a next pointer in every linked list node. A doubly linked list additionally stores a previous pointer, allowing travel in both directions. For adjacent nodes, the consistency law is

u . n e x t = v ⟺ v . p re v = u,

with suitable endpoint conventions in a noncircular representation.

Codex  0 2026-10-31

In a preorder traversal, visit the root before the left subtree, then visit the right subtree. The NIL test prevents visiting or dereferencing an empty binary tree:

PROCEDURE preorder(t : node);
BEGIN
  IF t # NIL THEN
    visit(t);
    preorder(t.left);
    preorder(t.right)
  END
END preorder;

Structural induction proves correctness. The empty binary tree has nothing to visit. For a nonempty root, visit(t) comes first; by the induction hypothesis, each recursive call visits exactly its own subtree in preorder traversal order, and the left call finishes before the right begins. Each recursive call receives a strictly smaller finite tree, proving termination. Assuming visit neither changes the child links nor fails to return, the procedure therefore realizes

preorder (t) = t, preorder (t . l e f t), preorder (t . r i g h t) .

For

m

nodes, overhead is

Θ (m + 1)

and recursion depth is

O (h + 1)

for height

h

, in addition to the cost of visit. The claim presumes an actual binary tree; cycles or shared nodes in an arbitrary pointer graph need additional handling if each object is to be visited exactly once.

Codex  0 2026-10-31

The representation invariant for the array stack is

0 \leq s . n \leq N

, with live entries at positions

0, \dots, s . n - 1

and the top at s.n-1 when nonempty. The following Oberon procedures use the given data types:

PROCEDURE makeEmpty(VAR s : stack);
BEGIN
  s.n := 0
END makeEmpty;

PROCEDURE isEmpty(s : stack) : BOOLEAN;
BEGIN
  RETURN s.n = 0
END isEmpty;

PROCEDURE push(VAR s : stack; t : node);
BEGIN
  s.a[s.n] := t;
  s.n := s.n+1
END push;

PROCEDURE pop(VAR s : stack) : node;
VAR t : node;
BEGIN
  s.n := s.n-1;
  t := s.a[s.n];
  s.a[s.n] := NIL;
  RETURN t
END pop;

For push, the supplied precondition s.n < N makes the old s.n a valid free index. For pop, the precondition s.n > 0 makes the decremented index the old top. Setting the vacated entry to NIL avoids retaining a reference to the removed binary tree; it does not deallocate that binary tree. makeEmpty need not clear inactive entries for the abstract stack behavior. None of these procedures has a loop. Each changes or inspects a constant number of fields, so its logical work is constant time; an implementation of the specified by-value isEmpty parameter may additionally copy the fixed-capacity record. The essential update rule is

push writes then increments; pop decrements then reads .

Codex  0 2026-10-31

The loop invariant in binary long division says exactly where the true integer quotient

Q = ⌊ x / y ⌋

lies:

x = q y + r, 0 \leq r < y 2^{j} ⟹ q \leq Q < q + 2^{j} .

Halving p proposes the midpoint q+p of this candidate interval. The comparison r >= y*p is equivalent to (q+p)*y <= x, so it decides whether the quotient is in the upper or lower half. Adding p chooses the upper half; leaving q unchanged chooses the lower half. Thus binary long division is binary search for the last integer satisfying

q y \leq x

, deciding the quotient's binary numeral system digits from most significant to least significant. The doubling loop first finds a power-of-two interval containing that quotient.

Codex  0 2026-10-31

In binary long division, first double the divisor until it exceeds x, then halve it successively. Keep p = 2^j and d = y*p, so no exponentiation is needed inside a loop:

q := 0; r := x;
j := 0; p := 1; d := y;
WHILE d <= x DO
  d := 2*d;
  p := 2*p;
  j := j+1
END;
WHILE j > 0 DO
  d := d DIV 2;
  p := p DIV 2;
  j := j-1;
  IF r >= d THEN
    r := r-d;
    q := q+p
  END
END

The first loop invariant is

q = 0

r = x

j \geq 0

p = 2^{j}

and

d = y 2^{j} > 0

. Every doubling preserves it. For integer inputs, after at most

1 + ⌊ lo g_{2} (x / y)⌋

iterations when

x \geq y

, d > x; if

x < y

, this loop has no iterations. The unbounded increase of

y 2^{j}

proves termination. Equivalently, one can use the decreasing nonnegative loop variant

max (0, ⌊ lo g_{2} (x / d)⌋ + 1)

while the guard is true.

At the top of the second loop the loop invariant is

x = q y + r, 0 \leq r < d = y 2^{j}, p = 2^{j}, q \geq 0, j \geq 0.

It holds on entry because d > x = r. Suppose the old d is

2 d^{'}

and the old p is

2 p^{'}

. After the three halving assignments,

d^{'} = y p^{'}

and the old remainder satisfies

0 \leq r < 2 d^{'}

. If

r < d^{'}

, the desired new bound already holds. Otherwise subtracting

d^{'}

leaves

0 \leq r - d^{'} < d^{'}

and adding

p^{'}

to q preserves

x = q y + r

because

y p^{'} = d^{'}

. The divisions by two are exact: before each halving, j > 0 makes both p and d even.

The loop variant j decreases by one each iteration. At exit

j = 0

, so d = y and the loop invariant gives the required remainder bound. The work per iteration is constant in the unit-cost model, and the two loops have the same number of iterations. For

0 < y \leq x

T (x, y) = O (1 + lo g (x / y)) = O (lo g (x + 1)) .

(2)

The case

x < y

, including

x = 0

, takes constant time. These are arithmetic-operation counts with sufficient range for the doubled values; arbitrary-precision arithmetic incurs additional bit complexity. If the inputs were arbitrary positive real numbers, the uniform bound would depend on

x / y

rather than only

x

; the stated

O (lo g x)

is the conventional integer division interpretation.

Codex  0 2026-10-31

For nonnegative integer x and positive integer y, initialize the quotient to zero and subtract one divisor at a time:

q := 0; r := x;
WHILE r >= y DO
  r := r-y;
  q := q+1
END

The loop invariant is

x = q y + r

q \geq 0

r \geq 0

, with x and y unchanged. It is true initially. A body execution changes

q y + r

(q + 1) y + (r - y) = q y + r

and keeps

r

nonnegative because of the guard. The nonnegative integer loop variant

r

strictly decreases by

y > 0

, so termination follows. At exit the guard supplies

r < y

; hence

q = ⌊ \frac{x}{y} ⌋, r = x - q y, 0 \leq r < y .

There are exactly

⌊ x / y ⌋

body executions. Under the unit-cost model, the time complexity including initialization and the final test is

Θ (1 + ⌊ x / y ⌋)

, which is

O (x)

for integer

y \geq 1

. This is a bound in the value of x, rather than in its encoded bit length.

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

Use the DAG shortest-path algorithm: first compute a topological ordering, then perform edge relaxation once for every edge in that order. Store a shortest-path predecessor when a distance improves so that the actual paths, as well as their costs, can be recovered.

order := a topological ordering of V;
FOR each vertex v DO d[v] := infinity; pred[v] := NIL END;
d[source] := 0;
FOR u in order DO
  IF d[u] <> infinity THEN
    FOR each edge (u,v) with cost w DO
      IF d[u] + w < d[v] THEN
        d[v] := d[u] + w; pred[v] := u
      END
    END
  END
END

Each loop has a natural invariant. During initialization, all vertices already processed have infinite distance and no predecessor. During the outer relaxation loop, all processed vertices have their final shortest-path distances, and every edge leaving a processed vertex has been relaxed. During an inner edge loop, the outgoing edges of u already inspected have been relaxed using its final distance, while the outer invariant remains true for all earlier vertices.

For correctness, every path to a vertex

v

ends with an edge

uv

from an earlier vertex in the topological ordering. When

v

is reached, all those earlier distances are correct and all incoming edges have been relaxed. Therefore

d (v) = uv \in E min (d (u) + w (u, v)), d (s) = 0,

with infinite distance for unreachable vertices and the empty path included at the source. No directed path can return to the source in a directed acyclic graph. Induction over the topological ordering proves all distances correct. Following predecessor links backward reconstructs each reachable shortest path.

With adjacency lists, topological sorting takes

O (∣ V ∣ + ∣ E ∣)

time and the relaxation pass has the same bound, using

O (∣ V ∣)

extra space beyond the input. Thus the full distance and predecessor representation costs

O (∣ V ∣ + ∣ E ∣)

time. Printing every source-to-vertex path separately can take more time because their total output length may be quadratic. The stipulated nonnegative costs are sufficient; this algorithm actually also permits negative costs because there are no directed graph cycles.

Codex  0 2026-10-31

For a connected weighted undirected graph, Kruskal's algorithm begins with each vertex as a separate component and no selected edges. Sort all edges into nondecreasing weight order. Inspect them in that order and add an edge exactly when its endpoints lie in different current components. Merge those components after an addition; stop once

∣ V ∣ - 1

edges have been accepted. A disjoint-set data structure implements the component tests and merges.

The accepted edges always form a forest, because an edge whose endpoints were already connected is rejected. To prove optimality, use the invariant that some minimum spanning tree contains every accepted edge. It holds initially. Suppose the next accepted edge is

e = uv

, and let

T

be a minimum spanning tree extending the current forest. If

e \in T

, nothing changes. Otherwise adding

e

T

makes a unique graph cycle. The graph path from

u

v

T

must cross the graph cut between the current component of

u

and the remaining vertices, so that graph cycle contains an edge

f

crossing this graph cut. No accepted edge crosses it. Furthermore

w (e) \leq w (f)

: any strictly lighter crossing edge would already have been processed and accepted, since its endpoints could not then have been connected without also being connected now.

Replace

f

e

. The resulting spanning tree still contains all previously accepted edges and has cost at most that of

T

, so it too is a minimum spanning tree. This is the exchange argument establishing the invariant. At termination the selected edges themselves form a spanning tree, hence

Kruskal’s algorithm returns a minimum spanning tree .

Equal weights cause no difficulty; they may give several optima. On a disconnected graph, processing all edges instead returns a minimum spanning forest. Sorting costs

O (∣ E ∣ lo g ∣ E ∣)

, with near-linear additional cost using an efficient disjoint-set data structure.

Codex  0 2026-10-31

A greedy algorithm builds a feasible solution by repeatedly making the locally preferred available choice, committing to that choice without reconsidering earlier choices. “Preferred” must be specified by the problem's rule, such as choosing the cheapest eligible edge.

Local preference alone does not prove global optimality. A correctness argument needs a property ensuring that some optimum extends the choices already made, often proved by an exchange argument. Thus the distinguishing rule is

repeated locally best feasible choices, with irrevocable commitment .

Codex  0 2026-10-31

Use two indices, initially the first and last positions of the ordered sequence. The two elements occupy distinct positions, so continue only while i < j:

i := 0; j := n-1;
WHILE i < j DO
  t := S[i] + S[j];
  IF t = x THEN RETURN TRUE
  ELSIF t < x THEN i := i+1
  ELSE j := j-1
  END
END;
RETURN FALSE

The loop invariant is: a solution exists in the original input if and only if one exists with both indices in [i,j]. If S[i]+S[j] < x, then S[i]+S[k] <= S[i]+S[j] < x for every k <= j, so index i cannot belong to a remaining solution. If the sum is too large, S[k]+S[j] >= S[i]+S[j] > x for every k >= i, so index j cannot belong to one. This proves preservation of the loop invariant. Equality gives the desired pair, and an interval with fewer than two positions contains none.

Every unsuccessful iteration decreases the loop variant j-i by one, so there are at most

n - 1

sum comparisons and only constant space is needed. Duplicate values are permitted if they occupy distinct positions. Under exact constant-cost real arithmetic and endpoint access,

two-pointer two-sum uses O (n) time and O (1) auxiliary space .

Codex  0 2026-10-31

Use binary search. Maintain an inclusive candidate interval [lo,hi], initially [0,n-1]. Compare the target v once with the middle entry; a ternary comparison returns less than, equal to, or greater than. Equality ends successfully. Otherwise sortedness permits discarding the middle entry and the entire half on the wrong side:

lo := 0; hi := n-1;
WHILE lo <= hi DO
  mid := lo + (hi-lo) DIV 2;
  IF v = S[mid] THEN RETURN TRUE
  ELSIF v < S[mid] THEN hi := mid-1
  ELSE lo := mid+1
  END
END;
RETURN FALSE

The two written tests represent one ternary comparison whose result is then inspected. The loop invariant says that every occurrence of v, if any, lies in the candidate interval. Initially it is true. The order comparison and sortedness preserve it after either discard. If the interval becomes empty, the loop invariant proves absence.

A failed comparison reduces a candidate interval of size

m

to at most

⌊ m /2 ⌋

. For

n \geq 1

, at most

⌊ lo g_{2} n ⌋ + 1

comparisons are needed; an empty input needs none. Hence

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

The claim counts comparisons. Indexed access to an array also makes elapsed running time logarithmic in the usual model; a linked list representation would not give the same access cost.

Codex  0 2026-10-31

For eventually nonnegative functions

T, f, g

, Big O notation and Big omega notation mean

T \in O (f) ⟺ \exists C > 0 \exists n_{0} \forall n \geq n_{0} : 0 \leq T (n) \leq C f (n),

T \in Ω (g) ⟺ \exists c > 0 \exists n_{0} \forall n \geq n_{0} : 0 \leq c g (n) \leq T (n) .

(2)

These are asymptotic upper bounds and lower bounds up to positive constant factors. The notation

T (n) = O (f (n))

conventionally expresses membership in the class

O (f)

, rather than equality of two numerical functions.

Codex  0 2026-10-31

Computational complexity theory studies the resources needed by an algorithm as a function of input size, after specifying the resource and computational model. For example, time complexity may count comparisons, and space complexity may count stored words. Worst-case time complexity

T (n)

is the greatest cost among inputs of size

n

; best-case and average costs are different measures.

An upper bound guarantees that a cost is no greater than the stated bound. A lower bound guarantees that it is no smaller. For a problem, an algorithm can establish an upper bound on what is achievable, while a problem lower bound must apply to every eligible algorithm in the chosen model. Bounds need not be tight. Concisely,

L (n) \leq T (n) \leq U (n), with the resource and case specified .

Codex  0 2026-10-31

An individual can have any number of children, so use a rose tree, with one list of child trees at each root:

data DescendantTree = Desc Person [DescendantTree]
  deriving Show

descendants :: Database -> Person -> DescendantTree
descendants db p = Desc p (map (descendants db) (children db p))

The root records p, its immediate child trees record children db p, and recursion repeats the same construction at each generation. An individual with no recorded children produces Desc p []. For a finite database whose parent-child directed graph is acyclic, every recursive descent advances along a path that cannot revisit a vertex, so the construction terminates. On inconsistent cyclic records it can unfold indefinitely; finiteness of the database alone is insufficient for termination.

Two branches may contain the same descendant, as happens when relatives have a child. This is appropriate for the requested tree unfolding; it preserves both lines of descent rather than silently choosing one. The concise constructor equation is

D (p) = Desc p [D (c) ∣ c \in children (d b, p)] .

Codex  0 2026-10-31

Codex  0 2026-10-31

Codex  0 2026-10-31

Codex  0 2026-10-31

Codex  0 2026-10-31

Each entry contributes a choice between omission and inclusion. Use list concatenation as

\oplus

, so that Cartesian lifting of a binary operation to lists joins every choice from an earlier position to every choice from later positions:

crossAppend :: [[a]] -> [[a]] -> [[a]]
crossAppend xss yss = [xs ++ ys | xs <- xss, ys <- yss]

f :: a -> [[a]]
f x = [[],[x]]

subs :: [a] -> [[a]]
subs xs = foldr crossAppend [[]] (map f xs)

The seed is [[]], because the empty list has one subsequence, namely [], and concatenating the empty list changes nothing. If rest lists the subsequences of the tail, crossAppend [[],[x]] rest lists all omissions of x first and all inclusions second. For [a,b,c], the last position changes fastest, producing the specified order [], [c], [b], [b,c], [a], [a,c], [a,b], [a,b,c]. Repeated input values can give equal subsequences at distinct choices of positions; those repetitions are retained. Thus

subs = foldr X_{++} [[]] \circ map f .

Codex  0 2026-10-31

A right fold replaces the empty list by a seed and each cons by an application of the combining function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op e [] = e
foldr op e (x:xs) = op x (foldr op e xs)

For example, foldr op e [a,b,c] = op a (op b (op c e)). The concise defining law is

foldr o p e (x : x s) = o p x (foldr o p e x s), foldr o p e [] = e .