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$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)=2T(\frac{n}{2})+n^{2}logn$

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

$3.T(1)=C,T(n)=2T(\frac{n}{2})+3n^2$

$4.T(n)=3T(\frac{n}{2})+n$

Question $2.$ Solve the following recurrences using recursion tree

$1.T(n)=T(\frac{n}{5})+T(\frac{3n}{4})+cn$

$2.T(n)=3T(\frac{n}{2})+n$

Question $3.$

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

$p(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+$dots$+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 $(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 inR. 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

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