Question

1 (15 pts) Implement recursive, memoized, and dynamic programming Fibonacci and study their performances using different problem instans You can choose to look at the perfor- mance by either timing the functions or counting the basic operations (in code) Provide your results below, and submit your code. Also, describe the pros and cons of your choice of performance metric Note: If you decide to use timing, the standard way to time an algorithm is to run the same problem 100 or 1000 times (use a loop), getting the overall running time (get the start time run the same test 1000 times, get the end ti and averaging over the number of runs. You should not try to time an individual test. You may find that algorithms that run faster need to have more repetition whereas algorithms that ru slower need fewer repetitions. Be careful when running mo hanone memoized Fibonacci, as the dictionary should be reset each time, 2. (10 pts) Fill in the LCS matrix for CCGGTTACCA and GGAGTTCA using the LCS algo- rithm given in class, and provide the actual longest common subsequence

Answer 1