A mutable cell holding a value of type 'a. ref allocates a cell, ! reads it and := updates it. Aliases share the same cell; the value restriction prevents unsafe polymorphic mutable storage.

// Target: computer-science.bigb

A call stack stores active procedure calls and the information needed to resume each caller, such as its return location and local variables. A call adds a frame; returning removes that frame and resumes the previous call. When depth-first search uses recursion, a frame also records where its adjacency list scan paused. The active frames describe a graph path from the starting vertex to the current vertex; finished calls have left the call stack, although their vertices remain marked as discovered.

DPPH is a neutral organic radical used as a spin reference in electron paramagnetic resonance (EPR), also called electron spin resonance (ESR). Its unpaired electron remains bound within the chemical species: “free radical” does not mean a freely moving electron. The DPPH electron spin resonance experiment makes its magnetic moment observable.

For the normalized sRGB calculations here, relative luminance is the linear-light weighted sumwhere $R,G,B$ are decoded linear-light components, not encoded code values. This is the sRGB calculation specified in W3C's WCAG 2.2 definition of relative luminance. It places reference black at 0 and reference white at 1; it does not by itself specify an absolute display light level.^[ref]

For a neutral sRGB shade, $R=G=B=l$, and the weights sum to 1, so $Y=l$. For a coloured pixel, relative luminance can be encoded as a neutral sRGB shade with all three encoded components $E(Y)$. This preserves the specified $Y$ while discarding colour differences; it is one precisely defined grayscale conversion, not a unique way to turn all colour images into grayscale.

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

The directed graph whose vertices are the spreadsheet cells and whose directed edges $u\to v$ mean that the spreadsheet formula in $v$ references $u$. Input spreadsheet cells have no prerequisites in this model. Retain both incoming references and outgoing consumers: depth-first search for evaluation follows incoming references backwards, whereas downstream invalidation follows outgoing consumers forwards. A directed path then expresses indirect dependence, and a directed cycle expresses a spreadsheet circular reference.

A mathematical expression stored in a spreadsheet cell, with references to other spreadsheet cells. In this example =A1+A2 asks for addition, =2*A1 for multiplication, and =A2^2 for exponentiation. The evaluator in spreadsheet dependency evaluation assumes these spreadsheet formulas have already been represented by their ordered lists of referenced spreadsheet cells and operations on the resulting numbers; it does not execute arbitrary formula text.

Copying a spreadsheet formula produces a new expression by adjusting its spreadsheet cell references. Copying only its displayed value produces a number instead. For example, copying the spreadsheet formula =A2*B2 down one row gives =A3*B3; entering its former value $15/2$ in the next row would give neither the required relationship nor this example's correct subtotal $7$.

Einstein coefficients describe spontaneous emission, stimulated emission and absorption between atomic levels. With $B$ multiplying radiation energy density per frequency, thermal detailed balance gives $g_i{B}_{ij}=g_j{B}_{ji}$ and $A_{ji}/B_{ji}=8\pi h{\nu }^3/c^3$. Coefficients defined using mean specific intensity instead have a different normalization; specify the radiation convention.

The critical density of an atomic transition is the electron density at which its collisional de-excitation rate equals its spontaneous radiative decay rate. A multilevel atom requires summed competing rates rather than a single-transition ratio. This atomic density scale is distinct from cosmological critical density.

A radiative cascade is a sequence of downward photon-emitting transitions following excitation or recombination. Cascades feed lower excited levels and change their emitted line intensities. An effective recombination coefficient includes all relevant cascade paths under its stated optical-depth and density assumptions.

A species can encompass many biological populations. A biological population specifies a set of organisms in a place and time; a biological strain identifies a maintained variant or lineage, often in a laboratory. A species name, a local census and a biological strain designation therefore describe different things. Multiple independently maintained cultures can also share the same biological strain designation.

For example, a culture identified as Escherichia coli K-12 MG1655 specifies more than the species alone. Two flasks inoculated from that culture are separate experimental biological populations; the separate containers do not establish two species or two different biological strains. This is an original experimental bookkeeping example, not a claim that every biological strain name encodes a complete genotype.

Species delimitation infers the boundaries and number of species from evidence. No single arbitrary percentage of nucleotide sequence difference is a universal boundary. Divergence within an old, widespread species can exceed divergence between recently separated species; geography and multiple kinds of evidence matter. ^[ref]

An original counterexample to a universal percentage rule: an assay could examine a strongly conserved gene in one comparison and a rapidly changing nucleotide sequence in another. Equal percentages then answer different historical questions. Even the denominator needs specifying: all sites, aligned sites, or only a filtered region? A threshold is an operational rule for a stated assay and group of organisms, whose errors need evaluating. It is not a definition that automatically transfers to every species.

The diagram's hypothetical pair B has similar morphology but reduced mating and distinct ancestry evidence. A morphological species concept could miss that distinction. Pair C instead has different morphology but compatible mating and ancestry that fails to separate the samples. That combination calls for checking variation in phenotype within a species. Pair A has only a structural difference observed: the other criteria remain untested. These examples show why missing evidence, disagreeing evidence and agreeing evidence require different interpretations.

A species concept states what should make organisms members of the same species; an operational criterion states what observations will test that claim. Reproductive isolation, distinguishable morphology and ancestry inferred through phylogenetics answer different questions. In a lineage-based interpretation, they are evidence for separation of evolving biological populations, and need not appear together. ^[ref]

Reproductive isolation consists of barriers that reduce gene flow through sexual reproduction. Distinguish premating isolation from barriers after mating. Barriers before fertilization also include incompatible gametes; barriers after fertilization can reduce offspring survival or fertility. ^[ref]

An assay should state which step it measures. Observing fewer cross-group matings does not measure offspring fertility; observing fertilization does not demonstrate that the offspring will reproduce. These distinctions make a partial barrier informative without declaring completed speciation.

A massive particle is nonrelativistic when its speed is small compared with the speed of light. Its energy expansion is $E=m{c}^2+p^2/(2m)+O(p^4/(m^3{c}^2))$. The leading momentum-dependent term is the classical kinetic energy.

A relativistic massive particle is described by a timelike worldline with proper-time four-velocity $u^{\mu }$. In signature $(+---)$ its normalization is $u^{\mu }{u}_{\mu }=c^2$ and its momentum is $p^{\mu }=m{u}^{\mu }$. The relativistic charged-particle action adds electromagnetic coupling, whose variation gives the Lorentz force.

The laws of physics have the same form in all inertial frames; uniform absolute motion cannot be identified by experiments confined to an inertial laboratory. The invariant vacuum speed of light is a separate postulate. Together they motivate the Lorentz transformations of special relativity.

Merge sort is a divide-and-conquer algorithm that sorts a finite array by splitting it into contiguous halves, sorting each half using recursion, and combining the two sorted arrays with the merge algorithm. An empty or one-entry array is returned immediately. For length $n\ge 2$, put the first $\lfloor n/2\rfloor$ entries on the left and the remaining $\lceil n/2\rceil$ on the right; the brackets are the floor function and ceiling function. Always choose the left head on equal keys to obtain stable sorting. This is the split, sort, combine structure taught in the MIT lecture notes.^[ref]

Take the concrete input arrayThe tags identify the entries originally at indices $1$ and $3$, counting from zero. Both keys are $2$; the tags are never compared. Reading downward in the figure follows the splits, then the returned sorted arrays. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.

The first two halves are $(7,2_a,5,2_b)$ and $(9,1,4,3)$. Their pairs split into one-entry base cases. Applying the merge algorithm gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.

In the left-half merge algorithm, the head pairs are $(2_a,2_b)$, $(7,2_b)$ and $(7,5)$; it takes $2_a,2_b,5$, then appends $7$. In the final merge algorithm, the head pairs are $(2_a,1)$, $(2_a,3)$, $(2_b,3)$, $(5,3)$, $(5,4)$, $(5,9)$ and $(7,9)$. It takes $1,2_a,2_b,3,4,5,7$, then appends $9$. Thus this precise version makes $4+6+7=17$ head comparisons and, ignoring identity tags, returns $(1,2,2,3,4,5,7,9)$.

The elegance of merge sort is that it creates exactly the structure its next step needs: two smaller sorted arrays make the larger ordering inexpensive. Once the whole array is sorted, equal keys are adjacent and binary search can serve repeated queries. Stable sorting also retains information that the keys alone do not express. If the left-half merge algorithm instead takes the right head on the $2_a=2_b$ tie, it returns $(2_b,2_a,5,7)$; the keys are sorted but stable sorting has failed.

For time complexity, assume each key comparison, entry access and entry copy has constant cost. The merge algorithm processes $n$ entries in $O(n)$ time. In Big O notation, the resulting recurrence relation isFor $n=2^k$, the balanced levels contain $n$ entries each and there are $k={\log }_{2}n$ returning levels. Each costs $O(n)$, so the worst-case time complexity is $O(n\log n)$. For arbitrary $n$, there are at most $\lceil {\log }_{2}n\rceil$ returning levels, each processing at most $n$ entries, giving the same bound. The worst-case number of head comparisons is also $O(n\log n)$. Here ${\log }_2$ is the base-two logarithm. The MIT notes give this level-by-level analysis for merge sort.^[ref]

The conventional array implementation uses a reusable buffer of $n$ entries for the merge algorithm, together with $O(\log n)$ pending calls for recursion. Its auxiliary space complexity is therefore $O(n)$, beyond the original array. This bound describes that implementation. A linked list permits a merge algorithm that reconnects existing nodes; its storage accounting differs from copying array entries into a buffer.

For a short algorithm correctness outline, the empty and one-entry base cases are sorted. Assuming recursion correctly sorts both shorter halves, the merge algorithm returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves stable sorting. Both half-lengths decrease for $n\ge 2$, establishing termination.

Stable sorting preserves the original relative order of entries with equal keys. The entries may carry different names or other information even when their keys coincide. For example, sorting records $(2,\mathrm{Ada}),(1,\mathrm{Bo}),(2,\mathrm{Cy})$ by the numerical key gives $(1,\mathrm{Bo}),(2,\mathrm{Ada}),(2,\mathrm{Cy})$: Ada remains before Cy. This is useful when a previous ordering contains information worth retaining, such as arrival order among equally ranked requests.