Question 1 [10 Marks]

(a) Perform mergesort on the array  ┌ 25．23．17．29．7．16．33．21┐, showing the result after each

recursive call.  Indicate which range of elements are being considered during each recursive call by outlining those elements.

[2 marks]

(b) Which two operations must a queue implement?  Give the name and a brief description of

these two operations.

[2 marks]

(c) Describe how you would implement a queue using a singly linked list to ensure that both of these operations run in ò(1) time.

[1 mark]

(d) Insert the characters C,  O, M,  P,  L,  E,  X,  I,  T, Y into an initially empty 2-3 tree. You must show the state of the 2-3 tree after every insertion.

[2 marks]

(e) Describe which two rotations must be done to balance the following tree? Give the node and

the direction of the rotation (left or right).

[1 mark]

I   

C              M   

A               D               Y   

N  

(f) Describe how performing a right rotation of the tree above would change the in-order traversal

of the tree. You should give the resultant in-order traversal as part of your answer.

[2 marks]

Question 2 [9 Marks]

(a) Demonstrate how to search for the pattern EAR in the text STRINGSEARCH using Horspool’s

algorithm. How many comparisons were made?

[1 mark]

(b) A pair of strings are anagrams of each other if they contain the exact same letters, for example

"DESSERTS" and "STRESSED" are anagrams.

Write an algorithm which takes as input two strings, 夺 and ╱ , and determines whether or not they are anagrams. Your algorithm should run in ò(n) time where n := max●(夺(．(╱ (e. You may assume that all characters in 夺 and ╱ are uppercase alphabetic characters.

[4 marks]

(c) Write an algorithm which takes as input an array of n strings, of length no longer than m characters long, and outputs the largest set of strings which are all anagrams of each other.

For example, given the array ┌  "ABC",  "ABBA",  "CAB",  "BABA",  "CBA",  "BAC",  "BAD"  ┐ your algorithm would output "ABC",  "CAB",  "CBA",  "BAC" (not necessarily in that order).

Your algorithm must run in ò(mn log n) time.  You may again assume that all characters are uppercase alphabetic characters.

[4 marks]

Question 3 [8 Marks]

(a) For each of the following, explain whether f (n)  · ò(g(n)),  f (n)  · Ω(g(n)), or f (n)  ·

Θ(g(n)). Only solutions with sufficient justification will be awarded marks.

(i)  f (n) = log(n) and g(n) = log(log(n))

(ii)  f (n) = log3 (n) and g(n) = log2 (n2 )

(iii)  f (n) = 100}n + 0．01n2 + 0．001n3  and g(n) = n

(iv)  f (n) = log n + n2  and g(n) = n

[4 marks]

(b)  Solve, using the method of repeated substitutions, the following recurrence relation.  You

must give a closed form expression and a Big-Theta bound for ╱ (n).

╱ (n) = 2╱ (n - 1) + 7．    ╱ (2) = 0

[2 marks]

(c)  Consider the following sorting algorithm:

function CHuNKSoRT(![0．．．n - 1])

if n == 2 and ![0] 女 ![1] then

swap ![0] and ![1]

else

CHuNKSoRT(![0．．． - 1])

CHuNKSoRT(![．．．n - 1])

CHuNKSoRT(![．．． - 1])

CHuNKSoRT(![0．．． - 1])

CHuNKSoRT(![．．．n - 1])

CHuNKSoRT(![．．． - 1])

Write the recurrence relation (including the base case) for the number of comparisons of CHuNK-SoRT.

[1 mark]

(d) Recall, the master theorem states that if ╱ is a recurrence relation such that ╱ (n) = α╱ ()+ Θ(nc ) and ╱ (1) = constant then,

,．Θ (nc )        ╱ (n) · ．Θ (nc log n)

．．Θ ╱nlogb(a)、

if c 女 logb (α)

if c = logb (α)．

if c ! logb (α)

Use the master theorem to find the time complexity of CHuNKSoRT.

[1 mark]

Question 4 [10 Marks]

(a)  Consider a hash table with 8 slots and a hash function h(k) = k  mod 8, which uses open

addressing with a step size of 1. Show the contents of the table after inserting 16, 23, 7, 10 and 12.

[2 marks]

(b) How many comparisons are required to lookup the key  7?   Indicate which comparisons

are performed.  You can assume that we can check if a slot is empty without making any comparisons.

[1 mark]

(c) How many comparisons are required to lookup the key  15?   Indicate which comparisons are performed.  You can assume that we can check if a slot is empty without making any comparisons.

[1 mark]

(d)  Consider again a hash table with 8 slots and a hash function h1 (k) = k  mod 8. This time, the hash table uses separate chaining. Show the state of the hash table after inserting 9, 17, 4, 11 and 1 into an empty hash table.

[1 mark]

(e) Now consider the same hash table (with separate chaining) but with a different hash function

h1 (k) = k  mod 5. Explain why this hash function is not ideal for this hash table.

[1 mark] (f) Use Huffman’s algorithm to construct a Huffman tree for the string "free-coffee".

[2 marks]

(g) What is the encoded version of this string, using your Huffman tree? Let each left child be

0 and each right child be 1. Give the total length of the encoding in bits.

[1 mark]

(h) Using the following Huffman tree (again, using 0 for left and 1 for right), give the codes for

f,  o,  t, and y and decode 0111001000.

o

f

t

[1 mark]

Question 5 [10 Marks]

(a) A string of parentheses ("(" and ")") is valid if no pair of parentheses is “closed” before it

is “opened”. For example, "(())()" is valid while "())(" is not.

The 5 valid strings of 6 parentheses are:                                                        "()()()", "(())()", "()(())", "(()())" and "((()))".

Give 3 (three) examples of valid strings of parentheses containing 8 (eight) parentheses.

[1 mark]

(b) Write a recursive formula and base case(s) for the subproblem 女i , where 女i  is defined as the

number of different valid strings containing exactly i parentheses.

[4 marks]

(c) Using the recursive formula you derived in Part (b) write pseudocode for an algorithm which computes the number of different valid strings containing n parentheses.

[3 marks]

(d) What is the space complexity of your algorithm? Give an answer in Big-Theta notation and justify your answer.

[1 mark]

(e) What is the time complexity of your algorithm? Give an answer in Big-Theta notation and

justify your answer.

[1 mark]