Problem Solving Episode – Polya style

Although the majority of my blog postings deal with a problem solving episode, here is one written using Polya’s approach. I will write problem set 4 using this approach, only because it’s not mentioned on my blog yet.

1. UNDERSTANDING THE PROBLEM

My csc207 Python knowledge helped me understand the code. Specifically how substrings work in Python. The code was not too complicated. The pre-condition was that the string s must be Python string. The post-condition was that the function revString return the characters in s in reverse order. The body of the code involved a recursive call to revString. It simply truncates the first character and concatenates it to the end of the string at each recursive call. When the loop terminates, the order of the characters in the original string would be reversed.

2. DEVISING A PLAN

Before devising a proof for this code, I had to consult the lecture slides and course notes and find similar correctness proof examples. To prove the correctness of this code, I had to consider cases. The code has two conditional executions. If the length of the string is less than 2 or otherwise. Within the first case (length less that 2), there are two sub-cases: when the length is 0 and when it’s 1. These cases are essentially the base cases of the proof by complete induction. In the induction step, I would proof the case when the length is greater than 2. It is here I would make use of the induction hypothesis, that is P (pre-condition implies post-condition) holds true for length =0 to length = n -1.

3. CARRYING OUT THE PLAN

I began with the assumption that the size of the string is a natural number n. I defined the predicate P to be that pre-condition implies post-condition of revString for all size n. Finally I assumed that P holds for length=0 to length = n-1.

Then I completed the base cases. If the length of the string is 0 (empty string), then the code simply returns an empty string. Thus P holds when n =0. If the length is 1, then the code returns back the string, since the reverse of a single character is itself. Thus P holds for n=1.

The final part was the induction step. This is the case where the length is greater than 2. My argument here was that by line 2 of the code: return revString(s[1:]) + s[0] , we know that the length of s[1:] is n – 1, since it slices the original string starting from the second character. Also we assumed in the IH that P(n-1) holds true. Line 2 return a string of length n, since s[1:] is n – 1 and s[0] is 1. Thus P(n) holds true. That is, pre-condition implies post-condition for length n and consequently for all natural numbers n.

4. LOOKING BACK

Reviewing the above proof, I felt satisfied that it adequately proved the correctness of revString. I suppose there are more elegant ways of proving this code, but I’m quite content with my approach. It seems simple and straightforward.