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 the 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