Palindromes
Introductory tasks
Asking, 'what is a palindrome?' is a fairly low-level type of introduction. More thinking would be required by writing half a dozen palindromes on the board along with one (or more) that isn't a palindrome, and ask students to work out which word or phrase is the odd one out. Harder still might be to write a dozen words or phrases on the board, half of which are palindromes and half of which aren't, and then get students to split the list into two groups, justifying the reasoning behind the split. You can find some interesting palindromes online to use, to make it as hard or as easy a task as you want. Start looking here.
The problem
Students have to write a program to test to see if a word is a palindrome. You want to be able to pass the word or phrase you want to test to a function and have the function return either True (it is a plaindrome) or False (it isn't).
Overview of our solution
You could get your students into groups and get them to discuss possible solutions, and then bring their ideas together as a class. Tell them they are 'brainy' if they can come up with one solution, a 'genius' if they can come up with two and 'Einstein' if they can come up with three or more different approaches.
There are at least three approaches you might want to discuss on testing to see if a string is a palindrome.
1) Reverse the string. Then test to see if the original string is the same as the reversed string.
2) Divide the string into two equal halves. Reverse the second half. Then test to see if the first half equals the second half. If the string has an equal number of letters, such as noon, then where to do the split is straightforward. If there is an odd number of letters such as in radar, then you can omit the middle letter when testing.
3) you could test the outer pairs of letters and see if they are equal. Then move inwards, testing the pairs of letters, until all the letter pairs have been tested. For example, with radar, you would test the first and last letters, then the second and fourth letter.
There are other solutions. In each case, students should be encouraged to think about special cases. These might include:
1) What if the string has an even or an odd number of letters?
2) What if the string is empty?
3) What if the string has spaces or punctuation in it?
Pseudo-code
Here is the pseudo-code for reversing the string and testing it. We will write a function to receive a string and test it against the reverse of the string:
def is_palindrome(test):
return True if test == reverse (test)
def reverse (test):
reverse = empty string
for each letter in the word test:
reverse = letter + reverse # put each letter in front of the empty string to reverse the word
return reverse
print (is_palindrome('radar')
Solution
Other solutions
You could look at the other possible ways of solving this problem. If you are going to split the word you want to test into two, you could do this a number of ways. You can re-use the reverse function you have already written and then use integer division and string slicing. You can modify your code in the is_palindrome function to read:
def is_palindrome(test):
return True if the first half of (test) == reverse of the second half of (test)
In the following solution, we have printed out some extra information on lines 4 and 5, so that students can see the result of integer division and slicing on the word. Some students may need reminding that myString[:n] means 'get everything from the beginning of myString to n-1 positions'.
Slightly more elegant is the last solution, although how it works is a little less obvious. The pseudo code is as follows:
def is_palindrome(test):
start = 0 (the first index)
end = the length - 1 (the last index)
while (start index is less than the end index) and both letters match:
start = start + 1
end = end - 1
return True if the pointers have met or crossed over each other
You start by pointing at the start and end of the word you are testing. You only enter the loop to increase the start index and decrease the end index if both letters have matched (so the word could still be a palindrome) and you haven't finished testing pairs of letters yet (which you will know if the end index passes the start index). If the pointers have met or crossed over, this must have meant that all pairs of letters matched, so you return True. Here is the code:
Extension tasks
Some students might want to modifty the print statements so it is clearer what is True or False. Students could see if they can find any other ways of testing for palindromes. Similar problems where a function returns a True or False could be set. They should have one function to return the True or False, and one function that they call to do the actual calculations. For example:
a) write a program to test a number, to return True if a number is Even and False if it is odd.
b) write a program to test if a number is a hex number or not (because it only contains 0 - 9 and a - f)