MATH40006 Practice Paper 6 Solutions

Notes — cell 1

# MATH40006 Revised Historical-Coverage Mock 6 - Course-Method Audited Solutions

**Time allowed:** 60 minutes 
**Total marks:** 50 
**Role:** Mixed migration pressure: codebooks, instrumented algorithms and representation transforms

The main solutions use methods evidenced in the supplied official papers and mark schemes. No lecture notes or problem sheets were available in this window, so “course-method audited” here means audited against the official answer methods that are actually accessible.

Code — cell 2

import numpy as np
import sympy as sp
import matplotlib.pyplot as plt
import pandas as pd
from time import perf_counter
from copy import copy
import pickle
import ast
import math
sp.init_printing()

words=['amber','bridge','circle','delta','ember','forest','globe','harbour','island','jungle','lantern','meadow']
plaintext='amber forest island delta meadow'

def binary_digits(n): return [int(c) for c in bin(n)[2:]]
def from_binary_digits(bits): return int(''.join(map(str,bits)),2)

Notes — cell 3

## Question 1 (20 marks)

**Recognition signal.** A word-substitution code requires copying, stable key ordering, binary lookup and reverse mapping.

**First key step.** Copy before shuffling; then zip the unchanged words with the shuffled copy and sort by the plain key.

**Course-method chain.** copy/shuffle -> pairs/dict/Series -> iterative binary search -> two encoders -> reverse map -> decode -> aliasing explanation.

**Marking points.** 3+3+5+3+3+3.

**Common errors.** Aliasing the original list; binary-searching an unsorted pair list; reversing a dictionary with duplicate values; splitting/joining incorrectly.

**Final self-check.** Binary-search and dictionary encodings must match, and decoding must reproduce the original sentence exactly.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2021-22 Assessment 3 Q4(a-i)
- **Accessible course-material basis:** 2021-22 official marking scheme 
- **Historical ability gap filled:** add copying, shuffling, pairing, bidirectional maps and recursive binary encoding/ decoding as a complete historical chain 
- **Equivalent 2026 difficulty unit:** 2026 Q1(20 mark multi-function synthesis difficulty unit )
- **Why equivalent:** several short functions and round-trip checks, with the information order changed; total code and tests about 20 minutes .

Code — cell 4

rng=np.random.default_rng(7); code_words=words.copy(); rng.shuffle(code_words)
pairs=sorted(zip(words,code_words)); dic=dict(pairs); ser=pd.Series(dic)
def pair_partner(pairs,key):
    lo,hi=0,len(pairs)-1
    while lo<=hi:
        mid=(lo+hi)//2
        if pairs[mid][0]==key:return pairs[mid][1]
        if pairs[mid][0]<key:lo=mid+1
        else:hi=mid-1
    return 'failed'
enc1=' '.join(pair_partner(pairs,w) for w in plaintext.split()); enc2=' '.join(dic[w] for w in plaintext.split())
reverse={v:k for k,v in pairs}; decoded=' '.join(reverse[w] for w in enc1.split())
print(words); print(code_words); print(enc1,enc1==enc2,decoded)

['amber', 'bridge', 'circle', 'delta', 'ember', 'forest', 'globe', 'harbour', 'island', 'jungle', 'lantern', 'meadow']
['ember', 'globe', 'lantern', 'amber', 'bridge', 'delta', 'island', 'harbour', 'circle', 'forest', 'jungle', 'meadow']
ember delta circle amber meadow True amber forest island delta meadow

Notes — cell 5

## Question 2 (20 marks)

**Recognition signal.** The question combines an instrumented official Newton method with the data-export workflow from the determinant paper.

**First key step.** Choose a power of two from `bit_length`, then count every Newton update until it no longer decreases.

**Course-method chain.** Newton root/count -> invariant tests -> exponential-size experiment -> compare with log-log scale -> nested records -> pickle/DataFrame/CSV.

**Marking points.** 6+3+3+4+4.

**Common errors.** Floating arithmetic on huge ints; unsafe initial value; inconsistent count convention; measuring different inputs; forgetting binary mode for pickle.

**Final self-check.** All roots satisfy the defining inequalities; export files exist and the DataFrame has one row per exponent.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2022-23 Assessment 3 Q5(a-e) + 2026 Alternative Q3
- **Accessible course-material basis:** 2022-23 official marking scheme ;Alternative question paper 
- **Historical ability gap filled:** combine across years Newton iteration counts, performance data , pickle/DataFrame/CSV
- **Equivalent 2026 difficulty unit:** 2026 Q2(20 mark long-algorithm + data difficulty unit )
- **Why equivalent:** Newton main algorithm: approximately 12 marks, and the data pipeline about 8 marks; synthesis increases but each function is short; estimated 24 minutes .

Code — cell 6

from pathlib import Path
def isqrt_newton_count(n):
    if n<0: raise ValueError
    if n<2:return n,0
    old=1<<(((n.bit_length()-1)//2)+1); count=0
    while True:
        new=(old+n//old)//2; count+=1
        if new>=old:return old,count
        old=new
for n in [2,17,12345**2-1,12345**2,12345**2+1,10**100+123]:
    r,c=isqrt_newton_count(n); print(r*r<=n<(r+1)**2,c)
records={}
for e in range(100,2001,100):
    n=2**e; t=perf_counter(); r,c=isqrt_newton_count(n); elapsed=perf_counter()-t
    records[e]={'runtime':elapsed,'iterations':c,'log2log2':math.log2(math.log2(n))}
with open('newton_profile.pkl','wb') as f: pickle.dump(records,f)
df=pd.DataFrame.from_dict(records,orient='index'); df.index.name='exponent'; df.to_csv('newton_profile.csv')
print(df.head()); print(Path('newton_profile.pkl').exists(),Path('newton_profile.csv').exists())

True 2
True 3
True 5
True 4
True 4
True 8
 runtime iterations log2log2
exponent 
100 0.000004 7 6.643856
200 0.000003 7 7.643856
300 0.000005 8 8.228819
400 0.000004 8 8.643856
500 0.000005 9 8.965784
True True

Notes — cell 7

## Question 3 (10 marks)

**Recognition signal.** A binary representation is transformed by grouping maximal equal-bit runs.

**First key step.** Scan once from left to right, starting the current run count at one.

**Course-method chain.** inverse tests -> one-pass run lengths -> retain run heads -> convert back -> logarithmic complexity from bit length.

**Marking points.** 2+4+3+1.

**Common errors.** Forgetting the final run; comparing a bit with the count rather than the previous bit; treating binary digit count as Theta(n).

**Final self-check.** The sum of run lengths equals the number of binary digits, and outputs for n=1..20 are positive integers.

### Historical-basis and difficulty audit

- **Historical formal-question basis:** 2023-24 Assessment 3 Q2(f-i)
- **Accessible course-material basis:** 2023-24 official marking scheme 
- **Historical ability gap filled:** use unfamiliar wording to practise identifying binary runs , run lengths and run heads Transfer 
- **Equivalent 2026 difficulty unit:** 2026 Q3(10 mark short-recursion / list difficulty unit )
- **Why equivalent:** base case, traversal, two outputs and sample self-check form 4 steps; about 10 minutes .

Code — cell 8

def run_lengths(bits):
    if not bits:return []
    out=[]; count=1
    for i in range(1,len(bits)):
        if bits[i]==bits[i-1]:count+=1
        else:out.append(count); count=1
    out.append(count); return out
def run_heads_value(n):
    bits=binary_digits(n); heads=[bits[0]]+[bits[i] for i in range(1,len(bits)) if bits[i]!=bits[i-1]]
    return from_binary_digits(heads)
print(all(from_binary_digits(binary_digits(n))==n for n in range(1,13)))
print(run_lengths([1,1,1,0,0,1])); print([(n,run_heads_value(n)) for n in range(1,21)])

True
[3, 2, 1]
[(1, 1), (2, 2), (3, 1), (4, 2), (5, 5), (6, 2), (7, 1), (8, 2), (9, 5), (10, 10), (11, 5), (12, 2), (13, 5), (14, 2), (15, 1), (16, 2), (17, 5), (18, 10), (19, 5), (20, 10)]