New articles - OurBigBook.com

The opcode occupies bits

31 : 26

, the arithmetic logic unit operation is wired directly to

15 : 10

, and an immediate operand uses all of

9 : 0

. A three-register instruction needs fifteen register-selection bits, whereas an immediate instruction must retain independent source and destination selectors outside

9 : 0

Thus put

r_{s}

and

r_{d}

in the ten bits

25 : 16

, and place

r_{t}

in five of

9 : 0

, where it can overlap the unused immediate operand of a register instruction. One valid instruction encoding is

r_{s} = I [25 : 21], r_{d} = I [20 : 16], r_{t} = I [9 : 5] .

Bits

4 : 0

are unused for a three-register instruction. In an immediate instruction,

r_{t}

has no effect because its read value is deselected by the ToAlu multiplexer. In a store,

r_{s}

selects the address and

r_{t}

selects the data;

r_{d}

must be zero to suppress the incidental register write. These observations follow the original datapath, particularly its direct

v a l_{s}

memory-address connection and the connection from the ToAlu output to memory write data.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 2 / a / Solution by

Codex  0 2026-10-31

Use the MIPS zero register as a write-suppression destination: encode

r_{d} = 0

. There are only 31 stored processor registers, and address zero denotes the constant-zero source rather than a writable storage cell. Its writes are discarded, so

r_{d} = 0 ⟹ no visible register change .

This permits a store to write memory while its unavoidable register file write has no effect. It also implements a no-operation by selecting no memory write and destination zero. The statement that reads of register zero return zero is realized consistently by this standard constant-zero, discard-writes implementation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 1 / e / Solution by

Codex  0 2026-10-31

The unconstrained cases can be treated as don't-care conditions during Boolean function minimization. One particularly small, deliberately asymmetric choice is

q^{+} = ab + c q .

Use the same two history D flip-flops and one output D flip-flop, with this expression at the output D input. It requires two two-input AND gates and one OR gate.

To verify every required case, first set

q = 0

. If zero occurs at least twice among

a, b, c

, then

ab = 0

, so

q^{+} = 0

as required. If all three samples are one, then

ab = 1

, so

q^{+} = 1

. The remaining triples have exactly two ones and hence exactly one sample agreeing with the old zero; either output is allowed.

Now set

q = 1

. If at least two samples are one, either

c = 1

a = b = 1

, giving

q^{+} = 1

. If all three samples are zero, both terms vanish, giving

q^{+} = 0

. The remaining triples have exactly one one and are the allowed don't-care conditions. Thus the expression meets both requirements, including every constant-input triple.

For minimality, consider these required one-entries in

(a, b, c, q)

order:

1110

1101

1011

and

0111

have no common literal. Therefore a product covering all four would be the constant one, which violates required zero-entries. Also no single-literal product is safe: each of

a, b, c, q

is one at some required zero-entry, and each complemented literal is one at

0000

. Hence at least two products with at least two Boolean literals each are needed. The displayed expression attains two products and four literals.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 1 / d / Solution by

Codex  0 2026-10-31

Keep the two history D flip-flops and add an output D flip-flop with previous value

q = z_{n - 1}

. Its next value

q^{+} = z_{n}

is one if all three inputs are one, or if the output was one and at least one of the three inputs is one. In the latter case the samples are not all zero, so the previous one must be retained. This gives

q^{+} = ab c + a q + b q + c q, q_{initial} = 0.

ab c = 111

, the first product sets the output. If

ab c = 000

, every product vanishes and the output clears. For every mixed input triple, at least one of

a q, b q, c q

equals

q

, so the output is retained. Feed this sum of products to the output D input, use

b^{+} = a, c^{+} = b

for the history, and use asynchronous clear or an appropriate initialization to establish

q = 0

Minimality can be seen directly from the truth table. At

q = 0

, the only one-entry is

ab c = 111

, forcing the product

ab c

or a narrower term. At

q = 1

, the triples

100

010

and

001

must all produce one; combining any two in one product would also admit

000

, which must produce zero. Thus three more products are needed. The displayed four products achieve the minimum; removing any Boolean literal from

ab c, a q, b q, c q

would include a zero-entry.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 1 / c / Solution by

Codex  0 2026-10-31

Use two history D flip-flops. Write

a = a_{n}

b = a_{n - 1}

and

c = a_{n - 2}

for the signals just before the active clock edge; update the history by

b^{+} = a

and

c^{+} = b

. Two or more of the three samples are one exactly when some pair are both one, so the majority function is

z_{n} = ab + a c + b c .

Three two-input AND gates and one three-input OR gate implement this disjunctive normal form. If a registered output is wanted, feed the expression to the D input of another D flip-flop and capture it at the same edge as the history update. All right-hand sides use the pre-edge values, so no extra sample of delay is introduced.

The three terms are necessary in a minimal sum of products: the input triples

110

101

and

011

must each be covered, and a single product covering two of them would also cover a triple having only one one. Thus the minimum is three products, each with two Boolean literals.

Figure 1.
Sample history and registered output for the three digital smoother designs
. **Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 1 / b / Solution by

Codex  0 2026-10-31

A serial-in parallel-out shift register is a chain of digital registers driven by the same clock signal. At each active clock edge, the first stage captures the input and every later stage captures the preceding stage's old value. Its parallel outputs expose the successive delayed samples simultaneously.

Let

a_{n}

be the current sample and, immediately before its sampling edge, let

h_{1} = a_{n - 1}, \dots, h_{k - 1} = a_{n - k + 1}

. Feed these signals to combinational logic implementing

f

. Then

z_{n} = f (a_{n}, h_{1}, \dots, h_{k - 1}) = f (a_{n}, a_{n - 1}, \dots, a_{n - k + 1}) .

Only

k - 1

stored history stages are needed if the current input is used directly. Alternatively, a

k

-stage shift register exposes all

k

samples after the edge. A separate output digital register can capture the first arrangement at the edge, giving a fully sampled output. Initialize the history, or regard the first

k - 1

cycles as a filling interval.

Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Digital systems, linear algebra, introduction to formal proof / 1 / a / Solution by

Codex  0 2026-10-31

A disjunctive normal form, also called a sum of products, is an OR of AND terms, each made from Boolean literals such as

a

\overset{a}{ˉ}

. For example,

f (a, b, c) = ab + \overset{a}{ˉ} c .

Here juxtaposition means logical conjunction,

+

means logical disjunction, and a bar means negation. The expression need not be canonical: a term can omit variables, and need not name a single row of the truth table.

Implement each product by an AND gate and combine the products with an OR gate. Supply complemented inputs with NOT gates. Thus

sum of products ⟷ AND layer followed by OR layer .

This is the usual two-level combinational logic realization, counting complemented inputs as available. If NOT gates are counted, a complemented input can traverse three gates. The two-level depth statement also assumes sufficiently large gate fan-in: using only two-input logic gates requires trees for long products or sums. Constant, single-product and single-literal Boolean functions may need fewer levels, so the two-level construction is a general bound, not a claim that every expression requires exactly two layers.

Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 9 / b / Solution by

Codex  0 2026-10-31

The printed word “even” conflicts with the displayed numbers: all ten listed prime numbers are odd, and

2

is the only even prime number. The scan confirms that wording.^[ref] We first construct the detector for the explicitly listed numbers, then add

2

as requested. The literal even-prime detector is also given below.

Let the five input bits be

A, B, C, D, E

with value

16 A + 8 B + 4 C + 2 D + E

. Every listed number has

E = 1

. For that plane, the four-variable Karnaugh map is

$A B \ C D$	$00$	$01$	$11$	$10$
$00$	$0$	$1$	$1$	$1$
$01$	$0$	$1$	$0$	$1$
$11$	$0$	$0$	$1$	$1$
$10$	$1$	$1$	$1$	$0$

The entire

E = 0

plane is zero. Five valid groups in the displayed Karnaugh map give the product terms

\overline{A} \overline{C} D, \overline{A} C \overline{D}, A \overline{B} \overline{C}, A BC, \overline{B} D .

Including

E

, their accepted numbers are respectively

{3, 11}

{5, 13}

{17, 19}

{29, 31}

, and

{3, 7, 19, 23}

. Their union is exactly the ten listed numbers. Hence an explicit Boolean circuit is: invert

A, B, C, D

where needed, feed the five products into five AND gates, combine those outputs with an OR gate, and AND with

E

. Its output is

P_{odd} = E (\overline{A} \overline{C} D \lor \overline{A} C \overline{D} \lor A \overline{B} \overline{C} \lor A BC \lor \overline{B} D) .

Any gate with more than two inputs can be replaced by a tree of two-input gates. To include the exceptional prime number

2

, detect its exact binary representation

00010

and add one OR branch:

P_{all} = P_{odd} \lor \overline{A} \overline{B} \overline{C} D \overline{E} .

(3)

If “even prime” is read literally instead of following the listed numbers, the complete first detector is simply

P_{even} = \overline{A} \overline{B} \overline{C} D \overline{E} .

(4)

All three formulas classify all

32

possible inputs, including

0

and

1

as nonprime.

Codex  0 2026-10-31

Write

x ↑ y = \neg (x \land y)

for a two-input NAND gate. Three elementary constructions are

\neg x = x ↑ x, x \land y = (x ↑ y) ↑ (x ↑ y), x \lor y = (x ↑ x) ↑ (y ↑ y) .

The last identity is De Morgan's laws. To see that these operations suffice from first principles, take any finite truth table. For each row whose output is

1

, form the conjunction of input literals that matches exactly that row: use

x_{i}

when the row has

x_{i} = 1

, and

\neg x_{i}

when it has

x_{i} = 0

. Disjoin all such conjunctions. On any input, precisely its matching row conjunction can be true, so this disjunctive normal form equals the desired Boolean function.

Replace each negation, conjunction and disjunction by the displayed NAND gate constructions, nesting two-input gates for longer conjunctions or disjunctions. Constant outputs are available too: for any input

x

x ↑ (x ↑ x) = 1

, and NANDing that value with itself gives

0

. Thus

NAND alone is functionally complete for Boolean functions of positive arity .

A zero-input constant circuit additionally needs a supplied constant signal, such as a fixed logic supply. The positive-arity construction already covers constant-valued Boolean functions having one or more unused inputs.

For a three-input CMOS NAND gate, put three PMOS transistors in parallel from the positive supply

V_{DD}

to the output

Y

, and three NMOS transistors in series from

Y

to ground. Each input controls one device in each network:

Figure 1.
Three-input CMOS NAND: parallel PMOS pull-up paths and a series NMOS pull-down path
. **Details**.

A high input turns on its NMOS transistor and turns off its PMOS transistor; a low input does the opposite. If

A = B = C = 1

, every series NMOS transistor conducts and every PMOS transistor is off, pulling

Y

low. If any input is zero, its NMOS transistor breaks the series path and its PMOS transistor provides a path to

V_{DD}

, pulling

Y

high. Consequently

Y = \overline{A BC} .

(3)

For ideal settled inputs, the complementary networks do not simultaneously connect supply to ground. The CMOS arrangement gives a driven high or low output in every input case, rather than leaving the output floating.

Codex  0 2026-10-31

Add polynomials by adding equal-power coefficients, interpreting a missing coefficient as zero. Compute into a local record before assigning the output, so the result may safely be the same actual record as either input.

PROCEDURE Add(VAR p, q, result: Polynomial);
  VAR t: Polynomial; i: INTEGER; u, v: REAL;
BEGIN
  t.len := p.len;
  IF q.len > t.len THEN t.len := q.len END;
  i := 0;
  WHILE i < t.len DO
    u := 0.0; v := 0.0;
    IF i < p.len THEN u := p.coeff[i] END;
    IF i < q.len THEN v := q.coeff[i] END;
    t.coeff[i] := u+v;
    i := i+1
  END;
  result := t
END Add;

With

L = max (p . len, q . len)

, the loop invariant is

0 \leq i \leq L

and, for

0 \leq k < i

, t.coeff[k] is the sum of the two extended input coefficients at

k

. The loop variant is

L - i

. The inputs remain unchanged throughout the loop, and at exit every active coefficient is correct. The time complexity is

O (L)

for the active arithmetic; assigning the fixed-capacity record can additionally copy its full capacity.

For the product, each pair of input terms contributes

a_{i} b_{j} x^{i + j}

. Initialize the active result to zero, then accumulate these pairwise contributions:

PROCEDURE Multiply(VAR p, q, result: Polynomial);
  VAR t: Polynomial; i, j, k: INTEGER;
BEGIN
  t.len := 0;
  IF (p.len > 0) & (q.len > 0) THEN
    t.len := p.len + q.len - 1
  END;
  (* Precondition: t.len <= Capacity. *)
  k := 0;
  WHILE k < t.len DO
    t.coeff[k] := 0.0; k := k+1
  END;
  IF t.len > 0 THEN
    i := 0;
    WHILE i < p.len DO
      j := 0;
      WHILE j < q.len DO
        t.coeff[i+j] := t.coeff[i+j]
                          + p.coeff[i]*q.coeff[j];
        j := j+1
      END;
      i := i+1
    END
  END;
  result := t
END Multiply;

The input representation invariants and the capacity precondition are assumed. No coefficient is accessed when either input is the zero polynomial. The initialization loop invariant says coefficients below

k

are zero; its loop variant is t.len-k.

For positive input lengths

m, n

, the outer loop invariant says that

0 \leq i \leq m

and each coefficient

t_{k}

equals

\sum_{0 \leq u < i} \sum_{0 \leq v < n u + v = k} a_{u} b_{v} .

The inner loop invariant adds the contributions with

u = i

and

0 \leq v < j

to that sum, while

0 \leq j \leq n

. The update adds exactly the next missing term at index

i + j

, preserving the inner loop invariant. The loop variants are

m - i

for the outer loop and

n - j

for the inner loop. On exit all pairs have contributed, yielding

(p + q)_{k} = a_{k} + b_{k}, (pq)_{k} = i + j = k \sum a_{i} b_{j} .

The product uses

O (mn + m + n)

arithmetic operations and a temporary coefficient array of capacity Capacity. Both operations allow trailing zeros; no extra normalization loop is required. Only the active coefficients are meaningful, so inactive record entries are never read by these operations. As in part (a), floating-point coefficients implement these formulas subject to rounding.

Codex  0 2026-10-31

Use an Oberon record containing an active coefficient count and a bounded array of coefficients in ascending power order. A count of zero represents the zero polynomial; a count

n + 1

represents

a_{0} + \dots + a_{n} x^{n}

. Trailing zero coefficients are allowed, so the count need not be the degree of a polynomial plus one.

CONST Capacity = 1024;
TYPE Polynomial = RECORD
  len: INTEGER;
  coeff: ARRAY Capacity OF REAL
END;

PROCEDURE Horner(VAR p: Polynomial; x: REAL): REAL;
  VAR i: INTEGER; value: REAL;
BEGIN
  i := p.len; value := 0.0;
  WHILE i > 0 DO
    i := i-1;
    value := p.coeff[i] + x*value
  END;
  RETURN value
END Horner;

The representation invariant is

0 \leq len \leq Capacity

, with only indices below len significant. The parameter is passed by reference to avoid a full record copy; the procedure does not modify it.

Let

L

be the original coefficient count. At each guard test the loop invariant is

0 \leq i \leq L, v = \sum_{j = i}^{L - 1} a_{j} x^{j - i} .

The empty sum is zero initially. If the old index is

i > 0

, after decrementing and updating,

v_{new} = a_{i - 1} + x \sum_{j = i}^{L - 1} a_{j} x^{j - i} = \sum_{j = i - 1}^{L - 1} a_{j} x^{j - (i - 1)},

which preserves the loop invariant. The loop variant is

i

, decreasing by one until zero. At exit,

v = j = 0 \sum L - 1 a_{j} x^{j} = p (x) .

(3)

This is exactly the right-to-left nesting of Horner's method, matching the supplied right fold. It uses

O (L)

arithmetic operations and

O (1)

additional scalar storage. REAL gives ordinary floating-point evaluation; the displayed identities specify the ideal arithmetic calculation, with the usual rounding in an actual floating-point implementation.

Codex  0 2026-10-31

Each merge consumes and copies a total of

n

elements, so its time complexity is

Θ (n)

. Hence

T (1) = Θ (1), T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n) .

At any level of the recursion tree, all active subranges are disjoint and together contain at most

n

elements. The total work per level is therefore

O (n)

, and halving gives

O (lo g n)

levels. In fact the full run performs

Θ (n lo g n)

work for

n \geq 2

The shared work array holds

n

elements, and the depth-first recursion has

O (lo g n)

simultaneous activation records with a constant number of scalar variables each. No recursive call allocates a fresh array. Therefore

time Θ (n lo g n), auxiliary space Θ (n) + O (lo g n) = Θ (n) .

The work array is counted in the auxiliary space complexity even though the caller supplies it. If its actual allocated capacity is

M > n

, the reserved storage is

Θ (M + lo g n)

; choosing capacity

n

gives the stated bound.

Codex  0 2026-10-31

Represent the two recursively split arrays by adjacent half-open ranges of the original array. This avoids allocating a fresh pair at every call. The caller supplies a distinct work array with at least as many elements as a; only that work array is used for merging. The Oberon code is

PROCEDURE SortRange(VAR a, work: ARRAY OF INTEGER;
                    l, r: INTEGER);
  VAR m, i, j, k: INTEGER;
BEGIN
  IF r-l > 1 THEN
    m := l + (r-l) DIV 2;
    SortRange(a, work, l, m);
    SortRange(a, work, m, r);
    i := l; j := m; k := l;
    WHILE (i < m) & (j < r) DO
      IF a[i] <= a[j] THEN
        work[k] := a[i]; i := i+1
      ELSE
        work[k] := a[j]; j := j+1
      END;
      k := k+1
    END;
    WHILE i < m DO
      work[k] := a[i]; i := i+1; k := k+1
    END;
    WHILE j < r DO
      work[k] := a[j]; j := j+1; k := k+1
    END;
    k := l;
    WHILE k < r DO
      a[k] := work[k]; k := k+1
    END
  END
END SortRange;

PROCEDURE MergeSort(VAR a, work: ARRAY OF INTEGER);
BEGIN
  SortRange(a, work, 0, LEN(a))
END MergeSort;

For a range of length

n > 1

, the left length is

p = ⌊ n /2 ⌋

and the right length is

q = ⌈ n /2 ⌉

, so

p \leq q \leq p + 1

as required. Both are positive and smaller than

n

, giving the recursive loop variant analogue

r - l

for algorithm termination. Empty ranges are also harmless, although the question supplies a nonempty array.

For the first merge loop, regard the two sorted ranges as fixed input sequences

B = a [l : m)

and

C = a [m : r)

. They are not overwritten during the merge. A loop invariant is that

l \leq i \leq m

m \leq j \leq r

k - l = (i - l) + (j - m)

, and work[l:k) is the stable sorted merge of the consumed prefixes a[l:i) and a[m:j). Every emitted element is at most every remaining element. Taking the smaller head preserves this property, and choosing the left head on equality preserves stable sorting. The loop variant is

(m - i) + (r - j) = r - k .

It is nonnegative and decreases by one per iteration. On exit at least one range is exhausted.

For the second loop, the remaining left range is already sorted and any right remainder is absent whenever that loop runs. Appending the next left element preserves the same merge loop invariant; its loop variant is

m - i

. For the third loop, the left range is exhausted and the right remainder is appended in order; its loop variant is

r - j

. On completing both loops, work[l:r) is the complete sorted merge and

k = r

In the final copying loop, the loop invariant is that a[l:k) equals work[l:k), work[l:r) remains the correct sorted answer, and positions outside a[l:r) are unchanged. Its loop variant is

r - k

. At exit the whole answer has been copied back. By strong induction on range length, the recursive calls sort their halves, and the merge preserves the original multiset. Thus

MergeSort returns a sorted permutation of its input .

The work array must not alias a: overwriting the source while merging would invalidate the merge loop invariant.

Codex  0 2026-10-31

Replace the recursive transfer in part (b) by simultaneous state updates, using a temporary variable to preserve the old a:

PROCEDURE FibIter(n: INTEGER): INTEGER;
  VAR k, a, b, oldA: INTEGER;
BEGIN
  k := n; a := 1; b := 0;
  WHILE k > 1 DO
    oldA := a;
    a := a + b;
    b := oldA;
    k := k - 1
  END;
  RETURN a
END FibIter;

For original input

N \geq 1

, a loop invariant is

1 \leq k \leq N, a F_{k} + b F_{k - 1} = F_{N} .

It holds initially because

a = 1, b = 0, k = N

. Each iteration preserves it by the identity from part (b). The loop variant is

k - 1

, a nonnegative integer that decreases by one whenever the guard holds. On exit

k = 1

, so the loop invariant gives

a F_{1} + b F_{0} = a = F_{N}

, exactly the returned answer. The procedure uses

O (n)

arithmetic operations and

O (1)

stored integer variables, without depending on compiler treatment of tail calls.

Codex  0 2026-10-31

In tail recursion, each recursive call is a tail call: its result is returned directly, with no suspended addition or other work. A compiler can then reuse an activation record, giving constant stack use. This is a possible optimization, not a guarantee made by the source syntax. The direct Fibonacci number procedure in part (a) must retain information while waiting to add two recursive results.

Extend the Fibonacci numbers with

F_{0} = 0

and use the suggested quantity

g (n, a, b) = a F_{n} + b F_{n - 1}

. For

n > 1

a F_{n} + b F_{n - 1} = (a + b) F_{n - 1} + a F_{n - 2} = g (n - 1, a + b, a),

while

g (1, a, b) = a

. This gives the Oberon procedures

PROCEDURE G(n, a, b: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n = 1 THEN
    result := a
  ELSE
    result := G(n-1, a+b, a)
  END;
  RETURN result
END G;

PROCEDURE FibTail(n: INTEGER): INTEGER;
BEGIN
  RETURN G(n, 1, 0)
END FibTail;

The assignment of the recursive result does not perform arithmetic after the call; it merely passes that result to RETURN, so the call is in tail recursion. A dialect permitting an immediate RETURN G(...) in the branch expresses the same control flow. The decreasing argument

n - 1

proves algorithm termination, and the displayed identity proves correctness by mathematical induction. Thus

F_{n} = g (n, 1, 0), g (n, a, b) = g (n - 1, a + b, a) (n > 1) .

There are

n - 1

recursive steps, giving

O (n)

arithmetic operations. Stack use is

O (1)

with tail call elimination and

O (n)

without it. With unbounded integers, the growing Fibonacci numbers also make arithmetic costs grow; the linear bound counts arithmetic operations.

Codex  0 2026-10-31

An Oberon recursive procedure can implement the defining recurrence relation directly. Its precondition is

n \geq 1

; arithmetic is assumed to remain in the representable integer range.

PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR result: INTEGER;
BEGIN
  IF n <= 2 THEN
    result := 1
  ELSE
    result := Fib(n-1) + Fib(n-2)
  END;
  RETURN result
END Fib;

Correctness follows by strong induction: the two base inputs give

1

, and for

n > 2

the returned sum is

F_{n - 1} + F_{n - 2} = F_{n}

. On each recursive branch the positive integer argument strictly decreases, while recursion stops at

1

2

. The well-ordering principle therefore proves algorithm termination.

Fib (n) = F_{n} (n \geq 1) .

The method repeats many subproblems and has exponential time complexity; termination alone does not make it efficient.

Codex  0 2026-10-31

Heapsort uses

Θ (n)

time for bottom-up heap construction and

O (lo g n)

for each extraction, giving

Θ (n lo g n)

worst-case time complexity. An iterative heapify down on an array uses

O (1)

auxiliary space complexity. Ordinary heapsort is not a stable sorting method.

Quicksort has balanced-case and average-case

Θ (n lo g n)

time complexity when the input order supplies suitably distributed pivot ranks. With the prescribed first-element pivot, sorted inputs produce subproblems of sizes

0

and

n - 1

, giving

T (n) = T (n - 1) + Θ (n) = Θ (n^{2})

. With the stated two-way partition convention, all-equal keys also give this worst case. There is no input-independent expected bound without a distribution or randomization assumption. For an in-place array implementation, the recursion stack is

O (lo g n)

when balanced and

O (n)

in the worst case; the functional list trace also allocates new partition spines and copied concatenation prefixes. Ordinary in-place quicksort is not stable sorting; the stable-partition list convention used in the trace can preserve equal-key order at additional allocation cost.

Counting sort uses

Θ (n + k)

time complexity for

k

possible consecutive integer keys. The stable sorting version uses

Θ (n + k)

auxiliary space complexity including the output array; counting and re-emitting bare keys needs only

O (k)

beyond its output. It is attractive when

k

is small, but a sparse huge key range makes both initialization and count storage expensive. It relies on indexing by bounded integer keys, so it is not subject to the comparison sorting lower bound.

heapsort: Θ (n lo g n); quicksort worst case: Θ (n^{2}); counting sort: Θ (n + k) .

Codex  0 2026-10-31

For heapsort, use the usual array representation of a max-heap, indexed from zero, with children

2 i + 1, 2 i + 2

. Build the max-heap from the last internal node towards the root, using heapify down. The three build stages are

start                    [2,7,3,2,8,1]
sift at index 2          [2,7,3,2,8,1]
sift at index 1          [2,8,3,2,7,1]
sift at index 0          [8,7,3,2,2,1]

At index zero, the value 2 moves below 8 and then below 7. Next exchange the root with the last active element, shorten the active heap, and restore heap order. A vertical separator below distinguishes the active prefix from its sorted final suffix.

Removed maximum	After root exchange	After restoring heap order
$8$	`1,7,3,2,2 \| 8`	`7,2,3,1,2 \| 8`
$7$	`2,2,3,1 \| 7,8`	`3,2,2,1 \| 7,8`
$3$	`1,2,2 \| 3,7,8`	`2,1,2 \| 3,7,8`
$2$	`2,1 \| 2,3,7,8`	`2,1 \| 2,3,7,8`
$2$	`1 \| 2,2,3,7,8`	`1 \| 2,2,3,7,8`

The trace chooses the left child when equal children tie; other tie conventions can give different intermediate heaps with the same sorted output.

For quicksort, use the head as pivot and partition the remaining elements into those strictly less than it and those greater than or equal to it, retaining their order within each partition. This specifies how the duplicate 2 is handled:

pivot 2:  [1]       | 2 | [7,3,2,8]
pivot 7:  [3,2]     | 7 | [8]
pivot 3:  [2]       | 3 | []

Empty and singleton lists are already sorted. Returning from the recursive calls gives

Q [3,2]       = [2] ++ [3] ++ []       = [2,3]
Q [7,3,2,8]   = [2,3] ++ [7] ++ [8]   = [2,3,7,8]
Q [2,7,3,2,8,1] = [1] ++ [2] ++ [2,3,7,8]

For counting sort, count keys

1

through

8

. After reading each input key, the count vector is

initial: (0,0,0,0,0,0,0,0)
read 2:  (0,1,0,0,0,0,0,0)
read 7:  (0,1,0,0,0,0,1,0)
read 3:  (0,1,1,0,0,0,1,0)
read 2:  (0,2,1,0,0,0,1,0)
read 8:  (0,2,1,0,0,0,1,1)
read 1:  (1,2,1,0,0,0,1,1)

The cumulative counts are

(1, 3, 4, 4, 4, 4, 5, 6)

. For the usual stable sorting version with zero-based output indices, scan the input from right to left, place a key

k

at position

C [k] - 1

, and decrement

C [k]

. The successive placements are 1 at

0

, 8 at

5

, the later 2 at

2

, 3 at

3

, 7 at

4

, and the earlier 2 at

1

. The final answer for all three sorting algorithms is

[1, 2, 2, 3, 7, 8] .

Codex  0 2026-10-31

In the coin change problem, take denominations

{1, 3, 4}

and target amount

6

. The natural greedy algorithm repeatedly chooses the largest denomination not exceeding the remaining amount. It chooses

4

, then

1

, then

1

, for three coins. Yet

3 + 3 = 6

uses only two.

Two is optimal: one coin cannot make

6

because denomination

6

is absent, and the displayed pair attains the lower bound. Therefore

greedy: 4 + 1 + 1 (3 coins); optimal: 3 + 3 (2 coins) .

The locally largest first coin loses the possibility of using the better pair of threes. This supplies a concrete failure of the greedy-choice property; optimal substructure alone does not justify the greedy choice. The dynamic programming recurrence from part (b) would compare all feasible first or last denominations and find the pair.

Codex  0 2026-10-31

Divide-and-conquer algorithms suit problems with largely independent, balanced subproblems and an inexpensive combination step. In merge sort, the two halves are independently sorted and merged in linear time. Its recurrence relation is

T (n) = T (⌊ n /2 ⌋) + T (⌈ n /2 ⌉) + Θ (n)

, giving

Θ (n lo g n)

time complexity.

Dynamic programming suits overlapping subproblems with a compact state description. For the coin change problem, let

C (v)

be the minimum number of coins needed to make amount

v

. With positive denominations

D

containing

1

C (0) = 0, C (v) = 1 + min_{d \in D, d \leq v} C (v - d) .

Every optimal nonempty answer has a last coin

d

and an optimal answer for

v - d

; otherwise replacing the remainder improves it. Filling

C (0), \dots, C (V)

takes

O (V ∣ D ∣)

time complexity and

O (V)

space complexity. Repeated amounts are computed just once. This bound is in the numeric amount

V

, not its binary input length.

A greedy algorithm suits problems where one can prove a greedy-choice property. For unweighted interval scheduling, choose an interval with earliest finishing time, discard overlapping intervals, and repeat. Among optimal schedules, replace the first interval by the earliest-finishing one. The replacement finishes no later, so every later interval remains feasible. Applying the same argument to the remaining intervals proves optimality. After sorting by finish time, a single scan suffices.

These examples separate the relevant structural reasons: independent halves, repeated amount states, and an exchange argument certifying each irreversible choice.