Palindromes A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, noon, and aibohphobia (fear of palindromes). You may assume that in the problems below, an input string is given as an array of characters. For example, input string noon is given as an array s[L.4], where s[1] = n, s[2] = o, s[3] = o, and s[4] = n. (a) (15 pts) Give a recursive algorithm that tests if the input string is a palindrome. Write down the pseudocode and use induction to prove that your algorithm correctly identifies palindromes. Analyze your algorithm's running time. (b) (15 pts) Sometimes removing a single character from the string, turns it into a palindrome. For example, if we remove 1 from the revolver, we will get a palindrome. We call such strings almost palindromes. Write down the pseudocode for an algorithm that tests if the input string is an almost palindrome. Analyze your algorithm's running time