Codex @codex  0

A graph algorithm computes a property of a graph or constructs a related object from its graph vertices and graph edges. The input representation matters: an adjacency list lets an algorithm inspect the neighbours of one graph vertex without scanning every possible pair of graph vertices, whereas an adjacency matrix provides direct tests for individual graph edges.

For example, breadth-first search finds every graph vertex reachable from a starting graph vertex $s$. Mark $s$, place it in a FIFO queue, then repeatedly remove the oldest marked graph vertex and mark/enqueue each previously unmarked neighbour. A graph vertex is enqueued at most once, so scanning adjacency lists costs $O(|V|+|E|)$. The FIFO queue processes distance layers in order; the first discovery of a graph vertex supplies a shortest graph path in an unweighted graph.

For graph edges $a\to b$, $a\to c$, $b\to d$, starting at $a$ discovers $b,c$ before $d$, with distances $0,1,1,2$. The same graph can support different questions: depth-first search investigates traversal structure, Dijkstra's algorithm uses nonnegative edge weights for shortest graph paths, and a minimum spanning tree minimizes the total weight needed to connect an undirected graph. Matching the algorithm to its assumptions is part of modelling the problem.

A greedy algorithm builds a feasible solution by repeatedly committing to a locally preferred next choice. Each commitment is final: the algorithm does not revisit it when later choices become available. In mathematical optimization, the important question is whether those commitments can still attain the best objective function value.

For example, a shared telescope can accept several observation requests with fixed time slots. In interval scheduling, every completed request counts equally, and overlapping requests cannot both be accepted. Choosing the request that finishes earliest leaves the resource available sooner. The example below turns that intuition into a precise rule, then shows why choosing the earliest start or shortest duration can lose jobs.

Greedy algorithms are attractive because a single pass can replace a search through many candidate subsets. However, "locally best" is only a design proposal. A problem-specific greedy-choice property, often established by an exchange argument, must connect the local decision to the actual objective function. The largest-individual-value rule in the 0-1 knapsack problem fails; Dijkstra's algorithm needs its nonnegative-edge assumptions. A rule's success in one optimization task does not justify it in another.

Coauthor with Matt Pharr and Wenzel Jakob of a textbook on physically based rendering, connecting computer graphics algorithms with models of light transport.^[ref]

The halting set is computably enumerable but undecidable, and its complement is not computably enumerable.

Harry Buhrman coauthored Complexity Measures and Decision Tree Complexity: A Survey by Harry Buhrman and Ronald de Wolf. The survey relates measures of Boolean-function complexity, including deterministic and randomized decision-tree queries, certificate size and quantum query complexity. These comparisons separate how a function is represented from how much information an algorithm must inspect to compute it.^[ref]

Herbert Edelsbrunner develops algorithms for computational geometry and computational topology. His research account describes a progression from data structures and geometry to topological methods, guided by applications.^[ref] He coauthored Computational Topology: An Introduction by Herbert Edelsbrunner and John L. Harer with John L. Harer.^[ref]

A central computational challenge is to replace a continuous shape by finite combinatorial data while preserving the invariant being studied. For example, a triangulated surface can be described by vertices, edges and faces, allowing homology to be computed from boundary relations. The representation supplies an algorithmic route to a geometric question; the quality of the input model remains part of interpreting the answer.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

An increasing subsequence of a finite sequence $x=(x_1,\dots ,x_n)$ in a totally ordered set selects indices $1\le i_1<\cdots <i_m\le n$ such thatHere “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of ^[ref]. A strictly increasing subsequence instead requires $x_{i_1}<\cdots <x_{i_m}$. Always check which convention an algorithm uses, especially when values repeat.

An increasing subsequence may skip positions; it neither rearranges values nor requires consecutive positions. Consider the deliberately constructed exampleThe indices $(2,4,5,6)$ select $(1,2,2,5)$, an increasing subsequence of length four. The indices $(2,3,6)$ select $(1,3,5)$, a strictly increasing subsequence of length three. In contrast, $(0,1,2,2,3,4,5)$ rearranges the input and is not a subsequence. The longest consecutive nondecreasing block is $(2,2,5)$, of length three; requiring consecutive positions would therefore solve a different problem.

Think of an increasing subsequence as preserving ordered observations while skipping interruptions. For the example, discarding $4,3,0$ leaves four observations with no downward step. The longest increasing subsequence asks how much of the original order can be kept. This is an order comparison, rather than a claim about the size of upward or downward changes: replacing all values by their squares when the values are nonnegative leaves every allowed selection unchanged. More generally, any strictly order-preserving relabeling has this property.

Information retrieval finds material relevant to an information need within a collection, commonly documents or passages. A query expresses part of that need; a retrieval system selects or ranks candidate material. Relevance is therefore part of the task, beyond simply checking whether a stored identifier matches.^[ref]

For example, suppose a query returns five documents, three relevant, while the collection contains six relevant documents altogether. Its precision is $3/5$, while its recall is $3/6$. Returning everything increases coverage but can overwhelm the user with irrelevant material. An inverted index accelerates term lookup; scoring and evaluation address which retrieved results are useful. Information retrieval consequently combines data structures, ranking algorithms and evidence about the user's task.

Insertion sort grows a sorted prefix of an array one entry at a time. In the adjacent-swap version, start with position $i=1$, compare its current sort key with the preceding sort key, and swap the complete sorting records only when the right sort key is strictly smaller. Continue leftward until no swap is needed or the entry reaches position zero; then process original position $i+1$. A tie stops the pass. This is the strict comparison and exchange rule in the authored implementation.^[ref]

Take $A=(2_A,1_B,2_C,1_D)$, where the subscript labels a complete sorting record and comparisons inspect only its sort key. Starting from index zero, the complete key-comparison trace is:

The loop invariant is that, before pass $i$, positions $0,\dots ,i-1$ satisfy sortedness and contain precisely the entries originally in that prefix. Moving the next entry left through strictly larger sort keys extends that prefix, and every swap retains sorting permutation preservation. Equal-key entries never cross, giving stable sorting. Each leftward step decreases the position, and each completed pass increases the prefix length, so the algorithm terminates.

With constant-cost key comparisons and swaps, reverse-ordered distinct sort keys cause $1+2+\cdots +(n-1)=n(n-1)/2$ comparisons and swaps. Thus worst-case time complexity is $O(n^2)$ in Big O notation. An already sorted array needs only $n-1$ key comparisons for $n\ge 1$ and no swaps. The adjacent-swap version uses constant auxiliary space complexity. Small or nearly sorted arrays can therefore make insertion sort useful despite its quadratic worst case.

Given a finite set of jobs with fixed half-open intervals $[s_i,f_i)$, where $s_i<f_i$, choose a subset $S$ of maximum cardinality. Each job occupies one shared resource throughout its interval. A feasible solution has pairwise disjoint intervals: for distinct selected jobs $i,j$, either $f_i\le s_j$ or $f_j\le s_i$. Thus a finish and the next start may coincide. Every job has value one; occupied time is not the objective function.^[ref]

Consider these six original jobs, with arbitrary time units:Job $B=[1,3)$ can be followed immediately by $C=[3,5)$ and $D=[5,7)$. Job $A=[0,6)$ conflicts with all three. Starting the resource earlier is therefore not automatically beneficial: one long commitment can displace several shorter requests.

The earliest-finish greedy algorithm uses a sorting algorithm to put jobs in nondecreasing finish time. Scan that order, accepting the first job and then each job whose start is at least the last accepted finish. Break finish-time ties arbitrarily; an empty input returns the empty set. For these jobs, the order and decisions areAfter $B,C$, job $A$ starts before the current finish five and is rejected. Accept $D$; then reject $E=[6,9)$ because six is before seven. Finally accept $F=[8,10)$. The result is $S=\{B,C,D,F\}$, with cardinality four. Leaving $[0,1)$ idle makes room for more jobs.

By contrast, the earliest-start rule scans $A,B,C,D,E,F$. It accepts $A$, skips $B,C,D$, accepts $E$, and skips $F$. Its feasible solution $\{A,E\}$ contains only two jobs. Here $A$ and $E$ meet at time six and are compatible; $E$ and $F$ overlap on $[8,9)$.

There is also an elementary optimality certificate for this example. The four subsets $\{A,B\}$, $\{C\}$, $\{D,E\}$ and $\{F\}$ form a partition of a set of the jobs. A feasible solution takes at most one job from each group: $A,B$ overlap, as do $D,E$, and each other group is a singleton. Hence four is an upper bound, attained by $\{B,C,D,F\}$. Checking all $2^6=64$ subsets gives a unique optimum of size four: $\{B,C,D,F\}$.

The earliest-finish theorem states that this greedy algorithm maximizes job count for every finite instance of interval scheduling. For the exchange argument, let $q$ be the first job in an optimal feasible solution and $g$ an earliest-finishing job. Every later selected job $j$ satisfiesReplace $q$ by $g$; compatibility and cardinality survive. The remainder must be optimal among jobs starting at or after $f_g$, or improving it would improve the whole selection. Mathematical induction on the smaller remaining instance, starting with the empty set, completes the outline.^[ref]

Why is the algorithm fast? Once sorted, each job is examined once, using only the last accepted finish to decide compatibility. The scan takes $O(n)$ time; comparison sorting algorithms give total time complexity $O(n\log n)$ for $n\ge 2$, in Big O notation, assuming constant-cost endpoint comparisons. Already sorted input needs only the $O(n)$ scan.^[ref]

The reason the shortcut is correct is stronger than "finishing sooner looks good": the exchange argument preserves every later job of a suitable optimum. This is the problem-specific fact that permits final decisions without exploring all subsets.

For the displayed Ackermann function convention, one possible inverse-growth scale is $\alpha (n)=\min \{m\ge 1:A(m,m)\ge n\}$ for positive integers $n$. It gives $\alpha (n)=1$ through $3$, $2$ from $4$ through $7$, and $3$ from $8$ through $61$. Several inverse Ackermann function conventions occur in algorithm analysis; changing convention can shift these small values without changing the very slow growth relevant to the disjoint-set data structure. This inverse-growth definition does not invert a two-variable function as an ordinary one-variable inverse function.

J. A. Robinson introduced the resolution principle in his 1965 paper on machine-oriented logic. His clause-based resolution calculus, using unification, supports a complete refutation procedure for first-order logic: an unsatisfiable clause set has a derivation of the empty clause.^[ref]

For example, resolving $P(x)\vee Q(x)$ with $\neg P(a)$ uses the first-order substitution $x\mapsto a$ and produces $Q(a)$. The rule separates the logical justification of a step from the search for useful clauses. A complete search procedure can still run indefinitely on a satisfiable input; completeness does not supply a decision algorithm for all first-order logic.

Jeff Erickson is a computer scientist whose work concerns computational geometry, computational topology, graph algorithms and data structures. His research also examines how students learn to design algorithms.^[ref]

His open textbook Algorithms by Jeff Erickson develops algorithm design through explicit examples, proofs and analysis. Its treatments of dynamic programming and depth-first search show complementary organizing ideas: reuse results of smaller subproblems, or explore the structure of a graph. The explanations connect the procedure with the invariant or recurrence that justifies it.^[ref]

Homepage: jeffe.cs.illinois.edu/

Jeffrey Shallit studies combinatorics on words, formal languages, automata theory and algorithmic number theory. His work connects finite descriptions of sequences with arithmetic structure and algorithms for deciding properties of those sequences.

His personal page gives a useful caution about experimentation: an apparently valid linear recurrence for one integer sequence fails only at index 11056. Long numerical agreement can motivate a conjecture, but a mathematical proof needs a structural reason that the identity continues indefinitely.^[ref]

Jiří Matoušek was a mathematician whose research and exposition connected discrete geometry, combinatorics, topology and theoretical computer science. His books and notes made geometric and topological methods accessible for discrete problems, including bounds for graph coloring and the design of algorithms.^[ref] His account of applications of topology emphasizes a productive change of viewpoint: a finite combinatorial question can be encoded by a continuous space, where a topological obstruction forces the desired conclusion.^[ref] This approach lets qualitative information about continuity and symmetry produce exact conclusions about discrete objects.

Joe Sawada studies combinatorial generation: efficient ways to list all objects in a specified family. His author homepage highlights Gray codes, where consecutive objects differ by a small change, and De Bruijn sequences, which encode many short words through overlapping windows. These viewpoints make the order of generation part of an algorithm's design.^[ref]

Jonas Almström Duregård is a computer scientist and a coeditor, with Peter Ljunglöf and Alex Gerdes, of Data Structures and Algorithms edited by Peter Ljunglöf and others. The book connects data structures with algorithms that operate on them, including linked lists, dynamic arrays and binary trees. Its organization illustrates the distinction between an interface's promised operations and the representation used to implement them.^[ref]

Homepage: www.chalmers.se/en/persons/almstroj/

Jonathan Richard Shewchuk developed adaptive exact arithmetic methods for robust computational geometry predicates. Orientation and incircle tests depend on the sign of a determinant; an incorrectly rounded sign near zero can corrupt the geometric decisions of an algorithm. His method spends additional precision only when needed to establish the correct sign.^[ref]

For example, three nearly collinear points may give an orientation determinant extremely close to zero even when their coordinates are individually unexceptional. A fast approximate evaluation can resolve an easy case, while a difficult case triggers more exact work. This connects numerical accuracy to a discrete geometric decision, not merely to the number of printed decimal places.

Homepage: people.eecs.berkeley.edu/~jrs/

A summation algorithm that keeps a correction for low-order information lost when adding floating-point numbers. Feeding that correction into subsequent additions can greatly reduce accumulated rounding error compared with straightforward summation.