Thread: Induction, algorithm etc

The Algorithm

1. FindZero(i,j)

2. if j = i then

3. return T[i] =0

4. else

5. k <- i+[(j-i)/2] (I cant make the correct panrenthesis, but they are meant to round down)
6. if T[k] > or = 0 then

7. return FindZero(i,k)

8. else

9. return FindZero(k+1, j)


N = 12
and T are shown in this table:

| -211 | -101 | -80 | -45 | 0 | 3 | 42 | 80 | 204 | 320 | 325 | 531 |

I have to run FindZero(1,12) and I'm really not diciplined enough to trust my calculations.

Could you help me with this first step?

So, i = 1 and j = 12. Then , so we proceed to . We have j - i = 11, 11 / 2 = 5.5, , so k is assigned 1 + 5 = 6. Then T[6] = 3 >= 0, so we call FindZero(1,6), i.e., the new values for i and j are 1 and 6, respectively.

For your verification, the next value of k is 3, and zero is found on the 5th step.

.

..

Nevermind, I figured it out now - thanks.

I need to prove by induction;

j-i < 2^n => A(i, j) =< n

for any random table T with N entries.

for every number i,j,n where 1=< i =< j =< N and n >= 0.

My basisstep is P(0)

j-i < 1 => A(i,j) =< 0

I want to prove p(n) is true and by that I show that p(n+1) is true.

So I need to prove

j-i < 2^(n+1) => A(i,j) =< n+1

My feeling is that I have to show that both j-i < 2^(n+1) is true and A(i,j) =< n+1 is true.

is this what Im supposed to do and if so how?

I need to prove by induction;

j-i < 2^n => A(i, j) =< n

for any random table T with N entries.

for every number i,j,n where 1=< i =< j =< N and n >= 0.

1. You have not defined A(i, j). I assume it is the number of recursive calls in FindZero(i, j).

2. I suspect that even though T is random, it must be ordered.

3. I also suspect that N and n are the same object.

My basisstep is P(0)

j-i < 1 => A(i,j) =< 0

This is what you need to show. Is this indeed true?

I want to prove p(n) is true and by that I show that p(n+1) is true.

No, you assume that P(n) is true and from there you show P(n+1). When you assume, it's like you are payed and you can spend this sum on buying P(n+1); when you prove, it is similar to paying. Also, p and P should not be confused. Finally, it's a good idea to write P(n) (not P(0) or any other special case) explicitly in the beginning. First, this serves to define the letter P (and every object must be properly introduced), and, second, this help eliminate errors when one writes P(n+1).

So I need to prove

j-i < 2^(n+1) => A(i,j) =< n+1

My feeling is that I have to show that both j-i < 2^(n+1) is true and A(i,j) =< n+1 is true.

Again, you assume j-i < 2^(n+1); this is given to you for free. From here, you have to show A(i,j) =< n+1. It's also a good idea to write the induction hypothesis (IH): j-i < 2^n => A(i, j) =< n, which is also given for free.

To show A(i, j) =< n + 1, we look at the algorithm. If i = j, then A(i, j) = 0 <= n + 1. Suppose i <> j. Then we have and at least one recursive call: either A(i, k) or A(k + 1, j). Thus, either A(i, j) = A(i, k) + 1 or A(i, j) = A(k + 1, j) + 1. We could use the IH if we showed that k - i < 2^n and j - (k + 1) < 2^n; this would give us that A(i, k) < n and A(k + 1, j) < n, so in either case we have A(i, j) < n + 1. So, we are left to prove that k - i < 2^n and j - (k + 1) < 2^n.

The first of these inequalities is easier, so let me make a couple of remarks about the second one. It is pretty easy but requires accuracy in finding upper and lower bounds. This skill is very important for the analysis of algorithms.

We have j - k - 1 < 2^n iff j - k <= 2^n since both sides are integers. Next, . To find an upper bound (hopefully, 2^n) for this, we have to find a lower bound for . (Recall that for any a, b and b', a - b <= a - b' iff b >=b', i.e., the inequality is reversed.) You could use the fact that (in fact, strict inequality holds). Make sure you understand why this is the case and try to finish the proof.

I will need some time to get all this in - loads of thanks to you.