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$

log n

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

$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

$5$

$)+$ T$($

$3$n

$4$

$)+$ cn

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

n

$2$

$)+$ n

Question $3.$

a$)$ Design a brute$-$force algorithm for computing the value of a polynomial

p$($x$)=$ anx

n $+$ an$1$x

n$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 example, 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