Let be the number of objects in box . The arrangements correspond exactly to nonnegative integer solutions of . By stars and bars, place stars and separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives
Using with integers ,The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives
By Euclidean division, write and , with integers and . The hypothesis is . Apply the addition rule from part (b)(i) with to obtainTherefore . But , and the only multiple of in that interval is zero. Henceso the two remainders agree.
Set . The definition of the floor function gives . Adding the integer yieldsSince is an integer, it is exactly the floor of . Thus
The probability generating function of a nonnegative integer-valued random variable isusing also at . It is always defined for , and indeed the power series converges absolutely for all real or complex with , becauseIt may be defined beyond the unit disk where this power series converges absolutely; such a larger domain depends on the distribution. In particular and .
For parts (b)–(e), use array indices as tree handles. This also makes the shared storage in part (d) type-correct: both pending handles and output markers occupy integer cells. Zero denotes a leaf of a rooted tree; a positive handle denotes a fork whose children are in Initialize
nodes[t-1]. Only finite acyclic structures are admitted. An allocated fork's children are themselves valid handles.CONST MaxForks = 100000;
TYPE Tree = INTEGER;
Node = RECORD left, right: Tree END;
Arena = ARRAY MaxForks OF Node;
VAR nodes: Arena;
used: INTEGER;
PROCEDURE NewFork(left, right: Tree): Tree;
BEGIN
ASSERT(used < MaxForks);
nodes[used].left := left; nodes[used].right := right;
INC(used);
RETURN used
END NewFork;
PROCEDURE Preorder(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER);
PROCEDURE Visit(p: Tree);
BEGIN
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
Visit(nodes[p-1].left); Visit(nodes[p-1].right)
END
END Visit;
BEGIN
count := 0; Visit(t)
END Preorder;used := 0 before constructing any trees; NewFork allocates within this arena. The fixed capacity is an implementation parameter and may be replaced by a dynamically allocated arena. The returned prefix out[0..count) encodes Boolean values by and . This encoding is part of the chosen representation, not a conversion of a pointer into a Boolean value.The recursion invariant is that
Visit(p) appends exactly the preorder traversal of the subtree represented by p. If the full binary tree has forks, it has leaves; henceEach occurrence is visited once, using linear time complexity and a call stack bounded by the height of a binary tree. The arena is the input representation, not an extra copy made by the traversal.Let be the final output length, the number of emitted markers, and the number of pending handles. Each pending subtree contributes at least one future marker, soStore output from the low end and the stack from the high end of the same array. A pop frees one cell before the next write. For a fork, the two pushed children each account for at least one of the remaining markers. Thus the two regions never overlap.The loop invariant includes
PROCEDURE PreorderShared(t: Tree; VAR out: ARRAY OF INTEGER;
VAR count: INTEGER);
VAR top, cap: INTEGER; p: Tree;
BEGIN
cap := LEN(out); count := 0;
top := cap-1; out[top] := t;
WHILE top < cap DO
p := out[top]; INC(top);
IF p = 0 THEN
out[count] := 0; INC(count)
ELSE
out[count] := 1; INC(count);
DEC(top); out[top] := nodes[p-1].right;
DEC(top); out[top] := nodes[p-1].left
END
END
END PreorderShared;count <= top, with pending handles in out[top..cap) and final markers in out[0..count). The preceding accounting proves every intermediate write also respects array bounds. This uses the integer handle representation chosen in part (b). Simply putting a pointer into a genuinely Boolean-typed cell would not be valid Oberon.An Oberon pointer refers to a record containing an integer label and two subtree references:Use
TYPE
Tree = POINTER TO Node;
Node = RECORD
left, right: Tree;
label: INTEGER
END;NIL for the empty binary tree, including either absent child. The representation invariant requires a finite, acyclic binary tree with disjoint left and right subtrees. In particular, shared nodes would represent a different structure and invalidate destructive traversal arguments.Use binary search on an interval with unequal endpoint values. The array need not be sorted:The loop invariant isIt holds initially by the given endpoint inequality, which also implies . When , . If , replacing maintains unequal endpoints. Otherwise , so replacing maintains them. This does not require monotonicity or even just two possible values.
l := 0; r := n;
WHILE r-l > 1 DO
m := l + (r-l) DIV 2;
IF b[l] # b[m] THEN r := m ELSE l := m END
END;
k := l;The positive integer width is a loop variant, reduced to at most its old half rounded up. On exit , givingThere are at most iterations. The additive constant handles .
Maintain an integer The precondition is the abstract capacity condition. Appending at the first unused array index establishes in constant running time.
len, initially zero, with len = length xs:PROCEDURE Add(x: INTEGER);
BEGIN
ASSERT(len < N);
u[len] := x;
len := len+1
END Add;If
get(k) first applies a comparison sort to all entries, the comparison sorting lower bound gives at least comparisons in the worst case. A merge sort or heapsort meets that order, after which indexing costs constant time:This is a logarithmic factor worse than linear. The qualification to comparison sorting is necessary: merely saying that keys are integers does not prohibit counting sort for a bounded small range or radix sort under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.Represent a multiset by a pure multiplicity function. Every operation returns a new function describing updated counts:An empty instance is
class ContraMSet[-T](f: T => Int) {
def count(x: T): Int = f(x)
def insert(x: T): ContraMSet[T] =
new ContraMSet[T]((y: T) => f(y) + (if (y == x) 1 else 0))
def delete(x: T): ContraMSet[T] =
new ContraMSet[T]((y: T) => {
val old = f(y)
if (y == x && old > 0) old - 1 else old
})
def union[U <: T](that: ContraMSet[U]): ContraMSet[U] =
new ContraMSet[U]((y: U) => this.count(y) + that.count(y))
}new ContraMSet[T]((_: T) => 0). The constructor's precondition is that f is pure and gives a nonnegative integer count, with finite support of a multiset if only finite multisets are intended. Nonnegativity and the support condition are preserved by each operation. Integer overflow must be excluded for this fixed-width count interface.A contravariant type parameter makes
ContraMSet[T] a consumer of values of type T. Thus a counter able to answer queries for every animal can also answer queries restricted to cats. It does not expose or enumerate stored T values. The return type ContraMSet[T] is legal: its outer covariant result position and the class's contravariant argument position together place negatively.For
union, the argument itself is in a negative position, while its ContraMSet argument would reverse that sign. Using ContraMSet[T] directly as the parameter type would therefore put positively and fail the variance-position rule. Introduce : both operands can count every U, and their sum is a ContraMSet[U]. This is a restriction to a common query domain; operations do not promise to preserve counts outside the narrowed domain.[ref]Scala 2.11 basic declarations and definitions specification. Type Parameters, Variance Annotations; bounds and sign changes
Pointwise evaluation givesNo old function is modified, so updates preserve immutable object. Constructing each wrapper takes constant work, but a later
count may traverse a chain of previously created programming closures; its running time need not be constant in the history length. This functional representation trades enumeration and direct storage of occurrences for composable counting behavior.We prove the contrapositive. If , Euclidean division gives or for an integer . Squaring gives respectively or . Both have remainder upon division by , so . Taking the contrapositive yields .
For a proof by contradiction, suppose for positive integers in lowest terms, so . Squaring gives , and part (a) implies . Write ; then , hence , and part (a) again implies . This contradicts the coprimality of . Therefore is an irrational number.
For each fixed positive integer , part (i) gives . This meets big O notation with constant and threshold . True: for fixed . The constant may depend on ; no claim uniform in a varying is required.
Use the symmetric tree fold equations for the other algebraic data type:The most general type signatures, using the same schematic variable names independently for each function, areFor
foldZag (fZag,eZag) (fZig,eZig) Nal = eZag
foldZag (fZag,eZag) (fZig,eZig) (Cans x z) =
fZag x (foldZig (fZig,eZig) (fZag,eZag) z)foldZig :: (a -> s -> r, r) -> (b -> r -> s, s)
-> Zig a b -> r
foldZag :: (a -> s -> r, r) -> (b -> r -> s, s)
-> Zag a b -> rfoldZig, the first empty value has type r, so the first combining function must return r. Its label argument has type a. The recursively folded tail has some independent result type s, giving a -> s -> r. The second combining function consumes a b label and an r result and returns s, giving b -> r -> s. The second empty value has type s. Swapping the two handler pairs and the label types makes the recursive call well-typed. The identical argument applies to foldZag.The two result types need not coincide. For example, one handler can return an integer and the other a list; forcing both results to have one type would lose parametric polymorphism allowed by the definitions.
Evaluate the supplied function once at each positive integer, retaining its largest value so far. In particular do not initialize the maximum to zero: might be negative everywhere.At the loop head the loop invariant is ,
PROCEDURE record(f, emit);
VAR n, best, y: INTEGER;
BEGIN
best := f(1);
emit(1);
n := 2;
WHILE TRUE DO
y := f(n);
IF y > best THEN
emit(n);
best := y
END;
n := n + 1
END
END record;best , and precisely the record values with argument less than have been emitted, in increasing argument order. The first argument is a record because its comparison set is empty. The strict test correctly excludes ties. Updating best only on a strict increase preserves the loop invariant.Exactly one call of
f is made per processed argument. For an arbitrary supplied function, an unexamined argument can have a value larger than all previous values, so skipping its evaluation cannot be correct in general. This assumes is a total, deterministic function; the requested infinite computation ignores integer overflow.Use the Euclidean algorithm with floor quotient and nonnegative remainder, including for a negative numerator:For , Euclidean division gives with . If , the singleton
PROCEDURE rat2cf(n, d: INTEGER): fraction;
VAR q, r: INTEGER; p: fraction;
BEGIN
q := n DIV d; r := n MOD d;
NEW(p); p.head := q; p.tail := NIL;
IF r # 0 THEN p.tail := rat2cf(d, r) END;
RETURN p
END rat2cf;[q] is exact. Otherwiseso the recursive tail represents . Its numerator is positive and greater than its denominator, so every tail head is a positive integer. The new denominator is strictly smaller than , proving algorithm termination by descent through the positive integers.The returned list represents exactly . For example gives
[-3,1,2]; truncating negative division toward zero would violate the required positivity of the tail. There are Euclidean algorithm steps, with output allocation and recursive stack depth linear in the number of generated nodes.