Problem $1-[1\mathrm{.}5$ points$]$

$($a$)(1$ point$)$ Assume you start from floor one and you want to reach the top of a building. Due

to health reasons, you decide to take the stairs instead of using the elevator. Depending on

your mood, sometimes you climb one stair at a time or two stairs at a time. Design a linear

time algorithm that given number n of stairs, computes the number of ways to reach the top.

Example: For n $=3$ you can reach the top with three ways $(1+1+1,1+2,2+1).$

$($b$)(0\mathrm{.}5$ points$)$ Give a O$($log n$)$ time algorithm. Hint: A

n

can be computed in log n time for A

being a $2\backslash$times $2$ matrix.