algorithm

Problem 2 (15 points) Consider the sequence A(n) defined as follows: A(n)= B(n-1) + A(n-2), A(O) = A(1) = 1 B(n)= A(n-1) + B(1-2), B(O)= B(1) = 2 [5 points) Transform the above expressions into a recursive algorithm in JAVA, Python or C. Print the first 30 values of each sequence. What is the largest value n of A(n) that can be computed by your computer in 1 minute? Show a screenshot 15 BONUS points) Prove that the running time of your recursive procedure computing An) is exponential in n. Hint. Guess a lower bound and prove it by induction. [10 points] Use the Dynamic Programming approach to compute A(n) more efficiently. What are its running time and space requirements? Show the DAG of subproblems and prove the correctness of your algorithm