” 159.271编程 写作、 写作data课程编程1901/159.271MTUI DISD TSNICP1MASSEY UNIVERSITYMANAWATU, DISTANCE AND TIANJIN CHINA CAMPUSESEXAMINATION FOR159.271 COMPUTATIONAL THINKINGSEMESTER ONE 2019Time 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 CoS1. Returns-R-Us is a company that makes secure investments for clients. Capitalinvested by clients is put into a term deposit for either 1, 2 or 3 years. Once theterm deposit finishes, the money is re-deposited for another 1 to 3 years. Interestrates for term deposits depend on the length of the deposit, and may differ eachyear (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 investmentsperformed, by comparing actual returns to the best result that could havebeen achieved. Given all historical interest rates available during the time of theinvestment, your Job is to design an algorithm that calculates this optimum.(a) Implement a recursive function optimal, which computes the optimal returnvalue in year n, as a multiple of the original investment amount. Given belowis a data structure which records the available interest rates, for 1, 2 or 3years, that are available to Returns-R-Us for the past n years.# interest rates for each year since start of investment in year 0159.271作业 写作、 写作data课程作业、Python编程设计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 CoS2. In the following let the input consist of graphs with V vertices and E edges. Inputgraphs do not contain duplicate edges.(a) Indicate all pairwise containment relationships between the followingcomplexity classes when input graphs are connected:Note: Containment means O(. . .) O(. . .).(b) Indicate all pairwise containment relationships between the complexityclasses in 2(a) when input graphs can be disconnected.(c) Indicate all Pairwise containment relationships between the complexityclasses in 2(a) when input graphs are trees.(d) Let k denote the maximal degree of vertices in the input graph. Indicate allpairwise 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 containmentrelationships between the complexity classes in 2(d).[3 + 3 + 3 + 3 + 3 = 15 marks]Page 3 of 8 CoS3. A security company is wanting to determine a cost-effective way to place guardposts. In order to reduce costs, they want to determine if they can position at mostk guard posts (represented by vertices in a graph) so that they can reach (cover) allthe houses (also represented by vertices in the graph) with a path of length at mostr. To do this, they want to solve the following decision problem.r-Dominating SetInstance: A graph G = (V, E), and a positive integer kQuestion: Does there exist a size k set S V of vertices such thatevery vertex in V can be reached from some vertex si Sby a path of length at most r? e.g. {si, vj, . . . , vj+r1}(a) The classical Dominating Set problem, where we ask for a size k set S Vof vertices such that every vertex in V can be reached from some vertex si Sby a path of length at most 1, is N P-Hard. Use this fact to show that ther-Dominating Set problem is N P-Hard.(b) Assuming you have shown that this problem is N P-Hard, is it possible to finda 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 shouldutilise a strategy that can be applied without reference to previous choices ateach step.You can use either python or pseudo code.(d) What is the running time of your greedy algorithm? Comment on any datastructures your algorithm uses to achieve this.(e) How good is your greedy algorithm? Draw or describe a counter examplewhere your greedy strategy will not return an optimal solution. Note thatyou can choose any value for r that you like when constructing your counterexample.[6 + 6 + 6 + 6 + 6 = 30 marks]Page 4 of 8 CoS4. Consider the following loop. cards is a list of pairs, where the first component isan 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 cardsin the list.ind = 0attack = cards[ind][0]while ((defence attack) or (cards[ind][1]==1)) and (ind numCards-1):ind +=1attack = 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 CoS5. The partition subroutine for QuickSort partitions the list to be sorted into threeparts. The first element of the list is used as the pivot. All items smaller than thepivot should end up to the left of the pivot, all items greater than the pivot shouldend up to the right of the pivot.Partitioning begins by locating two position markers, we call them leftmark andrightmark, at the beginning and end of the remaining items in the list. We beginby 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 respectto the eventual split point. Now, we can swap these two items and then repeat theprocess again, drawing leftmark and rightmark closer together.At the point where rightmark becomes less than leftmark, we stop. The positionof rightmark is now the split point. The pivot value (first item in the list) can beexchanged 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+1rightmark = lastdone = False#main loopwhile not done:while leftmark = rightmark and alist[leftmark] = pivotvalue:leftmark = leftmark + 1while alist[rightmark] = pivotvalue and rightmark = leftmark:rightmark = rightmark -1if rightmark leftmark:done = Trueelse:temp = alist[leftmark]alist[leftmark] = alist[rightmark]alist[rightmark] = temptemp = alist[first]alist[first] = alist[rightmark]alist[rightmark] = tempreturn rightmarkQuestion 5 Continued Over. . .Page 6 of 8 CoS. . . Question 5 Continued:(a) The main while loop exits when done becomes true. Write down the conditionthat causes this to happen.(b) Write down a post-condition for the main while loop. What should be thesituation 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 eachiteration of the loop.(f) Give an argument to show that your loop invariant, combined with the loopexit condition, causes your post-condition to be fulfilled.[2 + 2 + 3 + 2 + 3 + 3 = 15 marks]Page 7 of 8 CoS6. The Graph 3-Colouring problem takes a graph as input and determines whetheror not its nodes can be coloured with three colours so that two nodes do not havethe same colour if they have an edge between them. In order to design a recursivebacktracking algorithm For this problem, we redefine the problem so that the inputconsists of a graph and a partial colouring of its nodes.(a) An input instance for this problem consists of a graph and a partial colouringof 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 tocreate 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 canbe used to prune the recursion tree?(d) Suppose the problem specification is recast so that the algorithm should returna 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如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
