5. The following algorithm determines whether a word is a palindrome, that is, if the word is the same read left to right as right to left. An example of a palindrome is racecar. procedure Palindrome(s18283.. .n) 1, if (n = 0 or n-1) then return true if si = sn then return Palindrome(s2 else return false sn-1) 3. Note: Writing s18283... Sn denotes a string of length n whose characters are s1, s2, s3, etc These characters are being concatenated (not multiplied) to form a string. (a) (5 points) Prove that this algorithm is correct, i.e. that it returns true if and only if #1#783 . . . sn 1s a palindrome. (b) (2 points) Let C(n) be the number of times this algorithm compares two characters si and sj for some i,j. Write a recurrence relation that C(n) satisfies. (c) (3 points) Solve the recurrence found in part (b) to get a closed-form formula for C(n) 5. The following algorithm determines whether a word is a palindrome, that is, if the word is the same read left to right as right to left. An example of a palindrome is racecar. procedure Palindrome(s18283.. .n) 1, if (n = 0 or n-1) then return true if si = sn then return Palindrome(s2 else return false sn-1) 3. Note: Writing s18283... Sn denotes a string of length n whose characters are s1, s2, s3, etc These characters are being concatenated (not multiplied) to form a string. (a) (5 points) Prove that this algorithm is correct, i.e. that it returns true if and only if #1#783 . . . sn 1s a palindrome. (b) (2 points) Let C(n) be the number of times this algorithm compares two characters si and sj for some i,j. Write a recurrence relation that C(n) satisfies. (c) (3 points) Solve the recurrence found in part (b) to get a closed-form formula for C(n)