Codex @codex  0

Accompanying software for Algorithms, 4th edition by Robert Sedgewick and others, authored by Robert Sedgewick and Kevin Wayne, as credited in the implementation. GitHub hosts the author repository. The footer identifies 2011 as textbook publication; no implementation publication or revision date is established.

Online source: raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/KruskalMST.java

Cited passages: class documentation lines 39–68: signed weights, ties, minimum spanning forest, union-find, sorting complexity, author tags; constructor lines 79–100: sort, representative queries, merges, n-1 stopping condition; footer lines 194–199: textbook metadata.

Online text: raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/FordFulkerson.java

Accompanying software for Algorithms, 4th edition by Robert Sedgewick and others, authored by Robert Sedgewick and Kevin Wayne, both named in the implementation bylines. GitHub hosts their algs4 repository. The footer gives 2011 as the textbook publication year; its copyright interval does not date the implementation. These locators refer to the inspected software rather than to textbook pages.

Cited passages: Lines 12–35: maximum-flow/minimum-cut purpose and explicit implementation authors.; Lines 138–177: excess computes incoming minus outgoing edge amounts; isFeasible checks capacity constraints and conservation at nonterminal vertices.; Lines 180–209: check verifies feasibility, s-in/t-out membership, forward-only cut capacity sum and equality with flow value.; Lines 246–252: copyright interval and accompanying book authors, publisher, 2011 publication year..

Online text: raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/FlowEdge.java

Accompanying software for Algorithms, 4th edition by Robert Sedgewick and others, authored by Robert Sedgewick and Kevin Wayne, both named in the implementation bylines. GitHub hosts their algs4 repository. The footer gives 2011 as the textbook publication year; its copyright interval does not date the implementation. These locators refer to the inspected software rather than to textbook pages.

Cited passages: Browser lines 0–3: class documentation, directed endpoints, real-valued capacity and flow, @author declarations.; Browser lines 4–6: constructors enforce nonnegative capacity and flow bounded between zero and capacity.; Browser lines 11–13: actual residualCapacityTo and addResidualFlowTo bodies distinguish forward capacity-minus-flow and backward flow.; Browser lines 14–16: footer credits whole-book authors, publisher and 2011 publication year..

Accompanying implementation by Robert Sedgewick and Kevin Wayne, explicitly credited by the source file’s author tags, for Algorithms, 4th edition by Robert Sedgewick and others. GitHub hosts the inspected source. The textbook publication year is 2011; no source-file publication date is established, and the copyright range is a separate date role.

Inspected source: raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/BellmanFordSP.java

Inspected locators: class documentation and author tags; constructor; relax and check methods; textbook attribution footer. This is the queue implementation.

Given a nonempty finite sequence $a=(a_0,\dots ,a_{n-1})$ of integers, return its maximum value. Represent the sequence by an array whose contents remain unchanged during execution. The precondition requires an integer length $n\ge 1$ and exact, terminating integer comparisons and variable assignments. The postcondition for returned value $r$ isThus the output belongs to the finite set of entries and is at least every entry. The contract permits ties and negative integers; it asks for a value, not the position of a particular occurrence. There is no maximum of an empty set of integers, so empty input is deliberately outside this precondition. A service accepting empty inputs needs a different formal specification, such as a separate absent result.

This Python implementation makes the variable assignments explicit. Its index arithmetic models exact integer arithmetic; fixed-width implementations additionally need enough index range for $n$:For the original input $[3,1,4,4,2]$, initialization gives $k=1$ and $\mathrm{best}=3$. Reading $a_1=1$ keeps $3$; reading $a_2=4$ changes it to $4$; reading $a_3=4$ and $a_4=2$ keeps $4$. At successive condition checks, the pairs $(k,\mathrm{best})$ are $(1,3),(2,3),(3,4),(4,4),(5,4)$. The returned maximum is $4$.

At each condition check, use the loop invarianttogether with the fact that the input array is unchanged. The prefix is the first $k$ entries of the sequence, so its finite set of values is nonempty. The maximum need not be unique as an occurrence: the invariant concerns its value.

Initialization establishes $I$: $k=1$ and $\mathrm{best}=a_0$, the maximum of a one-element set. For preservation, suppose $I$ and $k<n$ hold. Then $a_k$ is a valid array entry. Either the comparison replaces $\mathrm{best}$ with the larger value $a_k$, or it keeps a value at least $a_k$. Before increasing $k$, the resulting value isThe variable assignment $k\leftarrow k+1$ restores the complete loop invariant. Between the two variable assignments, the old prefix formula may temporarily be false; the loop invariant is required at condition checks, not at every instruction.

At exit, $k\ge n$, while $I$ gives $k\le n$. Hence $k=n$, and $I$ gives exactly the required postcondition. This establishes partial correctness. The preservation argument is mathematical induction on the number of completed iterations, covering every permitted integer sequence, rather than just the pictured input.

For algorithm termination, the loop variant $V=n-k$ is a nonnegative integer whenever $I$ holds. If $k<n$, then $V\ge 1$. Every body terminates under the precondition and changes $V$ to $V-1$. Starting at $n-1$, it reaches zero after exactly $n-1$ iterations. For $n=1$, the initial value is already zero and the body is never entered. Together with partial correctness, this proves total correctness.

Starting $\mathrm{best}$ at zero instead of $a_0$ fails on the original negative input $[-7,-3,-3,-8]$: it returns zero, which is neither an entry nor the maximum $-3$. Keeping $k=1$ forever preserves the correct initial prefix claim but loops forever when $n>1$; a loop invariant alone does not ensure algorithm termination. Using >= instead of > still returns the same maximum value when entries tie, although a version returning a position would need an explicit tie rule.

Total correctness requires partial correctness and algorithm termination for every program state allowed by the precondition. For a deterministic sequential program, every permitted start must reach a final program state satisfying the postcondition after finitely many steps. Thus an infinite execution can satisfy partial correctness, but refutes total correctness for a permitted start.

In the summation loop verification, the loop invariant establishes the answer conditional on exit, and the loop variant establishes exit. Both parts matter: replacing the body by a step that never returns would defeat total correctness even if every completed iteration preserved the loop invariant. Likewise, a terminating loop with the wrong sum fails partial correctness and therefore fails total correctness.

These obligations depend on the formal specification. A program that rejects every input might correctly implement a rejection service, but does not meet a contract promising a sum for every nonnegative integer. A proof of total correctness also gives no particular physical response-time guarantee: time complexity and the execution environment require their own assumptions.

Partial correctness means that every terminating execution begun in a program state satisfying the precondition $P$ finishes in a program state satisfying the postcondition $Q$. For a sequential program $C$, the usual Hoare triple notation isHere the notation expresses partial correctness; it makes no promise that $C$ finishes. The precondition and postcondition describe permitted starting circumstances and required final circumstances, rather than tests performed automatically by the program.^[ref]

For a sharp example, take the precondition $n=4$ and the following sequential program over mathematical integers:The condition remains true, so execution never reaches the instruction after the loop. Consequently its partial correctness claim holds for the postcondition $2s=n(n+1)$, and even for the impossible postcondition $0=1$: there is no terminating execution with a wrong final result. This is vacuous truth, not evidence that the loop computes a sum. The same program fails total correctness for this permitted input.

The distinction is useful in a proof: first show that an answer, whenever produced, is right; then establish algorithm termination. The summation loop verification supplies both arguments for a loop that actually progresses. Its finite trace illustrates one execution, while its loop invariant covers every permitted input.

Lecture note in Algebraic Techniques and Semidefinite Optimization, MIT 6.972, Spring 2006. The printed heading is Lecture 6; Resultants and Discriminants is a descriptive subject title. The heading credits Pablo A. Parrilo as lecturer and leaves the scribe unidentified. No individual authorship or editing credit is inferred. The Massachusetts Institute of Technology issues the course material; MIT OpenCourseWare hosts this copy.

Lecture PDF: ocw.mit.edu/courses/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/46bf636ecc6195991e396703bfe1a1ae_lecture_06.pdf

Cited passages: printed pp. 6–1 to 6–2, §1 Resultants, Sylvester matrix and equation (1); printed p. 6–2, §2 Discriminants, Definition 2; printed p. 6–3, §3.1 Polynomial equations, elimination and backsubstitution. The printed date is the lecture date; no separate online publication or revision date is established.

Algebraic notation represents variables, coefficients and algebraic operations by written symbols, so one expression can describe a family of equations.

A gel electrophoresis size calibration relates migration distance to known fragment lengths on the same gel. Here is an explicitly chosen model for linear double-stranded DNA, not measured data or a universal law. Let $L$ be the numerical length in base pairs and $d$ the numerical migration distance in millimetres from the wells:The logarithm has a dimensionless argument: $L/100$ is the length divided by 100 base pairs. The chosen DNA ladder fragments $L=100,250,500,1000$ give $d=55.00,50.22,46.61,43.00$, respectively. The gel bands therefore appear in the reverse order of length along the direction of migration.

To invert the calibration, rearrange the logarithm:Our chosen unknown $L=375$ gives $d=48.1116248\dots$, between the 250-base pair and 500-base pair references. Inserting that distance into the inverse recovers 375; retaining only $d=48.11$ gives about $375.12$ base pairs. The extra digits reflect rounding in this model, not the resolving power of a real gel.

For linear interpolation between those two reference gel bands, use the logarithm of length. Here the fraction of the distance from the 500-base pair reference toward the 250-base pair reference is $t={\log }_{10}(500/375)/{\log }_{10}2\approx 0.4150$, giving $L=500(250/500{)}^t=375$. Direct linear interpolation of lengths instead gives approximately $396.24$ base pairs. This difference explains why the choice of calibration coordinates matters. A real calibration must be checked over its usable range; folded RNA or circular DNA does not automatically share the linear double-stranded DNA calibration.

A DNA ladder contains DNA fragments of known lengths in base pairs. Its gel bands supply size references. Match the sample's strandedness and shape, and use the specified lengths for that DNA ladder. A size reference need not provide a quantitative mass standard.^[ref]

In 1918, Irving Langmuir measured adsorption using freshly split mica strips, handled at their edges, separated by iron spacers and held with brass fasteners. A glass bulb contained the bundle; a similar blank contained matching iron and brass but no mica. Evacuated glass connections, Mercury seals, liquid air traps, and McLeod gauges provided controlled gas handling. Calibrated compartment volumes and pressure readings before and after expansion gave free-gas amounts; their deficit indicated uptake. Lowering pressure and measuring released gas tested desorption.^[ref]

Hydrogen blank runs calibrated cooling-related pressure differences. Irving Langmuir pre-cooled the bulbs to reduce thermal delay; he suggested slow diffusion between strips could control the remaining approach to equilibrium. Critically, blank uptake was not subtracted: he estimated the mica-bulb results were 10–30% too high. Liquid air temperature drift was unrecorded. These limits constrain inference of intrinsic binding from the uptake curve. The paper's pressure unit called “bar” was $1\mathrm{dyn}\mathrm{c}{\mathrm{m}}^{-2}=0.1\mathrm{Pa}$, unlike the modern bar used above.^[ref]

An adsorption isotherm relates equilibrium uptake to surrounding pressure or concentration at fixed temperature. For a gas, specify the partial pressure of the adsorbing chemical species. An uptake trace during incomplete equilibration need not be an adsorption isotherm.

Desorption releases material previously retained at a boundary. At chemical equilibrium, adsorption and desorption can both continue while their mean rates balance.

A monolayer is a single layer of chemical atoms or molecules. In the Langmuir adsorption model, a complete monolayer occupies every adsorption site; partial surface coverage leaves vacancies within that first layer. One layer need not mean one molecule per surface chemical atom.

An adsorption site is a position or local environment at which a chemical species can be retained at a boundary. Treating all adsorption sites as identical is an assumption about their binding properties, not a definition of adsorption.

The interfacial excess of a species relative to bulk reference phases extrapolated up to a chosen reference surface. An excess number density per area is denoted $\Gamma$; its molar counterpart is $\Gamma /N_A$. When an interface is dominated by a molecular layer, an effective area per adsorbed molecule is $\Sigma =1/\Gamma$. The reference-surface convention matters in multicomponent systems.