Results 1 to 7 of 7
Like Tree1Thanks
  • 1 Post By MarkFL

Math Help - Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

  1. #1
    Newbie
    Joined
    Dec 2012
    From
    Ireland
    Posts
    3

    Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    Hi everyone,

    I'm really stuck on the following two questions. In essence, our lecturer went through these examples in class and a week later, the exact same questions were put to our lab demonstrator from a student who failed to grasp the original lecture. The problem? the demonstrator's answers were completely different to those of the lecturer. The demonstrator is adamant she is right, and the lecturer has not returned our emails yet because we have broken up for the Christmas holidays.

    Question 1

    Given the function f, where

    f(0) = 3
    f(n+1) = ceil(f(n)/2) + 1 (ceil = ceiling function)
    Evaluate f(19)

    Question 2

    f(0) =1
    f(n+1) = 2*f(n) +1
    Evaluate the f(3)

    Just to demonstrate this is not a homework assignment etc - please just provide the answer to both - without the method if you wish.
    For those who are curious the results we have so far is;

    Question 1 Lecturer Ans = 21 Demonstrator = 3
    Question 2 Lecturer Ans = 15 Demonstrator = 18

    This is very frustrating as we have an exam with recursive algorithms. Can someone please help?? How on earth can they be polar opposites??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    I get:

    1.) 3 (closed form f_n=3)

    2.) 15 (closed form f_n=2^{n+1}-1)
    Last edited by MarkFL; December 14th 2012 at 02:36 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    It would help you more if you post your attempt at a solution.

    It's 2:0 in favour of your lecturer.
    Last edited by a tutor; December 14th 2012 at 02:41 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2012
    From
    Ireland
    Posts
    3

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    Thank you both for your replies, this is wrecking my head!!
    here is my attempt from question 2 - which follows what the lecturer did
    for question 2;

    f(0+1) = 2*f(0) +1
    f(1) = 2*1+1
    f(1) = 2+1
    f(1) = 3

    f(1+1) = 2*f(1)+1
    f(2) = 2*f(1)+1
    f(2) = 2*3+1
    f(2) = 6+1
    f(2) = 7

    f(2+1) = 2*f(2)+1
    f(3) = 2*7+1
    f(3) = 14+1
    f(3) = 15

    Ans = 15

    I'm going to have to root out question one, you both believe the answer is 3? Is it that every value put into the function will return 3 each time?
    Or is it that 1 simply gets added each time the function runs, so to run up to f(19) thats 18 times +1 , plus the 3 = 21?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    I get 3 for any appropriate n for the first one, since \left\lceil \frac{3}{2} \right\rceil+1=2+1=3.

    For the second one, I used symbolic differencing to get the homogeneous linear recursion:

    f_{n+2}=3f_{n+1}-2f_{n}

    whose characteristic roots are r=1,\,2, hence the closed form is:

    f_n=k_1+k_2\cdot2^n

    and using initial values to determine the parameters, we find:

    f_n=2^{n+1}-1
    Thanks from BobP
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2012
    From
    Ireland
    Posts
    1

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    Q1) I got 21 for this. Considering the fact that the questions are on recursive functions I would assume that one should work from the f(19) back to the base case. With this in mind it works out that there are 18 +1s and a 3 for the base case which gives 21. If we work from the f(0) up to the f(19) we can see that the function just returns 3 every time so I am still somewhat unclear on the method one should use in the case of recursive functions

    Q2) I got 5 for this. Here's the method I used. I'm not really too confident on it's validity but I'm only posting it to offer another perspective on the questions. I used the same method for q1 too.

    f(3) = 2*f(2) + 1
    = 2*f(1) + 1 + 1
    = 2*f(0) + 1 + 1 + 1
    = 2*1 + 1 + 1 + 1
    = 5
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Recursive Algorithms - who is right? Lecturer or lab demonstrator?????

    I'm afraid that's wrong chuck.

    See MarkFL2's post above.

    Don't know why I posted what I did above.

    Simplest approach in this case where we only want f(3) is to work out f(1), f(2), f(3) in that order.

    3, 3, 3......

    1, 3, 7, 15........
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Language recursive, sat recursive
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2012, 10:29 AM
  2. Algorithms
    Posted in the Math Software Forum
    Replies: 2
    Last Post: November 4th 2010, 08:25 PM
  3. algorithms
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2010, 02:25 PM
  4. Algorithms
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2009, 03:06 AM
  5. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM

Search Tags


/mathhelpforum @mathhelpforum