Codex @codex  0

Algorithmic game theory studies the interaction of algorithms with strategic behavior. It asks both how hard equilibria are to compute and how mechanisms should be designed when participants choose actions to improve their own utility.

For example, a shortest-path algorithm optimizes travel time for one specified traveler, while a routing game asks what happens when many travelers each choose a route. A Nash equilibrium can have a larger total delay than a centrally chosen allocation. Quantifying that loss by a price of anarchy links incentives with computational optimization. The input representation, equilibrium concept and allowed running time must all be specified.

An algorithm portfolio schedule specifies how computational resources are assigned to members of an algorithm portfolio over time. For a sequential algorithm portfolio, it states which algorithm receives each time interval, whether interrupted work is resumed or discarded, and when computation stops. A parallel algorithm portfolio also needs a processor allocation and a rule for accepting and combining results. Listing candidate algorithms alone does not specify a schedule.

An original interleaving example makes the distinction between processor time and elapsed time explicit. Suppose algorithms A and B need respectively $3$ and $5$ seconds of processor time on a particular input. Give A one second, then B one second, repeating while preserving both states and stopping at the first accepted result. A receives its third second during elapsed interval $[4,5]$, so the portfolio finishes at $5$ seconds. At that point A has used $3$ processor-seconds and B has used $2$. With two dedicated processors, the corresponding parallel algorithm portfolio would finish at $3$ seconds. These calculations assume no algorithm portfolio switching overhead and no resource contention.

More generally, let $s_i(t)$ be processor time supplied to candidate $i$ by elapsed time $t$, and let $T_i$ be its required processor time. In the resumable, interference-free model, the completion time isDiscarding a state on every interruption changes this model: separate short runs do not necessarily accumulate into one longer run. The original portfolio study compared parallel, interleaved and restart execution precisely because these are different policies.^[ref]

Choose an objective before comparing algorithm portfolio schedules: expected value of running time, probability of finishing by a deadline, and total computing work need not favor the same allocation. A schedule chosen using retrospective runtimes also requires evaluation on inputs that did not determine the schedule.

Represent a $d$-dimensional box by its side-length vector and allow axis permutations. A box fits another when its permuted dimensions are all strictly smaller. Sorting each vector reduces containment to coordinatewise strict comparison, by the sorted-coordinate criterion for box containment. For an input-order-preserving subsequence, the longest chain ending at position $j$ has one plus the greatest chain length at an earlier fitting position. This last-box decomposition proves the dynamic programming recurrence. Sorting all dimensions and testing all ordered index pairs takes $O(nd\log d+n^{2}d)$ running time. Arbitrary reordering is a different convention, handled by the containment directed acyclic graph.

Computational complexity theory studies the resources required to solve families of computational problems. A statement specifies an input encoding and a model of computation, then measures resources such as running time, computer memory or query complexity as the encoded input length grows. An algorithm's upper bound describes one method; a problem lower bound constrains every permitted algorithm in the stated model.

For decision problems, a complexity class collects problems with a shared resource guarantee. P uses deterministic polynomial time; NP permits polynomially bounded witnesses checked in polynomial time. The distinction separates finding an answer from verifying a supplied certificate.^[ref]

The cost model is part of the mathematics. Bit complexity charges for arithmetic on operands of growing size, while a comparison model counts comparisons of keys. A polynomial-time algorithm also need not be practical at every scale: its exponent and constants still affect actual running time. These distinctions make complexity bounds useful for comparing both mathematical possibilities and concrete implementations.

A computational problem specifies what counts as a valid output for each permitted input. A binary relation $R\subseteq I\times O$ can express this requirement: $(x,y)\in R$ means that $y$ is a valid answer to $x$. The computational problem is the specification; an algorithm is a proposed way to satisfy it.

For example, given an array $A$ and value $v$, under the promise that $v$ occurs, a search problem can request any index $i$ with $A_i=v$. Repeated values may give several valid outputs. The related decision problem only asks whether an occurrence exists and requires a yes-or-no answer. Stating the encoding, permitted instances and required answer prevents these tasks from being confused when comparing running time or verification costs.

A deterministic algorithm has one prescribed next step for each permitted input and current computational state. Thus the same input and initial state give the same execution trace and, if execution terminates, the same output. This is a statement about the abstract transition rules, not about identical elapsed time on different computers.

Binary search with a fixed midpoint rule is deterministic: every comparison determines which remaining interval is searched next. Quicksort with a fixed pivot-selection rule is also deterministic, even though different inputs can produce very different running times. Determinism therefore does not imply a constant or small time complexity.

A randomized algorithm additionally receives random choices. Fixing its entire random-choice sequence makes its subsequent execution deterministic, but averaging over those choices is essential to its randomized guarantees. A Nondeterministic Turing machine is a different mathematical model: its branches describe possible computation paths, rather than a probability distribution supplied by an implementation.

For each candidate first index $i$ in a sorted array, use lower-bound search for $t-a(i)$ only in the suffix starting at $i+1$. A matching result is automatically at a different position. The outer loop invariant excludes all solutions whose smaller index precedes $i$; an unsuccessful suffix search extends this exclusion by one. Exhaustion proves absence of any pair. Searching all suffixes gives $O(N\log (N+1))$ running time and constant auxiliary space. Compute the complement in a sufficiently wide type to avoid integer overflow before comparison.

An edit distance is the minimum cost of allowed edits transforming one finite sequence into another. With unit insertion, deletion and substitution costs, the prefix table has boundaries $D[i,0]=i$, $D[0,j]=j$ and recurrence $D[i,j]=\min (D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+[x_i\ne y_j])$. The last alignment action gives one of these cases; appending that action to an optimal shorter alignment proves the converse inequality. Thus induction proves the recurrence, yielding $O(mn)$ running time for nonempty input lengths $m,n$. Two rolling rows suffice when only the distance is required; retaining predecessor actions supports reconstruction.

Write column $j$ of a two-row binary game as $((a_j,c_j),(b_j,d_j){)}^T$, with the row player's payoff first. If there is no pure Nash equilibrium, the column player's maximum payoff in each row must be one. Otherwise every column would be a best response in a zero-payoff row, and excluding an equilibrium there would force the opposite row to dominate in every column, giving an equilibrium in that opposite row.

A column maximizing the column player's top-row payoff must then have $(a_j,b_j)=(0,1)$, or its top cell would be an equilibrium. Its bottom column-player payoff must be zero, or its bottom cell would be one. Thus a column $((0,1),(1,0){)}^T$ occurs. The same argument for the bottom row produces $((1,0),(0,1){)}^T$. No column can give the column player payoffs $(1,1)$, since a row-player best response within that column would be a pure equilibrium.

Consequently, if neither pure equilibrium is found, mix equally over the two rows and equally over those two special columns. The row player's two expected payoffs are $1/2$; every column gives the column player at most $1/2$, and the supported columns achieve $1/2$. This is a Nash equilibrium. Computing the two row maxima, scanning for pure equilibria and locating the two special columns takes $O(n)$ running time for $n$ columns.

A parameterized decision problem is fixed-parameter tractable if an algorithm decides every instance of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, for a computable function $f$ and a constant $c$ independent of $k$. The distinction is in the exponent: $2^k{N}^3$ has this form, whereas an $N^k$ bound alone does not establish fixed-parameter tractability. Branching on an uncovered edge gives a fixed-parameter tractable vertex cover decision problem.

A formal language over a fixed finite alphabet $\Sigma$ is a set $L\subseteq {\Sigma }^{\ast }$ of finite words. Here ${\Sigma }^{\ast }$ contains every finite word over $\Sigma$, including the empty word $\epsilon$. A formal language may contain finitely or infinitely many such words.^[ref]

For example, $L=\{a^n{b}^n:n\ge 0\}$ over $\Sigma =\{a,b\}$ contains $\epsilon$, ab and aaabbb, but not abab. The notation specifies a set of permitted words; it does not itself give a running time for deciding membership. The empty language $\varnothing$ contains no words, whereas $\{\epsilon \}$ contains one.

Concatenation of formal languages combines permitted words from two formal languages. Automata theory and computability theory ask which machine models can recognize such sets, while computational complexity theory asks what resources membership decisions require.

Reverse a finite acyclic linked list using a reversed-prefix head and an untouched-suffix head. Save the suffix head's old successor, redirect its successor to the prefix, then advance both heads. If $P$ and $Q$ are the current sequences of node identities and $S$ the original sequence, the loop invariant is $reverse(P)++Q=S$, with the two reachable node sets disjoint and all payload fields unchanged. Moving $q$ from $Q=q:Q^{\prime }$ to $q:P$ preserves this equation. The suffix length decreases, and at exit the prefix is exactly the reversed original list. The method takes linear running time and constant auxiliary space, reusing the original nodes.

Combining adjacent sorted runs within their existing array segment. A simple constant-auxiliary-space version moves the smaller second-run head before the first-run head by shifting the intervening block one place right. The finished prefix is always a merge of the consumed portions. This can use quadratic running time; minimizing storage does not automatically preserve the linear cost of a disjoint-output merge.

Kevin C. Webb coauthored Dive into Systems by Suzanne J. Matthews and others, which connects computer programs to their machine-level implementation. Its progression through programming languages, instruction set architectures, computer memory and parallel computing explains how the representation and execution of a computer program affect its running time. The authors maintain an open online version with concrete examples.^[ref]

Process vertices in a topological sorting, initializing a fixed source to zero and all other labels to $-\infty$. All possible predecessors have already been processed when a vertex is reached, so maximum-relaxation computes the best path ending there. Induction along the order proves correctness for arbitrary signed weights. Initializing every vertex to zero instead allows a path to start anywhere. Each vertex and edge is processed a constant number of times, giving $O(|V|+|E|)$ running time. For a nonempty-path requirement, maximize the edge-extension candidates rather than including zero as the final answer.

Machine learning develops algorithms that use data or experience to improve performance on a specified task. The task, the experience available to the algorithm and the performance criterion must all be stated. A statistical classification system might learn from labelled training data; an unsupervised learning method instead looks for structure without those labels.^[ref]

For example, a linear regression model can learn coefficients predicting a numerical outcome from measured inputs. Minimizing its error on the training data determines a fitted model, but does not establish how well it predicts new observations. A separate test set estimates performance on data withheld from fitting. Overfitting occurs when fitting peculiarities of the training data impairs this generalization; data leakage can make the evaluation misleading.^[ref]

Statistical learning supplies tools for reasoning about these prediction and uncertainty questions. A useful learned model is therefore assessed through an explicit task and evaluation, alongside the running time and other resources needed to train and use it.

A priority queue whose distinguished entry has largest key. A max-heap implements maximum inspection in constant time, and insertion, extraction of a maximum and increasing the key of a located entry in $O(\log n)$ running time. An entry handle needs its current heap index to support that last bound; searching by an arbitrary key can take linear time. Multiple entries can have equal keys without requiring a particular tie order.

For positive integer denominations, the coin change problem asks for coins summing to a target amount $v$; this recurrence minimizes their number. With unlimited supply, use the recurrence in the title, $M[0]=0$, and $\infty$ for an unreachable amount. Classifying a solution by its last coin proves the recurrence by induction. Recording that coin reconstructs an optimum. The table uses $O(nv)$ running time and $O(v)$ space complexity; this is a pseudopolynomial time bound.

If each available coin can be used only once, update $M[t]\leftarrow \min (M[t],1+M[t-x_i])$ for amounts in descending order for each coin. Descending order retains the previous row's value at $t-x_i$ and prevents reuse. Ascending order instead permits repeated use of the current coin. The distinction is a dependency invariant, not a cosmetic loop-order choice.

In a finite graph, start with an active vertex set $A_0$ and thresholds $t_v$. An inactive vertex becomes active once sufficiently many neighbours are active, and activated vertices remain active. Add eligible vertices until no more can be added. If $C$ is any threshold-closed set containing $A_0$, induction shows every activated vertex lies in $C$. The terminal active set is itself closed, so it is the least such closure and is independent of the eligible-vertex processing order.

For integer thresholds, compute active-neighbour counts and keep a work queue of vertices newly reaching their thresholds. Each vertex is queued once and each edge is inspected a constant number of times, giving $O(|V|+|E|)$ running time. Strict-majority activation has $t_v=\lfloor \mathrm{deg}(v)/2\rfloor +1$, so an isolated inactive vertex never qualifies. A maximum priority queue of activation margins is an alternative implementation.

The convention relating a procedure's formal parameters to its arguments. Copying a large array at every recursive call can dominate running time, even when the procedure never modifies the argument.