Codex @codex  0

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

A data structure storing entries at numbered positions, usually starting at index zero. The fixed-capacity representation considered here puts equal-sized slots consecutively in computer memory. The number $n$ of occupied slots can be smaller than the capacity; unused slots provide room for later entries. An array of references stores consecutive references, while the objects they identify can be elsewhere. ^[ref]

Let the first slot have abstract address $b$ and each slot occupy $s$ address units. Then indexed access computesFor toy values $b=100$, $s=4$, the slots for $A,B,C$ start at $100,104,108$; index $2$ goes directly to $C$ through $100+2\cdot 4=108$. These are illustrative slot addresses, not observed allocation addresses. Under the word-RAM (random-access machine) model for time complexity, word-sized arithmetic operations and any addressed computer memory access have constant cost, and the addresses and entries fit in words. Thus one array access takes $O(1)$ time in Big O notation, independently of the index. This is the access assumption needed by binary search. ^[ref]

Inserting $X$ after $B$ in an array holding $A,B,C$ with one unused slot produces $A,B,X,C$: first copy $C$ from slot $2$ to slot $3$, then write $X$ into slot $2$. Writing $X$ first would lose $C$ unless it had been saved separately. More generally, insert at index $i$ by copying occupied slots from right to left, then fill the gap; with spare capacity this moves $n-i$ entries and takes $O(1+n-i)$ time in Big O notation, so insertion near the middle has $O(n)$ time complexity. Removing an entry closes the gap by shifting later entries left. ^[ref]

A fixed-capacity array cannot accept another entry when full. A resizable representation can allocate a larger array and copy the entries. Doubling capacity when full gives $O(1)$ append cost by amortized analysis over a sequence starting empty, but a single append that copies $n$ entries still has $O(n)$ worst-case time complexity. The outline is a geometric series: copied capacities $1,2,4,\dots ,2^k$ sum to $2^{k+1}-1$, less than twice the number of appends that triggered the last copy. Middle insertion still pays for its shifts. ^[ref]

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are $1+2+\cdots +2^h=2^{h+1}-1$ vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

A binary tree, in the data structure convention used here, is a rooted tree in which each vertex has zero, one or two children in a rooted tree, occupying distinct left and right positions. A single left child and a single right child give different binary trees. A vertex with no children in a rooted tree is called a leaf. An empty binary tree has no root of a tree and is also allowed as a storage case. ^[ref]

For example, give the root of a tree label $4$, its left child label $2$ and its right child label $6$. Attach $1,3$ as the left and right children in a rooted tree of $2$, and $5,7$ as those of $6$. This binary tree has seven vertices, six edges, and height of a binary tree $2$: a longest downward graph path contains two edges. The binary search tree lookup illustration below shows this shape alongside the binary tree consisting only of successive right children $1,2,\dots ,7$, whose height of a binary tree is $6$.

Left and right positions specify an ordered shape, not a numerical total order on stored labels. Swapping labels $1$ and $7$ in the first example still gives a binary tree, but destroys the binary search tree property. Nor must a binary tree be balanced: the right-child chain is just as valid. The same shape convention supports a binary heap, a Huffman code, or a binary search tree, each with its own additional rules. The useful idea is to describe two smaller subtrees at each vertex, making structural recursion natural.

For a precise recursive description, a finite binary tree is either empty or a root of a tree carrying a value together with an ordered pair $(L,R)$ of disjoint smaller binary trees. The entries of this ordered pair are its left and right subtrees, each of which may be empty. Thus two binary tree child slots exist even when fewer than two children in a rooted tree exist; an empty slot does not denote an extra vertex. This decomposition is the basis of structural recursion.^[ref]

In the four-vertex mixed example, $A$ has left child $B$ and right child $D$, while $B$ has only a right child $C$. Count its vertices by structural recursion: the empty binary tree contributes zero and each nonempty binary tree contributes one plus the counts of its left and right subtrees. Thus $B$ contributes $1+0+1=2$, and $A$ contributes $1+2+1=4$. The same decomposition computes height of a binary tree, supports inorder traversal, and supplies short proofs by structural induction. It separates shape from the values stored in a data structure.

Ignoring values, let $b_n$ count finite binary tree shapes with $n$ vertices, retaining left and right slots and counting the empty shape once. Splitting at the root of a tree gives the recurrence relationFor each left subtree size $i$, choose its shape and the right subtree shape independently. This yields the Catalan numbers: $b_1=1$, $b_2=2$, and $b_3=2+1+2=5$. The two shapes at $n=2$ are exactly the left-only and right-only examples. Forgetting the slot distinction would change the counting problem.

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles $A,B$ from bounding volume, together with $C$ having vertices of a polygon $(6,0),(8,0),(6,2)$ and $D$ having vertices of a polygon $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent axis-aligned bounding boxes and the box at the root of a tree areThe diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangleleft-first depth-first search tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-coordinate is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two broad phase candidates. The narrow phase rejects $A$, since $x+y\ge 16/5>2$ throughout $Q$, and accepts $B$: the point $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.

For a query asking for all intersections, time complexity depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work iswhere $c$ counts candidate objects and $O$ is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing $[0,8]\times [0,5]$ visits all seven nodes and tests all four triangles. More generally, a full binary tree with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its height of a binary tree is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

A data structure holding the contents of one fixed-size region of a storage device, together with its buffer cache key, buffer cache validity, modification state and lifetime information. A storage region containing file metadata is just as eligible as a file data block. The structure can survive many callers: releasing it usually makes it available for later reuse, rather than immediately deleting the cached contents.

Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.

The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.

Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.

A data structure organizes stored information together with operations for accessing and changing it. Choosing a data structure means choosing which questions should be cheap to answer: an array supports access by numbered position, a hash table supports lookup by key, and a priority queue supports selecting an item by priority. The operations and their time complexity matter as much as the stored values.

Suppose three requests arrive as $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, where the number is a priority and smaller numbers are more urgent. A FIFO queue removes Ada first because she arrived first. A minimum-oriented priority queue removes Bo first because $2$ is the least priority. An array can store the same three records in arrival order, but finding the least priority by scanning this representation takes three key inspections. A binary heap organizes these records so the least priority is immediately available. The information is the same; the representation changes the work needed to use it.

This is a useful design principle: preserve just enough organization for the operations the application needs. Maintaining a sorted array gives the whole order, but moving entries to insert a new key can be expensive. A binary heap keeps a weaker heap order that supports fast repeated selection without maintaining a sorted array. A good data structure makes an algorithm's next step easy.

Encapsulation bundles related program state and operations or hides implementation details behind an interface. Encapsulation in object-oriented programming realizes this through objects and their permitted operations; encapsulation also applies to modules outside object-oriented programs.

The useful boundary is a promise: clients request operations through an API, and the implementation maintains a representation invariant. Instead of proving that every client updates several storage fields consistently, prove that the permitted operations preserve the representation invariant. Information hiding also leaves room to replace the data structure while keeping the client-facing behavior, a property called representation independence.

Bundling state and operations alone does not establish that promise. Representation exposure can let clients bypass the API. A private annotation alone is not a security guarantee: it does not establish correctness of operations, isolation from hostile code or safe handling of shared mutable storage. The examples below concern sequential calls with no concurrent access and no client access to internal storage; they do not claim protection against arbitrary memory modification.

A FIFO queue is a data structure with first-in, first-out behavior: enqueue inserts at the rear, dequeue removes and returns the front, and peek inspects the front without removing it. Removal and inspection require a nonempty FIFO queue, or an explicitly defined empty-case result. Enqueue $A,B,C$ in that order, dequeue $A$, then enqueue $D$: the remaining sequence is $B,C,D$, with $B$ next. A LIFO stack would remove the most recently inserted item instead. A FIFO queue models arrival-order service and supplies the next vertex for breadth-first search; a stochastic service model belongs to queueing theory. ^[ref]

The FIFO queue interface specifies removal order, not time complexity. A linked list with both front and rear pointers supports enqueue, dequeue and peek in $O(1)$ worst-case time under constant-cost pointer operations and allocation, as in Sedgewick and Wayne's implementation. A plain array that deletes its first entry by shifting the remaining $n-1$ entries takes $O(n)$ time per such removal. An array with advancing front and rear indices can avoid these shifts; storage and resizing policies still need analysis. The two-list functional queue gives a different implementation with constant amortized analysis cost along a single sequence of uses. These representation choices matter when deriving the linear time complexity of breadth-first search in Big O notation.

// Destination: computer-science.bigb

A data structure using a bit per allocation unit to mark whether it is available. Its agreement with ownership references is a file-system crash consistency requirement; changing just this structure does not install the owner's update.

A hash function is a function assigning each key in an input set $U$ a value in an output set $B$. Usually $B$ is much smaller: a long name or large integer becomes a small bucket index. Equal keys must receive equal values from the same hash function; different keys may also receive equal values. Such a hash collision means "look in the same place", and does not establish key equality. If $|U|>|B|$, the pigeonhole principle makes some collisions unavoidable.

For example, modular arithmetic gives the hash function $h(k)=k\mathrm{mod}7$, with seven bucket indices $0,\dots ,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne 10$. A hash table is a data structure that uses these indices to locate records. With separate chaining, each bucket holds a linked list of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their hash function values agree.

Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This data structure trades a search through all records for a search through one short chain, provided the hash function distributes keys adequately. A fixed hash function can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A universal hash family introduces controlled randomness to limit the expected value of this extra work. Neither indexing nor a small collision probability inherently supplies encryption or message authentication; a cryptographic hash function has additional requirements such as collision resistance.

A tree-based data structure that orders each parent relative to its children so that an extremal value is available at the root. In a max-heap, every parent is at least as large as its children. Heap implementations provide one way to realize a priority queue; the abstract queue and its implementing structure are distinct concepts.

The 12 June 2013 preliminary examination paper, released as member 4216-1.pdf of Fakour Zip Final 1.zip. Questions 1–4 concern imperative programming and data structures; Questions 5–8 concern Scala object-oriented programming.

An inode is a data structure describing an object in an inode-based file system. For an ordinary file, it records file metadata such as type, owner, access permissions, size and hard link count, together with information locating the contents. In the direct-reference toy layout, inode 42 points to file data blocks 7 and 9; its two names a and b live in directory entries. Other file systems can locate contents differently, so the diagram is a model of the separation rather than a universal storage layout. ^[ref]

An inode number is unique only within its file system among allocated objects. Two different file systems can each have inode 42, referring to unrelated files. POSIX exposes the file system's device identity as st_dev and the file's serial number as st_ino; the pair identifies a file within a running system. Neither the bare inode number nor that pair is a permanent historical identifier: after reclamation, a later file can reuse the number. In particular, comparing an old saved number with a new one does not establish continuity of the file. ^[ref]

The design's appeal is that one inode unifies the file metadata and contents reached through several directory entries. Ritchie and Thompson's original 1974 account explicitly describes a directory entry as a name and an i-number, with the corresponding inode holding ownership, protection, size, content addresses and the hard link count. It gives a concrete early explanation of how names and file identity can evolve separately. ^[ref]

// Target: computer-science.bigb

A data structure representing a sequence through linked list nodes and links between them. In the singly linked representation used here, each linked list node holds an item and a next reference to its successor. head identifies the first linked list node; the final next is null, meaning no successor. An empty linked list has head = null. Sedgewick and Wayne use this representation to implement both a stack and a FIFO queue. ^[ref]

For $A\to B\to C$, place the linked list nodes at conceptual computer memory positions $40,12,76$, respectively. These deliberately separated labels describe a toy layout, not actual pointer values. The sequence order comes from the links, not increasing positions. To read index $2$, begin at head and follow two next references. For index $i$, this takes $i$ link-following steps and $O(1+i)$ time complexity, hence $O(n)$ in the worst case for $n$ linked list nodes, under the constant-cost operations assumed for the array example. ^[ref]

Suppose a reference to the existing linked list node $B$ is already known. To insert a fresh linked list node $X$ after it, first set X.next = B.next, preserving the old successor $C$, and then set B.next = X. The result is $A\to B\to X\to C$; none of the old items moves. Reversing these assignments would read the newly changed B.next and set X.next = X, losing the route to $C$ from head. This is a two-update algorithm correctness argument, rather than a claim that finding the insertion location is free.

The two pointer updates take $O(1)$ time in Big O notation. The complete insertion has $O(1)$ time complexity if the predecessor is already known, allocating and initializing the fixed-size linked list node costs $O(1)$, and copying its item has constant cost. Finding $B$ from head can instead cost $O(n)$; a position described only by an index does not confer the constant-cost advantage. This makes a linked list useful when an algorithm already holds the needed linked list node, or repeatedly works at the front as a stack does.

Deletion similarly needs the incoming link: to remove $X$ after known $B$, set B.next = X.next. A reference to $X$ alone does not identify its predecessor in this singly linked representation. The head is a special case: after checking for a nonempty linked list, remove it with head = head.next. If a tail reference is also maintained, deleting the only linked list node must clear that reference too; a stored length must also be updated. Removing a linked list node from the sequence and reclaiming its storage are separate responsibilities. ^[ref]

There are practical costs beyond Big O notation. Each singly linked linked list node needs a successor reference in addition to its item; separate allocation may add further overhead, while an array can reserve unused capacity. Consecutive array slots can make a scan reuse nearby contents already brought into a memory cache; separated linked list nodes can make link following wait for successive computer memory fetches. These are layout-dependent effects, not a guarantee that every array operation beats every linked list operation on every machine. An array of references can still lead to scattered objects, and linked list nodes can be allocated close together. ^[ref]

A page table is the data structure describing an address space's mappings from virtual page numbers to page frames, together with access and status information. A page table entry can describe a resident memory page and its permissions. Nonresident or unmapped memory pages require a representation that lets the operating system distinguish them; a hardware not-present flag alone need not make that distinction. On x86, additional operating system information determines whether a not-present mapping is legitimate. ^[ref]

The four rows drawn under paging are an illustrative model, combining page table and operating system information: virtual page 0x12 is resident in physical frame 0x07 with read-only permission; 0x13 is resident in 0x02 with read/write permission; 0x14 is mapped read/write but nonresident; 0x15 is unmapped. The labels deliberately separate mapping policy, residency and permission. They are not a literal x86 entry layout. A translation lookaside buffer valid flag is a fourth, independent notion: it says that a cached translation can be considered, not that every resident memory page has a cached translation.

A flat array with one page table entry per virtual page would have $2^{16}/256=256$ entries in this example. At an assumed four bytes per entry, it occupies $256\cdot 4=1024$ bytes, whether one memory page or all 256 memory pages are mapped. A multi-level page table saves space in sparse address spaces by allocating lower-level tables only for the regions that need them. The tradeoff is extra dependent lookups during a page table walk; a translation lookaside buffer avoids repeating those lookups on a hit. ^[ref]

The accounting method assigns each operation a charge, its amortized cost, that can differ from its actual cost. Cheap operations save the excess charge as credits associated with the data structure or its entries. An expensive operation spends these previously saved credits. The essential invariant is that the credit balance never becomes negative.

If the initial balance is zero, operation $i$ has actual cost $c_i$, charge ${\hat{c}}_i$, and leaves balance $B_i$, thenThus a nonnegative credit balance makes the total charge an upper bound on the total actual cost for every operation sequence. In particular, a constant time charge proves a linear time total. The argument is a deterministic amortized analysis; it requires no probability distribution on the operations. A nonzero initial balance must be included as an additive term in the bound.

Use the straightforward incremental three-dimensional convex hull algorithm. Assume distinct input points, at least four noncoplanar points, and general position with no four coplanar. Use exact orientation decisions, or robust predicates that certify the same signs. These assumptions avoid the separate bookkeeping for flat faces, points on the boundary and lower-dimensional initial data.

The determinant ${\sigma }_f$ is six times the oriented volume of the tetrahedron $abcp$; only its sign matters. A zero value needs a declared degeneracy policy if the general-position assumption is relaxed.

The data structure update is a separate local operation. Mark visible faces and walk their adjacency to collect the horizon cycle before deleting anything. Remove edges with two visible incident faces; retain horizon edges and their retained-face links. Insert a vertex of a polyhedron record for $p$ and a new edge from $p$ to each horizon vertex of a polyhedron. Add one face per horizon edge, connect its other two edges to its neighbours in the cone, and replace the deleted face reference on each horizon edge. Restore the cyclic boundary references and each retained vertex of a polyhedron's incident-edge reference; remove any old vertices of a polyhedron left without incident faces.

For an outward visible face with boundary edge $a\to b$ on the horizon, the new outward face can be ordered $(a,b,p)$. Its retained neighbour already traverses that edge as $b\to a$. As an independent orientation check, an interior point of the old hull must evaluate negatively against the new face.

The correctness step is geometric: the nonvisible part of a convex polyhedron remains supporting, while sight lines from $p$ to the horizon create precisely the new supporting faces. Replacing the visible cap by its cone therefore givesInduction from the initial tetrahedron yields the convex hull of all input points.

The iterator pattern separates traversal state from the aggregate being traversed. A client asks whether another entry exists, then requests that entry, without knowing whether storage is an array, a linked list or another data structure. Distinct iterators have independent positions in a traversal.

In Java, declare DataList implements Iterable<Point> and provide public Iterator<Point> iterator(). The returned iterator implements hasNext() and next(); exhausted next() throws NoSuchElementException. This also permits an enhanced for (Point p : data) loop.^[ref]

Returning points.iterator() directly would permit removal through that iterator and expose mutable stored Point instances. Part (e) instead returns an unmodifiable iterator snapshot containing fresh Point copies. That choice gives stable traversals and prevents representation exposure, with the tradeoff that a traversal does not see subsequent insertions. Thus