Question

1. A finite sequence of letters is called a palindrome if it reads the same forward or backward. Devise an algorithm for determining whether or not a string of n letters is a palindrome. Write your algorithm using the the same sort of pseudocode used in the text. Your algorithm should start with procedure palindrome (a1,a2,...,an: lowercase letters) Your procedure should return the value 0 if the string is a palindrome, and the first integer i such that ai 6=an−i+1 if the string is not a palindrome.

2. Show all steps taken by your algorithm if you input the string the string abcdba. What number does the procedure return?

3. Show all steps taken by your algorithm if you input the string the string azyza. What number does the procedure return?

Answer 1

a)

procedure palindrome(a1, a2, ..., an: lowercase letters)
Set j = n/2
Set i = 1
Repeat while i<=j and a[i]==a[n-i+1]
i = i + 1
[End of loop]
If i>j then
Return 0
Else
Return i

b) input string = abcdba
Here, n = 6
Therefore, j = n/2 = 3
i = 1
a[i] = a[1] = 'a' and a[n-i+1] = a[6] = 'a'
The conditions of the while loop i<=j and a[i]==a[n-i+1] both are satisfied.
Execute the body of the loop: i = i + 1 = 2
a[i] = a[2] = 'b' and a[n-i+1] = a[5] = 'b'
The conditions of the while loop i<=j and a[i]==a[n-i+1] both are satisfied.
Execute the body of the loop: i = i + 1 = 3
a[i] = a[3] = 'c' and a[n-i+1] = a[4] = 'd'
The condition of the while loop i<=j is satisfied, but another condition a[i]==a[n-i+1], which is not satisfied
Therefore, terminate the loop.
Now, check i>j condition, which is not satisfied, since i=3 and j=3
Finally return the value of i, that means returns 3

c) input string = azyza
Here, n = 5
Therefore, j = n/2 = 2
i = 1
a[i] = a[1] = 'a' and a[n-i+1] = a[5] = 'a'
The conditions of the while loop i<=j and a[i]==a[n-i+1] both are satisfied.
Execute the body of the loop: i = i + 1 = 2
a[i] = a[2] = 'z' and a[n-i+1] = a[4] = 'z'
The conditions of the while loop i<j and a[i]==a[n-i+1] both are satisfied.
Execute the body of the loop: i = i + 1 = 3
a[i] = a[3] = 'y' and a[n-i+1] = a[3] = 'y'
The condition of the while loop i<=j is not satisfied, therefore, terminate the loop.
Now, check i>j condition, which is satisfied, since i=3 and j=2, therefore, return 0

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.
Thank you.