It's been a long trip, from the first class to now. Unfortunately I don't know if I remember everything - in fact I most likely don't. But for the most part it seemed that CSC236 was one of those classes where you either get it or you don't, and luckily I "got it". I've been relying on my CSC236 mark to bring up my overall GPA, since it's probably my best class. Although that isn't saying that its easy - not by a long shot - I just happen to eventually figure out whatever I'm work on, be it a problem set or assignment or test, and do rather well. I think the reason why I'm doing well in this course is simply because it's one of those courses where you either get or you don't. Unlike most science based courses this course would be infinitely harder if I didn't understand it, there's no formulas where I can just plug some numbers into and hope to get lucky. Doing proofs requires understanding what I'm proving, so getting even a passing grade requires me to actually understand what's going on - and that's the difference, understanding; knowing the reason why puts meaning into what I'm learning. I'm no longer just memorizing when to use what formula and getting completely stumped when I'm thrown a question that actually requires some thought. Even though I'd occasionally hate this work - staring at assignment questions for hours hoping to figure it out - in the end CSC236 is probably the only course that I really "get", the only course that my knowledge of isn't limited to what theorems I can remember but I have no idea of how to prove, or what formulas I can apply without knowing (or caring) where they came from.
Even though I've been doing well in CSC236 my mark is only destined to drop. I have 5 exams in 4 days and CSC236 is the last one. No matter what I do to study and prepare I'll be burnt out by the time Friday morning comes. Its sort of aggravating, having put so much effort into getting decent grades and have it all potentially ruined simply because I'm unlucky. If I die of sleep deprivation I'm blaming U of T.
On a lighter note, I'm done working for the night. I think this will be my last post, since SLoGs are due this Friday, but I had fun with this. Keep up the good work Professor Heap, its refreshing to be in a class where I'm not just a number. And my thanks to the T.A.s for being generous markers and never angrily giving me zero for indecipherable tests or ridiculously long assignments.
~B.M.
Tuesday, December 2, 2008
Saturday, November 22, 2008
Week 11 Still: Polya Problem Solving Episode!
I've decide to write up a problem solving episode of how I solved Problem Set #6.
Problem: Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)).
1) Understanding the Problem:
In class we were shown the process for proving a language equivalency question such as this, and what it boils down to is proving mutual inclusion: that if x is in L then x is in L(((0+1)(0+1))*(0+1)) and if x is in L(((0+1)(0+1))*(0+1)) then x is in L, for any arbitrary string x. So this question is really doing two shorter proofs and using them to make one larger claim.
2) Devising a Plan:
The best way to plan out this proof is to use the structure that was presented in lecture and in the textbook. This structure consists of first proving each inclusion separately, by taking an arbitrary element of one of the languages and breaking it into sub strings then recombining those sub strings and showing that they meet the criteria for the other language.
To do this, it would be best to split each arbitrary string into sub strings based on the amount of characters, not specific characters. I think this would be best because all we need to know is that the string has an odd length, and the generic odd number is 2k+1 where k is some natural number. In fact this formula for odd numbers gives me some insight into how to prove it: break the string into k sub strings with 2 characters and then a suffix of 1 character. The good thing about this idea is that it it is the same format as L(((0+1)(0+1))*(0+1)) - replacing (0+1) with one and the Kleene star with a k give the definition of odd: (1+1)k+1 = 2k+1.
Now that I've discovered how to go from one language to the other I just have to write it up in a formal manner.
3) Carrying out the Plan:
Let x be an arbitrary element of L(((0+1)(0+1))*(0+1)). Then there exists some k e N, and y_0,y_1,...,y_k e {0,1}* such that y_0 e L(0+1) and y_i e L((0+1)(0+1)) for all 1 <= i <= k.
Then for each y_i for 1 <= i <= k has two characters - 0 or 1 followed by 0 or 1 - so 2k characters total, when concatenated together in the form y_1y_2...y_k.
Also, y_0 has exactly 1 character - 0 or 1 - so y_1y_2...y_k_y_0 concatenated together has 2k+1 characters, an odd number. Thus x, represented by y_1_y_2...y_k_y_0, has an odd length and thus is an element of L.
Let x be an arbitrary element of L. Then by definition x has an odd number of characters (an odd length), lets say 2k+1 characters for some k e N. Now we can define k consecutive sub strings of x, where for each i, 1 <= i <= k, y_i is the sub string of x from the (2i-1)th character to the (2i)th character, both inclusive.
Thus each y_i e L((0+1)(0+1)). Also, let y_k+1 b the last character of x, the (2k+1)th character. Then y_k+1 e L(0+1).
Nowe we have defined x = y_1y_2...y_ky_k+1 concatenated, where each y_i e L((0+1)(0+1)) for all i, 1 <= i <=k, and y_k+1 e L(0+1).
Therefore, x e (L((0+1)(0+1))^k)(L(0+1)) which is a subset of L((0+1)(0+1))*L(0+1) = L(((0+1)(0+1))*(0+1)). Thus it follows that x e L(((0+1)(0+1))*(0+1)).
We have proven that x e L ==> x e L(((0+1)(0+1))*(0+1)) and x e L(((0+1)(0+1))*(0+1)) ==> x e L. Thus they are mutually inclusive and therefore equivalent.
4) Looking Back:
The key to proving that one language is equivalent to another seems to be how I seperate each language into its basic parts and relate them to eachother, informally seeing why they are indeed equivalent.
Problem: Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)).
1) Understanding the Problem:
In class we were shown the process for proving a language equivalency question such as this, and what it boils down to is proving mutual inclusion: that if x is in L then x is in L(((0+1)(0+1))*(0+1)) and if x is in L(((0+1)(0+1))*(0+1)) then x is in L, for any arbitrary string x. So this question is really doing two shorter proofs and using them to make one larger claim.
2) Devising a Plan:
The best way to plan out this proof is to use the structure that was presented in lecture and in the textbook. This structure consists of first proving each inclusion separately, by taking an arbitrary element of one of the languages and breaking it into sub strings then recombining those sub strings and showing that they meet the criteria for the other language.
To do this, it would be best to split each arbitrary string into sub strings based on the amount of characters, not specific characters. I think this would be best because all we need to know is that the string has an odd length, and the generic odd number is 2k+1 where k is some natural number. In fact this formula for odd numbers gives me some insight into how to prove it: break the string into k sub strings with 2 characters and then a suffix of 1 character. The good thing about this idea is that it it is the same format as L(((0+1)(0+1))*(0+1)) - replacing (0+1) with one and the Kleene star with a k give the definition of odd: (1+1)k+1 = 2k+1.
Now that I've discovered how to go from one language to the other I just have to write it up in a formal manner.
3) Carrying out the Plan:
Let x be an arbitrary element of L(((0+1)(0+1))*(0+1)). Then there exists some k e N, and y_0,y_1,...,y_k e {0,1}* such that y_0 e L(0+1) and y_i e L((0+1)(0+1)) for all 1 <= i <= k.
Then for each y_i for 1 <= i <= k has two characters - 0 or 1 followed by 0 or 1 - so 2k characters total, when concatenated together in the form y_1y_2...y_k.
Also, y_0 has exactly 1 character - 0 or 1 - so y_1y_2...y_k_y_0 concatenated together has 2k+1 characters, an odd number. Thus x, represented by y_1_y_2...y_k_y_0, has an odd length and thus is an element of L.
Let x be an arbitrary element of L. Then by definition x has an odd number of characters (an odd length), lets say 2k+1 characters for some k e N. Now we can define k consecutive sub strings of x, where for each i, 1 <= i <= k, y_i is the sub string of x from the (2i-1)th character to the (2i)th character, both inclusive.
Thus each y_i e L((0+1)(0+1)). Also, let y_k+1 b the last character of x, the (2k+1)th character. Then y_k+1 e L(0+1).
Nowe we have defined x = y_1y_2...y_ky_k+1 concatenated, where each y_i e L((0+1)(0+1)) for all i, 1 <= i <=k, and y_k+1 e L(0+1).
Therefore, x e (L((0+1)(0+1))^k)(L(0+1)) which is a subset of L((0+1)(0+1))*L(0+1) = L(((0+1)(0+1))*(0+1)). Thus it follows that x e L(((0+1)(0+1))*(0+1)).
We have proven that x e L ==> x e L(((0+1)(0+1))*(0+1)) and x e L(((0+1)(0+1))*(0+1)) ==> x e L. Thus they are mutually inclusive and therefore equivalent.
4) Looking Back:
The key to proving that one language is equivalent to another seems to be how I seperate each language into its basic parts and relate them to eachother, informally seeing why they are indeed equivalent.
Week 11: A3 and being tired.
So far I've spent all day on Assignment #3, and started this assignment about a week ago. I've managed to finish everything except question 3, which I really don't want to do because it looks very complicated. This assignment is really wearing me out. And it doesn't help that I don't have any time to go to office hours - studying for midterms, working on my CSC207 project, doing STA247 homework assignments, trying to figure out what's going on in linear algebra, it all never ends.
At least I sort of understand what's going on this course.
At least I sort of understand what's going on this course.
Sunday, November 16, 2008
Week 10: Happier
I did considerably better than I thought on Term Test #2, so that brought up my confidence. In addition to that I'm not having as many problems as usual with this assignment, although it would be much easier if the textbook gave a proof from why (0*1*)* = (0+1)*. I know why informally, but trying to prove it seems rather difficult so I hope its more of a lemma that I could site in my assignment.
I've also been looking at the bulletin board challenge thread, trying to come up with counterexamples to the regular expressions people have come up with. Sometimes I do, sometimes I don't, but overall it feels like good practice.
Edit: Upon going to office hours, I've been informed that I would indeed have to prove (0*1*)* = (0+1)*. It seems like a hassle to prove, so I might just have to go the long way and prove each part of question two on Assignment #3 separately.
I've also been looking at the bulletin board challenge thread, trying to come up with counterexamples to the regular expressions people have come up with. Sometimes I do, sometimes I don't, but overall it feels like good practice.
Edit: Upon going to office hours, I've been informed that I would indeed have to prove (0*1*)* = (0+1)*. It seems like a hassle to prove, so I might just have to go the long way and prove each part of question two on Assignment #3 separately.
Tuesday, November 11, 2008
Week 9: Hm..
I didn't do as good as I hoped I would on the second term test, for the 3rd question I couldn't think of what the loop invariant would be, although now I think it must be something like "n is a natural number". Classes haven't been going very well, and all this regular expression stuff is very confusing. I'm not sure what to do, even the latest problem set is hard, I have no idea how to approach it.
University is depressing.
Update: Making a post while depressed isn't a good idea. Problem Set #7 wasn't hard at all, and since I'm also doing regular expressions in CSC207 it dosen't seem to be too bad anymore. Also, Assignment #3 is going well and I actually enjoy doing the Finite State Automata questions.
University is depressing.
Update: Making a post while depressed isn't a good idea. Problem Set #7 wasn't hard at all, and since I'm also doing regular expressions in CSC207 it dosen't seem to be too bad anymore. Also, Assignment #3 is going well and I actually enjoy doing the Finite State Automata questions.
Sunday, November 2, 2008
Week 8: Confused
Having so much work to do each week is getting me confused with what's going on in CSC236. All the recent stuff that we have been learning, about the Master Theorem and proving the complexity of recurssive programs or loop invariants is pretty hard to understand. And the book dosen't help at all, it has pages and pages for just a single proof and things thrown in the middle like "Oh yeah, and you need to know this fact to solve this proof". It's sort of getting m worried for Term Test #2, I'd really like questions to be posted similar to questions that we do for Problem Sets for some practice before the test. At this point all I can really hope is that on Monday we'll get a slight list of things we need to know for the test. I don't like having to study the assignments for tests, since our assignment questions are always so long that its hard to see how any question could be on the test.
Will we get a little program and have to write a recurssive formula for its time complexity and then prove it right? Or will we just be given the formula and prove a closed form of it? Will he have to prove some sort of loop invariant? Or that a precondition implies the post condition of some function? My normal way of studying is to think about all the possible structures of questions that could be asked and study the ways of solving them before hand, but as of right now I'm not sure how I'd do that for this test.
Oh well, hopefully I'll have time to start studying on Tuesday.
Will we get a little program and have to write a recurssive formula for its time complexity and then prove it right? Or will we just be given the formula and prove a closed form of it? Will he have to prove some sort of loop invariant? Or that a precondition implies the post condition of some function? My normal way of studying is to think about all the possible structures of questions that could be asked and study the ways of solving them before hand, but as of right now I'm not sure how I'd do that for this test.
Oh well, hopefully I'll have time to start studying on Tuesday.
Saturday, October 25, 2008
Week 7: It's going good
Midterms have been keeping me from focusing on CSC236 a lot, and now I think I'm in trouble since Assignment #2 is due Monday and I'm still unsure as to how I should explain everything. I guess it's going to be a long weekend of working on it.
I'm finding the stuff we're doing now more interesting, proving programs correct. This part of it seems like its much more relevant to computer science than the first bit was, but I suppose the initial inductive proofs were needed in order to be able to prove programs correct. I'd like to mention something about what was shown in Friday's lecture, mainly about the proof for the function egcd(n, m). Prof. Heap said that we would have to prove special cases separately, if n <= m. Well if n < m then n%m is simply n, so then egcd(m, n) is called. Now this is a state that matches the inductive hypothesis, since n < m, and then we know egcd(m,n) returns gcd(m,n) which is the same as gcd(n,m). The only special case would be for n=m.
I don't feel like I'm running into any problems in the course or having a hard time, so for the time being I don't have too much else to say.
I'm finding the stuff we're doing now more interesting, proving programs correct. This part of it seems like its much more relevant to computer science than the first bit was, but I suppose the initial inductive proofs were needed in order to be able to prove programs correct. I'd like to mention something about what was shown in Friday's lecture, mainly about the proof for the function egcd(n, m). Prof. Heap said that we would have to prove special cases separately, if n <= m. Well if n < m then n%m is simply n, so then egcd(m, n) is called. Now this is a state that matches the inductive hypothesis, since n < m, and then we know egcd(m,n) returns gcd(m,n) which is the same as gcd(n,m). The only special case would be for n=m.
I don't feel like I'm running into any problems in the course or having a hard time, so for the time being I don't have too much else to say.
Subscribe to:
Posts (Atom)
