Question #$2-$ Complexity Analysis, Recursion, Searching $10$ marks$]$

a$)$ You have been given a set of numbers in an array and have been asked to compute the sum of the squares of the numbers given. Eg given the following: $3,1,5,2,7,$ your answer should compute the following $3^2+1^2+5^2+2^2+7^2$ obtaining the result $9+1+25+4+49=88.$ Write a recursive solution to this problem using either Java or $C++[4]$

b$)$ Discuss the concept of linear search and binary search. State the BigO notation for both. $[3]$

c$)$ State the BigO notation for each of the for loops below: $[1\mathrm{.}5]$

d$)$ Order your results for $c$ above, from the most efficient to the least efficient. $[1\mathrm{.}5]$

Question #$3-$ Trees & Sorting $[15$ marks$]$

a$)$ Given the set of numbers: $50,70,60,20,90,10,40,100.$ Construct the resulting Binary Search Tree $($BST$)[3]$

b$)$ Perform a PreOrder and a PostOrder traversal of the binary search tree above. $[2]$

c$)$ Discuss the issue that an AVL tree solves and state how it solves the issue. $[1]$

d$)$ Use the numbers: $50,70,60,20,90,10,40,100,97$ to construct an AVL tree. Be sure to identify the rotations which are performed as well as the reason for each rotation $[3]$

e$)$ Given a list containing: $15,28,17,12,18,9,6.$ Show how the selection sort changes the list during the first $3$ iterations $[3]$

f$)$ Given a list containing: $2,8,5,3,9,4,1.$ Show how the bubble sort changes the list during the first $3$ iterations $[3]$