xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写-MAY 2017

时间：2021-04-30

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

学霸联盟

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

学霸联盟