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

[amigaNutter3]

Hi everyone,

I'm really stuck on the following two questions. In essence, our lecturer went through these Recursive Algorithm 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 = 3 Demonstrator = 21
Question 2 Lecturer Ans = 15 Demonstrator = 5

This is very frustrating as we have an exam with recursive algorithms. Can someone please help?? How on earth can they be polar opposites??

 

[JeffM]

Hi everyone,

I'm really stuck on the following two questions. In essence, our lecturer went through these Recursive Algorithm 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 = 3 Demonstrator = 21
Question 2 Lecturer Ans = 15 Demonstrator = 5

This is very frustrating as we have an exam with recursive algorithms. Can someone please help?? How on earth can they be polar opposites??

Edit: I originally disagreed with Subhotosh Khan and your lecturer about the answer to Question 2. I was wrong. Subhotosh and your lecturer are correct.
I apologize. I have corrected my answer below.

Question 1.

\(\displaystyle f(n + 1) = ceiling\left(\dfrac{f(n)}{2}\right) + 1\ and\ f(n) = 3 \implies f(n + 1) = ceiling\left(\dfrac{3}{2}\right) + 1 = ceiling (1.5) + 1 = 2 + 1 = 3.\)

From this you can prove by mathematical induction that \(\displaystyle f(0) = 3 \implies f(n) = 3\ for\ any\ integer\ n \ge 0.\)

Question 2.

\(\displaystyle g(x) = 2^{(x + 1)} - 1 \implies g(x + 1) = 2^{\{(x + 1) + 1\}} - 1 = 2\left(2^{(x + 1)}\right) - 1 = 2\left(2^{(x + 1)} + 1 - 1\right) - 1 = 2\left(2^{(x + 1)} - 1\right) + 2 - 1 = 2 * g(x) + 1\)

\(\displaystyle \implies f(n) = 2^{(n + 1)} - 1\ for\ every\ integer\ n \ge k\ if\ f(k) = 2^{(k + 1)} - 1.\)

\(\displaystyle But f(0) = 1 = 2 - 1 = 2^1 - 1 = 2^{(0 + 1)} - 1.\)

\(\displaystyle So\ f(3) = 2^{(3 + 1)} - 1 = 2^4 - 1 = 16 - 1 = 15.\)

Finally got it right. Off to the corner AGAIN.

 

[Deleted member 4993]

Hi everyone,

I'm really stuck on the following two questions. In essence, our lecturer went through these Recursive Algorithm 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 = 3 Demonstrator = 21
Question 2 Lecturer Ans = 15 Demonstrator = 5

This is very frustrating as we have an exam with recursive algorithms. Can someone please help?? How on earth can they be polar opposites??

Your lecturer is correct.

Let's do hand calculation:

problem #1

f(1) = ceil[f(0)/2] + 1 = ceil[3/2] + 1 = ceil[1.5] + 1 = 3

f(2) = ceil[f(1)/2] + 1 = ceil[3/2] + 1 = ceil[1.5] + 1 = 3

f(3) = ceil[f(2)/2] + 1 = ceil[3/2] + 1 = ceil[1.5] + 1 = 3 ..................... it is stuck at 3

problem # 2

again doing hand-calculation, I get:

f(3) = 15

You should be able to confirm this - without any external help.

 

[Deleted member 4993]

Question 2

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

f(0) = 1 → f(0+1) = f(1)= 2*f(0) + 1 = 2*1 + 1 = 3 → f(1+1) = f(2) =2*f(1) + 1 = 2*3 + 1 = 7 → f(2+1) = f(3) = 2*f(2) + 1 = 2*7 +1 = 15

Wrong whistle → Go back to empty hockey rinks and practice, practice, practice....

Jeff - half hour additional detention....

 

[Deleted member 4993]

OK, but only if you go play cricket with the peasants

That's what I have been reduced to these days - all the noblemen went to Lords Stadium to watch India vs. England (MCC) game....

 

[JeffM]

OK I am going to the corner, but I am sulky. Will play neither hockey nor cricket.

 

[MarkFL]

This question was posted on another site, and after giving others here a chance to independently respond, this is what I wrote there:

I get 3 for any appropriate n for the first one, since \(\displaystyle \displaystyle \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:

\(\displaystyle \displaystyle f_{n+2}=3f_{n+1}-2f_{n}\)

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

\(\displaystyle \displaystyle f_n=k_1+k_2\cdot2^n\)

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

\(\displaystyle \displaystyle f_n=2^{n+1}-1\)

And so:

\(\displaystyle \displaystyle f_3=2^{3+1}-1=15\)