MATH40006 2026 Practice Paper 3

1.2 Question 1 (20 marks) The Chebyshev polynomials satisfy T0(x)=1, T1(x)=x, and Tn(x)=2xT(n-1)(x)-T(n-2)(x). (a) Write an iterative chebyshev(n,x) returning a SymPy expression, and test T0,…,T4. [3] (b) Lambdify T6 for NumPy arrays and plot it at 200 points on [-1,1]. [3] (c) On one axes plot T1,…,T8. [3] (d) Write an efficient recursive version that makes only one recursive call at each level; test it against the iterative version for n=0,…,10. [5] (e) For n=5, use the exact roots of T5 obtained with SymPy and the Gauss-Chebyshev formula integral from -1 to 1 of f(x)/sqrt(1-x^2) dx ~= (pi/5) sum f(xi). Approximate the integral for f(x)=exp(x), and compare with a high-resolution trapezoidal approx- imation after the substitution x=cos(theta). [6] 1 [2]: x=sp.symbols('x') def chebyshev(n,x): if n==0: return sp.Integer(1) if n==1: return x a,b=sp.Integer(1),x for _ in range(2,n+1): a,b=b,sp.expand(2*x*b-a) return b print([chebyshev(n,x) for n in range(5)]) T6=chebyshev(6,x) T6f=sp.lambdify(x,T6,'numpy') xs=np.linspace(-1,1,200) plt.figure(); plt .plot(xs,T6f(xs)) plt.figure() for n in range(1,9): fn=sp.lambdify(x,chebyshev(n,x),'numpy') plt.plot(xs,fn(xs)) def chebyshev_rec(n,x,pair=False): if pair: if n==1: return sp.Integer(1),x a,b=chebyshev_rec(n-1,x,True) return b,sp.expand(2*x*b-a) if n==0: return sp.Integer(1) return chebyshev_rec(n,x,True)[1] assert all(sp.expand(chebyshev(n,x)-chebyshev_rec(n,x))==0 for n in range(11)) T5=chebyshev(5,x) roots=sp.solve(sp.Eq(T5,0),x) approx=float(np.pi/5*sum(np.exp(float(r)) for r in roots)) theta=np.linspace(0,np.pi,200001) reference=float(np.trapezoid(np.exp(np.cos(theta)),theta)) print(roots,approx,reference,abs(approx-reference)) plt.show() [1, x, 2*x**2 - 1, 4*x**3 - 3*x, 8*x**4 - 8*x**2 + 1] [0, -sqrt(5/8 - sqrt(5)/8), sqrt(5/8 - sqrt(5)/8), -sqrt(sqrt(5)/8 + 5/8), sqrt(sqrt(5)/8 + 5/8)] 3.977463258776694 3.977463260506423 1.7297288046336234e-09 2 3 Marking points / verification. 3 marks for the recurrence and tests; 3 for a NumPy-compatible T6 plot; 3 for the family plot; 5 for genuinely efficient recursion and equality tests; 6 for roots, weight pi/5, correct transformed reference integral and an accuracy comparison.

1.3 Question 2 (20 marks) The following vectorised function returns primes up to n using Eratosthenes’ sieve: def primes_numpy(n): pos=np.ones(n+1,dtype=bool); pos[:2]=False for p in range(2,int(np.sqrt(n))+1): if pos[p]: pos[p *p::p]=False return np.arange(n+1)[pos] (a) Test it for a prime n, a composite n, and a square of a prime. [3] (b) Write append_if_prime(primes,p) that appends p in place exactly when it has no prime divisor at most sqrt(p). [4] (c) Test both the append and no-append branches. [3] (d) Write primes_incremental(n) starting with [2], testing only odd candidates, and using append_if_prime. [4] (e) Test it against primes_numpy for several n. [2] (f) Use perf_counter to compare both functions at n=200000. [2] (g) Briefly explain why the vectorised method is normally faster, without claiming an exact complexity proof from one timing. [2] [3]: def primes_numpy(n): if n<2: return np.array([],dtype=int) pos=np.ones(n+1,dtype=bool); pos[: 2]=False for p in range(2,int(np.sqrt(n))+1): if pos[p]: pos[p *p::p]=False return np.arange(n+1)[pos] for n in [101,100,121]: print(primes_numpy(n)[-5:]) def append_if_prime(primes,p): for q in primes: if q*q>p: primes.append(p); return if p%q==0: return primes.append(p) for p in [6,7]: L=[2,3,5]; append_if_prime(L,p); print(p,L) 4 def primes_incremental(n): if n<2: return [] primes=[2] for p in range(3,n+1,2): append_if_prime(primes,p) return primes for n in [1,2,30,101,500]: assert np.array_equal(np.array(primes_incremental(n)),primes_numpy(n)) start=perf_counter(); primes_numpy( 200000); t1 =perf_counter()-start start=perf_counter(); primes_incremental( 200000); t2 =perf_counter()-start print(t1,t2) # The NumPy version performs bulk slice updates in compiled code; the ␣ ↪incremental # version executes many Python-level modulus operations. A single timing ␣ ↪supports # an empirical comparison, not a standalone asymptotic proof. [ 79 83 89 97 101] [73 79 83 89 97] [101 103 107 109 113] 6 [2, 3, 5] 7 [2, 3, 5, 7] 0.004668947000027401 0.08391706200018234 Marking points / verification. 3 marks for the three test classes; 4 for bounded trial division and in-place behaviour; 3 for branch tests; 4 for odd-only construction; 2 for equality tests; 2 for fair timing; 2 for a restrained implementation-level explanation.

1.4 Question 3 (10 marks) Use the supplied list: words=['amber','bridge','circle','delta','ember','forest','globe','harbour','island','jungle'] (a) With a fixed NumPy random seed, create a separately copied and shuffled list code_words; prove that words is unchanged. [2] (b) Build pairs and then code_dict. [2] (c) Encode 'amber forest island delta' using split, lookup and join. [2] (d) Build a reverse dictionary and decode the result. [2] (e) Demonstrate briefly why code_words=words would have been incorrect. [2] [4]: words=['amber','bridge','circle','delta','ember','forest','globe','harbour','island','jungle'] original=words.copy(); rng =np.random.default_rng(2026) code_words=words.copy(); rng .shuffle(code_words) assert words==original and code_words is not words pairs=list(zip(words,code_words)); code_dict =dict(pairs) plain='amber forest island delta ' 5 coded=' '.join(code_dict[w] for w in plain.split()) reverse={v:k for k,v in code_dict.items()} decoded=' '.join(reverse[w] for w in coded.split()) print(coded,decoded) assert decoded==plain alias=words assert alias is words # Mutating alias would mutate words because both names reference the same list. bridge delta harbour globe amber forest island delta Marking points / verification. 2 marks for a true copy, reproducible shuffle and preservation check; 2 for zip/dict; 2 for encoding; 2 for a valid inverse mapping and decoding; 2 for an explicit aliasing demonstration/explanation. 6