Question

Determine whether each of the following algorithms is fully correct, and prove that your answer is correct.

Determine whether each of the following algorithms is fully correct, and prove that your answer is correct. 4 5 (a) [10 points) A(2) IN :TER,r> 1 1 r'= 2 p=0 3 while r'> 1 do p=p+1 r' = 2/2 6 return p OUT: p = log2 (b) [10 points) B(2) IN : r ER, 1 > 1 1 while r > 1 do 2 r = x/2 3 if : == 1 + return true 5 else 6 return false OUT: true if r = 2" for some integer n (initially); false otherwise.

Answer 1

solution:

a. Algorithm is not fully correct.

Algorithm should return the value of log_​2

But when the x is not in the form of 2ⁿ (for some n initially), the log_{​​​​2} will return a real number. But variable p can have the value that is of type integer only, as for each iteration in the while loop, the value of p is just incremented by 1.

For example if the x value is 3, then the value of p will be 2 according to the algorithm. But the actual value of log_{​​​​2}3=1.5849.

b. Algorithm is fully correct.

In the while loop, in each iteration the value x that is obtained in the previous iteration is divided by 2. If the value is in the form of 2^n then only x will become 1 at the end. Thus returning true. Otherwise at the end it will be some rational value less than 1. Hence it will return false.

please give me like