[Solved]: Prove correctness of recursive algorithm

Problem Detail: 

I have this java function:

public int foo(ArrayList l, int n) {   if(n <= 1)     return l.get(0);    if(l.get(0) < l.get(1))     l.remove(1);   else     l.remove(0);    foo(l, n-1); } 

So I figure to show that the algorithm is correct I would use an induction proof. However what I am not so sure about is how to go about doing the proof. Will I fist need to derive some sort of mathematical formula for this function and prove that?

Asked By : Steph

Answered By : hengxin

Generally, you should follow the instructions given by @vonbrand to carry out a mathematical induction proof for a recursive algorithm. Now I would like to show you more hints.

---

Playing with a small test case, we know that we should prove the following theorem:

Theorem: The function foo always returns the minimum value of the original list $l$.

---

To carry out a mathematical induction on the size $n$ of list, we go through the following three steps:

• Base Case: $n = 1$. In this case, you obtain $l[0]$ which is trivially the minimum. (Note that foo throws an exception for case $n = 0$.)
• Inductive Hypothesis: Suppose that the theorem holds for $2 \le n \le k$.
• Inductive Step: Consider $n = k + 1$. You should prove that (This is left as an exercise) $$\min(\text{modified list } l' \text{ by the `if/else` statement and of size } k ) = \min(\text{original list } l \text{ of size } k+1).$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52193

 Ask a Question

 Download Related Notes/Documents