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
(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
(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
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, otherwise
Program Analysis Term 1, 2015
(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: listsofcharactersA = (a1,…,an)andB = (b1,…,bm)wheren,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
(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
3. Consider the following functions that give the running times of six algorithms. Arrange them in ascending order of asymptotic running time.
f1(n) = f2(n) = f3(n) = f4(n) = f5(n) = f6(n) =
n2.5 √
2n
n + 10
10n 100n
n2 log n