The course seems to have sped by so fast, but I feel I have learned so much in the duration of this course. Before this course I wasn’t comfortable with induction to say the least, but after professor Heap’s illustration of induction in all this varieties I feel confident I can tackle any proofs in general. I admire his flare and enthusiasm for the course, even though it was a long 3 hour evening lecture. He was always prepared and attended to each student’s difficulties. He was also available after office hours for any late questions that came up. I hope he’s my professor for future courses.
All the csc236 TAs at the help center were a great help. I was always there for each problem set and assignment. I was always greeted in and taken care of. They were very informative and made sure I understood the underlying concepts. With their help I was able to complete the course work and gain a new perspective on the course material.
Tuesday, December 2, 2008
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.
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.
Monday, December 1, 2008
Problem Set 6
This problem set involved proving an implication (if-then statement). We had to prove that if a language L consists of odd length binary strings, then it can be denoted by ((0+1)(0+1))*(0+1). I used the idea of inclusion for both directions. That is if T is the set of all odd length binary strings, then an element belonging to T must also belong to L(((0+1)(0+1))*(0+1)). To prove this direction, I started off with an odd length binary string and constructed the regular expression that would denote it, step by step. In the end I was left with the expression ((0+1)(0+1))*(0+1)), thus proving the implication in one direction. The other direction is proving that if an element belongs to L(((0+1)(0+1))*(0+1)), then it must belong to T. To prove this direction I broke the regular expression into its even and odd components, and showed that the concatenation of both components yields an odd length binary string. This prove seemed to be pretty lengthy but it was straightforward.
Subscribe to:
Posts (Atom)