Question 1 [2 Marks]
We know, from lectures, the following facts. For 0 < ε < 1 < c,
where f(n) ≺ g(n) means both f(n) ∈ O(g(n)) and g(n) 6∈ O(f(n)) (i.e. g(n) is not in O(f(n))).
For the following pairs of functions, f(n),g(n), determine if f(n) ∈ Θ(g(n)), f(n) ∈ O(g(n)), or f(n) ∈
Ω(g(n)), making the strongest statement possible. That is, if both f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n))
are true, you must answer with the form f(n) ∈ Θ(g(n)). You must answer with f(n) on the left and
g(n) on the right, for example, you may not answer g(n) ∈ O(f(n)).
You must show all working. A correct answer that does not show your working will result in 0 marks.
Question 2 [2 Marks]
A string of characters is called a palindrome if reading the characters from left to right gives the same
sequence as reading the characters from right to left.
For example: abccba, ahgiigha and abgllggllgba are all palindromes while abcdabcd, lghddgl and
abcd are not.
Write the pseudocode for an algorithm which, given a string and its length n, can identify a palindrome
using only one scan from left to right (which means you can only access each letter once). Your
algorithm must employ the use of either a queue or a stack, and you must justify your choice.
If you use a stack myou must use PUSH() and POP(), and if you use a queue you must use ENQUEUE()
and DEQUEUE().
Assume for simplicity every input will be of even length.
Page 3 of 5
Question 3 [3 Marks]
The following graph represents a road network where each edge presents a road segment. The costs of
the road segments are given in the figure below. There are three hospitals at nodes B, D, and E, and an
accident occurs at node H.
(a) Which algorithm would you use to find the nearest hospital from the accident. Explain how and
why you would use this algorithm.
(b) Which is the nearest hospital, which path would you take and what is the cost of this path? You
must show the execution of the algorithm described above.
(c) List the order of the nodes visited from H in the graph when a breadth-first search is used.
You should break ties in alphabetic order.
Page 4 of 5
Question 4 [3 marks]
Consider the following recursive function, which takes an unordered array of integers, A, and an integer,
k, and returns TRUE if k appears in A and FALSE otherwise.
function THIRDSSEARCH(A[0..n-1], k)
if n == 0 then
return FALSE
else if n == 1 then
return (A[0] == k)
else
a ← THIRDSSEARCH(A[0..n/3−1], k)
b ← THIRDSSEARCH(A[n/3..n×2/3−1], k)
c ← THIRDSSEARCH(A[n×2/3..n−1], k)
return (a OR b OR c)
For simplicity, you may assume the input array is of length n = 3
m for some positive integer m, so that
each recursive call gets an exact third of the input array.
(a) Write down, and solve, a recursive formula W(n) = ... which describes the number of steps taken
by THIRDSSEARCH on an array of length n, for the worst case input. Make sure you include the
base case(s). Keep in mind that the basic operation is usually the most frequent or most expensive
operation. Remember the formula for the geometric series states that.
(b) Use the language of Ω,O,Θ to bound the time complexity of THIRDSSEARCH, using T(n) for its
runtime. You must include an upper and lower bound. Full marks are awarded only to the tightest
possible bounds.
(c) Explain how THIRDSSEARCH could be slightly modified to improve its efficiency in the best case,
and repeat the analysis from part (b), with justification.