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

Periodically sample an executing program's instruction pointer and accumulate an address histogram. Samples approximate time spent in address regions, rather than exact instruction execution counts. Jittering the sampling interval reduces accidental synchronization with periodic code.

// Destination: computer-science.bigb

Replace an operation by an equivalent operation sequence with lower cost on the target machine. For fixed-width wrapping integers, multiplication by eight equals left shift by three, and multiplication by fifteen equals left shift by four minus the original operand. Condition codes and wider results must also be preserved if the original machine instruction exposes them.

// Destination: computer-science.bigb

Linear search, also called sequential search, examines a finite sequence from its beginning, performing an equality test on each entry until one matches the target or the entries run out. It needs no sorted array or total order on the values. This makes it useful for a small collection, a one-off lookup, or data available only in succession: the next entry is enough to make progress.

Specify the answer precisely. For an array $A$ of length $n\ge 0$ with indices $0,\dots ,n-1$ and target $x$, return the smallest index $j$ satisfying $A_j=x$, or a distinct absent result if no such index exists. Repeated values are allowed. In this contract, finding a later duplicate is insufficient when an earlier match exists. Assume the input remains unchanged during the search and each equality test terminates with a stable truth value expressing the intended matching relation.

Here is an implementation in Python; None represents absence and is distinct from the valid index zero:The official Python sequence method s.index(x) likewise specifies the first occurrence, but signals absence by raising ValueError. An API's absent-result convention belongs to its contract.^[ref]

Take the original unsorted array $A=[7,4,7,2,9]$. For $x=7$, the first equality test succeeds and returns index $0$; the other $7$ at index $2$ is never inspected. For $x=2$, the checks against $7,4,7$ fail, the check against $2$ succeeds, and the answer is index $3$ after four equality tests. For absent target $x=6$, all five equality tests fail and the answer is None. On the empty sequence, there is no entry to inspect: return None with zero equality tests.

Value order never justifies skipping an entry in this algorithm. For $x=2$, stopping because the first value $7$ is larger would give a wrong absent result. Any permutation of the input remains searchable by linear search, although the first matching index and number of equality tests can change. By contrast, binary search uses a total order and the sorted array property to discard whole candidate ranges. Its logarithmic time complexity additionally assumes cheap access to middle entries; a sorted linked list does not acquire constant-cost indexed access merely by being sorted. Sorting for a single query also has a cost, and changes positions relative to the original sequence.

Partial correctness means that, if the algorithm terminates on a permitted input, its output meets the specification. Total correctness additionally requires termination on every permitted input.

A greedy algorithm commits to a locally preferred next choice without revisiting earlier choices. Its rule needs a justification to guarantee a globally optimal result: the largest-individual-value rule in the 0-1 knapsack problem example fails, whereas Dijkstra's algorithm correctly settles the smallest tentative distance under its nonnegative-edge assumptions.

For a rigid rough boundary and incident pressure $A{e}^{i\alpha x-i\beta z}$, use time dependence $e^{-i\omega t}$ and ${\alpha }^2+{\beta }^2=k^2$. The flat reflected wave is $A{e}^{i\alpha x+i\beta z}$. Expanding the Neumann boundary condition at $z=0$ gives ${\partial }_z{\psi }_1=2A{e}^{i\alpha x}({\beta }^{2}h+i\alpha h^{\prime })$. For height transform $\hat{h}(q)=\int h(x)e^{-iqx}dx$, the outgoing correction is $(2A/(2\pi i))\int (k^2-\alpha q)\hat{h}(q-\alpha )e^{iqx+i\beta (q)z}/\beta (q)dq$, with $\beta (q)=\sqrt{k^2-q^2}$ on the outgoing sheet. Controlled height expansions also require adequate slope and spectral regularity; small incident phase displacement alone does not bound every normal-derivative correction.

For a slowly varying parallel shear flow $U(y){\mathbf{e}}_x$, the leading WKB method neglects mean-velocity gradients while retaining local advection. The continuity equation and linearized Euler equations then give the displayed acoustic dispersion relation. On the positive intrinsic-frequency branch, $\omega =U{k}_x+c_0|\mathbf{k}|$ and the group velocity is $U{\mathbf{e}}_x+c_0\mathbf{k}/|\mathbf{k}|$. A wavefront normal is parallel to $\mathbf{k}$; the acoustic energy-ray direction generally differs because of the advection term.

A neutralization is a chemical reaction between a chemical acid and a chemical base. In the buffer solution example, hydroxide takes a proton from the weak acid to form water and the conjugate base. The stoichiometry updates the partner inventories before the approximate chemical equilibrium calculation. The name does not require the resulting pH to be $7$.

A buffer solution contains appreciable quantities of a weak acid and its conjugate base, and resists changes in pH caused by small quantities of added chemical acid or chemical base. The conjugate base accepts added protons; the weak acid supplies protons when a chemical base consumes them. Consuming most of either partner undermines the buffering action. See Flowers et al., Chemistry 2e, buffers.

For a separate toy calculation, stipulate pKa $5$ for a weak acid $\mathrm{HA}$; this is an input, not measured material data. Initially $1\mathrm{L}$ of buffer solution contains $0.10\mathrm{mol}$ of $\mathrm{HA}$ and $0.10\mathrm{mol}$ of its conjugate base ${\mathrm{A}}^{-}$. In the ideal concentration approximation, the Henderson-Hasselbalch equation gives initial pH $5$. Add $0.010\mathrm{mol}$ of hydroxide with negligible volume change. The dominant neutralization has one-to-one stoichiometry:Each mole of consumed hydroxide removes one mole of weak acid and forms one mole of conjugate base and water. Thus the inventories after neutralization areThe shared volume cancels from the concentration ratio. The Henderson-Hasselbalch equation therefore predictsThis small increase illustrates how conversion between abundant partners absorbs added chemical base. The calculation neglects the tiny free hydronium and hydroxide inventories, changes during re-establishment of chemical equilibrium, self-ionization of water, and activity coefficient corrections. The displayed inventories approximate the final chemical species distribution; they are not an exact solution of all chemical equilibrium conditions.

A buffer solution has a finite buffer capacity: its weak acid inventory supplies protection against added chemical base, and its conjugate base inventory supplies protection against added chemical acid. Here an addition approaching $0.10\mathrm{mol}$ of hydroxide uses up the available $\mathrm{HA}$ in the dominant stoichiometry calculation. Close to that limit, the neglected chemical equilibrium contributions matter; once $\mathrm{HA}$ is exhausted, inserting a zero denominator into the Henderson-Hasselbalch equation cannot predict the actual pH. Excess hydroxide and the remaining chemical species require a fresh chemical equilibrium calculation. This is why a buffer solution stabilizes conditions for chemical reactions over a finite range of additions. See Flowers et al., Chemistry 2e, buffer capacity and added base.

For the pair $\mathrm{HA}/{\mathrm{A}}^{-}$, rearranging the acid dissociation constant gives the activity relationWith thermodynamic activity of water approximated by one and ideal dilute thermodynamic activities for both partners, this yields the familiar Henderson-Hasselbalch equation:The concentrations are at chemical equilibrium; using initial values requires negligible equilibration changes. Below, also neglect self-ionization of water and competing chemical reactions.

Stipulate $\mathrm{p}{K}_a=4.76$ for an illustrative weak acid, without identifying it with a measured substance. A conjugate base to weak acid concentration ratio of two givesEqual concentrations give a ratio of one, whose logarithm is zero, hence pH $4.76$. Multiplying the ratio by ten raises pH by one: ratios $0.1$, $1$, and $10$ give pH values $3.76$, $4.76$, and $5.76$. The ratio controls the ideal prediction, while the absolute quantities control how much added chemical acid or chemical base the buffer solution can accommodate.

The pH of a chemical solution is the negative base-ten logarithm of its hydrogen ion thermodynamic activity:The thermodynamic activity is a dimensionless quantity, so the logarithm has a dimensionless argument. The definition uses thermodynamic activity, rather than total chemical acid concentration. Single-ion thermodynamic activities require a convention; practical pH measurements are tied to calibrated standards. See IUPAC Gold Book, pH.

In a dilute ideal chemical solution in water, a useful approximation isSquare brackets denote concentration in moles per litre. In water, $[{\mathrm{H}}^{+}]$ is shorthand for the hydronium concentration, often written $[{\mathrm{H}}_3{\mathrm{O}}^{+}]$; it does not describe isolated bare protons. Departures from ideal behavior need activity coefficients. The concentration formula approximates the thermodynamic activity definition.

For an ideal strong acid supplying one proton per initial unit, stipulate a total concentration of $0.001\mathrm{mol}{\mathrm{L}}^{-1}$ and negligible self-ionization of water. Then $[{\mathrm{H}}^{+}]\approx 10^{-3}\mathrm{mol}{\mathrm{L}}^{-1}$, soReducing that concentration tenfold by dilution gives $10^{-4}\mathrm{mol}{\mathrm{L}}^{-1}$ and pH $4$, under the same assumptions. More generally, dividing the hydrogen ion thermodynamic activity by ten raises pH by one. This is why the scale compresses an enormous range: equal steps of pH represent multiplicative changes, rather than equal differences in concentration. These are model calculations, rather than measured samples.

Neutrality depends on temperature. In the dilute ideal water model, define the dimensionless ion product $K_w=([{\mathrm{H}}^{+}]/c^{\circ })([{\mathrm{OH}}^{-}]/c^{\circ })$ and $\mathrm{p}{K}_w=-{\log }_{10}{K}_w$. Equal hydronium and hydroxide concentrations implyAt $25{}^{\circ }\mathrm{C}$, the textbook approximation $K_w\approx 10^{-14}$ gives neutral pH $7$. Since $K_w$ varies with temperature, neutrality need not mean pH $7$. Nor is pH restricted to $0$–$14$: the activity definition permits negative pH when $a_{{\mathrm{H}}^{+}}>1$, and pH above $14$ when $a_{{\mathrm{H}}^{+}}<10^{-14}$. High concentrations can invalidate the dilute ideal approximation. See Flowers et al., Chemistry 2e, pH and pOH.

S. P. L. Sørensen introduced pH at the Carlsberg Laboratory in 1909, as recorded in the Carlsberg Foundation historical timeline.

A chemical base can accept a proton, using an available electron pair to form a covalent bond; more generally it can donate an electron pair to form a covalent bond with another species. See IUPAC Gold Book, base.

A chemical acid can donate a proton, or accept an electron pair to form a covalent bond. The pH and buffer solution examples below use the former meaning. See IUPAC Gold Book, acid.

The isoelectric point is the pH at which a specified molecule's mean net electric charge is zero. Different protonation states can still carry nonzero electric charges; their contributions cancel in the average. For the two-step glycine speciation model, this gives $\mathrm{pI}=(\mathrm{p}{K}_{a1}+\mathrm{p}{K}_{a2})/2$. Additional ionizable amino acid side chains require their own chemical equilibrium calculations; averaging every pKa is not a general rule. ^[ref]

Below its isoelectric point, free glycine has positive mean electric charge and an electric field drives it toward the negative electrode; above its isoelectric point, the mean electric charge is negative and the direction reverses. At its isoelectric point the charge-driven contribution vanishes. Diffusion and bulk movement of the chemical solution can still move the sample. Gel electrophoresis applies this charge dependence to separation, although protein size, shape and interactions also affect migration. The pKa values of free glycine do not determine a protein's isoelectric point: its free N-terminus, C-terminus and ionizable amino acid side chains supply a different inventory. ^[ref]

Time evolution describes the change of a physical system's state with time. A closed quantum system has unitary time evolution; dissipative dynamics need not be unitary.