$($a$)$ Describe your algorithm clearly in English.

$($b$)$ Give pseudocode.

$($c$)$ Argue correctness, even if you don$$t give a formal proof and give a convincing

argument instead.

$($d$)$ Give with explanation the best upper bound that you can for the running time

ii$)(8$ points$)$ Give a non$-$recursive algorithm that asymptotically performs fewer addi$-$

tions than the recursive algorithm. Discuss the running time of the new algorithm.

iii$)(15$ points$)$ Give an algorithm to compute $F_n$ in $O(logn)$ time using only integer

additions and multiplications.

Hint: Observe that

$\left[\begin{array}{c}{F}_2\\ F_1\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]*\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right].$

Can you use this observation to compute $F_n?$

iv$)(15$ points$)$ The Fibonacci Plus numbers are defined below $(n,$a and $b$ are all inte$-$

gers$).$

$P_n=\{\begin{array}{ccc}a,& if& n=0\\ b,& if& n=1\\ P_{n-1}+2P_{n-2}+3n,& if& n2\end{array}$

Give an algorithm to compute $P_n$ in $O(logn)$ time.

Hint: Similarly to part iii$),$ find a suitable matrix to apply to the initial vector

${\left[\begin{array}{cccc}{P}_1& P_0& 2& 1\end{array}\right]}^T$ so that $P_2$ is an entry of the resulting vector. $($Other choices of

initial vector$-$and accordingly, matrix$-$may work too.$)$ Then show how to compute

$P_n.$

$($b$)(21$ points$)$ Now assume that adding two $m-$bit integers requires $(m)$ time and that

multiplying two $m-$bit integers requires $(m^2)$ time. Analyze the running time of the first

three algorithms in part $($a$)$ under this more reasonable cost measure for the elementary

arithmetic operations.