Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing problems into subproblems similar in structure to the original problem. In addition to this standard property, subproblems must 1) overlap and 2) have optimal sub- structure. The basic idea of dynamic programming is to obtain the optimal problem by exploiting the fact that it can be obtained from optimal solutions to subproblems and that we can save time by keeping track of subproblems we have already solved. Problem 1 - The Fibonacci Numbers There are many problems that can benefit from the ideas that go into dynamic programming, even if they are not naturally dynamic programming problems. Consider the Fibonacci numbers, defined by the recurrence: F = F.-1+F-2 n=2,3,..., F = F = 1 3-1 Lab 3: Dynamic Programming February 10, 2020 As discussed in class, this problem has overlapping subproblems. It does not, however, have optimal substructure because calculating the Fibonacci numbers is not an optimization problem. Nevertheless, the concept of memoization can be applied to this problem with dramatic effects on performance. Functions A) Implement a function called recursiveFibonacci that, given an integer n, evaluates and returns F. recursively without memoization). B) Implement a function called memoizedFibonacci that, given an integer n, evaluates and returns Frecursively with memoization. You may add whatever arguments you require, or a wrapper function as necessary, to make the memoized version of the function work to your liking C) Implement a function called bottomupFibonacci that, given an integer n evaluates and returns F in a bottom-up manner. Main Program Write a main program Lab.3.Problem.1 that specifies an array of values of n and collects the running times for your three functions A, B, and C for computing the Fibonacci numbers as a function of n. Data Collection and Analysis Once you have completed writing your functions and main program you need to: Call your main program on appropriate values of n to get the general trends of the computational costs of each method for computing the nth Fibonacci number. Determine the best Big-O notation fit for each of the three approaches. Show your work! Remember that operation counting and order-of-growth is always a possibility. For each of the three approaches, plot the analytic and measured costs/times and the output of the main program in one figure, producing 3 total plots. Scale the curves appropriately and provide details in the legend. Introduction In class we have been introduced to dynamic programming as a way of solving problems by subdividing problems into subproblems similar in structure to the original problem. In addition to this standard property, subproblems must 1) overlap and 2) have optimal sub- structure. The basic idea of dynamic programming is to obtain the optimal problem by exploiting the fact that it can be obtained from optimal solutions to subproblems and that we can save time by keeping track of subproblems we have already solved. Problem 1 - The Fibonacci Numbers There are many problems that can benefit from the ideas that go into dynamic programming, even if they are not naturally dynamic programming problems. Consider the Fibonacci numbers, defined by the recurrence: F = F.-1+F-2 n=2,3,..., F = F = 1 3-1 Lab 3: Dynamic Programming February 10, 2020 As discussed in class, this problem has overlapping subproblems. It does not, however, have optimal substructure because calculating the Fibonacci numbers is not an optimization problem. Nevertheless, the concept of memoization can be applied to this problem with dramatic effects on performance. Functions A) Implement a function called recursiveFibonacci that, given an integer n, evaluates and returns F. recursively without memoization). B) Implement a function called memoizedFibonacci that, given an integer n, evaluates and returns Frecursively with memoization. You may add whatever arguments you require, or a wrapper function as necessary, to make the memoized version of the function work to your liking C) Implement a function called bottomupFibonacci that, given an integer n evaluates and returns F in a bottom-up manner. Main Program Write a main program Lab.3.Problem.1 that specifies an array of values of n and collects the running times for your three functions A, B, and C for computing the Fibonacci numbers as a function of n. Data Collection and Analysis Once you have completed writing your functions and main program you need to: Call your main program on appropriate values of n to get the general trends of the computational costs of each method for computing the nth Fibonacci number. Determine the best Big-O notation fit for each of the three approaches. Show your work! Remember that operation counting and order-of-growth is always a possibility. For each of the three approaches, plot the analytic and measured costs/times and the output of the main program in one figure, producing 3 total plots. Scale the curves appropriately and provide details in the legend