Program Analysis Term 1, 2015 Problem Sheet 2
1. For each of the following problems, complete the algorithm in pseudo-code that solves the problem and discuss the way in which the time that the algorithm takes to run increases as the size of the input grows.
(a) Given a list of positive integers A, the problem is to determine the difference between the largest and smallest elements of A.
Algorithm Range(A) : integer
Input: a list of positive integers A = (a1,…,an) where n ≥ 1
Output: the difference between the largest and smallest values in A
Model Answer: Algorithm Range(A) : integer
Input: a list of positive integers A = (a1,…,an) where n ≥ 1
Output: the difference between the largest and smallest values in A
max ← a1
min ← a1
for i ← 2 to n do
if ai > max then max ← ai
else
if ai < min then
min ← ai return (max − min)
The running time of Range is always linear in the size of A, i.e. the running time is Θ(n).
(b) Given both a character a and a list of characters A, the problem is to deter- mine whether or not a appears as one of the elements of A.
Algorithm ElementOf (a, A) : boolean
Input: a character a and list of characters A = (a1,...,an) where n ≥ 1
Output: True if a = ai for some i and False otherwise
Model Answer: Algorithm ElementOf (a, A) : boolean
Input: a character a and list of characters A = (a1,...,an) where n ≥ 1 Output: True if a = ai for some i and False otherwise
Program Analysis Term 1, 2015
i←1 whilei≤nanda̸=ai do
i←i+1 return (i ≤ n)
The running time of ElementOf increases linearly with the size of A, in the worst case (e.g., when search fails). So the running time is Θ(n) in the worst case and Θ(1) in the best case — overall we can say that the running time is O(n).
(c) Given a list of characters A, the problem is to determine whether or not the input is a palindrome, i.e., whether or not A is the same as its reverse.
Algorithm Palindrome(A) : boolean
Input: a list of characters A = (a1,...,an) where n ≥ 1
Output: True if (a1,...,an) = (an,...,a1) and False otherwise
Model Answer: Algorithm Palindrome(A) : boolean Input: a list of characters A = (a1,...,an) where n ≥ 1
Output: True if (a1,...,an) = (an,...,a1) and False otherwise
i←1
while i ≤ ⌊n/2⌋ and ai = an−i+1 do
i←i+1 return (i > ⌊n/2⌋)
If the input A is a palindrome then the running time of Palindrome increases linearly with the size of A. However, if there is a mismatch of a1 and an then the running time is O(1). So the best-case running time is Θ(1) and the worst-case running time is Θ(n).
2. For each of the following problems, complete the algorithm in pseudo-code that solves the problem and discuss the way in which the time that the algorithm takes to run grows as the size of the input grows.
(a) Given a list of positive and negative integers A, the problem is to establish whether or not there is a continuous sub-sequence of values within this list such that the sum of all the numbers in the sub-sequence is zero. Note that a continuous sub-sequence within a list A will include all elements that appear in A from some position i to some position j where j ≥ i.
Algorithm HasZeroSequence(A) : boolean
Input: a list of integers A = (a1,…,an) where n ≥ 1 j
Output: True if there is some i,j such that i ≤ j and p=i ap = 0 and False,
Program Analysis Term 1, 2015 otherwise
Model Answer: Algorithm HasZeroSequence(A) : boolean
Input: a list of integers A = (a1,…,an) where n ≥ 1 Output: True if there is some i,j such that i ≤ j and otherwise
i←1
s ← undefined
while i ≤ n and not s = 0 do
s ← ai
j←i+1
while j ≤ n and not s = 0 do
s ← s + aj
j←j+1 i←i+1
return (s = 0)
j
p=i ap = 0 and False,
The running time of HasZeroSequence increases in proportion to the square of the size of A, in the worst case. So the running time is Θ(n2) in the worst case, but only Θ(1) in the best case.
(b) Given two lists of characters, A and B, the problem is to produce a list of characters C that contains all of the characters in A that also appear B, such that the relative ordering of the elements in C is the same as the relative order of those elements within A.
Algorithm Intersect(A, B) : C
Input: lists of characters A = (a1, . . . , an) and B = (b1, . . . , bm) where n, m ≥ 1 Output: a list C = (c1,…,ck) of the elements of A also in B with relative
order of elements within C unchanged from that in A
Model Answer: Algorithm Intersect(A, B) : C
Input: lists of characters A = (a1, . . . , an) and B = (b1, . . . , bm) where n, m ≥ 1 Output: a list C = (c1,…,ck) of the elements of A also in B with relative
order of elements within C unchanged from that in A
p←1
for i ← 1 to n do
j←1
whilej≤mandbj ̸=ai do
j←j+1
Program Analysis Term 1, 2015
if j ≤ m then cp ← ai
p←p+1 return C
The running time of Intersect increases as a product nm in the worse case. In the best case it increases proportional to just n. So the running time is Θ(nm) in the worst case and Θ(n) in the best case. We can say that the running time of Intersect is O(nm) and Ω(n).
(c) Given two lists of integers A and B, the problem is to determine whether or not it is the case that the difference between a pair of numbers taken from A appears in B. All possible pair of numbers in A needs to be considered (at least until a pair is found where the absolute difference is one of the numbers in B, if such a pair exists).
Algorithm DifferenceCheck(A, B) : boolean
Input: lists of integers A = (a1,…,an) and B = (b1,…,bm) where n,m ≥ 1
Output: True if for ai − aj = bp for some i, j, p and False otherwise Model Answer: Algorithm DifferenceCheck(A, B) : boolean
Input: lists of integers A = (a1,…,an) and B = (b1,…,bm) where n,m ≥ 1 Output: True if ai − aj = bp for some i, j, p where 1 ≤ i, j ≤ n and 1 ≤ p ≤ m,
and False otherwise
i←1
found ← False
while i ≤ n and not found do
j←1
while j ≤ n and not found do
p←1
while p ≤ m and not found do
found←ai −aj =bp
p←p+1 j←j+1
i←i+1 return found
The running time of DifferenceCheck increases in proportion to the product n2m in the worst case. In the best case it does not grow with n or m. So the running time is Θ(n2m) in the worst case, but only Θ(1) in the best case.
Program Analysis Term 1, 2015 3. Consider the following functions that give the running times of six algorithms.
Arrange them in ascending order of asymptotic running time.
f1(n) = n2.5 f2(n) = √2n f3(n) = n + 10 f4(n) = 10n f5(n) = 100n f6(n) = n2 log n
Model Answer: We know that polynomials (i.e. a sum of terms where n is raised to fixed powers, even if they are not integers) grow slower than exponen- tials. Thus, we will consider f1, f2, f3, f6 as a group, and put f4 and f5 after them. For polynomials fi and fj, we know that fi and fj can be order by comparing the highest exponent on any term in fi to the highest exponent of any term in fj . Thus, we can put f2 before f3 before f1. Now, where to insert f6? Since f1 can be
written as n2√
f3 and f1. Finally, comes f4 and f5. We know that exponentials can be order by their basis, so we put f4 before f5.
n, and since √
n grows faster than log n we can insert f6 between