Problem 2. Consider the algorithm below for checking whether a string represented in an array A of n characters is a palindrome. A palindrome is defined as a word that is spelled the same forward and backward (e.g. rotor, kayak). CHECK-PALindrome (A[1:n]) : 1. If n=0 or n=1, return True. 2. Otherwise, if A[1]=A[n] and CHECK-PALindrome (A[2:n1]) returns True, return True. 3. Return False. We analyze CHECK-PALINDROME in this question. (a) Use induction to prove the correctness of this algorithm. (15 points) (b) Write a recurrence for this algorithm and solve it to obtain a tight upper bound on the worst case runtime of this algorithm. You can use any method you like for solving this recurrence. (10 points)