MATH40006 Practice Paper A Questions

English review edition prepared on 4 October 2026 from a preserved source copy. It is a later presentation, not the historical study interface. Source checks and difficulty judgements describe the original material author's own process; they do not indicate Imperial College London endorsement. This material's source date is 2026-08-30; it is later than the recorded activity ending 21 August 2026 and is not evidence of use during that period.

Source SHA-256: 97c06f52d6b11149408e841c38813925c0b35b67ae256b1cde5e2161452d4a91
Source date: 2026-08-30

Notes — cell 1

# MATH40006 - Introduction to Computation

## Practice Paper Paper A - Candidate question notebook

**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__)

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)

Code — cell 5

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 6

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

**YOUR ANSWER HERE**

Notes — cell 7

## 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 8

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

Code — cell 9

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 10

### Q2 written answer for part (f)

**YOUR ANSWER HERE**

Notes — cell 11

## 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 12

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

Code — cell 13

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 14

### Q3 written answer for part (c)

**YOUR ANSWER HERE**