Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Integer
For finite sets, the inclusion-exclusion principle statesAn element present in of the sets is counted times, which explains the alternating corrections.
There are positive integers strictly below divisible by . For the divisors , the single counts are . Their pairwise intersections correspond to divisibility by , giving . The triple intersection has elements. Therefore
This numbered item specifies the model used below. A convenient sample space is the collection of ordered pairs , each with probability . The corresponding random variables are determined by the sum and difference. Inverting the two equations givesThus a candidate pair is possible exactly when and are both integers between and . In particular, and must have the same parity. This inverse description will determine the joint probability mass function.
First restrict to integers in the marginal supports: and . Their marginal probabilities are positive. By part (i), a feasible joint pair identifies a unique ordered pair of rolls, so its joint probability is ; an infeasible pair has joint probability zero.
Put and . If the two events were independent, a feasible pair would requireSince , equality forces , hence . But that pair is infeasible. An infeasible pair cannot give independence either, since its joint probability is zero while the product of its positive marginal probabilities is positive. ThusIf all real values of are allowed literally, an impossible event is independent of every event. The complete answer without a support restriction is therefore
These solutions follow the original examination of 11 June 2013, code
4208.[ref]Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2013). pp. 2–7, Questions 1–8
Each question's Haskell definitions form a separate namespace; hide redefined Standard Prelude names when compiling them. Unless stated otherwise, arguments are finite and total. Time complexity counts primitive operations; the cost of comparing variable-length words and the growing bit cost of exact integer arithmetic are stated separately where relevant.[ref]Represent Pascal's triangle by an infinite outer lazy list, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:
pascal :: [[Integer]]
pascal = iterate next [1]
where
-- Padding supplies the two boundary entries as well as the interior sums.
next :: [Integer] -> [Integer]
next row = zipWith (+) (0 : row) (row ++ [0])Here
iterate next [1] begins [[1],[1,1],[1,2,1],[1,3,3,1],...]. Every call to next receives a finite row, so its final zero is reachable. Lazy evaluation produces any requested finite prefix without trying to finish the infinite outer list.Indexing rows and columns from zero, Pascal's rule saysTake out-of-range binomial coefficients to be zero. The seed is the zeroth row, and the padded addition implements this identity at every position, including the two boundaries. Mathematical induction therefore proves every generated row correct. Using unbounded integers prevents overflow. Generating rows zero through takes arithmetic operations, with additional bit costs as the binomial coefficients grow.
In the 0-1 knapsack problem, item has weight and value . Choose a subset of the items, using each at most once, whose total weight is at most and whose total value is as large as possible. For the capacity-indexed dynamic program, take and the weights to be nonnegative integers. The empty choice is allowed.
Let be the greatest value attainable using only items with capacity . The base case is . With item unavailable when it is too heavy, the recurrence isEvery feasible optimum either excludes item , giving the first candidate, or includes it exactly once, leaving capacity for earlier items. The principle of optimality proves that the remaining earlier items must attain the indicated residual optimum. Conversely, either candidate constructs a feasible solution, so taking the larger is both necessary and sufficient. Mathematical induction on proves the table's meaning and the final answer .
Store item weights and values in arrays and the values in a two-dimensional array with entries. Fill rows in increasing ; each entry uses at most two values from the previous row. There are constant-work updates, givingFor positive growing capacities this is the familiar bound. The terms also cover capacity zero and zero-weight items: one must not initialize every to zero if zero-weight, positive-value items are allowed.
To recover an actual subset, store the chosen alternative at each entry or compare the two candidates while tracing backward from . A selected item changes to ; an excluded item changes it to . This takes extra time.
If only the optimal value is needed, keep two rows, using space. With strictly positive weights, a single capacity row updated in decreasing capacity also prevents item reuse. The two-row version handles zero weights without special in-place reasoning. The running time is pseudopolynomial, since the binary input length of is only logarithmic in its numerical value.
For the two-bag 0-1 knapsack problem, let be the maximum total value using the first items, with remaining capacity limits in the first bag and in the second. Initialize . Item has exactly three possible decisions: omit it, place it in bag one if it fits, or place it in bag two if it fits. HenceA braced candidate with a false condition is omitted. All candidates refer to layer , which prevents the same item from entering both bags. Combining two independently optimized single-bag knapsacks would not enforce that restriction.
The principle of optimality proves correctness exactly as in part (b): condition on the location of the final item and replace the earlier items by the optimal feasible residual assignment. Every candidate is realizable, and every feasible assignment belongs to one of the three cases. The final answer is .
Fill the three-dimensional array in increasing item index. Each of its updates inspects at most three candidates:For positive capacities the customary expression is . Keeping only two item layers reduces space to for the optimal value. Full decision storage also permits backward reconstruction of each item's bag assignment. Nonnegative integer weights and capacities are the assumptions behind this capacity-indexed dynamic programming table.
Use an abstract finite sequence of integers, initially empty. In the following trait, comments are the mathematical specification; means the abstract state on entry, and The postcondition of
result means the returned value.trait ReversableBuffer {
// Abstract state s: finite sequence of Int, initially [].
// Pre: true. Post: s = s0 ++ [x].
def append(x: Int): Unit
// Pre: true. Post: s = [x] ++ s0.
def prepend(x: Int): Unit
// Pre: 0 <= i < length(s0).
// Post: result = s0 !! i,
// s = take i s0 ++ drop (i+1) s0.
def get(i: Int): Int
// Pre: true. Post: s = reverse(s0).
def rev: Unit
}get includes removal: it is not merely indexed reading. In particular,Repeated equal values elsewhere in the sequence remain present. List concatenation, indexing and list reversal in the specification describe abstract behavior without committing to a physical representation.Reuse A useful loop invariant is that the pending segments are pairwise disjoint valid array segments of length at least two; the whole array multiset equals its original value; and every inverted pair of positions lies in a single pending segment. Explicitly, if and , some queued contains both and . Thus all ordering obligations are localized to queued segments.
split and swap, but replace recursive calls with a FIFO queue of unresolved segments. Enqueue only segments of length at least two.def quicksortLoop(): Unit = {
val work = scala.collection.mutable.Queue[(Int, Int)]()
if (a.length > 1) work.enqueue((0, a.length))
while (!work.isEmpty) {
val (l, r) = work.dequeue()
val (lt, gt) = split(l, r)
if (lt - l > 1) work.enqueue((l, lt))
if (r - gt > 1) work.enqueue((gt, r))
}
}Initially the only possible pending segment is the whole array. One array partitioning confines all its remaining inversions to its two child segments. Its equal middle segment is ordered, the left/middle/right boundaries have the correct ordering, and segments of length at most one cannot contain an inversion. Because array partitioning only permutes the selected segment's entries, it cannot create an inversion across a boundary that previously had no inversions. This proves preservation of the loop invariant.
The loop variant is the total pending lengthProcessing one segment removes from and adds at most , strictly less because . Thus is a nonnegative integer and decreases. At exit no pending segment exists, so no inversion exists:The FIFO queue itself can grow to pairs. The time complexity is that of the corresponding recursive quicksort, including linear behavior on equal input. Removing recursion does not make the worst-case time complexity linear or eliminate the work storage.
Keep the neighboring Fibonacci number in a private closure. Before calling the transition with , let its captured The transition returns and stores , preserving the paired Fibonacci recurrence. Initialization gives and , soUsing
following equal .def fibonacci(): Iter[BigInt] = {
var following = BigInt(1)
val step: BigInt => BigInt = (x: BigInt) => {
val result = following
following = x + following
result
}
new FunIter[BigInt](BigInt(0), step)
}BigInt allows all Fibonacci numbers rather than a finite prefix before integer overflow. Replacing BigInt by Int gives the source's suggested machine-integer interface with that limitation. With the FunIter implementation from part (c), each transition runs once per generated cell, and copied iterators can advance independently while sharing the privately owned generator. A simpler alternative uses a pure function on pairs, , and projects the first component; the closure above follows the source's suggested single-value approach directly.An immutable object can widen its element type when adding a value by returning a new object. Introduce a lower type bound on the method's fresh type parameter.As before, the representation invariant excludes duplicates, and the abstraction function returns the unordered set of entries. The constructor normalization makes the representation invariant hold even for repeated initial entries. Both operations construct a fresh set object and leave the original object unchanged, including when addition finds an existing member.
class ISet[+T](contents: List[T]) {
private val elems: List[T] = contents.distinct
def add[U >: T](x: U): ISet[U] = {
val widened: List[U] = elems
if (widened.contains(x)) new ISet[U](widened)
else new ISet[U](x :: widened)
}
def delete(): (T, ISet[T]) = {
require(elems.nonEmpty)
(elems.head, new ISet[T](elems.tail))
}
}For a receiver representing , the new object returned by
add represents . Deletion returns a pair with and representing . Crucially,The widened list is valid because immutable List itself has a covariant type parameter. A client can view an ISet[Int] as ISet[Any], but adding a string creates a separate widened result; it cannot put a string into the old integer set. This explains how using immutable objects makes the desired type variance sound. A direct add(x: T) on a covariant software class would still violate the variance-position rule; immutability alone does not repair an incorrectly typed method signature.Write with . The difference of two squares factors asThe final factor is an integer, so divides the difference. By congruence modulo an integer, .
Here are fixed integers. The term has exponential growth, whereas has fixed-degree polynomial growth and is linear. Since a fixed-base exponential eventually dominates every fixed-degree polynomial,Hence the requested Big O notation bound, with its matching lower order, is .
The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case and use , for . This integer rounding in a divide-and-conquer recurrence gives . The unrounded calculation is the special split fraction .
Prove by strong induction. Put , choose , and choose . The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses . This closes the inductive hypothesis and proves in Big O notation.
The solutions use the original 17 June 2014 preliminary examination, code
4208.[ref]Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2014). original scan, pp. 2–8
Haskell definitions use separate question namespaces; names suffixed F or U distinguish alternative implementations. For Question 4, use import Prelude hiding (foldr, (++), concat, flip) when compiling the definitions together. Unless an infinite input is discussed explicitly, inputs are finite and total. Arithmetic operation counts do not include the growing bit costs of exact integers.[ref]The two constructors encode a natural number by its number of successors. Structural recursion replaces the zero constructor by zero and every successor by one addition:
convert :: Natural -> Integer
convert Zero = 0
convert (Succ n) = 1 + convert nStructural induction gives . The output uses unbounded integers, so there is no machine-word overflow.
The scan permits an arbitrary signed integer but prints . That expression is undefined for . The printed bound is proved below for positive ; for the stated signed domain the corresponding bound uses . This is a source qualification, rather than an unreadable part of the question.[ref]
Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2014). p. 7, Question 5(b), printed logarithm and final absolute-value sentence
Choose a fixed positive integer with , and put . For positive , use coarse exponential bracketing: compare against until the first . Equality determines immediately. Otherwise, , except in the first interval where the lower bound is zero. Apply binary search to the remaining integer candidates.
There are at most bracketing comparisons and at most subsequent comparisons, because the interval width is at most . Minimality of gives . HenceThe additive constant may depend on the fixed , but is independent of . Taking larger jumps in the bracketing phase reduces its leading comparison cost; the overshoot costs only the fixed number of extra binary search levels.
For signed inputs, first compare with zero. If negative, set conceptually and perform the same search for : comparing with yields the reversed outcome of comparing with . Thus every test is still a permitted test of the sign of . Return zero immediately on equality in the initial test. The corrected all-input bound isAll thresholds are exact integers, generated by repeated multiplication by . Their arithmetic and storage costs are outside the requested comparison model; bounded machine arithmetic would not suffice for arbitrarily large .
Assume . Use bottom-up heap construction to make a max-heap of the first input items. For each subsequent input value , compare it with the root. If is at least the root, discard it; otherwise replace the root by and apply heapify down. Return the final root.
The loop invariant says the heap contains a multiset of the smallest values seen so far. It holds after initialization. If is at least the current largest retained value, the already retained items are no larger, so discarding preserves the invariant. If is smaller, remove one largest retained value and keep instead; precisely the smallest values remain. This argument handles equal integers by treating repeated occurrences as separate items. At the end,Construction costs ; each remaining value uses one comparison and at most one logarithmic repair. Thus the selection algorithm has time complexityFor , the heap is a single running minimum and the time is . The uniform expression covers that boundary; interpreting the printed literally at would incorrectly make it zero.