MATH40006 Revised Historical Coverage Practice Paper 4

Question 1 (20 marks) Recognition signal. A three-term polynomial recurrence, exact symbolic roots and a quadrature formula based on those roots. First key step. Keep the pair (P_{n-1},P_n) together; this is also the key to an efficient one-call recursive version. Course-method chain. exact recurrence -> lambdify/plot -> pair-return recursion -> roots/derivative/weights -> affine interval transform and weighted sum. Marking points. 2+3+5+5+5. Common errors. Two recursive calls per level; converting to float too early; using P5 derivative with P4 roots; omitting the interval scaling factor. Final self-check. The quadrature value should agree with 1-exp(-1) to many digits. Historical-basis and difficulty audit - Historical formal-question basis: 2022-23 Assessment 3 Q1(a-f) - Accessible course-material basis: 2022-23 official marking scheme - Historical ability gap filled: Legendre recurrence, symbolic-to-numerical conversion, roots and weights, and Gauss quadrature - Equivalent 2026 difficulty unit: 2026 Q1 (20-mark highly abstract integrated question) - Why equivalent: the original 35-mark question is compressed to 20 marks, retaining recurrence, lambdify, roots/weights and one integral; approximately 20 minutes. x=sp.symbols('x') print([legendre_poly(n,x) for n in range(5)]) p6=legendre_poly(6,x); f6=sp.lambdify(x,p6,'numpy'); xx=np.linspace(-1,1,200) plt.figure(); plt.plot(xx,f6(xx)); plt.show() MATH40006_COURSE_METHOD_AUDITED_Mock_4_Solutions Page 1 def legendre_recursive(n,x,pair=False): if pair: if n==1:return sp.Integer(1),x pa,pb=legendre_recursive(n-1,x,True) return pb,sp.together(sp.expand(((2*n-1)*x*pb-(n-1)*pa)/n)) if n==0:return sp.Integer(1) return legendre_recursive(n,x,True)[1] print(all(sp.simplify(legendre_poly(n,x)-legendre_recursive(n,x))==0 for n in range(9))) p4=legendre_poly(4,x); dp4=sp.diff(p4,x); roots=sp.solve(sp.Eq(p4,0),x) weights=[float(2/((1-r**2)*dp4.subs(x,r)**2)) for r in roots] vals=[math.exp(-float((r+1)/2)) for r in roots] approx=0.5*np.dot(weights,vals); exact=1-math.exp(-1) print(roots); print(weights); print(approx,exact,abs(approx-exact)) [1, x, (3*x**2 - 1)/2, x*(5*x**2 - 3)/2, (35*x**4 - 30*x**2 + 3)/8] True [-sqrt(3/7 - 2*sqrt(30)/35), sqrt(3/7 - 2*sqrt(30)/35), -sqrt(2*sqrt(30)/35 + 3/7), sqrt(2*sqrt(30)/35 + 3/7)] [0.6521451548625461, 0.6521451548625461, 0.34785484513745385, 0.34785484513745385] 0.6321205584853381 0.6321205588285577 3.4321956388083663e-10

Question 2 (20 marks) Recognition signal. The integer square root is defined by inequalities, and the question supplies bit-level construction plus discrete Newton iteration. First key step. Derive smax from bit_length; keep every operation integer-valued. Course-method chain. bit-length identity -> descending even shifts -> invariant tests -> logarithmic iteration argument -> Newton with safe upper start -> cross-check. Marking points. 2+7+3+2+5+1. Common errors. Using floating sqrt; wrong parity for smax; stopping Newton after equality rather than when the update no longer decreases; missing n=0,1. Final self-check. For every n, verify r*r<=n<(r+1)*(r+1). Historical-basis and difficulty audit - Historical formal-question basis: 2022-23 Assessment 3 Q3-Q5 MATH40006_COURSE_METHOD_AUDITED_Mock_4_Solutions Page 2 - Accessible course-material basis: 2022-23 official marking scheme - Historical ability gap filled: the two historical method sequences for bitwise integer square roots and discrete Newton iteration - Equivalent 2026 difficulty unit: 2026 Q2 (20-mark long algorithm question) - Why equivalent: both algorithms include tests and counts; slightly more abstract, but the prescribed n=120 hand calculation and complete closed-form proof are omitted; approximately 25 minutes. def isqrt_bitwise(n): if n<0: raise ValueError if n<2:return n r=0; smax=2*((n.bit_length()-1)//2) for s in range(smax,-1,-2): r<<=1 if (r+1)**2 <= (n>>s): r+=1 return r def isqrt_newton(n): if n<0: raise ValueError if n<2:return n old=1<<(((n.bit_length()-1)//2)+1) new=(old+n//old)//2 while new<old: old,new=new,(new+n//new)//2 return old tests=[2,17,10**100+12345,12345**2,12345**2-1,12345**2+1] for n in tests: a=isqrt_bitwise(n); b=isqrt_newton(n) print(n if n<100000 else str(n)[:15]+'...',a==b,a*a<=n<(a+1)**2) 2 True True 17 True True 100000000000000... True True 152399025... True True 152399024... True True 152399026... True True

Question 3 (10 marks) Recognition signal. Two given loops solve the same problem but have very different comparison-count behaviour. First key step. Initialize the count to one so the final failed while test is included. Course-method chain. instrument loops -> edge tests -> enumerate b values -> identify worst inputs -> connect repeated additions to linear growth and Euclid to Fibonacci/logarithmic depth. Marking points. 4+2+2+2. Common errors. Off-by-one counts; changing original a,b before computing the LCM; claiming timing alone proves complexity. Final self-check. Both algorithms must return the same LCM on all tests. Historical-basis and difficulty audit - Historical formal-question basis: 2021-22 Assessment 3 Q1(a-h) - Accessible course-material basis: 2021-22 official marking scheme - Historical ability gap filled: exact LCM operation counting, worst-input experiments and asymptotic complexity - Equivalent 2026 difficulty unit: 2026 Q3 (10-mark short algorithm question) - Why equivalent: selects the counter, scanning and complexity core of the original 25-mark sequence; four marking stages, approximately 10 minutes. def lcm_add_count(a,b): a0,b0=a,b; count=1 while a!=b: if a<b:a+=a0 else:b+=b0 count+=1 return a,count def lcm_euclid_count(a,b): a0,b0=a,b; count=1 while b>0:a,b,count=b,a%b,count+1 return a0*b0//a,count for a,b in [(5,3),(35,21),(35,35),(35,1)]: print(a,b,lcm_add_count(a,b),lcm_euclid_count(a,b)) for fn in [lcm_add_count,lcm_euclid_count]: counts=[fn(144,b)[1] for b in range(1,144)]; print(fn.__name__,1+int(np.argmax(counts)),max(counts)) 5 3 (15, 7) (15, 4) 35 21 (105, 7) (105, 4) MATH40006_COURSE_METHOD_AUDITED_Mock_4_Solutions Page 3 35 35 (35, 1) (35, 2) 35 1 (35, 35) (35, 2) lcm_add_count 143 286 lcm_euclid_count 89 11 MATH40006_COURSE_METHOD_AUDITED_Mock_4_Solutions Page 4