A priority queue stores items with comparable priority keys and supports insertion, inspection of a best-priority item, and removal of a best-priority item. Here we use the minimum convention: keys have a total order, and smaller means earlier. The operation peek returns a stored item of minimum priority without removing it; extract-min removes and returns such an item. Both require a nonempty priority queue, or an explicitly specified empty-case result. A maximum-oriented priority queue reverses the choice.

For the requests $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, peek returns Bo and leaves all three requests stored. extract-min returns Bo and leaves Ada and Cy; another peek returns Cy. Inserting $(1,\mathrm{Dee})$ now makes Dee the next request selected. This changing collection need not be a sorted array: only the next choice must be available.

Distinct items may share a priority. Inserting $(2,\mathrm{Eli})$ alongside $(2,\mathrm{Bo})$ permits either item to be removed first. A priority queue does not inherently promise arrival order on ties. If that policy matters, compare priority first and a unique increasing arrival number second; the resulting total order makes earlier arrivals win equal-priority ties. This is analogous to the motivation for stable sorting, but it is an extra policy for the priority queue.

The interface specifies behavior; the data structure determines costs. A binary heap implements a priority queue with constant-time peek and logarithmic-time insertion and extract-min, under the cost assumptions below. Scheduling by urgency or by the time of the next event needs exactly this repeated next-item selection. MIT's notes use these applications to motivate the priority queue interface.^[ref]

An adjacency list represents a graph by keeping, for each vertex $v$, a collection $\mathrm{Adj}[v]$ of the vertices reached by its outgoing edges. An array indexed by vertex identifiers can locate each collection; the collection itself may use a linked list or an array. In an undirected graph, each nonloop edge supplies an entry at both endpoints.^[ref]

For a worked example, take the simple graphwhere $AB$ denotes the unordered pair $\{A,B\}$. Its adjacency lists, displayed in label order, areThus $C$ has three neighbours, although the graph has six vertices. Its list contains exactly the destinations available for a single step from $C$; no slots are reserved there for $C,E,F$. The fourteen neighbour entries represent seven edges, with $CD$ appearing as $D$ in $C$'s list and as $C$ in $D$'s list. The label order makes the example easy to read; an adjacency list need not be sorted.

The useful idea is to store existing connections explicitly. Neighbour enumeration can then follow exactly the possible next steps, which is what breadth-first search and depth-first search need. In a sparse graph, most pairs of vertices have no edge; adjacency lists avoid reserving a separate adjacency matrix entry for every such absence. Whether this saves work depends on the question: neighbour enumeration and testing one proposed edge have different costs.

Image compression applies data compression to pictures, usually represented by raster images. Nearby pixels often have related shades; an encoder can exploit that structure. A flat region invites run-length encoding, while lossy block averaging trades fine detail for fewer stored samples. The choice depends on whether exact pixel values matter and on the patterns in the image.

Lossless source coding recovers the encoded pixel values exactly, including sharp text or numerical image data. Lossy compression preserves an approximation and can remove features that later image processing might need. A visually smooth result is therefore a different promise from exact recovery. Neither method has a universal compression ratio: the chosen file format, its file header and the particular image all matter.

PNG is a real format with lossless source coding of its encoded image data. Its specified compression uses Deflate on reversibly filtered rows, rather than our toy RLE format. The lossy block averaging example is also a teaching format, not a description of PNG. A lossy preprocessing step followed by saving as PNG preserves the already changed pixels, not the earlier original.^[ref]

Deflate is the lossless source coding method specified for PNG compression. It can describe repeated stretches of earlier data, going beyond the single-value repetitions of run-length encoding.^[ref]

The format combines Deflate backreferences, which describe repeated stretches, with Deflate Huffman coding, which represents the resulting instructions using prefix codes. Deflate block framing tells the decoder which codes apply and where decoding stops. RFC 1951, DEFLATE Compressed Data Format Specification version 1.3 (May 1996), defines the format; different encoders can choose different instructions for the same input.^[ref]

This separation is useful: discovering a repeated phrase and choosing short codewords solve different problems. A repeated phrase can contain many distinct bytes, while unequal codeword lengths can help even when no phrase repeats. Neither mechanism removes Deflate compression overhead or guarantees a saving on every input.

Run-length encoding replaces each maximal consecutive group of equal values, called a run, by its value and length. Decoding repeats each value the specified number of times. It is lossless source coding: no values are discarded. For a binary string, successive maximal runs alternate between 0 and 1, so storing the first bit and all run lengths is enough.

Take this $8\times 8$ raster image, with 0 black and 1 white, read left to right across each row and then top to bottom:Reading the whole image as one 64-bit binary string gives exactly seven runs:The lengths sum to $12+8+8+8+8+8+12=64$. Repeating the alternating values for these lengths and splitting after every eighth pixel reconstructs every displayed row exactly.

Here is a complete toy file format. Its file header is an eight-bit unsigned width, an eight-bit unsigned height, then a one-bit mode: 0 means raw pixels, 1 means run-length encoding. Fields are written most significant bit first; this profile accepts only width and height 8, so both decoders know to stop at 64 pixels. Raw mode contains 64 bits. RLE mode contains the initial bit, followed by seven-bit unsigned run lengths in the range 1 to 64. Zero and lengths above 64 are invalid; a decoder rejects a run that would exceed the remaining pixel count. It stops when the decoded lengths sum to 64, so no run-count field or end marker is needed.

For this image, the complete RLE serialization is:Spaces and vertical bars are explanatory separators, not stored characters. The seven-bit fields directly store the lengths; 64 would be 1000000. The payload costs $1+7\cdot 7=50$ bits, versus 64 raw bits. The 17-bit file header has the same size in either mode, giving complete sizes of 67 versus 81 bits. If packed into eight-bit units, append zero padding only at the end: the sizes become 72 versus 88 bits. These are sizes of this toy representation, not sizes of PNG files.

The field design matters. Restarting RLE on every row costs eight initial bits plus four bits per run when lengths are stored directly: three bits represent only 0 through 7, whereas a row can have length 8. This pattern has row-run counts $1,2,2,2,2,2,2,1$, totalling 14, so that payload costs $8+4\cdot 14=64$ bits, with no saving. Storing length minus one would instead fit lengths 1 through 8 into three bits, but is a different declared file format. An alternating flat 64-bit binary string has 64 runs and costs $1+7\cdot 64=449$ payload bits in our flat format; restarting each row costs $8+4\cdot 64=264$ payload bits. A one-run image costs only eight payload bits. These extremes explain when RLE is useful: long uninterrupted regions make short instructions, while frequent changes make instructions expensive.

Prefix codes of unequal lengths can replace fixed-width run lengths, provided the decoder knows the code and any necessary code description is counted. Run-length encoding names a technique, not one universal serialization. For a real implementation, Microsoft's bitmap documentation specifies BI_RLE8 with count and value fields plus special commands, rather than our initial-bit convention.^[ref]

Lossy compression reduces a representation while permitting irreversible changes to the original. The encoder can map distinct inputs to the same output, so its decoder cannot recover both originals exactly. The useful question becomes how much storage is saved for an acceptable amount of distortion: mean squared error is one numerical criterion, but it does not by itself measure how noticeable a visual change is.

For example, storing the arithmetic mean of four grayscale pixels retains their average shade while discarding their arrangement. Blocks $\left(\begin{array}{cc}0& 100\\ 100& 0\end{array}\right)$ and $\left(\begin{array}{cc}50& 50\\ 50& 50\end{array}\right)$ both produce 50. The former has detail and the latter is uniform, yet the decoder receives the same value. Lossy block averaging makes this ambiguity, its bit saving and its mean squared error exact.

Fix $n\ge 1$. There is no injective function from all length-$n$ binary strings to binary strings of length strictly less than $n$. There are $2^n$ possible inputs, but even allowing the empty string gives onlypossible shorter outputs. The finite geometric series and pigeonhole principle leave at least two inputs sharing an output, which prevents exact decoding. For $n=3$, eight inputs compete for the empty string and the six strings 0, 1, 00, 01, 10, 11.

This counting argument includes any file header or other information sent to the decoder. An algorithm chosen separately for each input must also be identified to the receiver; its description is not free. A useful compressor saves space on some inputs while leaving others unchanged or making them longer. Lossy compression avoids the exact-recovery requirement by deliberately allowing several inputs to share an output.

Privacy amplification compresses a partially secret random string into a shorter key by a publicly selected hash function, reducing an adversary's information about the final key. In the BB84 protocol it follows parameter estimation and error correction, and accounts for information leaked in the public reconciliation transcript. Authentication of the public channel remains necessary.

A protocol for two distant parties to agree on a random bit without trusting either party to announce an unverified coin toss. In the Rabin-Williams scheme, a publicly committed square hides which of two half-interval roots the sender selected. The other party guesses a digit distinguishing those roots; subsequent root and factor revelations verify the completed exchange. The protocol's fairness relies on prescribed randomness and the difficulty of finding a second root; it does not force a party to complete communication.

Quantum key distribution uses a quantum channel and an authenticated public classical channel to establish matching random keys for two parties while limiting an eavesdropper's information. The public transcript is included in the adversary's information. In an ideal successful protocol, a key of length $\ell$ is uniform and independent of that information. Actual protocols allow small disagreement and secrecy errors and may abort. Measurement in quantum mechanics disturbance provides parameter tests, while privacy amplification removes residual knowledge after classical reconciliation. The BB84 protocol and entanglement-based protocols are examples.

A bit commitment allows a sender to fix a bit while concealing it from the receiver until an opening phase. Binding prevents a sender from opening the same commitment as either bit; hiding prevents the receiver from learning the bit prematurely. With a one-way permutation $F$ and a hard-core predicate $h$, a commitment can consist of $F(x)$ and the masked bit $b\oplus h(x)$. Opening reveals $x$. Injectivity gives binding, while unpredictability of the hard-core predicate gives computational hiding. For an RSA cryptosystem, the receiver must not possess the inverse trapdoor.

A hard-core predicate is an efficiently computable bit of an input to a one-way function that cannot be predicted from the function output with nonnegligible advantage over random guessing. For a one-way function $f$, padding it to $F(x,r)=(f(x),r)$ gives the inner-product predicate $h(x,r)={\sum }_j{x}_j{r}_j\mathrm{mod}2$. This is the Goldreich–Levin construction. It provides a way to mask a bit using an otherwise publicly revealed one-way function value.

A one-way function is efficiently computable but computationally infeasible to invert on a randomly sampled input with nonnegligible success probability, under its stated security assumption. An RSA cryptosystem supplies the candidate map $x\mapsto x^e\mathrm{mod}N$ on units modulo $N$. Inversion hardness is an assumption; it is not a proved consequence of merely choosing large primes.

On a finite rectangular Conway's Game of Life board stored as an array of Boolean variables, retain the preceding row's old values in one auxiliary row. Before overwriting a column, retain rolling sums of the old three-cell vertical columns. Their sum minus the old center is the old neighbor count. Read the next column before changing the current one; replace the saved row entry by the old current cell. The invariant is that every count uses the previous generation, just as in the two-array algorithm. For a board with $H$ rows and $W$ columns this uses $O(W)$ auxiliary storage and $O(HW)$ time. The boundary convention must still be implemented explicitly. The Life blinker and Life glider provide exact expected generations for checking it.

The Life glider is a five-cell pattern that recreates its shape after four generations, shifted one cell along each coordinate. Use $x$ increasing rightward and $y$ increasing downward, as in the figure, and start from the live setEvery cell outside $G_0$ starts dead. Applying the Conway's Game of Life rule, rather than moving the drawing by hand, gives:

For an exact check of every frame, the intermediate live sets areHere $G_0+(1,1)$ means add $(1,1)$ to each ordered pair in $G_0$. In the first step, the live cells $(1,0)$ and $(0,2)$ have respectively one and one live neighbors, so die; the other three have respectively three, three and two and survive. Exactly $(0,1)$ and $(1,3)$ are born, with three live neighbors each. This derives $G_1$ and explains how motion can occur while individual cells merely switch states.

Because the rule uses the same relative neighbors at every position, applying the global update function and applying a translation commute. Thus $G_{t+4}=G_t+(1,1)$ for every generation $t$; the four-step calculation establishes continued motion on the infinite board. The average displacement is $(1/4,1/4)$ cells per generation, or Euclidean distance $\sqrt{2}/4$ per generation. The live-cell count happens to stay five in these frames, but the rule does not conserve live-cell count in general: a single isolated live cell dies immediately. The Life glider persists indefinitely in an otherwise empty infinite board; encounters with other patterns or a finite implementation's edge can change that conclusion.

// Destination: computer-science.bigb

A Life oscillator is a nonconstant periodic orbit of the Conway's Game of Life update function $F$. Its period is the least positive integer $p$ for which $F^p(A)=A$, comparing the entire live-cell set at the same coordinates. A configuration that never changes is instead a fixed point; a Life glider is not a Life oscillator on the infinite board because it returns at displaced coordinates. The Life blinker has period two.^[ref]

Publisher: Python Software Foundation.

Online text: github.com/python/cpython/blob/3.14/Parser/Python.asdl

Cited passages: CPython 3.14, Parser/Python.asdl: Module, Assign, BinOp, Constant, Name and expr_context constructors.

By Linux man-pages project.

Publisher: Linux man-pages project.

This source is credited to an organization.

Online text: man7.org/linux/man-pages/man2/msync.2.html

Cited passages: DESCRIPTION, RETURN VALUE, ERRORS and VERSIONS: covered range, MS_SYNC versus MS_ASYNC, page-aligned address, and Linux MS_ASYNC behavior since 2.6.19.

By The kernel development community.

Publisher: The kernel development community.

This source is credited to an organization.

Online text: docs.kernel.org/mm/page_cache.html

Cited passages: Page Cache, opening paragraph: normal reads, writes and mmaps go through the page cache; bypass paths exist.

By IEEE, The Open Group.

Publisher: IEEE and The Open Group.

This source is credited to an organization.