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.
Monday, November 10, 2008
Busy, busy, busy...
It's been a while since my last post. Having a full course-load, a job, and having to commute for 2.5 hours each day makes this whole log-keeping process a challenge, as there's simply no time to fit this into the schedule. I was finally able to put some time aside today to write a few things about CSC236.
So, we've covered a considerable amount of material so far. Induction, recursion, complexity, completeness, and now we've starting exploring formal languages and regular expressions. Induction and completeness seem like very interesting concepts, and relatively useful. Complexity, unfortunately, is something that I still am having problems understanding. I've to, somehow, find some time to put in more work in that area of CSC236 and catch up.
The 2nd midterm was held last Friday. Seemed like a fair test. The completeness questions were interesting, and the last one was a bit of a challenge as there wasn't a useful invariant(that I could see, at least) that would be useful in proving the termination of the loop.
The assignments, on the other hand, have proven to be very difficult for me. Maybe I lack the thorough understanding that's required to solve those questions, or maybe the questions are simply very difficult. I don't know. What I do know though is that trying to tackle and expect to complete the assignment on my own does not seem like a very good idea anymore. For the coming assignment, I'll have to consider pairing up with someone or getting some help from the TAs/profs, both of which are relatively unfamiliar concepts for me. More things to get used to, it seems.
Time constraints coupled with the ridiculous workload of the other courses I'm taking this semester have lead to my missing the last couple of lectures, which is unfortunate as formal languages and especially regular expressions are things that interest me. Another set of things to add to my "236 catch-up" list.
Looking forward to the next few lectures.
Signing out.
PS. I'm hoping the next assignment is a bit more "sane" than the previous.
So, we've covered a considerable amount of material so far. Induction, recursion, complexity, completeness, and now we've starting exploring formal languages and regular expressions. Induction and completeness seem like very interesting concepts, and relatively useful. Complexity, unfortunately, is something that I still am having problems understanding. I've to, somehow, find some time to put in more work in that area of CSC236 and catch up.
The 2nd midterm was held last Friday. Seemed like a fair test. The completeness questions were interesting, and the last one was a bit of a challenge as there wasn't a useful invariant(that I could see, at least) that would be useful in proving the termination of the loop.
The assignments, on the other hand, have proven to be very difficult for me. Maybe I lack the thorough understanding that's required to solve those questions, or maybe the questions are simply very difficult. I don't know. What I do know though is that trying to tackle and expect to complete the assignment on my own does not seem like a very good idea anymore. For the coming assignment, I'll have to consider pairing up with someone or getting some help from the TAs/profs, both of which are relatively unfamiliar concepts for me. More things to get used to, it seems.
Time constraints coupled with the ridiculous workload of the other courses I'm taking this semester have lead to my missing the last couple of lectures, which is unfortunate as formal languages and especially regular expressions are things that interest me. Another set of things to add to my "236 catch-up" list.
Looking forward to the next few lectures.
Signing out.
PS. I'm hoping the next assignment is a bit more "sane" than the previous.
Tuesday, September 30, 2008
First post
Hello everyone,
This blog (SLOG) is part of the required/marked set of works for the CSC236 course offered at UofT, a course which is required for the Computer Science program that I'm enrolled in. This is the first course which made it obligatory to keep a public journal/log, and I'm not much impressed with this requirement; however, I'm sure that my being impressed with this was not in the list of criteria when prof. Heap was deciding to put this requirement in the course, so there's not much more that should be said about it.
... And now onto the the actual b/slogging. It has been just over 3 weeks now since the first lecture. The material we're covering is relatively interesting; however, mastering it is a time-consuming process. We've just covered induction and its three flavours(simple, complete and PWO) and seen how each is related to the others. The problem sets are a niece touch in that they provide a medium for exercising the art and practical skills attained in the lectures. The first assignment was relatively challenging but still manageble. Proffersor's and TAs office hours are vast and distributed well throughout the week but I would definitely prefer a tutorial for the class, as it was the case in the past. I'm sure others agree with me on this when I say that having a tutorial provides more of an incentive to go and ask questions. Oh well, perhaps next iterations of the course will reconsider having tutorials again...
I would like to conlcude this post by saying that even though I can't describe the process of working on the first assignment as enjoyable, it did provide a couple of "But of course..." or eureka moments which I haven't experienced in a while. Definitely enjoyed those!
That's it for now. Signing out...
This blog (SLOG) is part of the required/marked set of works for the CSC236 course offered at UofT, a course which is required for the Computer Science program that I'm enrolled in. This is the first course which made it obligatory to keep a public journal/log, and I'm not much impressed with this requirement; however, I'm sure that my being impressed with this was not in the list of criteria when prof. Heap was deciding to put this requirement in the course, so there's not much more that should be said about it.
... And now onto the the actual b/slogging. It has been just over 3 weeks now since the first lecture. The material we're covering is relatively interesting; however, mastering it is a time-consuming process. We've just covered induction and its three flavours(simple, complete and PWO) and seen how each is related to the others. The problem sets are a niece touch in that they provide a medium for exercising the art and practical skills attained in the lectures. The first assignment was relatively challenging but still manageble. Proffersor's and TAs office hours are vast and distributed well throughout the week but I would definitely prefer a tutorial for the class, as it was the case in the past. I'm sure others agree with me on this when I say that having a tutorial provides more of an incentive to go and ask questions. Oh well, perhaps next iterations of the course will reconsider having tutorials again...
I would like to conlcude this post by saying that even though I can't describe the process of working on the first assignment as enjoyable, it did provide a couple of "But of course..." or eureka moments which I haven't experienced in a while. Definitely enjoyed those!
That's it for now. Signing out...
Subscribe to:
Posts (Atom)