MATH40006 Practice Paper A Solutions

Notes — cell 1

# MATH40006 - Introduction to Computation

## Practice Paper Paper A - Executed solutions

**REVIEW CANDIDATE - NOT PUBLISHED**

- Practice duration: 90 minutes
- Total: 75 marks; answer all three questions
- Work in this single Jupyter notebook.
- Use code cells for programs, tests, figures and requested output.
- Use Markdown answer cells for explanations, invariants, derivations and comments.
- No external files, network access, `input()` or package installation are required.
- Before submission, restart the kernel and run all cells from top to bottom.

The 90-minute/75-mark structure is a review assumption based on the nearest
alternative-assessment precedent and must be checked against Tony's own notice.

Code — cell 2

%matplotlib inline
import sys
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
print('Environment ready:', sys.version.split()[0], 'NumPy', np.__version__, 'Matplotlib', matplotlib.__version__)

Environment ready: 3.12.10 NumPy 2.3.5 Matplotlib 3.11.1

Notes — cell 3

## Question 1 (30 marks): Modular exponentiation under constraints

Here `a` is an integer, `b` is a non-negative integer and `m >= 2` is an
integer. Your implementations must not use `**` or `pow`; three-argument
`pow(a, b, m)` may be used only as an independent test oracle.

**(a) [5]** Write `mod_power_linear(a,b,m)` using exactly `b` repeated
modular multiplications. It must handle `b=0` and negative `a`.

**(b) [4]** Give four assertions: a typical case, `b=0`, a negative base and
a non-prime modulus. Explain in Markdown why each test is useful.

**(c) [4]** Write `mod_power_linear_count`, returning the residue and
multiplication count. State the exact count and Theta running time in `b`.

**(d) [8]** Write `mod_power_fast(a,b,m)` using one while-loop, repeated
squaring, `%` and `//`. Do not first construct the binary digits.

**(e) [4]** Compare the fast result with `pow(a,b,m)` on at least four cases,
including `b=0` and an exponent above one million. Explain why the linear
routine is unsuitable as the large-case oracle.

**(f) [5]** In Markdown, state a loop invariant involving `result`, `base`
and the current exponent. Justify correctness and give the exact number of
iterations for `b>0` and the Theta time.

Notes — cell 4

### Q1 code answers for parts (a)-(e) - solution

Code — cell 5

def mod_power_linear(a, b, m):
    """Return a**b modulo m using b modular multiplications."""
    result = 1 % m
    base = a % m
    for _ in range(b):
        result = (result * base) % m
    return result


def mod_power_linear_count(a, b, m):
    """Return the linear modular power and its multiplication count."""
    result = 1 % m
    base = a % m
    count = 0
    for _ in range(b):
        result = (result * base) % m
        count += 1
    return result, count


def mod_power_fast(a, b, m):
    """Return a**b modulo m by binary exponentiation."""
    result = 1 % m
    base = a % m
    exponent = b
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % m
        base = (base * base) % m
        exponent //= 2
    return result


assert mod_power_linear(3, 4, 7) == pow(3, 4, 7)  # typical case
assert mod_power_linear(2, 0, 5) == 1             # empty product
assert mod_power_linear(-3, 5, 7) == pow(-3, 5, 7)
assert mod_power_linear(5, 6, 8) == pow(5, 6, 8)  # composite modulus
assert mod_power_linear_count(7, 13, 19)[1] == 13

cases = [(2, 0, 5), (-3, 5, 7), (5, 6, 8), (7, 128, 13),
         (123456789, 1000003, 1000000007)]
for a, b, m in cases:
    assert mod_power_fast(a, b, m) == pow(a, b, m)

Code — cell 6

print("A1 deterministic assertions passed; sample fast result:", mod_power_fast(7, 128, 13))

A1 deterministic assertions passed; sample fast result: 3

Notes — cell 7

### Q1 written answers for parts (b), (c), (e) and (f) - solution

The four tests separately cover the ordinary recurrence, the empty-product case, reduction of a negative base, and the absence of any prime-modulus assumption. The linear method makes exactly b modular multiplications and is Theta(b). For the fast method, `result*base**exponent` remains congruent to `a**b (mod m)`. When the exponent reaches zero, `result` is the answer. For b>0 there are floor(log2(b))+1 loop iterations and Theta(log b) unit-cost modular multiplications. The linear routine is not a sensible oracle for a million-plus exponent because its work grows linearly; built-in three-argument `pow` is an independent logarithmic oracle.

Notes — cell 8

## Question 2 (35 marks): A vectorised logistic-map experiment

For parameter `r` and state `x`, define `f_r(x)=r*x*(1-x)`, with
`0 <= r <= 4` and `0 <= x <= 1`. Time is sequential, but all parameter values
must advance together in arrays.

**(a) [3]** Write `logistic_step(r,x)` as one broadcast-compatible NumPy
expression.

**(b) [10]** Write `logistic_tail(r_values,x0,burn_in,keep)`. Advance a 1D
`r` array through `burn_in` steps and return the next `keep` states with shape
`(keep,len(r_values))`. Do not change `r_values`.

**(c) [5]** Test shape and non-mutation. Test that `r=2, x0=0.5` stays fixed
and representative values remain in `[0,1]`.

**(d) [6]** For 1201 equally spaced `r` values in `[2.8,4.0]`, `x0=0.2`,
`burn_in=600`, `keep=160`, make one point plot of retained `x` against `r`.
Label axes and expose dense structure.

**(e) [7]** Write `period_two_mask(tail,tol=1e-8)`. A column passes when its
last value is within `tol` of its third-last, its second-last is within `tol`
of its fourth-last, and its last two values differ by at least `10*tol`. Test
`r=3.2` and reject the fixed point `r=2`.

**(f) [4]** Explain in Markdown why time needs a loop, why `r` does not, and
why the mask is numerical evidence rather than proof.

Notes — cell 9

### Q2 code answers for parts (a)-(e) - solution

Code — cell 10

import numpy as np
import matplotlib.pyplot as plt


def logistic_step(r, x):
    """One broadcast-compatible step of x -> r*x*(1-x)."""
    return r * x * (1.0 - x)


def logistic_tail(r_values, x0, burn_in, keep):
    """Return retained iterates, with one row per time step."""
    r = np.asarray(r_values, dtype=float)
    if r.ndim != 1:
        raise ValueError("r_values must be one-dimensional")
    if burn_in < 0 or keep < 1:
        raise ValueError("require burn_in >= 0 and keep >= 1")
    x = np.full(r.shape, float(x0), dtype=float)
    for _ in range(burn_in):
        x = logistic_step(r, x)
    tail = np.empty((keep, r.size), dtype=float)
    for row in range(keep):
        x = logistic_step(r, x)
        tail[row] = x
    return tail


def period_two_mask(tail, tol=1e-8):
    """Classify columns whose last four values appear period-two."""
    values = np.asarray(tail, dtype=float)
    if values.ndim != 2 or values.shape[0] < 4:
        raise ValueError("tail must have at least four rows")
    return ((np.abs(values[-1] - values[-3]) < tol)
            & (np.abs(values[-2] - values[-4]) < tol)
            & (np.abs(values[-1] - values[-2]) >= 10 * tol))


r_test = np.array([2.0, 3.2, 4.0])
r_saved = r_test.copy()
tail_test = logistic_tail(r_test, 0.5, 1000, 8)
assert tail_test.shape == (8, 3)
assert np.array_equal(r_test, r_saved)
assert np.allclose(tail_test[:, 0], 0.5)
assert np.all((0 <= tail_test) & (tail_test <= 1))
assert period_two_mask(tail_test)[1]
assert not period_two_mask(tail_test)[0]

r_values = np.linspace(2.8, 4.0, 1201)
tail = logistic_tail(r_values, 0.2, 600, 160)
mask2 = period_two_mask(tail)
fig, ax = plt.subplots(figsize=(7.2, 4.2))
ax.plot(np.tile(r_values, tail.shape[0]), tail.ravel(),
        ",", color="#17324D", alpha=0.22)
ax.plot(r_values[mask2], tail[-1, mask2], ".", color="#C7362F",
        markersize=2.0, label="period-2 test")
ax.set(xlabel="r", ylabel="retained x", title="Logistic-map tail")
ax.legend(loc="upper left")
fig.tight_layout()
plt.show()

<Figure size 720x420 with 1 Axes>

Code — cell 11

print("A2 tail shape:", tail.shape, "period-two candidates:", int(mask2.sum()))

A2 tail shape: (160, 1201) period-two candidates: 437

Notes — cell 12

### Q2 written answer for part (f) - solution

Time remains sequential because the next state depends on the previous state. At each time, all parameter values can be advanced together by NumPy broadcasting, so there is no parameter loop. A finite tail and tolerance can only provide numerical evidence: burn-in, floating-point rounding and the chosen tolerance can produce false positives or negatives.

Notes — cell 13

## Question 3 (10 marks): A non-destructive selection sort

**(a) [5]** Write `selection_sort_count(values)`, returning a sorted list,
data-comparison count and swap count while leaving `values` unchanged.

**(b) [2]** Test empty, singleton, repeated-value and four-element inputs.
Assert that the original object is unchanged.

**(c) [3]** In Markdown, derive the exact comparison total for length `n`.
Hence state best- and worst-case Theta times and explain why input order cannot
change the comparison count.

Notes — cell 14

### Q3 code answers for parts (a) and (b) - solution

Code — cell 15

def selection_sort_count(values):
    """Return a sorted copy plus comparison and swap counts."""
    out = list(values)
    comparisons = 0
    swaps = 0
    for i in range(len(out)):
        smallest = i
        for j in range(i + 1, len(out)):
            comparisons += 1
            if out[j] < out[smallest]:
                smallest = j
        if smallest != i:
            out[i], out[smallest] = out[smallest], out[i]
            swaps += 1
    return out, comparisons, swaps


source = [3, 1, 2, 1]
saved = source.copy()
answer = selection_sort_count(source)
assert answer[0] == [1, 1, 2, 3]
assert answer[1] == 6
assert source == saved
assert selection_sort_count([]) == ([], 0, 0)
assert selection_sort_count([5]) == ([5], 0, 0)

Code — cell 16

print("A3 sample output:", selection_sort_count([3, 1, 2, 1]))

A3 sample output: ([1, 1, 2, 3], 6, 2)

Notes — cell 17

### Q3 written answer for part (c) - solution

At outer index i there are n-i-1 data comparisons. Their total is `(n-1)+(n-2)+...+1+0=n(n-1)/2`. The same comparisons occur for every input order, so best- and worst-case running times are both Theta(n**2); only the swap count varies.

Code — cell 18

print('FINAL CHECK: all three questions executed without an exception.')

FINAL CHECK: all three questions executed without an exception.