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
