MATH40006 2023 24 assessment3 markscheme

Notes — cell 1

# MATH40006 In-Course Assessment

# 21 March 2024, 13:10 - 15:10

## Two Hours

### Answer all questions, submitting your answers as a single Jupyter notebook.

### <font color='red'>This test is worth 60% of your mark for the module. You may use notes, and access resources online. You may not use email, chat, social media, discussion forums or AI. Please ask if you have any questions about this policy.</font>

Notes — cell 2

To carry out this assignment, you may find useful, possibly amongst others:
<ul>
 <li>from the <code>numpy</code> module, the functions <code>ones</code>, <code>sqrt</code> and <code>arange</code>;</li>
 <li>from the <code>time</code> module, the function <code>time</code>;</li>
 <li>from the <code>pyplot</code> submodule of <code>matplotlib</code>, the <code>plot</code> function;</li>
 <li>from the <code>pandas</code> module, the function <code>Series</code>.

We recommend that you execute the following cell:</li>
</ul>

Code — cell 3

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from time import time

Notes — cell 4

## Question 1 (25 marks)

The following function implements the Sieve of Eratosthenes in order to calculate an array of the primes less than or equal to a given integer $n\ge 2$:

Code — cell 5

def primes1(n):
    prime_positions = np.ones(n+1, dtype='bool')
    prime_positions[0:2] = False
    for p in range(2,int(np.sqrt(n))+1):
        if prime_positions[p]:
            prime_positions[p**2::p] = False
    return np.arange(n+1)[prime_positions]

Notes — cell 6

(a) Test this function on a prime value of $n$, and two composite values, one of which should be the square of a prime.

Code — cell 7

print(primes1(100))
print(primes1(101))
print(primes1(121))

# 4 marks

Notes — cell 8

Another way to create a list of primes is simply to test each integer in turn, to see whether it has any factors among the primes you've already found.

(b) Write a function called `conditional_append`, which takes as its arguments a list `primes`, assumed to consist of primes, and an int $p$, assumed to be greater than all the elements of `primes`. 

It should then test whether $p$ has any factors among the elements of `primes`. (<b>Note</b>: to do this, it need only test whether $p$ is divisible by any element of `primes` less than or equal to $\sqrt{p}$.)

If $p$ has no factors among the elements of `primes`, your function should then append $p$ to `primes`. 

For full marks, your function should not return a value, but should append to `primes` in place.

Code — cell 9

def conditional_append(primes_list, p):
    for r in primes_list:
        if p%r==0:
            break
        elif r**2 > p:
            primes_list.append(p) 
            break

# 5 marks
# Accept any valid implementation
# Penalise 1 mark if the function returns a value instead of appending in place
# Penalise 2 marks for a gross error in loop length, such as checking all elements of primes
# Penalise 1 mark for a minor error in loop length, such as an off-by-one error

Notes — cell 10

(c) Test your function by checking it performs correctly when

-- `primes` is `[2, 3, 5]` and `p` is 6 (do not append);

-- `primes` is `[2, 3, 5]` and `p` is 7 (append).

Code — cell 11

primes, n = [2, 3, 5], 6
conditional_append(primes, n)
print(primes)
primes, n = [2, 3, 5], 7
conditional_append(primes, n)
print(primes)

# 4 marks

Notes — cell 12

(d) Write a function `primes2` that takes as its argument an int $n\ge2$ and returns a list of the primes less than or equal to $n$; it should do this by repeated applications of `conditional_append`, starting with `primes` equal to `[2]` and $p$ equal to $3$. (<b>Note</b>: you need only test <em>odd</em> candidate values of $p$, and some marks are available for that slight efficiency gain.)

Code — cell 13

def primes2(n):
    primes = [2]
    for p in range(3, n+1, 2):
        conditional_append(primes, p)
    return primes

# 4 marks
# Accept any valid implementation that uses conditional_append
# Penalise by 1 mark for minor inefficiencies such as using a step size of 1

Notes — cell 14

(e) Test this function on a prime value of $n$, and two composite values, one of which should be the square of a prime.

Code — cell 15

print(primes2(100))
print(primes2(101))
print(primes2(121))

# 4 marks

Notes — cell 16

(f) Using the `time` function from the `time` module, compare the execution time of `primes1` and `primes2` on the task of finding all the primes less than or equal to one million.

Code — cell 17

start = time()
primes1(10**6)
print(time()-start)
start = time()
primes2(10**6)
print(time()-start)

# 4 marks

Notes — cell 18

## Question 2 (35 marks)

The function $f$ is defined recursively on the positive integers as follows:

<b>Base case</b>: if $n = 1$ then let $f(n) = 1$.

<b>Recursion step</b>: otherwise:

-- if $n \equiv 0$ (mod $4$) then let $f(n) = f(n/2)$;

-- if $n \equiv 1$ (mod $4$) then let $f(n) = 2\,f\left(\lfloor n/2 \rfloor \right) + 1$;

-- if $n \equiv 2$ (mod $4$) then let $f(n) = 2\,f(n/2)$;

-- if $n \equiv 3$ (mod $4$) then let $f(n) = f\left(\lfloor n/2 \rfloor \right)$.

(Here, $\lfloor a \rfloor$ means the "floor" of $a$; that is, the greatest integer less than or equal to $a$.)

(a) Write a recursive Python function `f` that takes a single argument `n`, which may be assumed to be a positive int, and returns $f(n)$, as an int. (<b>Note</b>: marks will be lost if the return value is not an int.)

Code — cell 19

def f(n):
    if n==1:
        return 1
    else:
        res = n%4
        if res == 0 or res == 3:
            return f(n//2)
        else:
            return 2*f(n//2) + (res % 2)

# 5 marks
# Accept any valid RECURSIVE implementation
# Penalise by 3 marks if the implementation is correct but not recursive

Notes — cell 20

(b) Test your function: you should find that $f(1) = 1$, $f(300) = 42$ and $f(2024) = 10$.

Code — cell 21

[f(n) for n in [1, 300, 2024]]

# 3 marks

Notes — cell 22

(c) Create a point plot of $f(n)$ against $n$ for $1 \le n \le 1000$; use a markersize of 1.

Code — cell 23

plt.plot(range(1,1001), [f(n) for n in range(1,1001)],'.k', markersize=1)

# 4 marks
# Allow any colour
# Penalise 1 mark for markersize error
# Penalise 1 mark for a line plot instead of a point plot

Notes — cell 24

(d) Using a filtering comprehension, or otherwise, find and print, as a list, all those values of $n$ with $1\le n < 2024$ for which $f(n) = f(2024)$.

Code — cell 25

print([n for n in range(1,2024) if f(n) == f(2024)])

# 3 marks
# Accept any valid implementation
# Penalise 1 mark if results printed separately rather than as a list

Notes — cell 26

(e) Write some Python code to test, for $1\le n \le 1000$, the claim that for integer $n>0$, $f(n) = n$ if and only if, for some integer $r\ge0$,

$$n = \sum_{i=0}^r 4^i$$

or

$$n = 2\,\sum_{i=0}^r 4^i.$$

Is this claim consistent with the data? Briefly explain your answer.

Code — cell 27

print([n for n in range(1,1001) if f(n) == n])
print([sum([4**i for i in range(r)]) for r in range(1,6)])
print([2*sum([4**i for i in range(r)]) for r in range(1,6)])

# 3 marks
# Award marks at your discretion.
# If the code constitutes, on its own, a clear test of the claim, award full marks
# If the code, together with some content from the written section below, constitute 
# a clear test of the claim, award full marks
# (So for example, the first comprehension would be fine on its own as long as the correct 
# infinite sums are shown in the written section)
# If the code, together with the written section, seem to you seriously incomplete, penalise
# accordingly
# (For example, if the first comprehension appears on its own, with nothing in the written section
# showing it has generated the right values, award only up to 2 marks)

Notes — cell 28

The contents of the first list are clearly the combined contents of the other two.

<b>1 mark</b>

(Accept anything sensible.)

Notes — cell 29

The following two functions convert a positive int into a list of binary digits and vice versa:

Code — cell 30

def binary_digits(a):
    return [eval(c) for c in bin(a)[2:]]
def from_binary_digits(bits):
    return eval(''.join(['0b']+[str(bit) for bit in bits]))

Notes — cell 31

(f) Test these two functions on the integers between $1$ and $8$ inclusive.

Code — cell 32

bins = [binary_digits(n) for n in range(1,9)]
print(bins)
print([from_binary_digits(seq) for seq in bins])

# 3 marks

Notes — cell 33

(g) Write and test a python function called `list_crush` that takes as its argument a single list, and collapses any sublists consisting of identical elements into a single element: thus for example
```python
list_crush(['a', 'a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'c', 'c', 'b', 'b', 'b'])
```
should return
```python
['a', 'b', 'a', 'c', 'b']
```
(<b>Note</b>: it's best here if your function actually returns a value rather than "crushing" lists in place, as a side-effect.)

Code — cell 34

def list_crush(lis):
    crushed = [lis[0]]
    for i in range(1,len(lis)):
        if not lis[i] == lis[i-1]:
            crushed.append(lis[i])
    return crushed
list_crush(['a', 'a', 'a', 'a', 'b', 'b', 'a', 'a', 'a', 'c', 'c', 'b', 'b', 'b'])

# 6 marks
# Accept any valid implementation
# Do not penalise if lists are "crushed in place" instead of a value being returned

Notes — cell 35

(h) Use Python to verify, for $1 \le n \le 1000$, that $f(n)$ is identical to
```python
from_binary_digits(list_crush(binary_digits(n)))
```

Code — cell 36

all([f(n) == from_binary_digits(list_crush(binary_digits(n))) for n in range(1,1001)])

# 4 marks
# Accepy anything valid

Notes — cell 37

(i) If $m$ is the number of digits in $n$'s binary expansion, characterise the dependence of the time complexity of $f$ (in this recursive implementation) on $m$ using big Theta notation, giving a brief justification for your answer.

Notes — cell 38

The dependence is $\Theta(m)$ because each recursive call integer-divides by 2, which corresponds to removing the final binary digit. Worst-case and best-case behaviour are not distinguishable.

<b>3 marks</b>

(Accept anything valid. Award 1 mark for a correct dependency, 2 marks for a valid justification; part marks at your discretion.)

Notes — cell 39

## Question 3 (40 marks)

The file `lexicon.dat` contains a "dictionary" in the normal English sense of the word: that is, a collection of words together with their definitions. To distinguish this usage of "dictionary" from the technical Python meaning, we shall use the word "lexicon" to refer to the contents of the file.

The contents of `lexicon.dat` are in ASCII text format.

### Part (i)

(a) Open a stream for reading (as text, not as bytes), and read the contents of the file in as a string, which you should call `lexicon_string`. Remember then to close your stream.

Code — cell 40

fo = open('lexicon.dat', 'r')
lexicon_string = fo.read()
fo.close()

# 3 marks
# NOTE: in some versions of Python, very unfortunately, the above turns out not to work, and only opening 'rb' will work
# Definitely allow this (despite the rubric), and in general err on the side of generosity in this general area, because
# later problems can arise

Notes — cell 41

The following code should then convert this string into a Python list called `lexicon`.

Code — cell 42

lexicon = eval(lexicon_string)

Notes — cell 43

(b) Print the first five elements of `lexicon`, and thus verify that it is a Python list of Python dictionaries.

Code — cell 44

print(lexicon[:5])

# 2 marks

Notes — cell 45

The important information in `lexicon` consists of the values associated with the `'word'` key and those associated with the `'description'` key. The following code sets up a variable that represents that information, in the form of a list of $2$-tuples:

Code — cell 46

lexicon_tuples = [(dic['word'], dic['description']) for dic in lexicon]

Notes — cell 47

(c) Verify that this has worked by printing the first five elements of `lexicon_tuples`.

Code — cell 48

print(lexicon_tuples[:5])

# 2 marks

Notes — cell 49

We shall call element zero of each tuple the "key", and element one the "value".

(d) Write a function called `get_value`, which takes as its argument a list `lis` of $2$-tuples and a second argument, `key`, which can be any Python data. 

It then searches through `lis`, in order, tuple by tuple, until it finds a tuple whose key (i.e., whose element zero) is `key`; it should then return the corresponding value (i.e., the corresponding element one). 

If it fails to find `key` it should return the string `'failed'`.

Code — cell 50

def get_value(lis, key):
    for tup in lis:
        if tup[0] == key:
            return tup[1]
    return 'failed'

# 4 marks
# Accept any valid implementation
# Penalise 1 mark for incorrect failure behaviour

Notes — cell 51

(e) Test your function:
```python
get_value(lexicon_tuples, 'Elephant')
```
should return a string containing a definition for the word "Elephant". (Note that all words in the lexicon begin with capital letters.) 

Also test it on a nonsense word to check that it returns the string `'failed'`.

Code — cell 52

get_value(lexicon_tuples, 'Elephant')

# 1 mark

Code — cell 53

get_value(lexicon_tuples, 'Bliggle')

# 1 mark

Notes — cell 54

(f) Characterise the dependence of the time-complexity of `get_value` on `n`, the number of items in the lexicon, using big O and big Omega notation, giving brief reasons for your answers.

Notes — cell 55

The dependence is $O(n)$ but $\Omega(1)$. In the best case, the item is found at the start of the search, requiring only one comparison. In the worst case, the item is at the very end, or is not there, requiring n comparisons.

<b>3 marks</b>

(1 mark for each correct dependency, 1 mark for justification)

Notes — cell 56

(g) This function is less efficient than it could be, because it fails to make use of the fact that the items in the lexicon are in alphabetical order by word. Write a second function, `get_value_binary`, which takes the same argument as `get_value` and gives the same output, but which assumes the "keys" are in alphabetical order and locates the correct one, if it exists, using binary search. If it fails to find the correct key, it too should return `'failed'`.

(<b>Hint</b>: a recursive implementation works quite well for this.)

Code — cell 57

def get_value_binary(lis,key):
    n = len(lis)
    if n==1 and not lis[0][0] == key:
        return "failed"
    else:
        mid = lis[n//2]
        if mid[0] == key:
            return mid[1]
        elif mid[0] < key:
            return get_value_binary(lis[n//2+1:],key)
        else:
            return get_value_binary(lis[:n//2],key)

# 5 marks
# Accept any valid implementation
# Allow iterative implementations if they genuinely use binary search
# Penalise 1 mark for incorrect failure behaviour

Notes — cell 58

(h) Test this function on `'Elephant'` and on a nonsense word.

Code — cell 59

get_value_binary(lexicon_tuples, 'Elephant')

# 1 mark

Code — cell 60

get_value_binary(lexicon_tuples, 'Bliggle')

# 1 mark

Notes — cell 61

(i) Characterise the dependence of the time-complexity of `get_value_binary` on `n`, the number of items in the lexicon, using big O and big Omega notation, giving brief reasons for your answers.

Notes — cell 62

The dependence is $O(\log n)$ but $\Omega(1)$. In the best case, the item is found at the start of the search, requiring only one comparison. In the worst case, the item is found at the very end, or is not there, and at each recursive call the length of the list is halved, meaning that if $n=2^m-1$, exactly $m=\log_2(n+1)$ comparisons are required.

<b>3 marks</b>

(1 mark for each correct dependency, 1 mark for justification)

Notes — cell 63

### Part (ii)

Using lists of tuples in this way, even with binary search, is very inefficient.

(a) Write some code defining a variable called `lexicon_dict`, which should be a single Python dictionary. The keys of the dictionary should consist of the values associated with the `'word'` key in each element of `lexicon`, and the corresponding values should be the values associated with each `'description'` key.

Another way to say this is that `lexicon_dict` should contain exactly the same data as `lexicon_tuples`, but in the form of a dictionary rather than a list of tuples.

Code — cell 64

lexicon_dict = {dic['word']:dic['description'] for dic in lexicon}

# 2 marks

Notes — cell 65

(b) Test your dictionary by looking up `'Elephant'`, and also a nonsense word.

Code — cell 66

lexicon_dict['Elephant']

# 1 mark

Code — cell 67

lexicon_dict['Bliggle']

# 1 mark

Notes — cell 68

(c) Write some code defining a variable called `lexicon_ser` which should contain exactly the same data as `lexicon_tuples` and `lexicon_dict`, but in the form of a pandas Series; the keys of `lexicon_dict` should correspond to the index of `lexicon_ser`.

Code — cell 69

lexicon_ser = pd.Series(lexicon_dict)

# 2 marks

Notes — cell 70

(d) Test your Series by looking up `'Elephant'`, and also a nonsense word.

Code — cell 71

lexicon_ser['Elephant']

# 1 mark

Code — cell 72

lexicon_ser['Bliggle']

# 1 mark

Notes — cell 73

(e) Use the `time` function from the `time` module to print the execution time necessary in order to

-- look up the word `'Elephant'` one thousand times using `get_value` on `lexicon_tuples`;

-- look up the word `'Elephant'` one thousand times using `get_value_binary` on `lexicon_tuples`;

-- look up the word `'Elephant'` ten thousand times using `lexicon_dict`;

-- look up the word `'Elephant'` ten thousand times using `lexicon_ser`.

Comment briefly on your results

Code — cell 74

start = time()
for i in range(1000):
    get_value(lexicon_tuples, 'Elephant')
print(time() - start)
start = time()
for i in range(1000):
    get_value_binary(lexicon_tuples, 'Elephant')
print(time() - start)
start = time()
for i in range(10000):
    lexicon_dict['Elephant']
print(time() - start)
start = time()
for i in range(10000):
    lexicon_ser['Elephant']
print(time() - start)

# 4 marks

Notes — cell 75

[Some sensible comment; use your discretion.]

<b>2 marks</b>

Code — cell 76