91影视

Filling the missing details of the algorithm:

function pwr2bin(n)

if n=1 :

return ${1010}_2$

else:

z = pwr2bin (n/2)

return fastmultiply(z,z)

The highlighted part of the algorithm is the missing part.

Description: 鈥� "pwr2bin" is a function that takes a decimal integer and transforms it to binary using the power of ten as an input argument.

鈥� It first validates whether n is equal to 1 and then returns the binary number ${1010}_2$.

鈥� If not, it calls the same function "pwr2bin" with the argument (n/2).

鈥� It then returns the result of the function "fastmultiply" with arguments as the result of the function "pwr2bin."

o The "fastmultiply" technique returns the product of two binary digits.

The textbook contains the algorithm. Figure 2.1 shows the "fastmultiply" algorithm's execution time. is $0\left(n^{\log 3}\right)$.

Thus, it takes T(n/2) time to check the power of $0\left(n^k\right)$and a time of to perform the multiplication. So the recurrence relation is,

$T\left(n\right)=T\left(n/2\right)+\mathit{0}\mathit{\left(}{n}^{\log 3}\mathit{\right)}$ 鈥︹�� (1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT\left(n/b\right)+\mathit{0}\left(n^c\right)$ 鈥︹�� (2)

By comparing equation (1) and (2), the value of 鈥�$n^c$鈥� is 鈥渘鈥�, 鈥渃鈥� is 鈥� ${\log }_{2}3$鈥�, 鈥渂鈥� is 鈥�2鈥� and 鈥渁鈥� is 1.

By master鈥檚 theorem, if the value of $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$, then the running time is,

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{\mathrm{c}}\right)$ 鈥︹�� (3)

Check if $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$:

${\log }_{\mathrm{b}}\mathrm{a}$ 鈥︹�� (4)

Substitute the value of 鈥渂鈥� as 2 and 鈥渁鈥� as 1 in equation (4).

${\log }_{\mathrm{b}}\mathrm{a}={\log }_{2}1=0$

Thus, the value of ${\log }_{b}a$is less than 鈥渃鈥� which is ${\log }_{2}3=1.58$.

Substitute ${\mathrm{n}}^{\mathrm{k}}$as $n^{lo{g}_{2}3}$in equation (3). The running time of algorithm is shown below:

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{{\log }_{2}3}\right)$

Therefore, the algorithm takes a run time of $0\left({\mathrm{n}}^{{\log }_{2}3}\right)$.

Filling the missing details of the algorithm:

function dec2bin(x )

if n = 1:

return binary [x]

else:

split x into two decimal numbers ${\mathrm{x}}_{\mathrm{L}},{\mathrm{x}}_{\mathrm{R}}$with $n/2$digits each

return ( fastmultiply ( pwr2bin(n/2), dec2bin(localid="1659334894381" ${\mathrm{x}}_{\mathrm{L}}$)))+ dec2bin(localid="1659334900087" ${\mathrm{x}}_{\mathrm{R}}$)

The highlighted part of the algorithm is the missing part.

Explanation:

鈥� 鈥渄ec2bin鈥� is the function which accepts the decimal value 鈥渪鈥� as the input parameter and it converts the decimal integer 鈥渪鈥� with 鈥渘鈥� digits into binary.

鈥� Initially, it checks whether the number of digits 鈥渘鈥� is equal to 1 and returns the binary value.

鈥� Otherwise, it splits the decimal into two halves.

鈥� Then, it returns the value returned by the function 鈥渇astmultiply鈥� with parameters as the value of the function 鈥� pwr2bin(n/2) 鈥� and 鈥渄ec2bin($x_L$)鈥� along with the addition of dec2bin(${\mathrm{x}}_{\mathrm{R}}$).

o Here, 鈥減wr2bin鈥� function convert the decimal integer (n/2) into binary.

o 鈥渄ec2bin鈥� function convert the decimal integer 鈥�$x_L$鈥� into binary.

o Then, finally the value returned by the fastmultiply is added with the value returned by dec2bin($x_R$)

The algorithm 鈥渄ec2bin鈥� splits the number into two halves and process which takes a time of 2T(n/2) and as seen already the running time of 鈥渇astmultiply鈥� algorithm is $0\left({\mathrm{n}}^{{\log }_{2}3}\right)$.

So the recurrence relation is,

$\mathrm{T}\left(\mathrm{n}\right)=2\mathrm{T}(\mathrm{n}/2)+\mathit{0}\left({\mathrm{n}}^{{\log }_{2}3}\right)$ 鈥︹�� (1)

Consider the master theorem for the following recurrence equation,

role="math" localid="1659335661292" $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{a}\mathrm{T}(\mathrm{n}/\mathrm{b})+{\mathrm{n}}^{\mathrm{c}}$ 鈥︹�� (2)

By comparing equation (1) and (2), the value of 鈥渘鈥� is 鈥� ${\mathrm{n}}^{{\log }_{2}3}$鈥�, 鈥渃鈥� is ${\log }_{2}3$, 鈥渂鈥� is 鈥�2鈥� and 鈥渁鈥� is 2.

By master鈥檚 theorem, if the value of c > log_ba, then the running time is,

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{\mathrm{c}}\right)$ 鈥︹�� (3)

Check if $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$:

${\log }_{\mathrm{b}}\mathrm{a}$ 鈥︹�� (4)

Substitute the value for 鈥渂鈥� as 2 and 鈥渁鈥� as 2, in equation (4).

${\log }_{\mathrm{b}}\mathrm{a}={\log }_{2}2=1$

Thus, the value of ${\log }_{b}a$is less than 鈥渃鈥� which is role="math" localid="1659335310024" ${\log }_{2}3=1.58$.

Substitute 鈥渃鈥� as ${\log }_{2}3$in equation (3). The running time of algorithm is shown below:

$T\left(n\right)=0\left(n^{{\log }_{2}3}\right)$

Therefore, the algorithm takes a run time of $0\left(n^{{\log }_{2}3}\right)$.