Question $1.$ Solve the following recurrences using $($a$)$ repeated substitution method; and $($b$)$ master theorem if applicable and if not say why.

$1.$T$(1)=1,$ T$($n$)=2$T$($n$2)+$n$2$ logn $2.$T$(1)=$C$,$ T$($n$)=$T$($n$1)+$logn $3.$T$(1)=$C$,$ T$($n$)=2$T$($n$2)+3$n$2$

$4.$T $($n$)=3$T $($ n$2)+$ n

Question $2.$ Solve the following recurrences using recursion tree $1.$T$($n$)=$ T$($n$)+$ T$(3$n$)+$ cn

Question $3.$

a$)$ Design a brute$-$force algorithm for computing the value of a polynomial p$($x$)=$anxn $+$an$1$xn$1+...+$a$1$x$+$a$0$

at a given point x$0$ and determine its worst$-$case efficiency class.

b$)$ If the algorithm you designed is in $\backslash$Theta $($n$2),$ design a linear algorithm for this problem.

c$)$ Is it possible to design an algorithm with a better than linear efficiency for this problem?

Question $4.$ Given an unsorted array A$[1..$n$].$ Devise a divide$-$and$-$conquer based algorithm to find the second largest number. $($a$)$ Write the pseudo code, and $($b$)$ What is the complexity?

Question $5.$ Consider a list A$[1..$n$]$ of size n containing real numbers in R$.$ Consider for exam$-$ ple, A $=\{10,3\mathrm{.}5,17\mathrm{.}2,2\mathrm{.}35,15\mathrm{.}45,9\mathrm{.}1,1\mathrm{.}25\}.$ Devise a divide and conquer based algorithm $($must be a single procedure$)$ to compute the average

a$)$ Briefly describe in no more than two lines the basic idea of your algorithm. b$)$ Write the pseudo code of your devised algorithm.

c$)$ Write the recurrence relation expressing the complexity of the algorithm