Program Analysis Term 1, 2016
Assessed Coursework 1
Due date: Submit to Engineering and Informatics School Office by 4pm
on Wednesday 2nd of November.
Return date: Marked coursework will be available for collection from the School office on Tuesday November 22nd.
Assessment: Please answer all questions. A total of 100 marks are avail- able. Credit will be given for partially correct answers.
Avoiding misconduct 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.
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) = 2n log n + 3n5 f2(n) = 100n8 + n7 log n3 f3(n) = 17n log n5
f4(n) = 6n + 67n2
f5(n) = 0.3n5 + 12n2 log n
f6(n) = 13(n + 600)
[15 marks]
Program Analysis Term 1, 2016
2. Specify the running time of each of the following algorithms. Fully explain your answer. Discuss best- and worst-case running times where appropriate, indicating whether or not these are different. Ei- ther give a tight bound for the running time or different upper and lower bounds.
(a) AlgorithmEx1((a1,…,an)): x←0 n
fori←1to 2 do x ← x + ai
for i ← n to n do 2
x ← x + ai
(b) AlgorithmEx2((a1,…,an),(b1,…,bn)): x←0
for i ← 1 to n do if bi ≥ 0
x ← x + ai
[5 marks]
[5 marks]
[5 marks]
[5 marks]
(c) AlgorithmEx3((a1,…,an),(b1,…,bm)): x←0 √
fori←1to⌊ n⌋do
forj ←1to⌊√m⌋do x ← x + (ai + bj )
(d) AlgorithmEx4((a1,…,an),(b1,…,bm)): x←0
for i ← 1 to n do forj ←ntoido
for k ← 1 to m do
x ← x + (ai × aj × bk)
(e) Algorithm Ex5((a1,…,an),(b1,…,bm),(c1,…,cp)): x←0
for i ← 1 to n do j←1
whilebj ̸=0andj ≤mdo k←1
whileck ̸=0andk≤pdo x ← x + (ai × bj × ck) k←k+1
j←j+1
[5 marks]
Program Analysis Term 1, 2016 3. Considertwoalgorithms:AlgorithmAandAlgorithmBbothofwhich
solve some problem that we will call P .
Suppose you know that each of the following four statements is true.
• Statement1:theasymptoticrunningtimeofAlgorithmAisΘ(n4);
• Statement2:theasymptoticrunningtimeofAlgorithmBisO(n6);
• Statement 3: the best-case running time of Algorithm B is Ω(n);
• Statement 4: Any algorithm solving problem P has a worst-case running time of Ω(n3).
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 answer. In some of the questions you are being asked to determine whether or not something is possible. Note that this is not the same as being asked whether or not something must be the case.
(a) The running time of Algorithm A is Ω(n4).
(b) It is possible that the asymptotic running time of Algorithm A is
Θ(n3).
(c) It is possible that the asymptotic running time of Algorithm B is
Θ(n6).
(d) It is possible that the running time of Algorithm B is O(n2).
(e) It is possible that the running time of Algorithm B is Θ(n3).
[5 marks]
[5 marks]
[5 marks]
[5 marks] [5 marks]
Program Analysis Term 1, 2016 4. For this question we will consider the following problem.
Inputs:
D: a document which is a sequence of tokens (t1,…,tn) wheren≥1andfor1≤i≤nthetokenti isastringof characters.
L: a sequence of words (w1,…,wm) where m ≥ 1 and for 1 ≤ i ≤ m the word wi is a string of characters.
Output:
The longest token in the sequence D that is a substring of all of the words in L.
If none of the tokens in D are substrings of the words in L then the empty string should be returned.
A string x is a substring of a string y if the string x can be found anywhere within y.
Note that a string is a substring of itself.
(a) Describe, using pseudo-code, an efficient algorithm that solves this problem.
You can assume that you have access to the following two func- tions:
• length(w) that returns the length of a string w. You can assume that this function takes constant time to find the length of a string.
• substring(w, w′) that returns true if w is a substring of w′, and returns false otherwise. You will need to make a sensible assumption about the running time of this function.
The pseudo-code you write should provide sufficient detail that an experienced programmer would be able to confidently pro- duce an implementation that is faithful to the algorithm that you have in mind. [20 marks]
(b) Carefully discuss the efficiency of the algorithm you have given in answer to Question 4a.
In discussing your algorithm’s efficiency, you should consider both the best-case and worst-case scenarios.
Program Analysis Term 1, 2016 You should make use of upper bounds, lower bounds and tight
bounds.
You must explain your reasoning. No marks will be awarded if you provide a running time without an explanation.
[15 marks]