2. The sequence Fr of Fibonacci numbers is defined by the recurrence relation Fn = Fn1 + Fn-2 with seed values Fo = 1 and F = 1. (1) (a) (10 pts) Consider the recursive top-down implementation of the recurrence (1) for calculating n-th Fibonacci number Fn. i. Write down an algorithm for the recursive top-down implementation in pseu- docode. ii. Write down the recurrence for the running time T(n) of the algorithm and solve for it. (b) (15 pts) Consider the dynamic programming approach "top-down implementation with memoization" that memoizes the intermediate Fibonacci numbers by storing them in an array F[n]. i. Write down an algorithm for the top-down implementation with memoization in pseudocode. ii. Describe the behavior of the algorithm in terms of a traversal of a recursion tree. Describe how the array F is filled. iii. Determine the asymptotic running time of the algorithm. Prove your claim is correct by induction on the contents of the array. (c) (10 pts) Consider the dynamic programming approach "iterative bottom-up im- plementation that builds up directly to the final solution by filling the F array in order. i. Write down an algorithm for the iterative bottom-up implementation in pseu- docode. ii. Determine the time and space usage of the algorithm. Justify your answers and compare them to the answers in part (2b). (d) (5 pts) If you only want to calculate Fn, you can have an iterative bottom-up implementation with O(1) space usage. Write down an iterative algorithm with (1) space usage in pseudocode for calculating Fn. Justify your algorithm does have (1) space usage, and determine its running time. (e) (5 pts) In a table, list each of the four algorithms as rows and for each give its asymptotic time and space requirements, along with the implied or explicit data structures that each requires. Briefly discuss how these different approaches compare, and where the improvements come from. (Hint: what data structure do all recursive algorithms implicitly use?) (f) (5 pts) Implement your algorithm in part (2d) in Python and then compute Fn where n is the four-digit number representing your MMDD birthday, and report the first five digits of Fr. Now, assuming that it takes one nanosecond per opera- tion, estimate the number of years required to compute F using the algorithm in part (2a) and compare that to the time required to compute F using algorithm in part (2d).