Question

Problem 3.2

A more efficient version of the function for computing Tetranacci numbers can be defined by following three steps:

1. Implement a function which takes a list of integers and adds the sum of the top four elements to the head of the list (e.g., in F#, 1::1::1::1::[] should become 4::1::1::1::1::[]).
2. Implement a recursive function which computes the nth Tetranacci number in linear time. This function may use a linear amount of space to compute its result, but the number of recursive calls it makes must be linear in n.

Your task is to follow the three steps above, in order to implement the recursive function tetrn2 in F#.

• Hint: Try to define auxiliary functions first before taking on main function. You do not have to use auxiliary functions in your tetrn2, but they provide an insight on how to implement the tetrn2 function.

In [ ]:

// Problem 3.2.1

let append4Sum xs =

    // write your solution here

​

// Problem 3.2.2

let tetrn2 n =

    // write your solution here

Test your function:

In [ ]:

tetrn2 33 = 747044834 // this is fast compare to `tetrn 33` call

Answer 1

Tetranacci Numbers

The tetranacci numbers are a generalization of the Fibonacci numbers defined by the recurrence relation

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)

with T(0)=0, T(1)=1, T(2)=1, T(3)=2,

For n>=4. They represent the n=4 case of the Fibonacci n-step numbers. The first few terms for n=0, 1, … are 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, …

Given a number N. The task is to find the N-th tetranacci number.

Examples:

Input: 5
Output: 4

Input: 9
Output: 108

A better solution is to use Dynamic Programming (memoisation) as there are multiple overlaps.

Given below is the recursive tree for N=10.

                                        rec(10)

                             /         /       \          \

                       rec(9)      rec(8)     rec(7)     rec(6)

              /      /     \     \
                     
          rec(8) rec(7)  rec(6)  rec(5)

In the above partial recursion tree, rec(8), rec(7), rec(6) has been solved twice. On drawing the complete recursion tree, it has been observed that there are many subproblems which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.

Below is the implementation of the above approach in C++

// A DP based CPP // program to print // the nth tetranacci number #include <iostream> using namespace std; // Function to print the // N-th tetranacci number int printTetra(int n) {     int dp[n + 5];     // base cases     dp[0] = 0;     dp[1] = dp[2] = 1;     dp[3] = 2;     for (int i = 4; i <= n; i++)         dp[i] = dp[i - 1] + dp[i - 2] +                 dp[i - 3] + dp[i - 4];     cout << dp[n]; } // Driver code int main() {     int n = 10;     printTetra(n);     return 0; }

Output:

208

Time Complexity: O(N)
Auxiliary Space: O(N)

Next Solution

The time complexity of above is linear, but it requires extra space. Space used can be optimized in the above solution by using four variables to keep track of the previous four numbers.

Below is the implementation of the above approach

// A space optimized // based CPP program to // print the nth tetranacci number #include <iostream> using namespace std; // Function to print the // N-th tetranacci number void printTetra(int n) {     if (n < 0)         return;     // Initialize first     // four numbers to base cases     int first = 0, second = 1;     int third = 1, fourth = 2;     // declare a current variable     int curr;     if (n == 0)         cout << first;     else if (n == 1 || n == 2)         cout << second;     else if (n == 3)         cout << fourth;     else {         // Loop to add previous         // four numbers for         // each number starting         // from 4 and then assign         // first, second, third         // to second, third, fourth and         // curr to fourth respectively         for (int i = 4; i <= n; i++) {             curr = first + second + third + fourth;             first = second;             second = third;             third = fourth;             fourth = curr;         }         cout << curr;     } } // Driver code int main() {     int n = 10;     printTetra(n);     return 0; }

Output:

208

Time Complexity: O(N)
Auxiliary Space: O(1)