Just finished Test 3. Unfortunately, I left it with some regret, as I ran out of time while writing again. I knew exaclty what I needed to write, if only I had 2 more minutes...
The typos on the cartesian product question led to quite some delay and confusion. I had to rerun through the process several times and didn't have enough time to check my final answer. I believe I wouldn't have ran out of time if there weren't any typo.
I always disliked it when ppl kept writing when the time's up, and I never ever did it myself. But I *might* (leaving it a bit ambiguous for obvious reasons) have been guilty of it this time.... I came in a bit late, some ppl didn't have the typo in their tests (doesn't justify anything, as there are also others' tests that had the typos).
========================
I went to Danny's office hr. My understanding of the pumping lemma and its application in the last post is incorrect. I'm glad I went.
========================
As I mentioned in my first post, I thought I disliked the theory part of CSC because it was of little value to my practical mindset, and that I was weak in the skills needed in theory. Also in my first post, I mentioned the possibility that this course might change my mind. Indeed it has.
This class, in combination with significant changes in my work ethic and overall responsibility, changed my mind to a very large extent.
Working with classmates also helped change my mind: I worked with fellow students who struggled.
I also worked with brilliant fellow students whom I'm sure are significantly smarter than I am. They also struggled (albeit for a shorter time, and understands almost instantaneously with explanation) on some topics. Interestingly, it is somewhat comforting and motivating to know that brilliant people also struggle to understand some topics sometimes.
The way Danny structures and teaches the topic is just fantastic - it really helped narrow the "gap" between my intuitive thought process and the rigorous theory topics. This was never done so well in any other course I've taken that had theory components.
I think that, besides providing us with greater understanding of the rigorous topics themselves, from the way this course is taught I've also learnt approaches that would allow me to work better with other theory topics -> a very valuable and well executed course.
I look forward to csc300 with Danny next term.
And since I've decided to go to Shanghai where my father is working, to spend time with my family this summer instead of taking summer courses, I hope I can catch another Heap course in the fall, intro to database hopefully.
Friday, December 5, 2008
Monday, December 1, 2008
Pumping Lemma, CFGs
The end of the term is very close. Time passes way too fast...
I realized that the pumping lemma could be difficult so I did some pre-reading before the lecture. Unfortunately, I still don't really get it after the lecture. The test is this friday, so I'm going to be going over it right after I finish this.
Unfortunately I think I'm also rather unclear, or have a lack of intuitive understanding of the regularity of a language. Is it generally any language that requires some "memory" to represent as a regex or FSA?
Context-free Grammars are interesting.
It's obvious that we've only seen the tip of the iceberg in this area, and I'm quite interested in how the theory can be extended and applied in practical usage. Unfortunately (or maybe fortunately,) I won't have to get too deep into this, as I'm not planning to take compilers or programming language courses.
***edit
After looking at the course notes and lecture notes. I find the lecture notes much clearer intuitively. But the course notes has great stuff too. With the combination of going through both I *think* I understand how proof of regularity by the pumping lemma works now.
For languages which have some pumping length for which the pumping lemma holds for all strings in the language, it is regular.
For languages which have arbitrarily large pumping lengths, and so no single pumping length works for all strings in the language, the language is not regular.
I hope that understanding is correct.
I realized that the pumping lemma could be difficult so I did some pre-reading before the lecture. Unfortunately, I still don't really get it after the lecture. The test is this friday, so I'm going to be going over it right after I finish this.
Unfortunately I think I'm also rather unclear, or have a lack of intuitive understanding of the regularity of a language. Is it generally any language that requires some "memory" to represent as a regex or FSA?
Context-free Grammars are interesting.
It's obvious that we've only seen the tip of the iceberg in this area, and I'm quite interested in how the theory can be extended and applied in practical usage. Unfortunately (or maybe fortunately,) I won't have to get too deep into this, as I'm not planning to take compilers or programming language courses.
***edit
After looking at the course notes and lecture notes. I find the lecture notes much clearer intuitively. But the course notes has great stuff too. With the combination of going through both I *think* I understand how proof of regularity by the pumping lemma works now.
For languages which have some pumping length for which the pumping lemma holds for all strings in the language, it is regular.
For languages which have arbitrarily large pumping lengths, and so no single pumping length works for all strings in the language, the language is not regular.
I hope that understanding is correct.
Tuesday, November 25, 2008
regex and FSAs
I find current topics very interesting, and again, the way the course was structured for this material is fantastic. First we were shown that there is an equivalent NFSA to every regex. Then, we were shown that for every NFSA there is an equivalent DFSA. Then we were shown that we can construct an equivalent (I think? Havent yet seen the rigorous notes) regex from a DFSA, by "ripping" states and transitions out. So, every regex has an equivalent FSA.
I wonder how each of these different forms of representation are useful, and how they may be used in my further studis in compsci.
I wonder how each of these different forms of representation are useful, and how they may be used in my further studis in compsci.
Wednesday, November 19, 2008
Formal languages, FSA
I was completely new to regular expressions. We were introduced to regex from both the theoretical perspective in csc236, and in the practical usage perspective in csc207, at the same time.
I think this concurrent introduction from both perspectives helped quicken my learning, and I got familiar with regex pretty quick. The theoretical perspective is still harder for me though. Some regex proofs seem to require multiple induction, and it can get confusing as the concepts are quite abstract.
FSAs are quite interesting, I like its graphical nature. It is very interesting that every regex has an FSA (if we allow epsilon transitions). All in all, I really like this part of the course.
A3 is due at a really bad time though. It's another crazy week..
I think this concurrent introduction from both perspectives helped quicken my learning, and I got familiar with regex pretty quick. The theoretical perspective is still harder for me though. Some regex proofs seem to require multiple induction, and it can get confusing as the concepts are quite abstract.
FSAs are quite interesting, I like its graphical nature. It is very interesting that every regex has an FSA (if we allow epsilon transitions). All in all, I really like this part of the course.
A3 is due at a really bad time though. It's another crazy week..
Friday, November 7, 2008
Killed by test, again
I wasted about 5-10 minutes unwinding, when I didn't really need to... But the main killer is the loop termination proof, which I left as "I don't know how to do". It bothers me because it seems to be quite an elementary question on the topic.
To be honest, I didn't expect the test to have much on proving iteration. Particularly on proving termination using a loop invariant.
We've seen it only for a week, the week which is the last, and also busiest, week of the busiest run this semester. I'm an early starter, but as the deadlines piled on, this past week has been very hard. I've had no weekend at all for a while. Basically I had no time to study for the test until this thursday.
We've done no PS on it, no assignment on it, all we saw so far is a couple of examples in lecture, and very lengthy examples in the course notes. In situations like this, it's hard to know whether one's understanding of the topic is correct.
So, I still don't know if I even understand this topic enough, to do a seemingly elementary question like the one on the test. By contemplating the question more, on my way back home from the test I *think* I have a correct idea of what I should prove to prove termination. If I include the time during the test thinking about the question, that's about 40 minutes of thinking, to get an idea of what I think is a correct approach.
Essentially, the question was to me an assignment question that I had to do on a test.
I think it would have helped a lot if we were given more elementary examples, with clear explanations, on this topic. The posted past test had a question, but I didn't fully understand the solution either. The topic is not easy to understand, I think it warrants more examples than the ones we were given.
Maybe now after thinking about the test question I can look at the past test solution and understand it more. Though I doubt it. Probably have to go to an office hour, and spend a week thinking about it everyday and doing some practice questions to understand it. I wish I had the time this past week for that.
To be honest, I didn't expect the test to have much on proving iteration. Particularly on proving termination using a loop invariant.
We've seen it only for a week, the week which is the last, and also busiest, week of the busiest run this semester. I'm an early starter, but as the deadlines piled on, this past week has been very hard. I've had no weekend at all for a while. Basically I had no time to study for the test until this thursday.
We've done no PS on it, no assignment on it, all we saw so far is a couple of examples in lecture, and very lengthy examples in the course notes. In situations like this, it's hard to know whether one's understanding of the topic is correct.
So, I still don't know if I even understand this topic enough, to do a seemingly elementary question like the one on the test. By contemplating the question more, on my way back home from the test I *think* I have a correct idea of what I should prove to prove termination. If I include the time during the test thinking about the question, that's about 40 minutes of thinking, to get an idea of what I think is a correct approach.
Essentially, the question was to me an assignment question that I had to do on a test.
I think it would have helped a lot if we were given more elementary examples, with clear explanations, on this topic. The posted past test had a question, but I didn't fully understand the solution either. The topic is not easy to understand, I think it warrants more examples than the ones we were given.
Maybe now after thinking about the test question I can look at the past test solution and understand it more. Though I doubt it. Probably have to go to an office hour, and spend a week thinking about it everyday and doing some practice questions to understand it. I wish I had the time this past week for that.
Saturday, November 1, 2008
Got hit on the head
For the grasshopper question... I wrote a proof of the recursive formula using combinatorics, and this lemma:
(n C r) = (n-1 C r) + (n-1 C r-1)
(n-1 C r) + (n-1 C r-1) = (n-1)!/r!(n-1-r)! + (n-1)!/(r-1)!(n-1-r+1)!
= (n-1)!/r! * 1/(n-r-1)! + (n-1)!/(n-r)! * 1/(r-1)!
= (n-1)!/r! * (n-r)/(n-r)! + (n-1)!/(n-r)! * r/r!
= (n-1)!(n-r+r)/r!(n-r)!
= (n-1)!n/r!(n-r)!
= n!/r!(n-r)!
= (n C r)
The proof I wrote was quite satisfactory. Then I got a very bright csc236 student to look at my code. He just hit me on the head with what he said: " How many ways can you jump to G(n)? only 2 ways".
ARRGH! Oh well it was good practice..
====
The material about proving preconditions => post conditions seems to be somewhat like a rigorous expression of what goes on in our heads when we write recursion or loops.
Although I definitely have trouble seeing the loop invariant component in proving the correctness of iterative methods. That part is not very intuitive for me. I'm having trouble finding the loop invariants that would assist in the proof. And, for that matter, don't know what I'm looking for either. Got some good tips at lecture how how to find them though.
Will have to go through lec notes and course notes extensively before the test. Gosh, what a busy week it's been, and what a busy week next week will be. For that matter, what busy months oct and nov are...
(n C r) = (n-1 C r) + (n-1 C r-1)
(n-1 C r) + (n-1 C r-1) = (n-1)!/r!(n-1-r)! + (n-1)!/(r-1)!(n-1-r+1)!
= (n-1)!/r! * 1/(n-r-1)! + (n-1)!/(n-r)! * 1/(r-1)!
= (n-1)!/r! * (n-r)/(n-r)! + (n-1)!/(n-r)! * r/r!
= (n-1)!(n-r+r)/r!(n-r)!
= (n-1)!n/r!(n-r)!
= n!/r!(n-r)!
= (n C r)
The proof I wrote was quite satisfactory. Then I got a very bright csc236 student to look at my code. He just hit me on the head with what he said: " How many ways can you jump to G(n)? only 2 ways".
ARRGH! Oh well it was good practice..
====
The material about proving preconditions => post conditions seems to be somewhat like a rigorous expression of what goes on in our heads when we write recursion or loops.
Although I definitely have trouble seeing the loop invariant component in proving the correctness of iterative methods. That part is not very intuitive for me. I'm having trouble finding the loop invariants that would assist in the proof. And, for that matter, don't know what I'm looking for either. Got some good tips at lecture how how to find them though.
Will have to go through lec notes and course notes extensively before the test. Gosh, what a busy week it's been, and what a busy week next week will be. For that matter, what busy months oct and nov are...
Wednesday, October 22, 2008
Grasshopper question
This question has deceptively simple constraints.
The pattern seems quite unusual, but it is not difficult to see a recursive definition for G(n) that behaves similarly to the Fibonacci sequence, with a twist. showing that what I have is indeed the recursive formula is probably is sufficient for the proof part of the question
The hard part of the question is in proving that my formula is indeed correct. I believe I know how to, with some help from a combinatorics formula.
This is a great question that I am really enjoying working through. It feels great to work through a problem like this without outside help and without getting stuck.
The pattern seems quite unusual, but it is not difficult to see a recursive definition for G(n) that behaves similarly to the Fibonacci sequence, with a twist. showing that what I have is indeed the recursive formula is probably is sufficient for the proof part of the question
The hard part of the question is in proving that my formula is indeed correct. I believe I know how to, with some help from a combinatorics formula.
This is a great question that I am really enjoying working through. It feels great to work through a problem like this without outside help and without getting stuck.
Subscribe to:
Posts (Atom)
