Recursion and Algorithms for Arrays Instructions: Your assignment should represent your own effort. However, you are not expected to work alone. It is fine to discuss the exercises and try to find solutions together, but each student shall write down and submit his/her solutions separately. It is good academic standard to acknowledge collaborators, so if you worked together with other students, please list their names. You can write up your answers by hand (provided your handwriting is legible) or use a word processing system. For all programming tasks, it is not allowed to use any external libraries ("import") if not stated otherwise. 1. Recursion A palindrome is a phrase that reads the same forward and backward (examples: 'racecar', 'radar', 'noon', or 'rats live on no evil star'). By extension we call every string a palindrome that reads the same from left to right and from right to left. Develop a recursive algorithm that takes as input a string and decides whether the string is a palindrome. 1. Write down your algorithm in pseudocode. 2. Implement your algorithm in the PalindromeChecker class. (6 Points) 3. Write code to measure the running time of your Java program for random inputs of size n=10,100,1000, etc. Does the growth of the running time correspond to your estimate of the number of assignments? (14 Points)