Mystery(n: integer>0) 1 temp=1 2 for i = 1 to n do 3 temp=temp*1 4 return temp (

Question

Mystery(n: integer>0)

1      temp=1
2      for i = 1 to n do
3              temp=temp*1
4      return temp

(a) What does this algorithm compute?

(b) Write down the loop invariant for the loop in steps 2-3.

(c) Initialization: Prove that your loop invariant is true before the first iteration of the loop:

(d) Maintenance: Prove that if the loop invariant is true before any (say, the kth) iteration, show also that it remains true before the next(k+1 th) iteration:

(e) Termination: The two proofs above imply that the loop invariant must be true, show that the algorithm computes what you said it does in part(a):

Explanation / Answer

A) this algortihm multiplies 1 with 1, that is 1 * 1 which is performed n times, but it's output will be 1 .

B) Loop invariant is a condition that holds true inside the whole for loop, so here temp = 1 is the loop invariat since temp's value remain 1 in whole loop.

so loop invariant condition = temp = 1

C) in first step temp = 1 and in the first iteration temp = temp *1 = 1*1 , that is =1 so it is true in first iteration

D) using induction you can prove that if for i = k , temp = k times temp * 1 , since multiplication of 1 with 1 always holds = 1 , therefore for n = k , temp = 1,

for n = k +1 , temp(k+1) = temp(k) * temp * 1, now temp(k) =1 we proved before, thefore temp(k+1) = 1*1*1 = 1

so it holds for k+1th iteration

E) in the loop termination temp's value remains same so it terminates successfully and temp = 1 .

Cheers :)

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.