Question 1:
This question is concerned with a functional programming language for manipulating binary rooted trees.
The set BT consists of all binary rooted trees whose vertices are elements of the set N of natural numbers. The empty tree is denoted by Ø.
The following basic primitive functions for manipulating elements of BT are given:
ROOT : BT → N , where ROOT(t) = the root of the non-empty tree t
LEFT : BT → BT , where LEFT(t) = the left subtree of the non-empty tree t RIGHT : BT → BT , where RIGHT(t) = the right subtree of the non-empty tree t
MAKE : BT x N x BT → BT , where MAKE(t, n, s) = the tree with root n, left subtree t and right subtree s
MAX : N x N → N, where MAX(m, n) = the maximum of m and n
(a) Let s be the following element of BT:
Draw the trees
MAKE(Ø, 9, RIGHT(s)) (1 mark)
MAKE(RIGHT(LEFT(s)), ROOT(RIGHT(s)), LEFT(LEFT(s)))
(b) A function F : BT → N is defined as below. F(t) = 0 if t = Ø
F(t) = ROOT(t) if t ≠ Ø and LEFT(t) = RIGHT(t) = Ø
F(t) = F(LEFT(t)) + F(RIGHT(t)) otherwise
Evaluate F(s) where s is the tree in part (a).
Describe the general effect of F on any tree in BT.
(c) The function ROOTMAX : BT → BT replaces the root of an input tree t with the maximum of the roots of the left and right subtrees of t (provided that L(t) ≠ Ø and R(t) ≠ Ø). Give a description, in terms of the basic primitive functions above, of the function ROOTMAX.
Question 2:
The following algorithm, bubblesort, sorts a list of n integers into increasing order by successively comparing adjacent elements and interchanging them if they are in the wrong order.
Input x1, x2, x3, ..., xn;
begin
for i := 1 to (n - 1) do
for j := 1 to (n - i) do if xj>xj+1then
begin
temp:= xj;
xj:= xj+1;
xj+1 := temp ;
end
else{do-nothing};
end
Output x1, x2, x3, ..., xn;
(a) When n = 4, trace the values of i, j, x1, x2, x3 and x4 for the input values x1 = 3, x2 = 2, x3 = 7, x4 =1.
(b) A time complexity function T(n) can be found for bubblesort by counting the number of times the comparison xj > xj +1 is made for a general
positive input n. Show that T(n) is O (n2).
(c) Another sorting algorithm requires 3n log2 n comparisons to sort a list of n integers into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer.