Please give me answes for following ques Topic: ALGORITHMS Show all work 1 Compu
ID: 3810356 • Letter: P
Question
Please give me answes for following ques Topic: ALGORITHMS Show all work 1 Computer m' where m 0 and where n nuen nino is in bits, ie. n nu +2 r-1. nta-1 2 ml no Algorithm (m,n) Q 1 2. for i 0 to w T m"e note that T is either m 1 or mi m based on the bit ni for j 1 to i T T2 9. return Q (a what is the loop invariant property for the loop described in line 5. (b) prove the invariant property for line 5. is correct (c) what is the loop invariant property for the loop described in line 2. (d) prove the invariant property for line 2. is correctExplanation / Answer
(1)
Invariant property :
a. T <= m2^i
b. T = m2*2*2*...*2 (j times) * ni= m2^jx ni
(2)
At line 4, T can either be 1 or m. Based on this, we have handle two cases.
Case 1 :
If T is 1, [i.e., ni = 0], then no matter how many times we square it, T will always be 1. We just have to prove that the RHS of both the statements above are equal to 1.
a. T<= m0 ==> 1<=1, holds true.
b. Also, m2*2*2*...*2 (j times) * ni = m2^j * ni = m2^j * 0 = 1. Therefore, holds true.
Case 2 :
If T is m [i.e., ni = 1], then for every iteration, we are squaring the value of previous value of T. We can clearly see that T = m -> m2-> m2*2->......-> m2^j, and the final value of the T, m2^j <= m2^i, because j <= i.
--------------------------------------------------------------------------------------------------
(3)
Invariant property : Q = m(2^i * ni) + (2^i-1 * ni-1)+.....+(2*n1) + (n0) and Q <= mn
(4)
Every time after the inner loop runs, T will hold a resultant value of m2i*ni and correspondingly Q has a value of m(2^i-1 * ni-1)+.....+(2*n1) + (n0)
Therefore,
Q = Q.T = m(2^i-1 * ni-1)+.....+(2*n1) + (n0)* m2^i*ni
= m(2^i * ni) + (2^i-1 * ni-1)+.....+(2*n1) + (n0)