Last entry for CSC236... Unfortunately, I didn't get to enjoy this course due to my schedule (if one can enjoy a course like this ;)). Perhaps one day I'll look back at the notes, tests and assignments from this course and something will tickle my fancy and will further explore the subject. The material was certainly interesting. Sometimes..
Had the 3rd term test today and it was ok. A good evaluation of the material we covered recently.
The exam, however, I'm not sure about. Will definitely have to put some time in and review everything. Hopefully it doesn't end up being too difficult. (Prof. Heap, are you reading this? :)).
Final thoughts: SLOGs.. I didn't think they were appropriate forms of evaluation for this course. Now that the end has come, my thoughts about SLOGs have not changed. Perhaps future iterations of the course may have SLOGs as for-bonus-marks type of activity, rather than a requirement.
Signing out.
Friday, December 5, 2008
Problem solving episode
For problem set 4 we had this question to solve:
Question:
Prove that the python function revString(s) is correct with respect to
its precondition/postcondition, or else provide a string that
satisfies the precondition, but for which the postcondition fails.
# Precondition: s is a python String
# Postcondition: revString(s) returns a string with
# the characters of s in reverse order.
def revString(s) :
if len(s) < 2 : return s
else : return revString(s[1:]) + s[0]
UNDERSTANDING THE PROBLEM
The problem is proving the partial correctness of the function or proving its incorrectness by way of a counterexample which satisfies the precondition of the function but doesn't meet the postconditions.
DEVISING A PLAN
The idea is to go through some examples to see if the function "works". This way, one gets a chance to see if any counterexamples pop out. The function appears correct, however, so most likely there won't be counterexamples.
Considering that this is a recursive function, we have to keep in mind the condition of the recursion so the function is not called on non-valid input.
Since the string is being manipulated by the function one character at a time, the length of the string is a good property to do induction on.
CARRYING OUT THE PLAN:
Claim: P(k): for all non-negative integers k, if len(S) = k then precondition implies
postcondition
Base cases:
1. Empty string: len(s) = k = 0;
If k = 0 then the condition len(s) < 2 is satisfied and "return s" is executed, and so
the empty string s is returned. Empty strings are reverses of themselves so P(0) holds.
2. String composed of one character: len(s) = k = 1;
If k = 1 then, similar to the case above, condition len(s) < 2 is satisfied and "return
s" is executed. The one-character string s is returned which is a string with the
character of s in reverse order, which is the string itself, so P(1) holds
Induction step: Assume n is a non-negative integer. Also, assume P(0),..,P(n-1) hold. We
prove that P(n) holds also.
If len(s) = n < 2, P(n) holds by cases discussed above (base cases).
If len(s) = n >= 2, then condition on first line of algorithm is not satisfied and the
second line of the algorithm is executed returning revString(s[1:]) + s[0]. s[0] is the
first character of the string s, and is being added to the end of revString(s[1:]) which
is the string composed of characters of s in reverse order, with the exception of the
first one. So len(revString(s[1:0])) = len(s) - 1 = n - 1 < n. Then by IH
revString(s[1:0]) holds. Adding the first character of s to the end of the string
composed of characters of s, except the first, in reverse order, produces a string which
is composed of all characters of s in reverse order. Since len(revString(s)) = n then
we've shown that P(n) holds.
Conclusion: for all non-negative integers n, if len(s) = n then precondition implies
postcondition.
LOOKING BACK:
The proof seems sound and it shows exactly what we wanted, which is that the precondition implies the postcondition. Looking back, there appear to be no simpler methods of solving this question as its set out perfectly for the proof approach used above.
Question:
Prove that the python function revString(s) is correct with respect to
its precondition/postcondition, or else provide a string that
satisfies the precondition, but for which the postcondition fails.
# Precondition: s is a python String
# Postcondition: revString(s) returns a string with
# the characters of s in reverse order.
def revString(s) :
if len(s) < 2 : return s
else : return revString(s[1:]) + s[0]
UNDERSTANDING THE PROBLEM
The problem is proving the partial correctness of the function or proving its incorrectness by way of a counterexample which satisfies the precondition of the function but doesn't meet the postconditions.
DEVISING A PLAN
The idea is to go through some examples to see if the function "works". This way, one gets a chance to see if any counterexamples pop out. The function appears correct, however, so most likely there won't be counterexamples.
Considering that this is a recursive function, we have to keep in mind the condition of the recursion so the function is not called on non-valid input.
Since the string is being manipulated by the function one character at a time, the length of the string is a good property to do induction on.
CARRYING OUT THE PLAN:
Claim: P(k): for all non-negative integers k, if len(S) = k then precondition implies
postcondition
Base cases:
1. Empty string: len(s) = k = 0;
If k = 0 then the condition len(s) < 2 is satisfied and "return s" is executed, and so
the empty string s is returned. Empty strings are reverses of themselves so P(0) holds.
2. String composed of one character: len(s) = k = 1;
If k = 1 then, similar to the case above, condition len(s) < 2 is satisfied and "return
s" is executed. The one-character string s is returned which is a string with the
character of s in reverse order, which is the string itself, so P(1) holds
Induction step: Assume n is a non-negative integer. Also, assume P(0),..,P(n-1) hold. We
prove that P(n) holds also.
If len(s) = n < 2, P(n) holds by cases discussed above (base cases).
If len(s) = n >= 2, then condition on first line of algorithm is not satisfied and the
second line of the algorithm is executed returning revString(s[1:]) + s[0]. s[0] is the
first character of the string s, and is being added to the end of revString(s[1:]) which
is the string composed of characters of s in reverse order, with the exception of the
first one. So len(revString(s[1:0])) = len(s) - 1 = n - 1 < n. Then by IH
revString(s[1:0]) holds. Adding the first character of s to the end of the string
composed of characters of s, except the first, in reverse order, produces a string which
is composed of all characters of s in reverse order. Since len(revString(s)) = n then
we've shown that P(n) holds.
Conclusion: for all non-negative integers n, if len(s) = n then precondition implies
postcondition.
LOOKING BACK:
The proof seems sound and it shows exactly what we wanted, which is that the precondition implies the postcondition. Looking back, there appear to be no simpler methods of solving this question as its set out perfectly for the proof approach used above.
Subscribe to:
Posts (Atom)