Perform the requested steps, and display your work in a clear and comprehensive manner. Provide details in the following order:

$-$ Standard title page

$-$ Two algorithms $(2$ marks$)$

$-$ Two source codes and four outputs for $\backslash (\backslash$mathrm$\{$n$\}=7\backslash )(3$ marks$)$

$-$ Two tables for $\backslash (\backslash$mathrm$\{$n$\}=1,2,4,6,8\backslash )(1$ mark$)$

$-$ Detailed analysis $(3$ marks$)$

$-$ Algorithm or description of the solution with complexity analysis $(3$ marks$)$

Background

The following background information is necessary to complete this assignment:

$1.$ A sequence that grows quite rapidly $(\backslash ($ F$\_\{100\}\backslash )$ is a $21-$figure number$)$ is the Fibonacci sequence $[$text$/$p$.26,687],$ defined on non$-$negative integers by the following recurrence:

This famous sequence was originated in $1202$ by Leonardo Pisano $($Leonardo of Pisa$)$ who sometimes is called Leonardo Fibonacci $($Filius Bonaccii, son of Bonaccio$).$

$2.$ A first indication of the intimate connections between $\backslash ($ F$\_\{$n$\}\backslash )$ and algorithms came to light in $1844$ when $\backslash ($ G $\backslash ).$ Lam$$ used the Fibonacci sequence to study the efficiency of Euclid's GCD Algorithm to compute the Greatest Common Divisor $($GCD$)$ of two positive integers. During the next $50$ years, the mathematician E$.$ Lucas obtained very profound results about the Fibonacci numbers, and in particular, he used them to prove that the $39-$digit number $\backslash (2^\{127-1\}\backslash )$ is prime. Lucas gave the name "Fibonacci numbers" to the sequence $\backslash ($ F$\_\{$n$\}\backslash )$ and that name has been used ever since.

$3.$ A number of recursive algorithms $($e$.$g$.,$ Algorithm $1\mathrm{.}4$ on p$.12$; Exercise C $1\mathrm{.}30$ on p$.53$; Algorithm $2\mathrm{.}19$ on p$.80$; Algorithms preorder, postorder, and inorder in Chapter $2$; Algorithm BottomUpHeap on p$.109$; Algorithm BinarySearch on p$.143$; Algorithm inPlaceQuickSort on p$.248$; Divide$-$and$-$conquer technique on p$.219$ and p$.263$; etc.$)$ have been discussed. Recursive algorithms are particularly appropriate when the underlying problem is defined in recursive terms. However, this does not mean that such recursive definitions guarantee that a recursive algorithm is the best way to solve the problem.

$4.$ Consider a recurrence relation like the Fibonacci series:

$\backslash (\backslash$mathrm$\{$T$\}\_\{0\}=\backslash$mathrm$\{$T$\}\_\{1\}=2\backslash )$

$\backslash ($ T$\_\{$n$\}=2*$ T$\_\{$n$-1\}*$ T$\_\{$n$-2\}\backslash ),$ for $\backslash ($ n$>1\backslash )$

$5.\backslash ($ T$\_\{$n$\}\backslash )$ can be computed recursively. Requested Steps

$1.$ Write recursive and dynamic programming algorithms to compute $\backslash (\backslash$mathrm$\{$T$\}\_\{\backslash$mathrm$\{$n$\}\}\backslash ).$ Call them Algorithm Recur$1$ and Algorithm Recur$2.$

$2.$ Convert these algorithms to properly documented, professional quality programs. Call the programs RecurP$1$ and RecurP$2,$ respectively. In the heading documentation$-$in addition to your name, student ID number, and course code$-$clearly state the language, editor, compiler, operating system, and computer used.

$3.$ By executing programs RecurP$1$ and RecurP$2,$ print Numbers $\backslash (\backslash$mathrm$\{$T$\}\_\{0\}\backslash )$ to $\backslash (\backslash$mathrm$\{$T$\}\_\{7\}\backslash )$ to demonstrate that both programs produce correct results. Generate properly$-$labelled outputs. Remember that $\backslash (\backslash$mathrm$\{$T$\}\_\{0\}=\backslash$mathrm$\{$T$\}\_\{1\}=2\backslash ).$

$4.$ Try running both programs for $\backslash ($ n$=1,2,4,6,8\backslash ).$ You will start to notice something important from the viewpoint of computing science. Keep in mind the largest possible integer that can be represented on a $32-$bit and $64-$bit computer system. Use the internal clock to record the time to run each case.

$5.$ Tabulate your results$-$specifically, $\backslash ($ n $\backslash )$ versus result versus time$-$from the previous step into two tables: one for RecurP$1$ and the other for RecurP$2.$

$6.$ Analyze your algorithms and results, making sure to provide a detailed critical evaluation, from the viewpoint of "algorithm design and analysis" based on the above table. Include comments on the accuracy of your results. Use graphs or any other enhancements to support your analysis.

$7.$ Assume an integer array A contains $\backslash ($ n $\backslash )$ positive and negative numbers. Using dynamic programing, write an algorithm for finding a contiguous subset of numbers $\backslash ($ A$[$i$]\backslash$ldots A$[$j$]($i