Consider the following function that defines F$($n$)$ for all n $>=1$:

F$(1)=1$; F$(2)=2$; F$[3]=3$; F$[4]=4$; and

for all n$>4,$ F$($n$)=($ F$($n$-1)*$ F$($n$-2))+($ F$($n$-3)*$ F$($n$-4))+$ n

$$

Do the following:

Write a divide and conquer $($recursive$)$ algorithm R$($n$)$ that calculates F$($n$)$ for any given n$>=1.$ Your algorithm also prints out how many multiplication operations R$($n$)$ performs $($in $($ F$($n$-1)*$ F$($n$-2))+($ F$($n$-3)*$ F$($n$-4))+$ n$,$ there are two multiplications$).$

$$

Write a dynamic programming algorithm D$($n$)$ that calculates F$($n$)$ for any given n$>=1.$ Your algorithm also prints out how many multiplications $(*$ operation$)$ it performs in calculating F$($n$).$

$$

$$

Create a table in which you tabulate the number of additions R$($n$)$ and D$($n$)$ perform for n$=5,10,15,20,25,30,35.$

$$

Turn in your source codes for $1$ and $2$ above, and the result table in $3.$ You can put all of them in one file if you$$d like. Please write your programs in C$,$ C$++,$ or Java. Do not use recursion in Question $2($i$.$e$.,$ in implementing D$($n$))$