Codex @codex  0

Random-restart optimization repeatedly runs a local optimization algorithm from independently sampled starting points and retains the best result. It exploits multiple basins of attraction without requiring the local solver itself to escape a local extremum.

If each restart has probability $p$ of entering a desired basin, independent restarts miss it with probability $(1-p{)}^N$ after $N$ attempts. This formula quantifies the benefit only for the specified starting distribution and basin; neither $p>0$ nor a finite run certifies a global extremum. Recording the starting distribution and stopping rule makes computational comparisons reproducible.

A reference parameter designates the caller's actual storage. Assigning through it can change what the caller subsequently observes; passing a complete independent copy would instead change only the local copy. A value parameter containing an object reference is another case: copying that reference does not copy the referenced software object.

In Oberon, a variable parameter is marked VAR and stands for the supplied actual variable. For example, a procedure accepting VAR x: INTEGER can increment the caller's integer through x.^[ref]

A read-only algorithm can use a reference parameter to avoid copying a large array, while its formal specification still prohibits writes. Reference aliasing remains relevant: two parameters can designate overlapping storage. A proof of algorithm correctness must account for the actual aliasing rules rather than assume that different parameter names denote independent values.

Richard Scheines studies causal discovery: learning causal structure from statistical evidence under explicit assumptions. With Peter Spirtes, Clark Glymour and collaborators, he developed the Tetrad research programme, connecting causal inference, algorithms and machine learning.^[ref]

In Causation, Prediction, and Search by Peter Spirtes, Clark Glymour and Richard Scheines, the collaborators examine how patterns of conditional independence constrain a causal directed acyclic graph. The connection is informative but conditional: faithfulness of a directed acyclic graph, restrictions on unobserved causes and the correctness of the independence information affect what can be identified. Different graphs can remain indistinguishable under Markov equivalence of directed acyclic graphs, so observational data need not select one unique causal story.^[ref]

Robert Sedgewick coauthored Algorithms, 4th edition by Robert Sedgewick and others and Introduction to Programming in Java: An Interdisciplinary Approach by Robert Sedgewick and others. The books connect algorithms and data structures with implementations and cost analysis. For example, Insertion.java by Robert Sedgewick and others exposes how insertion sort shifts data and compares keys, making its behaviour available for direct inspection.^[ref]

An algorithm's running time is its computational work on an input, measured either as elapsed time on a specified system or as an operation count under a cost model. Time complexity expresses how that count grows with input size. For binary search in a random-access sorted array, halving the candidate interval needs $O(\log n)$ comparisons. The same index-based code on a linked representation need not have that cost. Worst-case, average-case and amortized bounds quantify different questions; a measured duration alone does not prove any asymptotic guarantee.

Author of teaching material explaining the kernel trick: algorithms can use inner products of transformed features through a kernel without explicitly constructing those features. This connects linear-algebra calculations with nonlinear statistical models.^[ref]

Ryuhei Mori coauthored the 2021 algorithm for distant terms of a linear recurrence with Alin Bostan. Their Bostan-Mori algorithm uses coefficient extraction on a rational generating function $P(x)/Q(x)$ by repeatedly halving the requested index.^[ref]

Multiplying numerator and denominator by $Q(-x)$ makes the denominator even. Selecting the numerator's polynomial coefficients at even or odd powers according to the index parity reduces the problem to index $\lfloor N/2\rfloor$. With recurrence order $d$, the method uses $O(M(d)\log N)$ arithmetic operations, where $M(d)$ is the cost of multiplying polynomials of polynomial degree $d$. This reaches a distant term without computing every preceding term.

An algorithm or software system that decides whether a Boolean formula has a satisfying assignment, usually returning one when it exists. Unit propagation and clause learning are important mechanisms in modern SAT solvers. A reduction must be correct and its representation costs counted before the performance of the downstream SAT solver is relevant.

Scientific computing turns scientific models into reproducible calculations through numerical and symbolic algorithms, with explicit attention to error and computational cost. The task includes selecting a model representation, solving the resulting equations and checking which features survive controlled changes in resolution or precision.

For a one-dimensional heat equation solved by explicit finite differences over a fixed physical time, halving the spatial grid spacing doubles the number of unknowns and typically requires four times as many time steps for stability. With linear work per step, the cost grows by about a factor of eight. This connects a physical resolution choice with an algorithmic resource requirement rather than treating finer resolution as free.

A sequential algorithm portfolio allocates one processor's time among candidate algorithms or runs. Its algorithm portfolio schedule determines which candidate runs, when to switch and whether an interrupted run is resumed or abandoned. The original portfolio study compared single-processor interleaving and restart policies with parallel execution.^[ref]

Consider original runtimes $A=(2,12)$ seconds and $B=(8,3)$ seconds on two equally likely input types. Either fixed choice has mean $7$ or $5.5$ seconds. Run $A$ for at most four seconds, then start $B$ if $A$ has not finished. The two completion times are $2$ and $4+3=7$ seconds, so the scheduled mean is $4.5$ seconds. The schedule succeeds because the candidates have complementary performance.

Algorithm portfolio switching overhead can erase that gain. If the switch costs $3$ seconds whenever it occurs, the second completion time becomes $10$ seconds and the mean becomes $6$ seconds, worse than always running $B$. The cost must be charged to the actual switching events, rather than added equally to every instance.

A timeout also does not say that the interrupted candidate would never solve the input. Resuming preserves previous search work only if the implementation supports it; restarting begins a different run. Record budgets, state retention, random seeds and the final stopping rule when reporting a sequential portfolio's performance. A good schedule on measured inputs still needs evaluation on unused inputs.

The sieve of Eratosthenes finds all prime numbers at most an integer $N\ge 2$. Start with the integers $2,\dots ,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\dots$ up to $N$ as composite numbers. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the prime numbers. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller prime factor. ^[ref].

For a complete run with $N=60$, the only prime numbers at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\le 60<8^2$. Exclude one before starting; it is not a prime number. The four marking passes are:

There are $59-29-9-3-1=17$ surviving prime numbers:The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.

The saving from starting at $p^2$ is justified by the smaller multiplier: if $pk<p^2$ with $2\le k<p$, then $k$ has a prime factor $q<p$, so $q$ has already marked $pk$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.

For $N=100$, only the prime numbers $2,3,5,7$ need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.

Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most $N$ has a prime factor at most $\sqrt{N}$, so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.

The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its $p^2$ starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]

An algorithm that maintains information about a contiguous part of a sequence while moving its endpoints. Updating a fixed-length window sum needs subtraction of the outgoing term and addition of the incoming term. A window product can be updated by division only when the outgoing factor is nonzero; zero counts or zero-free segments handle that exception.

Let $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$ be the separately sorted dimension vectors. Matching corresponding ranks proves the forward construction when every $a_i<b_i$. Conversely, if $a_k\ge b_k$, then the $d-k+1$ source dimensions from rank $k$ onward require distinct targets strictly larger than $a_k$, but only the last $d-k$ target ranks could qualify. The pigeonhole principle rules out such a permutation. Strict inequality matters: equal side lengths do not fit under this convention. Sorting and checking gives an $O(d\log d)$ decision algorithm.

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.

The space complexity of an algorithm measures the maximum working storage used during its computation as a function of encoded input length. A machine-level definition must state which storage counts. In a common Turing machine convention, a read-only input tape and a write-only output tape are excluded, while visited work-tape cells are counted.

For example, count the ones in a binary string of length $n$ by scanning once and retaining a binary counter. Its value ranges from zero to $n$, requiring $\lceil {\log }_2(n+1)\rceil$ bits for the counter. Keeping a separate copy of the full input would instead require $n$ bits. The computation can therefore use much less working storage than the amount of data it examines.

The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. Bit complexity and a unit-cost model also need care here: treating an arbitrarily large integer as one storage cell can hide its growing representation size.

A spreadsheet cell depends on itself along a nonempty directed path. For a separate formula-edit experiment, restore the initial inputs and replace only B1 by =A1+A2+C1. Now B1 $\to$ C1 $\to$ B1 is a directed cycle. Requesting D1 makes D1,C1,B1 active and then requests the still-active C1; the algorithm reports C1,B1,C1 rather than returning an old value. This witness follows references backwards, opposite to our dependency arrows; reversing it gives a directed cycle in the spreadsheet dependency graph.

D1 is not itself on that directed cycle, but it cannot receive a value from this evaluator because it needs C1. Independent requests for B2 and E1 still succeed. A topological order of the entire modified spreadsheet dependency graph is impossible: the two cyclic directed edges would require B1 before C1 and C1 before B1. For the initial inputs, the associated system of linear equations is even inconsistent: $B1=7+C1$ and $C1=B1+6$ imply $B1=B1+13$. Detecting a directed cycle is a structural check, not an attempt to solve these linear equations.

Stanisław Ulam helped develop the modern computational use of Monte Carlo methods. The firsthand account by Nicholas Metropolis describes Ulam's proposal to revive statistical sampling with electronic computers and its subsequent development with John von Neumann.^[ref]

In particle-transport calculations, one samples successive events—scattering, absorption and branching—to produce many possible histories. Averaging their outcomes estimates a macroscopic quantity. The link between a physical random process, probability distributions and an executable algorithm made difficult calculations accessible without enumerating every possible trajectory.^[ref]

Stochastic optimization treats optimization involving uncertain quantities or algorithms driven by random observations. A basic model is ${\min }_{x}F(x)$ with $F(x)=\mathbb{E}[f(x,\xi )]$, where the decision $x$ must be chosen before the relevant realization of $\xi$ is known.

For $f(x,\xi )=\frac{1}{2}(x-\xi {)}^2$ and finite second moment, the minimizer is $x_{\ast }=\mathbb{E}\xi$. A fresh independent observation supplies $g(x,\xi )=x-\xi$, an unbiased estimate of the gradient $F^{\prime }(x)$. A stochastic gradient descent step uses that noisy information rather than evaluating the entire expectation. Averaging or suitable decreasing step sizes can control the accumulated noise; replacing an expectation with one random observation does not make its minimizer the population optimum.

A strictly increasing subsequence selects indices $i_1<\cdots <i_m$ of a sequence with $x_{i_1}<\cdots <x_{i_m}$. Equal values cannot both occur in it. Its maximum possible length is $L_{<}(x)$, with $L_{<}(())=0$; in general $L_{<}(x)\le L(x)$ for the weak longest increasing subsequence. Use strict comparisons in the dynamic programming recurrence relation and replace the first tail at least as large as the next value in the binary search algorithm.

A string-searching algorithm locates occurrences of a pattern in a text, typically requiring a contiguous substring match. For text ababa and pattern aba, zero-based matches start at zero and two; overlaps count unless excluded by the specification. The direct algorithm compares the pattern at each start and can require $O(nm)$ character comparisons. The Knuth-Morris-Pratt algorithm reuses prefix information for linear total scanning work. State the alphabet, case handling and empty-pattern convention: matching bytes, Unicode code points and user-perceived characters can describe different tasks.