Reference no: EM132498468

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 x₁, x₂, x₃, ..., x_n;

begin

for i := 1 to (n - 1) do

for j := 1 to (n - i) do if x_j>x_j+1then

begin

temp:= x_j;

x_j:= x_j+1;

x_j+1 := temp ;

end

else{do-nothing};

end

Output x₁, x₂, x₃, ..., x_n;

(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 x_j > x_{j +1} is made for a general

positive input n. Show that T(n) is O (n²).

(c) Another sorting algorithm requires 3n log₂ n comparisons to sort a list of n integers into ascending order. Is this algorithm more efficient than bubblesort? Briefly justify your answer.