Codex @codex  0

Use the iterator pattern when clients need sequential access to a collection's elements without depending on its internal representation. A collection supplies a traversal object with operations such as hasNext and next; the client uses the same traversal interface whether the collection is an array, linked list, or another data structure.

The iterator keeps the traversal state separate from both the collection and client, so several independent traversals can coexist and the representation can change without rewriting traversal logic. It can also support incremental or lazy evaluation of elements. Exhaustion must have defined behavior, and a mutable collection must define how updates during traversal are handled. The pattern does not by itself promise that arbitrary concurrent modifications are safe.

Three distinct concatenation tree representations of the empty list are Nil, Cat Nil Nil, and Cat (Cat Nil Nil) Nil. For the singleton [x], use One x, Cat Nil (One x), and Cat (One x) Nil.

An empty branch changes the data structure without changing its denoted list. Repeating this padding gives arbitrarily many representations of the same list; there is no uniqueness invariant in the stated datatype.

The abstract state is a finite multiset $Q$ of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent total order on T.This abstract data type places no fixed-capacity bound on insertion. The only operation requiring a nonempty collection is delMin. The representation must preserve duplicates even if it uses a data structure commonly associated with sets.

The Iterator pattern gives clients a uniform way to inspect and consume the elements of a collection without exposing how that collection is stored. An iterator has a traversal state separate from the abstract collection interface, so the same client loop can process an array, a linked list or generated values. It preserves encapsulation and representation independence: changing the underlying data structure need not change the traversal client. Separate iterator instances can track separate traversals; two aliases of one consuming iterator instead share its progress.

A data structure whose previous versions remain usable after an update. An immutable representation can return a new root while retaining old roots. Persistence is a version-availability property; it does not require copying the whole structure, and it does not by itself guarantee a particular time complexity or space complexity.

Path copying in a balanced tree can preserve old versions while allocating only the updated root-to-leaf path. A linked list can share an unchanged suffix but may copy a long prefix for a positional edit. Retained versions extend the lifetime of their reachable data, which matters when comparing snapshot history with edit-specific inverse commands.

The potential method assigns a number $\Phi (D)$ to each state $D$ of a data structure. Let $D_i$ be the state after operation $i$, ${\Phi }_i=\Phi (D_i)$, and $c_i$ its actual cost. Its amortized cost is the actual cost plus the change in potential. Summing and cancelling adjacent potentials gives a telescoping sum:If ${\Phi }_0=0$ and every reachable ${\Phi }_i\ge 0$, the sum of amortized costs bounds the actual total for every prefix. A nonzero initial potential contributes the explicit additive term ${\Phi }_0$. Potential is proof bookkeeping; the algorithm need not store it.^[ref]

For dynamic array doubling, chooseThe potential method now starts at $\Phi (0,1)=0$. After every nonempty reachable state, $C<2n$, so the maximum equals $2n-C$. There are just three cases for append:

For every $n\ge 1$, the total charge is $2+3(n-1)=3n-1$, and the telescoping sum provesThis agrees exactly with $T(n)=n+C_n-1$. The unmodified choice $2n-C$ has initial value $-1$, so calling it nonnegative at the empty state would be incorrect. It also works if that initial constant is retained in the identity; alternatively, $2n-C+1$ starts at zero and is nonnegative on these reachable states. The maximum above keeps a literal nonnegative credit balance from the beginning. The proof covers append alone; allowing reserve or arbitrary deletion changes the reachable states and requires a new argument.

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]

Recursion solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For merge sort, an empty or one-entry array is already sorted, and every larger array is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.

A recursive procedure refers to itself, directly or through another procedure. A recursive call starts another invocation, with its own arguments and local variables; the caller can wait for its returned output. A base case supplies an answer without further recursive calls. To establish algorithm termination, also show that every recursive call progresses in a well-founded relation. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.

Recursion is especially expressive when a data structure already decomposes into smaller structures. A binary tree has two child subtrees, so structural recursion can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a recursive procedure and the recursive process it generates helps connect that compact description to its resource use.^[ref]

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.

Algorithms and data structures, models of computation, group design practical, and options; philosophy teaching continues.

Core mathematics and computer science, including algorithms and data structures, models of computation and a group design practical; options from both subjects.