As the final days of CSC236 came to a close, a 236 student thought back and looked at everything he had learned and (in vain) tried to remember. Test 3 was actually not as hard as I had expected and I am very happy for it. Fortunately I had learned enough about regexes to do well, and I had finally understood most of DFSAs to do well on the exam!
As much as I was nearly moved (read: bored) to tears over much of the material, I did find enjoyable several topics, including PSI, regexes, and DFSA machines (now that I understand them). Its been a hard semester, not only for me but for Danny Heap too. Thank you for your time and patience =D Maybe you'll be my prof again @_@
~fOrTT
Friday, December 5, 2008
Episode 12: Pumping lemmings...er..lemmas
Well, almost the last test (which imho I find ridiculous since it is our last class and our exam is in a week...I mean, come on...cut us some slack...)
Material about pumping lemmas and finding whether a language is regular or not!
I'm more worried about test3...its the last thing before the final exam so I want to do well to have a "safety net" before the final. Anyway, I'd write more but I have to do some hardcore studying for the test.
Material about pumping lemmas and finding whether a language is regular or not!
I'm more worried about test3...its the last thing before the final exam so I want to do well to have a "safety net" before the final. Anyway, I'd write more but I have to do some hardcore studying for the test.
Episode 11: (Too lazy to think of a witty title)
Well, working on A3 certainly was not fun. I did not even get much done for the creation of DFSA machines. I had mixed reactions from my peers as well- it seemed that some tried to do it with two machines, while others wanted to complete it with only one.
In class we learned more on DFSAs and then their evil cousin (twice removed)- NFSAs. I keep wondering who creates these crazy methods, but I suppose it is useful for something (such as doing csc236 assignments...but these are a result of someone creating the methods...paradox???)
I did enjoy seeing that it was possible to write a regex using a FSA. Of course drawing little circles and linking them with lines is also enjoyable ;D
Anyway, tired from working on A3 and getting denied and denied again on a good solution for the machine question...good night and good luck :D
In class we learned more on DFSAs and then their evil cousin (twice removed)- NFSAs. I keep wondering who creates these crazy methods, but I suppose it is useful for something (such as doing csc236 assignments...but these are a result of someone creating the methods...paradox???)
I did enjoy seeing that it was possible to write a regex using a FSA. Of course drawing little circles and linking them with lines is also enjoyable ;D
Anyway, tired from working on A3 and getting denied and denied again on a good solution for the machine question...good night and good luck :D
Episode 10: Return of the Assignment (special appearance by regex)
Well, A3 is due in about a week, and I am looking forward to finishing the last of a series of demanding questions == Did relatively well in A2 (well...almost a 200% improvement to the first) so hopefully this good work streak continues.
This week we continued our discussion about regex, which I had previously found quite simple, so not much to whine about there...
However, DFSA machines are quite difficult to understand. To me it seems like its writing a whole lot of if-clauses in Java. Basically each transition state is like an if-clause. Designing DFSAs seemed simple at first but the fact that we have to do DFSAs for modulus numbers (such as numbers with remainder 2 or 3) and doing everything in binary (which is simple because it only uses 0 and 1 in the alphabet, but very difficult since I don't really know binary by heart and have to take forever to remember how to convert to a binary number) made everything quite tedious.
This week we continued our discussion about regex, which I had previously found quite simple, so not much to whine about there...
However, DFSA machines are quite difficult to understand. To me it seems like its writing a whole lot of if-clauses in Java. Basically each transition state is like an if-clause. Designing DFSAs seemed simple at first but the fact that we have to do DFSAs for modulus numbers (such as numbers with remainder 2 or 3) and doing everything in binary (which is simple because it only uses 0 and 1 in the alphabet, but very difficult since I don't really know binary by heart and have to take forever to remember how to convert to a binary number) made everything quite tedious.
Episode 9: Regex- Making the lazy even lazier
This week we finally covered regular expressions. I had never used them before, nor known how they worked, but I had heard from my programming friends that it was insanely useful and easy to use; therefore I was very excited to learn about how to be as lazy as possible.
Fortunately, things did seem quite easy, as language operations just seemed like sets that we learned in 165, and regular expression examples were cool. It was like learning a complete language, and material like + (or), and * (Kleene stars) were not too difficult to learn.
The most difficult part of this (thus far) was proving equality of languages.
Not only did I have to prove that a string \in L1 (a language) implied that a string was in a language denoted by a certain regular expression, but I had to prove it the OPPOSITE way. The first proof was quite simple, but the reverse direction was a lot more difficult to comprehend (and the example in the txtbook did not help much in my understanding). Anyway, hoping to do well in this section since I do understand about 80% of the material and could do more with studying.
Fortunately, things did seem quite easy, as language operations just seemed like sets that we learned in 165, and regular expression examples were cool. It was like learning a complete language, and material like + (or), and * (Kleene stars) were not too difficult to learn.
The most difficult part of this (thus far) was proving equality of languages.
Not only did I have to prove that a string \in L1 (a language) implied that a string was in a language denoted by a certain regular expression, but I had to prove it the OPPOSITE way. The first proof was quite simple, but the reverse direction was a lot more difficult to comprehend (and the example in the txtbook did not help much in my understanding). Anyway, hoping to do well in this section since I do understand about 80% of the material and could do more with studying.
Episode 8: Test 2...soon.
Well, a week from now I will embark on another journey to hopefully pass the 236 test. I dislike how course coordinators seem to conspire to put everything at the same time. Either we don't get any hw or assignments, or we just get owned by a #&$*(^load of homework, assignments, tests, and projects. Note to future CSC students- you are screwed.
This week we covered iterative correctness (testing correctness for recursive proofs). I don't really understand loop invariants, but it seems like its basically a part of the FINAL solution, a piece of the puzzle if you will. At the end, the loop invariants will be found and the recursive function will terminate.
This week we covered iterative correctness (testing correctness for recursive proofs). I don't really understand loop invariants, but it seems like its basically a part of the FINAL solution, a piece of the puzzle if you will. At the end, the loop invariants will be found and the recursive function will terminate.
Episode 7: The Assignment Strikes Back
Well, A2 is around the corner...and from past experience for A1, I am NOT excited.
We learned how to determine program correctness, which I feel is trivial...hopefully my mind will change (or else I wont study it for exam xD). Why do we really need to determine pre/post conditions when we can just look through a relatively simple function and just know what it returns? Instead there was so much material covered about correctness which I found very confusing =/ Guess I'll pore over the txtbook and try to make light of it.
Please Please Please be nice for A2 marking T_T
We learned how to determine program correctness, which I feel is trivial...hopefully my mind will change (or else I wont study it for exam xD). Why do we really need to determine pre/post conditions when we can just look through a relatively simple function and just know what it returns? Instead there was so much material covered about correctness which I found very confusing =/ Guess I'll pore over the txtbook and try to make light of it.
Please Please Please be nice for A2 marking T_T
Episode 6: TURKEY DAY
First off, happy turkey day to everyone who reads this =P hope you had a great time^^
Anyway, with only 2 hours of class (omgyey), we started off on master theorems, which sounded insanely difficult. I thought it would be something like the a set that contains PSI,PCI and PWO, but I was wrong..it was much, much more sinister. It was however, cool to see that we could split a single task into smaller, easier problems to solve with the master theorem. Anyway, off to get some turkey and stuffing :D
Anyway, with only 2 hours of class (omgyey), we started off on master theorems, which sounded insanely difficult. I thought it would be something like the a set that contains PSI,PCI and PWO, but I was wrong..it was much, much more sinister. It was however, cool to see that we could split a single task into smaller, easier problems to solve with the master theorem. Anyway, off to get some turkey and stuffing :D
Episode 5: badbadbadbadA1
Wow. I did not expect to do this badly at a1. Unfortunately I had split the questions between me and my partners, so there wasn't as much teamwork and cooperation as I had hoped. Well, I can only work harder for the next two assignments...and study EXTREMELY hard in this section so I can do well for finals.
Anyway, on to the test. I'm glad PCI and PWO weren't on the test (although a huge chunk of my time was spent refining the technique D:) The Fibonacci question was easy enough, as I had studied on unwinding and closed forms. I'm hoping only to get at least 50%...but of course higher is better (;D :D TAs)
This week we learned more on closed forms, which is very related to unwinding. Its a very useful technique to turn a recursive function into a very simple function! Seems like a great shortcut..hopefully I can use it everywhere whenever I see a recursive function :D
Anyway, on to the test. I'm glad PCI and PWO weren't on the test (although a huge chunk of my time was spent refining the technique D:) The Fibonacci question was easy enough, as I had studied on unwinding and closed forms. I'm hoping only to get at least 50%...but of course higher is better (;D :D TAs)
This week we learned more on closed forms, which is very related to unwinding. Its a very useful technique to turn a recursive function into a very simple function! Seems like a great shortcut..hopefully I can use it everywhere whenever I see a recursive function :D
Episode 4: Unwinnnnnnnd
This week, we learned about Recursion and how to solve it via "unwinding" (!!!) It was confusing at first but it makes a lot of sense, and seems very useful since you can virtually make a recursive function...NOT recursive.
Well, A1 sample sol'n is posted. Since I spent a fair amount of time on it, I was not happy to see that what I did for every question was quite drastically different from the sol'ns. Hopefully my methods were valid for solving the questions...hopefully my hope is not false hope D: Question 3 completely confused me, and I even had to google and wiki phi and its relation to sqrt(5) to even remotely understand what I had to do.
Expect plenty of depression next week after the test.
Well, A1 sample sol'n is posted. Since I spent a fair amount of time on it, I was not happy to see that what I did for every question was quite drastically different from the sol'ns. Hopefully my methods were valid for solving the questions...hopefully my hope is not false hope D: Question 3 completely confused me, and I even had to google and wiki phi and its relation to sqrt(5) to even remotely understand what I had to do.
Expect plenty of depression next week after the test.
Episode 3: A New Assignment
Assignment woes...the questions looked very easy at first, since it seems like they are mutations of what we did in class. However, question 2 and esp. question 3 were infinitely harder than I thought. At least I easily found that a repeating cycle for 3 meals is:
{L},{},{S},{S,L},{S,L,P},{S,P},{P},{P,L}
That part was actually enjoyable, like some kind of puzzle.
Anyways, this week was all about well ordering and proving that principle of well ordering implies principle of simple induction implies principle of complete induction implies...etc
I didn't really know that they were equivalent to each other...thought it was just different ways to do a question. Guess its something like addition and multiplication =P
I wonder if these three principles are the only methods we need to use this course or proving O_O
{L},{},{S},{S,L},{S,L,P},{S,P},{P},{P,L}
That part was actually enjoyable, like some kind of puzzle.
Anyways, this week was all about well ordering and proving that principle of well ordering implies principle of simple induction implies principle of complete induction implies...etc
I didn't really know that they were equivalent to each other...thought it was just different ways to do a question. Guess its something like addition and multiplication =P
I wonder if these three principles are the only methods we need to use this course or proving O_O
Wednesday, December 3, 2008
Episode 2: Chocolate and Stamps
Finally getting to post my weekly notes (about 236 material, class, and life in general). . . unfortunately near the end of the course :x Hopefully I'll get some feedback^^ Anyway, time to digitize all my paper notes :D
---
Well, this week was mostly dealing with STRONG induction, rather than simple induction last week. I've always liked simple induction much more (well...more like the lesser of two evils but I digress). But it does make more sense for situations where base cases are not easily found.
The chocolate grid problem shown in class really helped my understanding of Strong induction- I had been used to using P(0) for most problems involving simple induction, and I had thought that strong induction could not involve any base cases. However, the base case of a 1-square chocolate grid made sense since it can be broken with 0 breaks (sounds a bit facetious though ==)
Another problem that I found quite fun was the postage to be formed with 4,5 cent stamps. It was slightly annoying to have a working sequence of numbers only to find the next number to fail (8, 9, 10 work but 11 does not).
Another note: so far, Principle of Well Ordering seems a bit too. . . simple. Doesn't any non-empty subset have at least 1 element? Then there has to be a smallest element- I don't really understand why there has to be some new "principle" to declare it. Hopefully, things will clear up in the coming weeks.
fOrTT
---
Well, this week was mostly dealing with STRONG induction, rather than simple induction last week. I've always liked simple induction much more (well...more like the lesser of two evils but I digress). But it does make more sense for situations where base cases are not easily found.
The chocolate grid problem shown in class really helped my understanding of Strong induction- I had been used to using P(0) for most problems involving simple induction, and I had thought that strong induction could not involve any base cases. However, the base case of a 1-square chocolate grid made sense since it can be broken with 0 breaks (sounds a bit facetious though ==)
Another problem that I found quite fun was the postage to be formed with 4,5 cent stamps. It was slightly annoying to have a working sequence of numbers only to find the next number to fail (8, 9, 10 work but 11 does not).
Another note: so far, Principle of Well Ordering seems a bit too. . . simple. Doesn't any non-empty subset have at least 1 element? Then there has to be a smallest element- I don't really understand why there has to be some new "principle" to declare it. Hopefully, things will clear up in the coming weeks.
fOrTT
Sunday, September 14, 2008
Episode 1 (Pilot)
After trying to think of some witty name to put to my blog (and settling on some obscure 1998 game reference...fail), here goes the first post of the year...
Well, after 4 months of freedom I've come to a conclusion that there's no place likehell home... a 4 day headache isn't exactly the best way to start off the year == but I think I've settled ok. To be honest I think CSC236 is going to be one of my hardest courses this semester, along with STA247 (11% retake rate?!) and maybe CSC207 (I don't know a thing about Java... TT). I've never been good at proofs and proof-related theory (like CSC165 and MAT137) so its going to be a long long year ahead...
I was surprised at the pattern that came out of investigating this question:
Case 1: {a}
Odd: {a}
Even: {Empty Set}
Case 2: {a,b}
Odd: {a}, {b}
Even: {Empty Set}, {a, b}
Case 3: {a,b,c}
Odd: {a}, {b}, {c}, {a, b, c}
Even: {Empty Set}, {a, b}, {a, c}, {b, c}
We can easily see that the odd subsets of a particular case contain the odd subsets of the previous case. However, a "hidden" pattern is adding the new element of the current set to each of the even subsets of the previous case, which makes them new odd subsets. For example, two of the odd subsets in Case 3, {a} and {b}, exist already from Case 2. To find the remaining odd subsets of Case 3, we must add the new element in Case 3 to the even subsets of Case 2, {Empty Set}, and {a, b}, creating {c}, and {a, b, c}. I was quite surprised that this method work, as shown in a proof during class.
On an unrelated note, I wish the lecture slides could be posted up perhaps a day or 2 before class, so I could have some time to look through them and prepare. It would be great to have the annotated version posted up soon after lectures as well.
Hope this is a decent enough first post ==...cheers to everyone else in 236,
Well, after 4 months of freedom I've come to a conclusion that there's no place like
Anyway, the course has been okay this far, I'm still following along at a reasonable pace. As for course material, the most interesting thing so far has been the proof of:
P(n): 3^n has units digit in 1, 3, 7, 9
since originally I had thought you did need 4 separate base cases to prove it, but the fact that you only need 1 was a bit surprising. The other question that was quite intriguing was:
How many subsets of odd size does a set with n elements have?
I was surprised at the pattern that came out of investigating this question:
Case 1: {a}
Odd: {a}
Even: {Empty Set}
Case 2: {a,b}
Odd: {a}, {b}
Even: {Empty Set}, {a, b}
Case 3: {a,b,c}
Odd: {a}, {b}, {c}, {a, b, c}
Even: {Empty Set}, {a, b}, {a, c}, {b, c}
We can easily see that the odd subsets of a particular case contain the odd subsets of the previous case. However, a "hidden" pattern is adding the new element of the current set to each of the even subsets of the previous case, which makes them new odd subsets. For example, two of the odd subsets in Case 3, {a} and {b}, exist already from Case 2. To find the remaining odd subsets of Case 3, we must add the new element in Case 3 to the even subsets of Case 2, {Empty Set}, and {a, b}, creating {c}, and {a, b, c}. I was quite surprised that this method work, as shown in a proof during class.
On an unrelated note, I wish the lecture slides could be posted up perhaps a day or 2 before class, so I could have some time to look through them and prepare. It would be great to have the annotated version posted up soon after lectures as well.
Hope this is a decent enough first post ==...cheers to everyone else in 236,
fOrTT
Subscribe to:
Comments (Atom)