159.271讲解、讲解data、Python编程设计调试、辅导Python语言

日期：2020-06-07 07:08

1901/159.271

MTUI DISD TSNI

CP1

MASSEY UNIVERSITY

MANAWATU, DISTANCE AND TIANJIN CHINA CAMPUSES

EXAMINATION FOR

159.271 COMPUTATIONAL THINKING

SEMESTER ONE 2019

Time allowed is THREE (3) hours.

All students are required to answer ALL questions.

There are 6 questions altogether.

Total marks: 100.

This is a closed book examination.

Write your answers in the Blue Answer Book supplied.

Non-programmable calculators only are permitted.

Students may NOT remove any part of this question paper from the exam room.

The exam paper will be made available on the University Library website.

Page 1 of 8 CoS

1. Returns-R-Us is a company that makes secure investments for clients. Capital

invested by clients is put into a term deposit for either 1, 2 or 3 years. Once the

term deposit finishes, the money is re-deposited for another 1 to 3 years. Interest

rates for term deposits depend on the length of the deposit, and may differ each

year (the rate for a multi-year deposit is fixed when the deposit is made.)

After operating for many years, the company wants to assess how well their investments

performed, by comparing actual returns to the best result that could have

been achieved. Given all historical interest rates available during the time of the

investment, your job is to design an algorithm that calculates this optimum.

(a) Implement a recursive function optimal, which computes the optimal return

value in year n, as a multiple of the original investment amount. Given below

is a data structure which records the available interest rates, for 1, 2 or 3

years, that are available to Returns-R-Us for the past n years.

# interest rates for each year since start of investment in year 0

rates_by_year = [

{ ’one_year’ : 1.03, ’two_years’ : 1.04, ’three_years’ : 1.035 },

{ ’one_year’ : 1.05, ’two_years’ : 1.045, ’three_years’ : 1.04 },

...

];

def optimal(year):

if year == 0: return 1; # investment for 0 years

# last investment is for x years

...

Note: Both python or pseudo-code are fine.

(b) Give a sensible upper bound for the complexity of function optimal.

(c) Design an algorithm that solves the same problem in polynomial time.

(d) Give a sensible upper bound for the complexity of your new implementation.

[6 + 2 + 6 + 2 = 16 marks]

Page 2 of 8 CoS

2. In the following let the input consist of graphs with V vertices and E edges. Input

graphs do not contain duplicate edges.

(a) Indicate all pairwise containment relationships between the following

complexity classes when input graphs are connected:

Note: Containment means O(. . .) ? O(. . .).

(b) Indicate all pairwise containment relationships between the complexity

classes in 2(a) when input graphs can be disconnected.

(c) Indicate all pairwise containment relationships between the complexity

classes in 2(a) when input graphs are trees.

(d) Let k denote the maximal degree of vertices in the input graph. Indicate all

pairwise containment relationships between the complexity classes:

O(V · k) O(V + k) O(E)

Note: The degree of a vertex is the number of its neighbours.

(e) Let k instead denote the minimal degree. Indicate all pairwise containment

relationships between the complexity classes in 2(d).

[3 + 3 + 3 + 3 + 3 = 15 marks]

Page 3 of 8 CoS

3. A security company is wanting to determine a cost-effective way to place guard

posts. In order to reduce costs, they want to determine if they can position at most

k guard posts (represented by vertices in a graph) so that they can reach (cover) all

the houses (also represented by vertices in the graph) with a path of length at most

r. To do this, they want to solve the following decision problem.

r-Dominating Set

Instance: A graph G = (V, E), and a positive integer k

Question: Does there exist a size k set S ? V of vertices such that

every vertex in V can be reached from some vertex si ∈ S

by a path of length at most r? e.g. {si, vj, . . . , vj+r?1}

(a) The classical Dominating Set problem, where we ask for a size k set S ? V

of vertices such that every vertex in V can be reached from some vertex si ∈ S

by a path of length at most 1, is N P-Hard. Use this fact to show that the

r-Dominating Set problem is N P-Hard.

(b) Assuming you have shown that this problem is N P-Hard, is it possible to find

a polynomial time algorithm to solve it?

Explain your answer.

(c) Describe a greedy algorithm to find a reasonable, but perhaps non-optimal,

solution for r-Dominating Set. Note that your greedy algorithm should

utilise a strategy that can be applied without reference to previous choices at

each step.

You can use either python or pseudo code.

(d) What is the running time of your greedy algorithm? Comment on any data

structures your algorithm uses to achieve this.

(e) How good is your greedy algorithm? Draw or describe a counter example

where your greedy strategy will not return an optimal solution. Note that

you can choose any value for r that you like when constructing your counter

example.

[6 + 6 + 6 + 6 + 6 = 30 marks]

Page 4 of 8 CoS

4. Consider the following loop. cards is a list of pairs, where the first component is

an integer representing an attack value and the second component is either 0 or 1,

defence is an integer representing a defence value, numCards is the number of cards

in the list.

ind = 0

attack = cards[ind][0]

while ((defence < attack) or (cards[ind][1]==1)) and (ind < numCards-1):

ind +=1

attack = cards[ind][0]

(a) Let A = (defence < attack), let B = (cards[ind][1]==1),

let C = (ind < numCards-1).

Draw the truth table, in terms of A, B and C, for the while condition.

(b) Write down the loop exit condition, i.e., the negation of the while condition.

(c) Give an argument to show that the loop exit condition is eventually achieved.

(d) If the loop exits before the end of the list is reached, what can be deduced?

[3 + 3 + 3 + 3 = 12 marks]

Page 5 of 8 CoS

5. The partition subroutine for QuickSort partitions the list to be sorted into three

parts. The first element of the list is used as the pivot. All items smaller than the

pivot should end up to the left of the pivot, all items greater than the pivot should

end up to the right of the pivot.

Partitioning begins by locating two position markers, we call them leftmark and

rightmark, at the beginning and end of the remaining items in the list. We begin

by increasing leftmark until we find a value that is greater than the pivot value.

We then decrease rightmark until we find a value that is less than the pivot value.

At this point we have discovered two items that are on the wrong sides with respect

to the eventual split point. Now, we can swap these two items and then repeat the

process again, drawing leftmark and rightmark closer together.

At the point where rightmark becomes less than leftmark, we stop. The position

of rightmark is now the split point. The pivot value (first item in the list) can be

exchanged with the contents of the split point and the pivot value is now in place.

Python code for this subroutine is given here.

def partition(alist,first,last):

pivotvalue = alist[first]

leftmark = first+1

rightmark = last

done = False

#main loop

while not done:

while leftmark <= rightmark and alist[leftmark] <= pivotvalue:

leftmark = leftmark + 1

while alist[rightmark] >= pivotvalue and rightmark >= leftmark:

rightmark = rightmark -1

if rightmark < leftmark:

done = True

else:

temp = alist[leftmark]

alist[leftmark] = alist[rightmark]

alist[rightmark] = temp

temp = alist[first]

alist[first] = alist[rightmark]

alist[rightmark] = temp

return rightmark

Question 5 Continued Over. . .

Page 6 of 8 CoS

. . . Question 5 Continued:

(a) The main while loop exits when done becomes true. Write down the condition

that causes this to happen.

(b) Write down a post-condition for the main while loop. What should be the

situation when this main loop is finished?

(c) Write down a meaningful loop invariant for the main while loop.

(d) Give an argument to show that your loop invariant is established, i.e. True,

before entry to the main loop for the first time.

(e) Give an argument to show that your loop invariant is maintained on each

iteration of the loop.

(f) Give an argument to show that your loop invariant, combined with the loop

exit condition, causes your post-condition to be fulfilled.

[2 + 2 + 3 + 2 + 3 + 3 = 15 marks]

Page 7 of 8 CoS

6. The Graph 3-Colouring problem takes a graph as input and determines whether

or not its nodes can be coloured with three colours so that two nodes do not have

the same colour if they have an edge between them. In order to design a recursive

backtracking algorithm for this problem, we redefine the problem so that the input

consists of a graph and a partial colouring of its nodes.

(a) An input instance for this problem consists of a graph and a partial colouring

of its nodes. Given an input instance, what is a valid solution for the problem?

(b) Given an input instance, what question should be asked about the solution to

create a small number of recursively solvable sub-instances?

(c) The problem specification only asks about the existence of a valid colouring.

Hence the algorithm can stop if one is found. What other basic strategy can

be used to prune the recursion tree?

(d) Suppose the problem specification is recast so that the algorithm should return

a 3-colouring, if one exists, with the fewest number of nodes coloured green.

What is a valid solution for the problem now?

(e) What is the cost of a valid solution for this new problem?

(f) How can we prune the recursion tree for this new problem?

[1 + 2 + 2 + 2 + 2 + 3 = 12 marks]

+ + + + + + + +

Page 8 of 8 CoS