Question

2. Question 2. Tribonacci numbers are a generalization of Fibonacci numbers and defined as follows: T, = 0,T, = 0,12 = 1 and T, = Tn–1 +1,-2 +T7-3. As in question 1, give recurcive, bottom-up dynamic and top-down dynamic algorithms for Tribonacci numbers. (15 pt)

in pseudocode please

Answer 1

Bottomup Approach:

Start from a subproblem and construct a larger problem using the solutions of the subproblems.

BottomUP_Tribonacci(n):

T0=0

T1=0

T2=1

a=T0 //assigning values to variables

b=T1 //assigning values to variables

c=T2 //assigning values to variables

print(a) //printing

print(b) //printing

printt(c) //printing

for(i=4 to n):

d=a+b+c

print(d)

a=b

b=c

c=d

Top Down Approach:

Top Down Approach is breaking a large problem into subproblems. Then solving the subproblems then ussing it to compute the main problems and also resuing the result when necessary.

TopDown_Tribonacci(n):

Array T[0...n] //We define an array, because we want to compute an subproblem only once.

T[0]=0

T[1]=0

T[2]=1

for(t=N to 0):

if(T[i]==NULL): //If we have not computed the answer before

Calculate(T[i])

print(T[i])

else:

print(T[i])

//This Function returns the nth  value in a recursive manner

Calculate(n):

if(n==0):

return 0

if(n==1):

return 0

if(n==2):

return 1

return Calculate(n-1)+Calculate(n-2)+Calculate(n-3)