$1.$ Objective:

The student will practice how to

$-$ Implement a simple algorithm using dynamic arrays $($STL vectors$)$

$-$ Design and implement recursive functions.

$-$ Describe the running time of the recursive functions using recurrence relations.

$2.$ Tasks:

$2\mathrm{.}1.$ Tribonacci sequence:

The Tribonacci sequence Tn is defined as follows:

$\backslash (\backslash$mathrm$\{$T$0\}=0,\backslash$mathrm$\{$~T$\}1=1,\backslash$mathrm$\{$~T$\}2=1\backslash ),$ and $\backslash (\backslash$mathrm$\{$T$\}\_\{\backslash$mathrm$\{$n$\}\}=\backslash$mathrm$\{$T$\}\_\{\backslash$mathrm$\{$n$\}-1\}+\backslash$mathrm$\{$T$\}\_\{\backslash$mathrm$\{$n$\}-2\}+\backslash$mathrm$\{$T$\}\_\{\backslash$mathrm$\{$n$\}-3\}\backslash )$ for $\backslash (\backslash$mathrm$\{$n$\}>=3\backslash ).$

Given $\backslash ($ n $\backslash ),$ return the value of $\backslash ($ T n $\backslash ).$

Required:

$-$ Write a recursive function to calculate Tn$.$

$-$ Write the recurrence relation of the Tribonacci function.

$2\mathrm{.}2.$ Fibonacci sequence:

The Fibonacci numbers, commonly denoted $\backslash ($ F$($n$)\backslash )$ form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from $0$ and $1.$ That is$,\backslash ($ F$(0)=0,$ F$(1)=1\backslash ),$

$\backslash ($ F$($n$)=$F$($n$-1)+$F$($n$-2)\backslash ),$ for $\backslash ($ n$>1\backslash ).$

Required:

$-$ Write a function to calculate Fn and consider the range of $\backslash ($ n $\backslash ).$

$-$ What is the time and space complexity for your code?

$2\mathrm{.}3.$ Reverse string recursively:

you need to design a recursive function that given a string S$,$ returns it in reversed order.

Required:

$-$ Write a recursive function to reverse a string.

$-$ Write the recurrence relation and determine its running time in big O notation.

$2\mathrm{.}4.$ Subarray division:

Given an array A$,$ find the number of subarrays of length $\backslash ($ m $\backslash )$ such that the sum of its elements equals $\backslash ($ d $\backslash ).$

Required:

$-$ Implement your algorithm to solve the problem.

$-$ What's the running time of your algorithm?