A progenitor cell is a precursor with relatively restricted cell differentiation potential and, generally, more limited self-renewal than a stem cell. Usage depends on the lineage and assay; an expression marker alone does not establish renewal capacity.

A stem cell can produce both renewed stem cells and differentiated descendants. Its developmental range depends on the type and setting; self-renewal does not imply unrestricted cell fate.

A cell state describes current properties of a biological cell, including its gene expression, structure and activity. A snapshot of cell state does not alone establish its future cell fate.

Spontaneous emission is radiative decay of an excited matter quantum state by emission of a photon, without an applied resonant drive. In a simple Markov decay model the excited-level population obeys ${\dot{P}}_e=-\Gamma P_e$. During driven control, the expected emission count is governed by $\Gamma \int P_e(t)dt$; suppressing the lossy level's population is therefore the purpose of dark-state adiabatic transfer.

The statistical weight of an atomic level counts its degenerate quantum states. With no external field resolving magnetic substates, a specified total angular momentum $J$ gives $2J+1$ states. An unresolved term can have a larger summed weight. These weights enter the Boltzmann distribution, Saha ionization equation and detailed-balance relations; term and resolved-level weights must not be interchanged.

An atomic oscillator strength is a dimensionless measure of an optical transition's absorption strength relative to a classical electron oscillator. It is related to its spontaneous radiative rate through the transition energy and the statistical weights of the two levels. The absorption convention $f_{ij}$ fixes the lower state $i$ and upper state $j$; interchanging that convention can lose a weight factor.

A collisional-radiative model solves coupled atomic population equations using collisions, radiative transitions, ionization and recombination. For one fixed ion stage, a common stationary approximation is $0={\sum }_{j\ne i}(n_j{P}_{ji}-n_i{P}_{ij})$, supplemented by the total ion population. Electron-impact rates contribute $n_e{q}_{ij}(T)$ and spontaneous downward transitions contribute $A_{ij}$. Additional radiation, proton collisions and adjacent-ion source terms are included when significant.

A metastable atomic level has no strong allowed radiative decay and therefore a comparatively long radiative lifetime. Weak multipole decays can still occur. At low density radiative decay can keep its population small; as density increases, collisional population and mixing compete with that decay. Metastable levels provide density-sensitive feeding of other spectral lines.

Fine structure splits atomic levels through relativistic corrections and interactions involving spin, such as spin-orbit coupling. Different total angular momenta can then have distinct energies. Even a small ground-term splitting can matter for density-sensitive metastable atomic levels, because weak radiative decay between the levels competes with collisional mixing.

Johannes Kepler inferred quantitative laws of planetary motion from astronomical observations. In Astronomia nova by Johannes Kepler, published in 1609, the problem of Mars's path led him to an ellipse with the Sun at one focus and an equal-area timing law.

The equal-area law states that the line from the Sun to the planet sweeps out equal areas in equal times. Together, a geometric orbit and a timing law specify where the planet moves and how its speed changes. Their later connection to a central force and an inverse-square law is explained in inferring an inverse-square force from Kepler laws; those dynamical deductions should be distinguished from Kepler's original empirical construction.^[ref]

Edmond Halley connected separate historical appearances of a comet by comparing their calculated orbits. In his 1705 synopsis he argued that the appearances of 1531, 1607 and 1682 belonged to the same returning body.

The important step was a testable prediction: the comet should return, with its timing affected by gravitational perturbations from the planets. Its later return in 1758 supported the interpretation. The achievement applied orbital dynamics to historical observations rather than treating each bright apparition as an unrelated event.^[ref]

Proper motion describes the change in a celestial object's direction on the sky due to its motion relative to the observer. Its angular velocity differs from the annual stellar parallax signal caused by the observer's orbit.

Thus proper motion is an angular velocity, rather than a speed in kilometres per second. It describes the relative transverse motion of source and observer in a specified reference frame. A star moving towards us can have little proper motion, while a nearer star can show larger proper motion than a faster but more distant one. In the example above, the observed coordinate actually decreases over the first half-year, although $\mu$ is positive: the annual stellar parallax excursion temporarily outweighs the steady drift. A short observed displacement alone therefore need not estimate proper motion well.

Real catalogues give two proper motion components. For right ascension $\alpha$ and declination $\delta$, the angular velocities in perpendicular directions on the local sky areThe cosine factor accounts for the shorter east-west arc associated with a given right ascension increment away from the celestial equator. ESA's Gaia DR3 fields pmra and pmdec already contain these two components; pm is their total proper motion. Do not multiply pmra by another cosine. Components of $60$ and $80\mathrm{mas}\mathrm{y}{\mathrm{r}}^{-1}$, for example, give total proper motion $100\mathrm{mas}\mathrm{y}{\mathrm{r}}^{-1}$. ^[ref].

For nearby stars in the ordinary nonrelativistic approximation, Euclidean distance $d$ converts total proper motion into transverse speed $v_{\perp }$:The small-angle approximation gives transverse speed as Euclidean distance times angular velocity in radians per unit time. With arcseconds and parsecs, the parsec convention turns their product into astronomical units per year. One astronomical unit per Julian year of $365.25$ days is approximately $4.74047\mathrm{km}{\mathrm{s}}^{-1}$. The coefficient is a unit conversion, rather than a property of a particular star.

Taking the model's $100\mathrm{mas}\mathrm{y}{\mathrm{r}}^{-1}=0.100\mathrm{arcsec}\mathrm{y}{\mathrm{r}}^{-1}$ as the total proper motion, with the other component zero, gives $v_{\perp }=4.74047\times 0.100\times 20\simeq 9.48\mathrm{km}{\mathrm{s}}^{-1}$. At the same total proper motion, Euclidean distances of $10$, $20$ and $100$ parsecs instead give transverse speeds of $4.74$, $9.48$ and $47.40\mathrm{km}{\mathrm{s}}^{-1}$, respectively. Their stellar parallax values are $100$, $50$ and $10\mathrm{mas}$. The same annual angular displacement can therefore describe quite different journeys through space.

The transverse speed still omits the line-of-sight velocity, which can be measured through the Doppler effect in spectral lines. Combining these measurements permits a three-dimensional velocity estimate in a consistent reference frame. ^[ref].

Historically, Edmond Halley's 1718 paper compared contemporary and ancient stellar directions and argued that some supposedly fixed stars had moved. Its title, "Considerations on the change of the latitudes of some of the principal fixt stars", captures the conceptual surprise: long-separated measurements could reveal motion invisible in an ordinary night's watching. Modern astrometry retains that insight, using repeated precise measurements to turn the apparently static sky into a record of changing positions. ^[ref]. ^[ref].

Binary search finds a target $x$ in a sorted array $A$ by inspecting the middle of the remaining candidate range. If the middle entry is smaller than $x$, every entry to its left is also too small; if larger, every entry to its right is too large. One comparison therefore rules out many entries. Equal entries are allowed; this version returns any matching index, without promising the first occurrence.

Use indices starting at zero and inclusive endpoints $L,R$. Initially $L=0$, $R=n-1$, where $n$ is the array length. While $L\le R$, chooseThe brackets denote the floor function. Compare $A_m$ with $x$: return $m$ on equality; set $L=m+1$ if $A_m<x$; otherwise set $R=m-1$. If $L>R$, report absence. The updates exclude the already inspected middle entry. This also handles an empty array, whose initial endpoints are $0,-1$. Sedgewick and Wayne specify a sorted array as input and return a matching index or $-1$ for absence.^[ref]

For a fully worked example, take the sorted arraySearch for $x=23$:

For $x=24$, the first two steps agree. Next $24>23$ retains only index $6$; inspecting $A_6=38$ sets $R=5$. Now $L=6>5=R$, so the answer is "absent" after four comparisons.

The loop invariant is: the array stays sorted, $0\le L\le R+1\le n$, and every index containing $x$ lies between $L$ and $R$. It holds initially. The sorted array property justifies each exclusion. Returning on equality gives a match; an empty candidate range implies absence. Crucially, this loop invariant allows $x$ to be absent from the beginning.

For a nonempty range of size $s=R-L+1$, an unsuccessful comparison leaves at most $\lfloor s/2\rfloor$ candidates. Thus sizes satisfy $s_k\le \lfloor n/2^k\rfloor$ after $k$ unsuccessful comparisons. This proves termination and, for $n\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ middle-entry comparisons. The final singleton still needs inspection: $n=1$ requires one comparison, not zero. For $n=15$, the bound is four. This is the halving argument behind logarithmic time complexity.^[ref]

A decision tree with $q$ binary tests has at most $2^q$ leaves. Distinguishing $n$ possible matching positions therefore requires $q\ge \lceil {\log }_{2}n\rceil$. This lower bound counts binary tests, whereas the bound above counts three-way comparisons.

The merge algorithm combines two finite sorted sequences under the same total order, retaining every entry exactly once. Keep a position at the first unconsumed entry, or "head", of each input. While both heads exist, compare their keys, append the smaller head to the output, and advance only that head's position. On equality take the left head. Once either sequence is exhausted, append the other remainder without further key comparisons. Empty inputs therefore require no head comparisons. The MIT notes illustrate this two-head combination step.^[ref]

For example, the merge algorithm applied to $(1,4,7)$ and $(2,3,8,9)$ returns $(1,2,3,4,7,8,9)$:

The head pairs $(1,2)$, $(4,2)$, $(4,3)$, $(4,8)$ and $(7,8)$ select $1,2,3,4,7$ respectively. After the fifth comparison the left sequence is empty, so $(8,9)$ is appended. Seven entries are written, but only five head comparisons occur: tests for exhaustion and appending the remainder are separate operations. This distinction makes the example's count smaller than the bound $3+4-1=6$.

For nonempty inputs of lengths $m,n$, each head comparison consumes exactly one entry. After $m+n-1$ such removals at most one entry remains, so both heads cannot still exist. Hence the merge algorithm uses at most $m+n-1$ head comparisons. The bound can be attained: $(1,3,5)$ and $(2,4,6,7)$ require six head comparisons before the left sequence is exhausted. With constant-cost comparisons, access and copying, writing all $m+n$ entries gives time complexity $O(m+n)$ in Big O notation. Writing a separate output array needs $m+n$ entry slots; the two positions require only constant additional storage.

The merge algorithm is useful whenever two already ordered collections must become one: it reads each input only forwards. This works with arrays and linked lists, without needing access to arbitrary middle positions. Choosing left on ties preserves each input's internal order and places equal left entries before equal right entries, which is the combination rule needed for stable sorting in merge sort.

The loop invariant behind algorithm correctness is that the emitted prefix is sorted, contains exactly the consumed entries, and every emitted key is at most every unconsumed key. Each sorted sequence has its smallest remaining key at its head, so the smaller of the two heads is safe to append. The invariant survives each removal; when one sequence ends, the other sorted remainder is safe to append in full. Each comparison removes an entry, so termination follows from the finite input lengths.

// Target: computer-science.bigb

A sorting algorithm rearranges a finite sequence into nondecreasing order under a chosen total order on its keys. Its output must contain every input entry exactly once, including repetitions: producing ordered values is insufficient if entries are lost. Merge sort is one such algorithm; stable sorting adds a requirement about equal keys.

Sorting creates reusable structure: equal sort keys become adjacent, and a sorted array supports binary search. However, an algorithm correctness check must establish both sortedness and sorting permutation preservation. Replacing every entry by the smallest key can produce ordered keys while destroying the original data. Stable sorting imposes a third condition when equal sort keys occur: retain their arrival order.

For example, take complete sorting records $(2,A),(1,B),(2,C),(1,D)$, with the first component as the sort key and the letter as associated data. A correct output is $(1,B),(1,D),(2,A),(2,C)$. The sort keys are ordered, every complete sorting record remains, and the equal-key pairs keep $A$ before $C$ and $B$ before $D$. The output $(1,D),(1,B),(2,C),(2,A)$ satisfies sortedness and sorting permutation preservation, but fails stable sorting. The output $(1,B),(1,B),(2,A),(2,A)$ has the right multiset of sort keys but loses $C,D$ and duplicates $A,B$; it fails sorting permutation preservation of complete sorting records.

To express stable sorting precisely, label every input occurrence by its original position, even when two complete sorting records have identical contents. Let $p(i)$ be the output position of the occurrence originally at position $i$. Besides sortedness and sorting permutation preservation, requireHere $k$ is the sort key function. Sorting by the pair $(k(A_i),i)$ under lexicographic order gives the same order as stable sorting by $k$: the original position breaks ties without discarding associated data. For a two-field ordering, first apply stable sorting by the secondary sort key, then apply stable sorting by the primary sort key. The second pass retains the secondary order within each group of equal primary sort keys. For instance, $(2,B),(1,C),(2,A),(1,A)$ first becomes $(2,A),(1,A),(2,B),(1,C)$ by letter, then $(1,A),(1,C),(2,A),(2,B)$ by number.

A divide-and-conquer algorithm divides a problem into smaller instances, solves them using recursion, and combines their answers. In merge sort, the division makes two contiguous halves, and the merge algorithm combines the resulting sorted arrays. The important design step is finding a combination rule cheaper than solving the whole problem afresh.

Halving the input is only one part of the design. The number of recursive calls and the work outside those calls determine whether the smaller instances actually save time. Divide-and-conquer combination cost keeps these quantities separate; the divide-and-conquer product ledger shows how an algebraic identity changes the number of required calls in Karatsuba multiplication.

For algorithm correctness, specify the meaning of each returned answer, prove the base cases, and show that combining correct smaller answers gives the required output. Induction then proves correctness, provided every recursive call progresses towards a base case. The combination rule must reconstruct everything the caller needs: two sorted halves alone are not a sorted array, and four digit blocks alone are not their integer product.

Recursion solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For merge sort, an empty or one-entry array is already sorted, and every larger array is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.

A recursive procedure refers to itself, directly or through another procedure. A recursive call starts another invocation, with its own arguments and local variables; the caller can wait for its returned output. A base case supplies an answer without further recursive calls. To establish algorithm termination, also show that every recursive call progresses in a well-founded relation. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.

Recursion is especially expressive when a data structure already decomposes into smaller structures. A binary tree has two child subtrees, so structural recursion can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a recursive procedure and the recursive process it generates helps connect that compact description to its resource use.^[ref]

Memoization retains a completed function result under a memoization key and returns that result when an equivalent request recurs. For a terminating pure function, repeated evaluation can therefore become lookup rather than repeated work. The benefit is especially striking with recursion and overlapping subproblems: a large tree of calls can refer to a small directed acyclic graph of distinct answers. The memoization cache contract determines whether reuse is correct; the memoization cache lifetime determines whether an answer is still present when wanted.

Memoization records computed answers, whereas a memory cache retains data from computer memory. A CPU cache hit does not by itself prevent a program from evaluating the same function again. Spreadsheet dependency evaluation adds an explicit mechanism for invalidating affected cached cell values after inputs change; a general memoization table does not discover such changes automatically.

A documented early motivation was to let programs improve their efficiency during execution through rote learning: the abstract of a 1968 paper explicitly proposes such a programming language facility.^[ref]

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb