Let the following sequence be called the FiFibonacci sequence of numbers: f(1) = 1, f(2) = 4, f(3) = 7, and for n bigge

[answerhappygod]

Let the following sequence be called the FiFibonacci sequence of
numbers:

f(1) = 1, f(2) = 4, f(3) = 7, and for n bigger than 3, f(n) =
f(n-1) + f(n-2) + f(n-3)

(a) Implement the 3 functions for FiFibonacci, one for each of the
3 approaches, like we did for Fibonacci sequence in class.

(b) Run the 3 functions for different n values and time their
runtime and describe what you see. It will be obvious that already
for small values of n, pure recursion takes too much time. So, for
further values of n, compare only pure tabulation and recursion
with tabulation. For big values of n, which approach seems
faster?


2. A different recurrence relation. Consider this recurrence
relation:

f(n) = n + (floor(n/2))*f(floor(sqrt(n))) for n bigger than 1
f(1) = 5

(a) Implement 3 functions for this recurrence relation, one for
each of the approaches.

(b) Run the 3 functions for different n values and time their
runtime and describe what you see.

(c) How is the pattern of runtimes different here than for the
FiFibonacci problem? Can you explain why? Did you expect these
results?


3. One more recurrence relation. Consider this one:

f(n) = f(1) + f(2) + ... + f(floor(sqrt(n))) for n
bigger than 3
f(1) = 2, f(2) = 5, f(3) = 7

(a) Implement 3 functions for this recurrence relation, one for
each of the approaches.

(b) Run the 3 functions for different n values and time their
runtime and describe what you see.

(c) How is the pattern of runtimes different here than for the
FiFibonacci problem? Can you explain why? Did you expect these
results?