A simple lesson in coding, revisited
The simple lesson in coding that I am revisiting today started as a course plan for the first week in my data structures class. The plan was to help students refresh their introductory coding skills. To do that, I used a simple task, like writing a method to evaluate if a string is a palindrome or not, to discuss coding practices.
The naive method to the left uses a for-loop to scan the string for palindromic properties. It looks at pairs of letters from the beginning and the end of the string, moving towards the center. Boolean palindrome remains true as long as letters in each pair are equal to each other. The moment a bad pair appears, boolean palindrome turns false. It never recovers from that state even if letters in subsequent pairs are equal. This is done in line 7, where we evaluate the pairwise equality of letters (pairMatched)in conjunction (&&) with the current state of palindrome.
Taking the conditional AND between the current state of palindrome and the equality between two letters here is critical: it ensures that once a letter mismatch is found, palindrome will remain false. Because a false value in an AND operation behaves like a zero in a multiplication. Once a variable is multiplied by 0, it becomes 0 itself no matter how many times we multiply it afterward with non-zero numbers.
After realizing that the for-loop is not a very efficient technique, we switch to the while-loop as shown to the left. A friend noticed that line 7 can be simplified. We no longer need to keep the current value of palindrome in the evaluation. We needed it in the for-loop version of the method because we evaluated every pair of letters in String s. With the while-loop, we do not evaluate every possible pair of letters in s. The moment we find a mismatch, the loop ends. It is, therefore, sufficient to simplify line 7 as shown below.
It’s not a terrible mistake if we left palindrome on the right side of the evaluation at line 7. But it’s worth reflecting on how we ended up with line 7: we started with a method that used the for-loop. Next, we modified that method to use the while-loop for efficiency. By focusing on replacing for with while, we may have forgotten the palindrome on the right side of line 7. And the method works just fine without changing that line.
If we focus on the role of palindrome in the new version of the method, we can see why we do not need it on the right side of line 7. The method starts by assuming that String sis a palindrome. It continues by comparing pairs of letters from both ends of the string, moving inwards. Each comparison renews the value of palindrome. The moment we hit two different letters, their comparison will yield false. That will become the value for palindrome. It will cause the while-loop to end. The return statement is next, pushing palindrome's false value out.
Or, we may end up getting to the last pairwise comparison, finding that every pair of letters in String s matches. In this case, the while-loop ends because pos is no longer less than s.length()/2. The current value of palindrome is now true. We are also done!
As I finalize this example and getting ready for my first week of classes, I need to do two more things: bring testing (and design by testing) to the discussion and transition the example to an application of some data structure. I’ll discuss these two things in my next posts.
