Question $1$ Set up Recurrence Relations from Algorithms Question $4$ Describe the approach you would take to solve the following recurrence

relation? Explain to support your statement by demonstrating through any of the methods

learned other than Master Method.

$T(n)=2T(\frac{n}{2})+2n+7,$ for $n1,$ with initial values $T(1)=1$ for $n=1$

Question $5$ The following questions relate to advanced trees

$($a$)$ Construct a AVL tree from the given keys.

$7,10,12,3,15,11,4,8,2$

$($b$)$ Construct a $2-4$ tree from the given keys.

$11,25,15,20,40,51,34,68,4,28,60,65,43$

Question $6$ Balancing the trees into AVL Trees

$($a$)$ Balance the following tree into an avl tree

$($b$)$ Balance the given bst into avl tree

$($a$)$ Set up the recurrence relation in terms of $T(n)$ for the following piece of code. You should have

two different variants considering literal and approximated steps.

int Factorial$($int n$)\{$

if$(\}$n$==0$

return $1$;

else if$($n$==1)$

return $1$;

else

$\}$

return n$*$Factorial $(\}$n$-1)$

$($b$)$ Consider the algorithm given below. Write the recurrence relation in their two variant forms,

one with all steps considered and the other with approximation approach.

Question $2$ Solve the following Recurrence Relations

$($a$)$ The recurrence relation is $T(n)=4T(n-1)+1,$ and provide tight asymptotic bounds on its

solution using iteration method. The initial value is $T(0)=1,$ for $n=1.$

$($b$)$ Using the Recursive Tree Method, draw the tree and find the solution before providing the

asymptotic upper bound. The recurrence is $T(n)=4T(\frac{n}{2})+n,$ for $n1,$ with initial conditions

$T(1)=1.$

$($c$)$ Draw the recursive tree for the recurrence $T(n)=4T(\frac{n}{4})+n,$ with initial condition $T(1)=1.$ Add

the labels only with general form, that is$,$ cost of internal nodes plus cost of leave nodes,

without solving the recurrence.