Results 1 to 8 of 8

Math Help - Induction, algorithm etc

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    50

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    So, i = 1 and j = 12. Then i\ne j, so we proceed to k\gets i+\lfloor (j-i)/2\rfloor. We have j - i = 11, 11 / 2 = 5.5, \lfloor 5.5\rfloor = 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    .
    Last edited by Madspeter; October 24th 2010 at 07:35 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    ..
    Last edited by Madspeter; October 24th 2010 at 07:35 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    Nevermind, I figured it out now - thanks.
    Last edited by Madspeter; October 24th 2010 at 07:32 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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 k=i+\lfloor (j-i)/2\rfloor 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, j - k = j - i - \lfloor (j-i)/2\rfloor. To find an upper bound (hopefully, 2^n) for this, we have to find a lower bound for \lfloor (j-i)/2\rfloor. (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 \lfloor (j-i)/2\rfloor\ge (j-i)/2-1 (in fact, strict inequality holds). Make sure you understand why this is the case and try to finish the proof.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Sep 2009
    Posts
    50
    I will need some time to get all this in - loads of thanks to you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 02:46 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2007, 11:47 PM

Search Tags


/mathhelpforum @mathhelpforum