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.
Saturday, October 18, 2008
Week 6: Work Overload
I didn't get my test back on Friday so I'm still not sure if I did as good as I hope/think I did. I know I can just go to the cdf marking website but I really don;t want to, just incase. Right now I'm really backed up though, too many more midterms to study for, and now Assignment #2 to do also. I hope I can finish it without having to go to as many office hours as I did for Assignment #1. Speaking of Assignment #1, I was pleasantly suprised with my mark. I hope I can maintain it through the whole term!
I don't really have too much else to write about since I'm just working on Assignment #2, while trying to study for a STA247 midterm and MAT223, in addition to starting my CSC207 group project. I hope by the end of the week I'll have more motivation to maintain my work ethic and have something significant to write about.
I don't really have too much else to write about since I'm just working on Assignment #2, while trying to study for a STA247 midterm and MAT223, in addition to starting my CSC207 group project. I hope by the end of the week I'll have more motivation to maintain my work ethic and have something significant to write about.
Friday, October 10, 2008
Week 5: Test Over!
Term test #1: not as easy as I was expecting. I spent awhile studying but I really didn't know how to study for it. I reviewed all my notes and redid the questions from class but I sort of had them memorized so it wasn't anything new that I was solving. The past tests sort of helped...but I guess in a course like this it's all about understanding the concepts. When I woke up this morning I felt fairly confident, but as soon as I started reading the test my blood ran cold. I spent probably 20 minutes on one question. But luckily, luckily, in the last 15 minutes of class I miraculously figured everything out - at least I hope. My only concern is that, well, being that I had only about 10 minutes to write up each proof I did it extremely messily. I even wrote "sorry for the messy writing" just before handing it in. If I could make one request it would be for some practice problems to be posted about a week or some prior to term tests, I think that would make studying a lot easier or at last help us feel more confident if we can do the practice questions.
Now I get a long weekend of not too much work to do, only study for a PSY midterm, finish assignment #1 for CSC207, and possibly work on Problem Set #3 if it gets posted.
Now I get a long weekend of not too much work to do, only study for a PSY midterm, finish assignment #1 for CSC207, and possibly work on Problem Set #3 if it gets posted.
Sunday, October 5, 2008
Week 4: A1 down, Term Test #1 to come.
Well I made it through A1, after a few office visits and a lot of asking TAs stupid questions. Imagine my surprise after finding out from a TA that we're allowed to simply state that Phi is greater than zero while I spent hours attempting to prove it, rather unsuccessfully, with the information given in question three. But its over, that's what counts.
I'm slightly worried about the upcoming term test since we really didn't cover all that much - only Simple Induction, Complete Induction, and a bit of Well Ordering. I really really hope that some practice problems will be posted along with some past tests, that would help give me a good gauge of the difficulty of the test. I've done the few questions in the textbook that seem relevant and reviewed lecture notes, the assignment, and the problem sets, but I still don't feel comfortable without having brand new questions to practice on. I'm hoping that the test will have a postage question, those aren't overly difficult yet are easy to come up with, plus they can be done with Simple Induction or Complete Induction. Or maybe a question involving types of sets, where it has to be partitioned into sets without a certain element and sets with that element. I'd rather there not be any questions with Well Ordering since it seems disconnected from induction proofs and we haven't studied it in much detail in the lectures. But overall I believe this first test won't be too much of a problem because I've learned induction before CSC236.
All that's left to do is study and not get consumed in the wave of work that comes every October. Oh October, I've come to loathe you, your constant battery of assignments, midterms, and whatever foul bits of education you can spew from your seasonal depths. But you have Halloween, so I forgive you. Atleast until next October.
I really need more free time.
I'm slightly worried about the upcoming term test since we really didn't cover all that much - only Simple Induction, Complete Induction, and a bit of Well Ordering. I really really hope that some practice problems will be posted along with some past tests, that would help give me a good gauge of the difficulty of the test. I've done the few questions in the textbook that seem relevant and reviewed lecture notes, the assignment, and the problem sets, but I still don't feel comfortable without having brand new questions to practice on. I'm hoping that the test will have a postage question, those aren't overly difficult yet are easy to come up with, plus they can be done with Simple Induction or Complete Induction. Or maybe a question involving types of sets, where it has to be partitioned into sets without a certain element and sets with that element. I'd rather there not be any questions with Well Ordering since it seems disconnected from induction proofs and we haven't studied it in much detail in the lectures. But overall I believe this first test won't be too much of a problem because I've learned induction before CSC236.
All that's left to do is study and not get consumed in the wave of work that comes every October. Oh October, I've come to loathe you, your constant battery of assignments, midterms, and whatever foul bits of education you can spew from your seasonal depths. But you have Halloween, so I forgive you. Atleast until next October.
I really need more free time.
Sunday, September 28, 2008
Week 3: Assignment #1...still...
So far CSC236 is in the lead for most work this semester. When I look at the actual work assigned it doesn't seem like it should take too long, but the process of explaining the proof clearly enough in hopes of getting full marks is taking me hours, literally. I'm hoping that once A1 is marked I'll get some feedback to whether I'm writing my proofs clear enough or not. Other then that, all I can do is go to office hours constantly.
I'm finally almost finished A1, after writing question #1 out three different ways and spending a good two hours writing out a clear proof for #2. All I have left to do is figure out how I'm supposed to prove that Phi is irrational, given that I only have natural numbers to work with. I have a strong feeling that I'll have to go to office hours Monday morning before its due. Oh well, I have most of today to think it over and hopefully figure it out.
I really hope October doesn't get too busy, but its not looking good: five midterms/tests, two assignments, three homeworks, two problem sets, two exercises, and the CSC207 project to work on. What little free time I had will soon be gone. Its a depressing situation, but I guess that's university life.
I'm finally almost finished A1, after writing question #1 out three different ways and spending a good two hours writing out a clear proof for #2. All I have left to do is figure out how I'm supposed to prove that Phi is irrational, given that I only have natural numbers to work with. I have a strong feeling that I'll have to go to office hours Monday morning before its due. Oh well, I have most of today to think it over and hopefully figure it out.
I really hope October doesn't get too busy, but its not looking good: five midterms/tests, two assignments, three homeworks, two problem sets, two exercises, and the CSC207 project to work on. What little free time I had will soon be gone. Its a depressing situation, but I guess that's university life.
Saturday, September 20, 2008
Week 2: Assignment #1, Oh God.
This second week of classes had a good feeling to it, my mind is no longer on vacation and my classes dont seem overly hard. I was glad that the 236 lectures stayed at the same pace and were 90% examples, seeing examples of how Induction/Complete Induction is done over and over hammers it in nicely. And also the problem set took me less time than I anticiplated - even though Prof. Heap informed everyone that they would not me "problem sets" in the sense that those of us who came from MAT137 were used to. The only problem I kept running into was whether or not I was explaining too much or too little in my justification, but that was solved relativtly painlessly through a quick visit during office hours (actually I think it wasn't during office hours, oops).
As I'm writing this I'm taking my break from working on Assignment #1. I just have to say: it's HARD. Not impossible, but hard nonetheless. I think I've figured out the pattren for the menu problem, but proving it inductively is a whole different ball game. I'm not worrying too much though, I'll just have to go to as many TA office hours as I can. At least I hope that will help.
In the mean time, working on problem set #2 will keep me productive without losing my sanity.
As I'm writing this I'm taking my break from working on Assignment #1. I just have to say: it's HARD. Not impossible, but hard nonetheless. I think I've figured out the pattren for the menu problem, but proving it inductively is a whole different ball game. I'm not worrying too much though, I'll just have to go to as many TA office hours as I can. At least I hope that will help.
In the mean time, working on problem set #2 will keep me productive without losing my sanity.
Sunday, September 14, 2008
Week 1: Still Half Asleep
Its been a long summer. Getting back into the swing of university life has been a rough process, but hopefully this upcoming week will be easier. But, I must say, I'm glad to be back. Summer got old fairly quickly: work, videogames, sleep, repeat. my mind needs more activity!
Unfortunatly CSC236 was my first class of the year and I had no idea what was going on. But I have hope, I did well in CSC165. I actually didn't know that this was going to be my first class; for some reason I was under the impression that Prof. Heap's class would be listed as CSC26_, so I expected it to be in the spring. It was a pleasant suprise, plus the textbook was only 25 dollars, so that helps my wallet.
The first few classes (aside from Monday) went well, a rough review of induction and some good example problems that initially stumped me. It seems like it will be an easy first couple weeks, I enjoy proofs by induction and the first problem set only took about 15 minutes to complete. Also, Prof. Heap's new tablet PC is an excellent teaching tool, since all of the notes that he writes up in class are posted online it means I have more time in class to simply listen and think about the problem presented (plus writing down a few personal notes and scratch work). That was one of the things that really bothered me last year, having to quickly type everything up as it was written on the board. That and the structured proof. By the end of last term I definitly wasn't a fan of the structured proof, but I will admit that in the beginning it helped a lot. Now that thats gone it'll be even easier. Well, aside from the fact that this class is inherently harder than CSC165. Oh well, can't win every battle.
Unfortunatly CSC236 was my first class of the year and I had no idea what was going on. But I have hope, I did well in CSC165. I actually didn't know that this was going to be my first class; for some reason I was under the impression that Prof. Heap's class would be listed as CSC26_, so I expected it to be in the spring. It was a pleasant suprise, plus the textbook was only 25 dollars, so that helps my wallet.
The first few classes (aside from Monday) went well, a rough review of induction and some good example problems that initially stumped me. It seems like it will be an easy first couple weeks, I enjoy proofs by induction and the first problem set only took about 15 minutes to complete. Also, Prof. Heap's new tablet PC is an excellent teaching tool, since all of the notes that he writes up in class are posted online it means I have more time in class to simply listen and think about the problem presented (plus writing down a few personal notes and scratch work). That was one of the things that really bothered me last year, having to quickly type everything up as it was written on the board. That and the structured proof. By the end of last term I definitly wasn't a fan of the structured proof, but I will admit that in the beginning it helped a lot. Now that thats gone it'll be even easier. Well, aside from the fact that this class is inherently harder than CSC165. Oh well, can't win every battle.
Subscribe to:
Posts (Atom)
