Program Analysis Term 1, 2015
Assessed Coursework 1
Due date: Submit to Engineering and Informatics School Office by 4pm
on Wednesday 4th of November.
Return date: Marked coursework will be available for collection from the School office on Tuesday November 24th.
Assessment: Please answer all questions. A total of 100 marks are avail- able. Credit will be given for partially correct answers.
Avoiding misconduct Do not discuss these questions with anyone other than me or one of the other course tutors. If you do not understand the question then ask me or another course tutor for clarification. If you do submit work that is not your own you must explicitly identify the source.
Program Analysis Term 1, 2015
1. Consider the following functions that give the running times of six algorithms. Arrange them in ascending order of asymptotic running time, and give an explanation of your ordering.
f1(n) = 15n3 + n2 log n
f2(n) = 204(n + 45) + log n f3(n) = log n2
f4(n) = 3n + 250n
f5(n) = 2n log n
f6(n) = 150000n2
2. Specify the running time of each of the following algorithms. You must fully explain your answer to receive full marks.
(a) AlgorithmEx1((a1,…,an),a): x←0
for i ← 1 to n do if ai > a
x ← x + ai return x
(b) AlgorithmEx2((a1,…,an),(b1,…,bm)): x←0
for i ← 1 to min(n, m) do ifai
forj ←itomdo x←x+ai ×bj
solve problem P .
Suppose you know that all of the following statements are true.
Statement1: theasymptoticrunningtimeofAlgorithmAisΘ(n2logn);
Statement 2: the asymptotic running time of Algorithm B is O(n3);
Statement 3: the best-case running time of Algorithm B is Ω(n2);
Statement 4: All algorithms that solve problem P have a worst-case running time that is Ω(n2 log n).
For each of the following statements, indicate whether you have suf- ficient information about the algorithms to justify the claim being made. Fully explain your answers.
(a) We know that the asymptotic running time of Algorithm A is Ω(n2). [5 marks]
(b) It is possible that the asymptotic running time of Algorithm B is Θ(n3). [5 marks]
[5 marks]
[5 marks] 3. Considertwoalgorithms:AlgorithmAandAlgorithmBbothofwhich
i←i+1 return x
Program Analysis Term 1, 2015 (c) It is possible that the asymptotic running time of Algorithm B is
O(n2). [5 marks]
(d) In any scenario where you need to solve instances of problem P , you would achieve better running time by using Algorithm A rather than Algorithm B. [10 marks]
4. You have been sent an email from your friend Zoe who is building an online dictionary of medical terminology for medical students. The dictionary contains a large number of entries, where each entry gives the definition of some piece of biomedical terminology, in the form of a short piece of text.
Zoe has had a clever idea, and is asking for your help to figure out how to make it work. Her idea is intended to address a problem that can arise when a learner finds that they don’t understand the text that appears in the definition of a piece of terminology t because the definition uses another piece of terminology t′ that they don’t yet understand. We can assume that the unknown terminology t′ will be defined in the dictionary, but learners must postpone the task of understanding the definition of t while they look up the entry for t′. Since the same problem can occur when reading this new entry, this process can potentially involve many layers of nesting, and result in confusion.
Zoe has asked you to devise a solution that has the following fea- tures.
(a) Itshouldkeeptrackoftheterminologythatalearnerhasmarked as “understood”.
(b) Given some piece of terminology t that a learner wants to un- derstand, it should find all of the other pieces of terminology that the learner needs to understand before the definition of t can be understood. Let us call this the pre-requisite list for t. Note that pieces of terminology that a learner has already marked as understood should not appear on their pre-requisite lists.
(c) A learner’s pre-requisite list (t1,…,tk) for a piece of terminol- ogy t must be ordered in a way that ensures that the definitions of each of the pieces of the terminology appearing in the list (t1,…,tk) can be understood by the learner in that order. In
Program Analysis Term 1, 2015
other words, when considered by the learner in that order, ev- ery piece of terminology that the learner comes across in the textual definitions will already be understood. This can be ex- pressed formally by saying that for every i where 1 ≤ i ≤ k, when reading the entry for term ti, all of the pieces of terminol- ogy that appear in the definition of ti should either have previ- ously been marked as “understood” by that learner, or be one of the pieces of terminology in the list (t1, . . . , ti−1).
(d) It should able to check that all pieces of terminology in the dic- tionary are learnable: i.e. that pre-requisite lists can always be constructed.
What would you say in response to Zoe’s email? Your aim should be to explain, in reasonable detail, how to design the software that she is looking for. Your description should contain sufficient detail that a competent programmer would be able to produce an implementa- tion of your proposal.
[35 marks]