Question $1.(20$ marks$)$ In class we discussed Karatsuba's divide$-$and$-$conquer algorithm FASTMult $(x,y),$

which takes as inputs the binary representations $x$ and $y$ of two non$-$negative integers, and computes the

binary representation of their product.

a$.$ Following is an algorithm $($with line $3$ left incomplete$),$ which takes as input a positive integer $n$ that is

a power of two, and computes the binary representation of the number ten to $n$th power $($i$.$e$.,$ the number

that is written in decimal as a $1$ followed by $n0s.$

POWEROFTEnTOBinary$($n$)$

if n$=1$ then return $"1010"($the binary string that represents the number ten$)$

else

x:$=???$

return FAStMult$(\}$x$,$x

Complete the missing expression in line $3,$ explain why this algorithm works, and analyze its running time.

b$.$ Following is an algorithm $($with line $6$ left incomplete$),$ which takes as input the decimal representation

$x$ of a non$-$negative integer whose number of digits is a power of $2,$ and computes the binary representation

of that number. Assume that $.$length $(x)$ is a string of digits $0,1,$dots,$9,$ where $x[1]$ is the most

significant and $x[length(x)]$ the least significant digit of the input, and that you have defined an array

binary $d,$ which, for any digit $d,$ gives the binary representation of $d$; i$.$e$.,$ binary $[0]=0,$ binary $[1]=1,$

binary $[2]=10,$ up to binary $[9]=1001.$

Complete the missing expression in line $6,$ explain why this algorithm works, and analyze its running time.

In constructing the missing expression, you may assume that, in addition to the algorithms PowerOf$-$

TenToBinary and FastMult, you are given a function $\frac{?}{\text{S}\text{u}\text{m}}(a,b),$ which takes as input the binary

representations a and $b$ of two non$-$negative integers and returns the binary representation of their sum in

length $(a),$ length $(b)$ time.