$1.(10$ points$)$ Let y and z be n$-$bit integers, where n is a power of $3.$ Consider the following

divide$-$and$-$conquer algorithm to compute the product yz$.$

Divide y into three n

$3-$bit pieces, a$,$ b$,$ and c; thus y $=$ a$22$n$/3+$ b$2$n$/3+$ c$,$ where the powers of

$2$ denote appropriate bit$-$shifting. Similarly, divide z into pieces d$,$ e$,$ and f $.$ Now compute yz

recursively as:

yz $=$ ad$24$n$/3+($ae $+$ bd$)2$n $+($af $+$ be $+$ cd$)22$n$/3+($bf $+$ ce$)2$n$/3+$ cf$.$

You may ignore the issue of $$carries$$ throughout this problem.

$($a$)$ Write down the recurrence, T $($n$),$ for the worst$-$case running time of this algorithm. Analyze

T $($n$)$ using the Little Master Theorem and determine the running time.

With a view towards improving the running time in part $($a$),$ consider the following approach,

where we first compute certain intermediate products $($r$1,...,$ r$6)$ recursively and use these along

with additions and bit$-$shifts to compute yz$.$

r$1=?,$ r$2=($a $+$ b$)($d $+$ e$),$ r$3=$ be$,$ r$4=?,$ r$5=$ cf$,$ r$6=?,$ and yz $=?.$

$($b$)$ Fill in the missing information above for r$1,$ r$4,$ and r$6$ and show how to compute yz$.$ Try to

use as few multiplications as you can to compute r$1,$ r$4,$ and r$6.$

$($c$)$ Write down the recurrence, T $($n$),$ for the worst$-$case running time of this algorithm. Analyze

T $($n$)$ using the Little Master Theorem and determine the running time. How does it compare with

the running time of the algorithm we designed in class, where we divided the input integers into

halves?