$($a$)(100$ pts$)$ Consider the following algorithm, and assume we have a function log$2($x$)$ which calculates

floor$($log$2$

$($x$))$ in $\backslash$Theta $($log x$)$ time. Describe what function g$1$ computes on input positive integers a and

b$,$ determine a tight $\backslash$Theta bound on its runtime, and argue that it the runtime correct.

$1$: function g$1($a$,$ b$)$

$2$: t $=1$

$3$: s $=0$

$4$: lgb $=$ log$2($b$)$

$5$: for i $=0$ to lgb do

$6$: if b $$ t $=$ t then

$7$: s $+=$ a $$ t

$8$: t $=2$

$9$: return s

$($b$)(80-120$ pts$)$ Modify the algorithm above into a function g$2($a$,$ b$)$ which computes pow$($a$,$ b$).$ You can receive

up to $80$ points for a $\backslash$Theta $($b$)$ algorithm and $120$ points for a $\backslash$Theta $($log b$)$ algorithm.

$($c$)(50$pts$)$ Give an algorithm which computes log$2($b$)$ on input positive integer b$,$ in $\backslash$Theta $($log b$)$ time, and argue

that both the algorithm and the runtime are correct.