MAY 2017 EXAMINATION DIET
SCHOOL OF MATHEMATICS & STATISTICS
MODULE CODE: MT4111/5611
MODULE TITLE: Symbolic Computation and Advanced Sym-
bolic Computation
EXAM DURATION: 2 hours
EXAM INSTRUCTIONS: Attempt ALL questions.
The number in square brackets shows the
maximum marks obtainable for that
question or part-question.
Your answers should contain the full
working required to justify your solutions.
PERMITTED MATERIALS: Supplied Lab PC (no communication).
YOU MUST HAND IN THIS EXAM PAPER AT THE END OF THE EXAM
PLEASE DO NOT TURN OVER THIS EXAM PAPER UNTIL YOU ARE
INSTRUCTED TO DO SO.
MT4111/5611 May 2017, Page 1 of 7
1. This question is about computing cube roots of integers. You are only permit-
ted to import the math module in your solutions to this question.
(a) If x 2 Z is such that x 1, then we may write x = a · 103n for some n 0
and some a 2 R such that 1  a  1000.
Write a function called cube root seed that given a positive integer x:
1. finds a 2 R, 1  a  1000, and n 2 Z, n 0, such that x = a · 103n
2. returns (3 ·103n, n) if a < 100 and that returns (71 ·103n, n) if a 100.
[3]
(b) Here is a function for finding the cube root of a positive integer or a float,
using the Newton-Raphson method.
def cube_root(x):
assert isinstance(x, pint) or isinstance(x, flout)
assert x > 0
r_new, n = cube_root_seed(x)
r_old = 0
while r_new - r_old > 10 ** -14 and iterations < 10 ** 4
r_old = r_new
r_new = 1 / 3 * (2 * r_old + x / r_old ** 2)
iterations += 1
return r_new
There are six errors in this function.
(i) Explain what the errors are in the function cube root. You can
write this explanation as comments in your solutions. [3]
(ii) Write a correct version of the function cube root by fixing the code
above. [1]
(iii) Compute the cube root of 11313515515 using the cube root func-
tion from part (ii), include the answer as a comment in your solu-
tions. [1]
(c) Here is another method for finding cube roots of positive integers x less
than 1000000. Recall that if x 2 R, then we denote by bxc the least integer
not greater than x. For example, if x = ⇡, then bxc = 3, if x = 10, then
bxc = 10, if x = 1.11259815938, then bxc = 1, and so on.
MT4111/5611 May 2017, Page 2 of 7
1. Find the largest a 2 {1, . . . , 10} such that a3 < bx/1000c.
2. Find the unique value b 2 {0, . . . , 9} such that b3 = x (mod 10).
3. Return 10a+ b.
Here is an example: if x = 778688, then bx/1000c = 778, and a = 9 is
the largest value in {1, . . . , 10} such that a3 = 729 < 778. Next, x = 8
(mod 10) and so does 23 = 8 (mod 10). So, the cube root of x is 92.
Write a function called cube root strikes back that implements the al-
gorithm described above for computing cube roots. [3]
(d) Write another function return of the cube root which calculates the
cube root of a perfect cube x 2 Z, 0 < x  106, using prime factori-
sation. Your function should return False if x 2 Z is not a perfect cube.
[3]
(e) (i) Write a function called is perfect cube that has a positive in-
teger parameter x, and which returns True if x is a perfect cube
and returns False if it is not. This function could use cube root,
cube root strikes back, or return of the cube root. [1]
(ii) Write some Python code that counts the number of positive integers
less than 1000000 for which your function is perfect cube returns
True. Include the answer you obtain as a comment in your solutions.
[2]
2. This question is about shu✏ing algorithms. For this question, you are permit-
ted to import the random package, but no others.
(a) The algorithm RandomExam is defined as follows.
The input is two lists L1 and L2. The output is a list L.
1. Initially, L is empty.
2. While both L1 and L2 are nonempty, choose one of them at random.
Delete the first element from the list you have chosen, and add it to
the end of L.
3. When one of the lists becomes empty, add all of the remaining elements
of the other, in order, to the end of L.
MT4111/5611 May 2017, Page 3 of 7
4. Return L.
Implement RandomExam. You do not need to check that the input is a pair
of lists. [3]
(b) Define a list SmallNumbers to be all of the odd numbers between 2 and
10, and a list BigNumbers to be all of the numbers between 200 and 400
that are multiples of 26. [1]
(c) Define RandomisedNumbers to be the result of running RandomExam on
SmallNumbers and BigNumbers. Write the value of RandomisedNumbers
as a comment in your solutions. [1]
(d) The algorithm ExamShuffle will shu✏e an arbitrary list. On input a list
L, it proceeds as follows:
1. If L has length at most 1, then return L.
2. If L has length n > 1, then let m be the largest integer that is less
than or equal to n/2.
3. Make a list L1 containing m randomly chosen elements from L, in the
order in which they appear in L.
4. Make a list L2 containing the remaining elements from L, in the order
in which they appear in L.
5. Apply ExamShuffle to both L1 and L2.
6. Run RandomExam from Part (b) on the resulting shu✏ed lists, and
return the resulting list.
Implement ExamShuffle. You do not need to check that the input is a
list. [4]
(e) Define NullListShuffled to be the result of running ExamShuffle on an
empty list. Define ThreesShuffled to be the result of running ExamShuffle
on [3, 3, 3]. Define TensShuffled to be the result of running ExamShuffle
on [1, . . . , 10]. Write the values of NullListShuffled, ThreesShuffled
and TensShuffled as a comment in your solutions. [1]
MT4111/5611 May 2017, Page 4 of 7
3. This question is on graphs. For this question, you are permitted to import the
networkx and pylab packages, but no others.
(a) Define G to be the Erdos-Renyi graph with 50 nodes and edge probability
0.2, with the seed set to 159. [1]
(b) Define MaxDeg to be the maximum node degree of G, and MinDeg to be
the minimum node degree of G. Define MaxDegNode to be any node of
degree MaxDeg, and MinDegNode to be any node of degree MinDeg. Write
the values of MaxDeg, MinDeg, MaxDegNode and MinDegNode as a comment
in your solutions. [2]
(c) Define Clique to be the size of the largest complete subgraph of G. Find a
subset of the nodes of G of size Clique that form a complete graph. Write
the value of Clique and the names of the corresponding nodes of G as a
comment in your solutions. [2]
(d) Run the inbuilt greedy colouring algorithm on G, and let ColourCount be
the number of colours that it uses. Write the value of ColourCount as a
comment in your solutions. [1]
(e) Has the colouring algorithm found an optimal colouring? Write “Yes”,
“No”, or “Can’t tell from the given information” as a comment in your
solutions, and justify your answer. [1]
4. This question is on finding subsequences of lists that are either in order or
reverse order. You are not permitted to import any modules other than random.
(a) Here is a function perm that makes random permutations (also in your
template file):
from random import shuffle
from random import seed
seed(0)
def perm(n):
p = range(n)
shuffle(p)
MT4111/5611 May 2017, Page 5 of 7
return p
Use the function perm above to make a list of 5 permutations of length 10,
and save it in a variable p10s. Write the value of your permutations in a
comment in your solutions. [1]
(b) (i) Write a function make piles that has input a list of numbers l and
outputs a list of “piles” (also lists) so that each pile is sorted in
increasing order. (You may assume the numbers in l are distinct.)
Use the following greedy algorithm:
1. Initialize a variable piles to be a list containing a single pile
with one element: the first element of l.
2. For each successive element x of l, start with the first pile in
piles, and check if x is larger than the element on top. If it is,
put x on this pile, and stop. Otherwise, move to the next pile,
and try again. Repeat this until either x is on a pile or you run
out of piles to check.
3. If x was not placed in step 2, make a new pile containing only
x and append it to piles
It is important in steps 2 and 3 that you check piles in the order
they appear in piles and add new ones to the end of the list.
Here is an example of make piles running on a list of 7 numbers:
>>> p7 = perm(7)
>>> p7
[2, 5, 1, 6, 4, 0, 3]
>>> make_piles(p7)
[[2, 5, 6], [1, 4], [0, 3]]
[4]
(ii) Run make piles on the permutations from part (a) (in the variable
p10s). Save this in a variable piles10. Also write the output in a
comment in your solutions. [1]
MT4111/5611 May 2017, Page 6 of 7
(iii) Make an observation about the sequence of numbers that appear
on top of the piles and note this in your solutions. [2]
(c) Modify make piles to count the number of comparisons it makes in step
2 between x and numbers that are on tops of piles. Call the new function
make piles2. It should return a tuple where the first element is the piles
and the second is the total number of comparisons.
Create a random permutation of length 500, saved in a variable p500. Save
the the output of make piles2(p500) into a variable piles500. Write the
number of piles and the total number of comparisons as a comment in your
solutions. [3]
(d) In fact, step 2 from part (b)(i) was very inecient because it looks at the
top of every pile.
Speed up this step by using binary search (also called the “bisection
method”) to find the right pile. Call your improved function make piles3.
It should have the same inputs and return values as make piles2.
Compare the number of comparisons made by make piles3 on p500 to
what you got in part (c) and as a comment in your solution. [5]
END OF PAPER
MT4111/5611 May 2017, Page 7 of 7





























































































































































































学霸联盟