Page 1 of 8 COMP2009-E1 COMP2009 -E1 Turn over The University of Nottingham SCHOOL OF COMPUTER SCIENCE A LEVEL 2 MODULE, FULL YEAR, 2019-2020 ALGORITHMS, CORRECTNESS AND EFFICIENCY (Reassessment Examination) Deadline for submission is Tuesday 25th of August at 10am (UK time) Open-book examination. Answer ALL FIVE questions Marks available for sections of questions are shown in brackets in the right-hand margin Suggested time to complete the paper is about 4-6 hours This open-book examination will be marked out of 100. You can write your answers using word processing software (such as Microsoft Word) and include within the Word document scanned or photographed portions that you have written by hand. Alternatively, you can write it all by hand and use a scanning system (such as Microsoft Office Lens) to produce a single PDF. Submit your answers containing all the work you wish to have marked as a single PDF file, maximum size 250MB, with each page in the correct orientation, to the appropriate dropbox on the module’s Moodle page. Start each answer on a new page. Use the standard naming convention for your document: YourStudentID_COMP2009.pdf. Write your student ID number at the top of each page of your answers. Do not include your name. Although you may use any notes or resources you wish to help you complete this open-book examination, the academic misconduct policy that applies to your coursework also applies here. You must be careful to avoid plagiarism, collusion or false authorship. Please familiarise yourself with the Faculty of Science Statement on Academic Integrity. This statement refers to, and does not replace, the University policy which stipulates severe penalties for academic misconduct. Please check the box indicated on Moodle to confirm that you have read this statement and that you understand it. Staff are not permitted to answer assessment or teaching queries during the period in which your open-book examination is live. If you spot what you think may be an error on the exam paper, note this in your submission but answer the question as written. The standard University of Nottingham penalty (5% deduction per working day) will apply to any late submission of this work. Page 2 of 8 COMP2009-E1 COMP2009-E1 1. This question is concerned with the ‘big-Oh’ family and recurrence relations. (20 marks total) (a) The usual definition of ‘big-Oh’ is that f(n) is O( g(n) ) if and only if there exists c and n0, such that, forall n ≥ n0 f(n) ≤ c g(n) Carefully explain, in your own words, the reasoning and motivation that justify this definition. Also, explain, with an example why the following (incorrect) definition, would not be suitable or useful: f(n) is O( g(n) ) if and only if there exists n0, such that, forall n ≥ n0, there exists c such that, f(n) ≤ c g(n) (6 marks) (b) Give the definitions of big-Omega and little-oh by completing each of the following, and for each one you should also briefly explain, in your own words, the reasoning and motivation that justify the definitions: i) ‘big-Omega’: f(n) is Ω( g(n) ) …. ii) ‘little-oh’: f(n) is o( g(n) ) …. (3 marks) (c) Consider the function 4 sum(n/2,n) if n is even f(n) = 2 n – 1 + sum(n-3,n) otherwise (i.e. if n is odd) where sum( j,k ) is a ‘partial arithmetic sum’ of the integers from j up to k, that is 0 if j > k sum(j,k) = j + (j+1) + (j+2) + … + k otherwise e.g. sum(3,4) = 3 + 4 = 7, etc. Note that sum(j,k) = sum(1,k) – sum(1,j-1) Page 3 of 8 COMP2009-E1 COMP2009-E1 Turn over From the definitions: i) Prove or disprove that f(n) is O( n2 ) (`Big-Oh of n squared’). ii) Prove or disprove that f(n) is Ω( n2 ) (`Big-Omega of n squared’). iii) Prove or disprove that f(n) is o( n2 ) (`little-oh of n squared’) In each of the three cases, you should also give an explanation of why the result is reasonable and matches the motivations underlying the appropriate definition. (7 marks) (d) Consider `perfect 5- trees’ that are defined similarly to perfect binary trees except that each internal node must have precisely 5 children, rather than 2, and the leaf nodes in the deepest layer have no children. Suppose that the total number of nodes at precisely depth d is designated by n(d). For example, the root node has depth d=0, and is the only node at that depth, and so n(0) = 1. (Note that n(d) is only the number of nodes at exactly depth d, and is not ‘the total number of nodes at depth d or less’.) Give a recurrence formula for n(d), showing how you arrive at the formula. Solve the recurrence relation, showing how you arrive at the solution. Then prove your answer is correct using induction. (4 marks) Page 4 of 8 COMP2009-E1 COMP2009-E1 2. This question concerns correctness of algorithms. (20 marks total) (a) A is an array of integers of length A.length indexed from 1 to A.length. State an assertion in Predicate Calculus that expresses that each element in A after the first two elements is the sum of the two preceding elements. (2 marks) (b) Given the program: if (y > 100) z = 100 else z = y ; x = z – 90 ; w = x * 5 use the proof rules for Assignment, Composition, Implied and If-Then-Else of Hoare’s proof calculus to derive the precondition corresponding to the postcondition { w =< 50 } Your answer should show each step in the derivation. (8 marks) (c) Consider the algorithm Reverse below that copies the values in array A into array B in reverse order, and returns array B as result: Reverse(A,B) n = A.length for(i = 1 to n) B[n - i + 1] = A[i] return B (i) Assuming A and B both have length n (i.e., n = A.length = B.length) and both arrays are indexed from 1 to the length of the array, state a loop invariant for the for loop (in English or Predicate Calculus) that can be used to prove correctness of Reverse. (2 marks) (ii) Give a proof of correctness of Reverse. (Hint: state pre- and postcondtions for Reverse and use the loop invariant to show that the postcondition follows necessarily from the precondition). (8 marks) Page 5 of 8 COMP2009-E1 COMP2009-E1 Turn over 3. This question is concerned with heaps. (25 marks total) (a) Define the properties that make a binary tree into a heap (specifically, a `minheap’ with the root containing the minimum value), and explain the reasons for the properties. (4 marks) (b) Give the standard system for converting a binary tree to be stored in an array. Give an argument for why it is correct, in the sense that it guarantees that no two nodes of the tree map to the same index of the array. (4 marks) (c) Using the following heap, stored as an array, show how to perform the removeMin() operation. Carefully explain how the removeMin() method guarantees that the heap properties remain satisfied in general. (5 marks) (d) Instead of using a binary tree, consider using a quad-tree – in which each node can have up to four children - but other than this the properties of the tree are the same as for th e binary heap. Show how to modify your answer from part (b) to apply to this system, so that the quad-tree is stored in an array, and give an example of how it works. (Hint: the index assigned to the root of the tree should be the same, as in (b)). Then, compare and contrast such a “quad-heap” with the usual binary heap. In particular, include one reason that it might gain an advantage, and one reason it might have a disadvantage. (6 marks) (e) Suppose that it is necessary to extend the heap with an operation that will support changing the value of a given key. Specifically, it needs to support an operation bool changeKey(int oldKey, int newKey) Assume that the keys are unique, no duplicate keys are permitted. If there is a key in the heap with value oldKey, and no existing entry with key newKey, it will change it to newKey, keeping the the heap properties and returning true. If there is no key in the heap with value oldKey, or an existing entry has value newKey, then it will take no action and return false. Show a method to implement this operation efficiently – so, with n entries in the heap, - 2 4 3 8 7 Page 6 of 8 COMP2009-E1 COMP2009-E1 it takes at most sub-linear, o(n), time. Explain the workings and reasoning behind the method, and also the complexity (big-Oh) behaviour. Hint: Use an auxiliary Map to store the locations of the keys within the array, and you can assume that an efficient (logarithmic time) implementation of the Map is given. (You do not need to explain the internal workings of such a Map.) (6 marks) Page 7 of 8 COMP2009-E1 COMP2009-E1 Turn over 4. This question concerns string matching. (20 marks total) (a) The algorithm MatchPatterns below returns the offset (shift) s of the first occurrence of any pattern in an array of k > 0 patterns P in a text T and -1 if no pattern in P occurs in T. That is, the first pattern in P is the array P[1] (with length P[1].length), the second pattern is the array P[2], and the last pattern is the array P[k], where k = P.length. MatchPatterns(T,P) for(i = 1 to P.length) for(s = 0 to T.length) j = 1 while(j =< P[i].length and j =< T.length and P[i][j] == T[s + j]) j++ if(j == P[i].length + 1) return s return -1 assuming MatchPatterns is only called when the length of the shortest pattern in P is less than or equal to the length of T: (i) what is the best case big-Oh complexity of MatchPatterns; explain your answer (4 marks) (ii) what is the worst case big-Oh complexity of MatchPatterns; explain your answer (4 marks) (b) A palindrome is a sequence of characters that reads the same backwards as forwards, e.g., “abba”. The algorithm FindPalindrome below returns the offset (shift) of the longest even-length palindrome in a text T and -1 if T does not contain a palindrome. FindPalindrome(T) k = T.length while(k > 1) for(s = 0 to T.length – k) j = 1 while(j =< k/2 and T[s + j] == T[s + k – j]) j++ if(j == (k/2) + 1) return s k = k - 2 return -1 (i) Assuming that T is indexed from 1 to the length of the array, state loop invariants (in English or Predicate Calculus) for each of the loops in FindPalindrome that can be used to prove the correctness of the algorithm. (6 marks) (ii) Show initialisation and maintenance of the outer while loop. (Hint: to show initialisation and maintenance of the outer while loop, you will need to show initialisation and maintenance of the inner for and while loops.) You do not need to show correctness of the whole algorithm, or termination. (6 marks) Page 8 of 8 COMP2009-E1 COMP2009-E1 5. This question concerns Maps and Minimum Spanning Trees. (15 marks total) (a) Explain the linear probing method for hashmaps. Your answer should include a way to handle deletions. You should also include an example of its usage, that you have devised, and that illustrates the key points. (6 marks) (b) Consider an extension to hashmaps in which two separate hashmaps HT and HF are used, and a Boolean function, B(n), is provided. For every key, n, B(n) is computed, and if B(n)=true then HT is used, otherwise HF is used. Discuss this scheme, giving a potential advantage and also a potential disadvantage. (5 marks) (c) Consider Minimum Spanning Trees and briefly give Prim’s algorithm for finding an optimal answer. In your own words, give an argument for why the algorithm is correct; that is, why it always produces an optimal spanning tree. (4 marks) END
