首页 > > 详细

159.271讲解、讲解data、Python编程设计调试、辅导Python语言讲解留学生Prolog|讲解留学生Processing

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]

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!