8. (10 points) Computational problem solving: Proving correctness: Complete the

Question

8. (10 points) Computational problem solving: Proving correctness: Complete the proof by contradiction this algorithm to compute the Fibonacci numbers is correct. function fib(n) 1. if n 0 then return(1) 2. if n=1 then return(1) 3. last-1 4. current-1 5. for i 2 to n do 6. 7. temp-last+current last-current current-temp 9. return(current) 1. Assume the algorithm is in 2. Fibonacci numbers are defined as Fo-1, Fi-1, Fi-F1+F 2 for i>1. 3. So the assumption in (1) implies that there is at least one input parameter n-k, k20, for correct. which the algorithm will produce an incorrect answer So in both cases the algorithm returns the correct answer This implies that there has to be at least one integer k>1, so that when n-k the algorithm does not return the correct answer Fk-Fk-1tFk-z- When n-k and k>1 and steps 3-9 will be executed 5. 6. 7. If k-2, the for loop in steps 5-8 will be executed exactly once. By step 6, temp last + current 1+1- FoF1. Then step 7 updates last to be equal to current F1. Step 7 updates current to be equal to temp which is Fo F1. So the value returned in step 9 is current Fot

Explanation / Answer

Proof by contradiction:

Assume the algorithm is incorrect.

Fibonacci numbers are defined as F0=1,F1=1,Fi=Fi-1 + Fi-2, for i>1.

So the assumption in (1) implies that there is at least one input parameter n=k, k0, for which the algorithm will produce an incorrect answer.

If k=0, then if statement in the step 1 will be executed and returns 0th Fibonacci number that is ‘1’.

If k=1, if statement in the step 2 will be executed and returns 0th Fibonacci number that is ‘1’.

So in both cases the algorithm returns the correct answer.

This implies that there has to be at least on integer k>1, so that when n=k the algorithm does not return the correct answer Fk=Fk-1+Fk-2.

When n=k and k>1, the first two steps will be skipped and steps 3-9 will be executed.

If k=2, the for loop in steps 5-8 will be executed exactly once. By step6, temp=last +current= 1+1 =F0+F1. Then step 7 updates last to be equal to current=F1. Step 8 updates current to be equal to temp which is F0+F1. So the value returned in step 9 is current=F0+F1=F2. This is the correct answer. So the k for which the algorithm fails must be greater than 2.

If k=3, the for loop in steps 5-8 will be executed exactly twice. In the first iteration of loop, By step6, temp=last +current= 1+1 =F0+F1. Then step 7 updates last to be equal to current=F1. Step 8 updates current to be equal to temp which is F0+F1.

Before moving to second iteration last= F1=1 and current=F2=2.

By step 6, temp=last + current=F1+F2=1+2=3. Step 7 updates last to be equal to current=F2. Step 8 updates current to be equal to temp which is F1+F2. So the value returned in step 9 is current=F1+F2=F3. This is the correct answer. So the k for which the algorithm fails must be greater than 3.

If k=4, the for loop in steps 5-8 will be executed exactly thrice.

In the first iteration of loop, By step6, temp=last +current= 1+1 =F0+F1. Then step 7 updates last to be equal to current=F1. Step 8 updates current to be equal to temp which is F0+F1.

Before moving to second iteration last= F1=1 and current=F2=2.

By step 6, temp=last + current=F1+F2=1+2=3. Step 7 updates last to be equal to current=F2. Step 8 updates current to be equal to temp which is F1+F2.

Before moving to third iteration last= F2=2 and current=F3=3.

By step 6, temp=last + current=F2+F3=2+3=5. Step 7 updates last to be equal to current=F3. Step 8 updates current to be equal to temp which is F2+F3.

So the value returned in step 9 is current= F2+F3=F4. This is the correct answer. So the k for which the algorithm fails must be greater than 4.

The above argument can be repeated to show that the algorithm returns correct answer.

That is, for, all k>1 the algorithm returns the correct k-th Fibonacci number.

So there is no k for which the algorithm will return a value not equal to Fk-1+Fk-2. This contradicts (3).

Therefore, the algorithm must be correct.

Note: newly filled statements are in bold style

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

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