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.
Tuesday, October 21, 2008
Test 1
Test 1 didn't go as well as I expected.
Even though i had the right induction insights, I had lots of mistakes in the write up. With one question completely missing the base cases. I also got marks off for not stating the conclusion... I thought the conclusion was implicitly obvious if we stated P(n) clearly... The course notes are like this too iirc.
The test ended with me not having enough time to finish write ups.
I think I spent too much time thinking of the insight, and had to rush through the write up. I Need more practice.
Had to miss class this Monday to complete a music essay. Apparently I missed the lecture about preconditions, and PS4 is on preconditions. I have no idea what it's about, and lecture notes aren't posted yet. so I must attend the evening lecture this week.
Even though i had the right induction insights, I had lots of mistakes in the write up. With one question completely missing the base cases. I also got marks off for not stating the conclusion... I thought the conclusion was implicitly obvious if we stated P(n) clearly... The course notes are like this too iirc.
The test ended with me not having enough time to finish write ups.
I think I spent too much time thinking of the insight, and had to rush through the write up. I Need more practice.
Had to miss class this Monday to complete a music essay. Apparently I missed the lecture about preconditions, and PS4 is on preconditions. I have no idea what it's about, and lecture notes aren't posted yet. so I must attend the evening lecture this week.
Friday, October 10, 2008
Unwinding
My blog was apparently flagged by a spam filtering system implemented by blogger.com... They say the system is inherently fuzzy... I wonder if it uses fuzzy logic and whether I will learn about it in later CSC theory courses.
I really like the way Danny first discussed and showed how the sum of the Fibonacci sequence up to n is equal to F(n+2) - 1. Then in the next lecture, showed us how to unwind T(n) of zpf(n), where the same sequence of Fibonacci sums showed up. The way he structures the course is really helping me learn more than I would have otherwise.
I am still feeling unclear about how to get from unwinding to a closed form, how and if unwinding helps in proofs. I was feeling the same about PSI, PCI, PWO as well, but now I feel quite comfortable with them. I'm sure with a bit of time and practice I will feel comfortable and clear about it
Written the first term test today. It was not too bad, but I wish I had time to finish the subset question... I believe I was on the right track . If I had 10 more minutes I might have finished a correct proof. I suppose I spent more time than I should have on the other questions, which are pretty straightforward.
In response to Danny's comment on my test structure concern post: I thought the test was structured quite well and fairly. Although personally I felt that I spent more time looking for insight than I'd have been comfortable with, and possibly more time than Danny intended. Not so used to doing the problems with such a short time constraint. All the practice I had in a1 and problem sets have days-long time constraints. I will be keeping that in mind while I do problems from now on, and perhaps not taking such a leisurely pace.
I really like the way Danny first discussed and showed how the sum of the Fibonacci sequence up to n is equal to F(n+2) - 1. Then in the next lecture, showed us how to unwind T(n) of zpf(n), where the same sequence of Fibonacci sums showed up. The way he structures the course is really helping me learn more than I would have otherwise.
I am still feeling unclear about how to get from unwinding to a closed form, how and if unwinding helps in proofs. I was feeling the same about PSI, PCI, PWO as well, but now I feel quite comfortable with them. I'm sure with a bit of time and practice I will feel comfortable and clear about it
Written the first term test today. It was not too bad, but I wish I had time to finish the subset question... I believe I was on the right track . If I had 10 more minutes I might have finished a correct proof. I suppose I spent more time than I should have on the other questions, which are pretty straightforward.
In response to Danny's comment on my test structure concern post: I thought the test was structured quite well and fairly. Although personally I felt that I spent more time looking for insight than I'd have been comfortable with, and possibly more time than Danny intended. Not so used to doing the problems with such a short time constraint. All the practice I had in a1 and problem sets have days-long time constraints. I will be keeping that in mind while I do problems from now on, and perhaps not taking such a leisurely pace.
Tuesday, September 30, 2008
Convincing Myself, and some Fundamentals
After finishing Q3 of a1, I had lingering thoughts about a certain part of the proof - I wasn't fully convinced that it works. I kept wondering if I needed induction to justify the implication, or if doing that is unnecessary and what I have is sufficient.
A dose of the very helpful Danny's Office Hour gave me the answer.
So, I believe the lesson today is that if I'm not fully convinced myself, I need to do more work on justifying the part of concern.
Danny also pointed out some problems with "big jumps" and generality issues. I think I had an idea of what he meant, but wasn't entirely sure.
As I worked on adding the induction proof, I encountered very similar generality issues, having to do with fundamental definitions of natural numbers, integers. It was then that I realized what Danny meant, and understood the importance of these fundamental definitions that I never really internalized.
So, the second lesson today is, even if I feel like I'm convinced, it may not be due to correct understanding, and so it's a good idea to visit Danny or a TA to check my works.
A dose of the very helpful Danny's Office Hour gave me the answer.
So, I believe the lesson today is that if I'm not fully convinced myself, I need to do more work on justifying the part of concern.
Danny also pointed out some problems with "big jumps" and generality issues. I think I had an idea of what he meant, but wasn't entirely sure.
As I worked on adding the induction proof, I encountered very similar generality issues, having to do with fundamental definitions of natural numbers, integers. It was then that I realized what Danny meant, and understood the importance of these fundamental definitions that I never really internalized.
So, the second lesson today is, even if I feel like I'm convinced, it may not be due to correct understanding, and so it's a good idea to visit Danny or a TA to check my works.
Sunday, September 28, 2008
a1 and Renewed Concern
Since the beginning of the term, I've gained a deeper understanding of Zen and Zen practice. Now, I should replace the word "unease" with the more accurately representative word "concern".
I really liked the way a1 questions are structured. It was challenging, but not overly so. Q1 and Q2 challenged me in putting ideas in formal language. Q3 is a great question, I love the structure and the way it guides into an elegant proof.
At this point after finishing A1 (minus Q4), I feel a sense of accomplishment, and a new level of acuteness in my logical sense.
The honeymoon feeling is quickly over, such is the norm during the school-year. I'm not even sure I understand the definition of a ternary tree in a1Q4 yet, and recursion wasn't easy for me in 148 when I took it several years ago. But, that was the immature and irresponsible me several years ago, with a terrible work ethic.
I'm also slightly concerned about the structure of tests in 236. Sometimes insights to proofs come in seconds, sometimes several minutes, and sometimes sleeping on it works wonders. It all seems rather arbitrary. Will the test structure be able to accurately represent a student's level of understanding?
I really liked the way a1 questions are structured. It was challenging, but not overly so. Q1 and Q2 challenged me in putting ideas in formal language. Q3 is a great question, I love the structure and the way it guides into an elegant proof.
At this point after finishing A1 (minus Q4), I feel a sense of accomplishment, and a new level of acuteness in my logical sense.
The honeymoon feeling is quickly over, such is the norm during the school-year. I'm not even sure I understand the definition of a ternary tree in a1Q4 yet, and recursion wasn't easy for me in 148 when I took it several years ago. But, that was the immature and irresponsible me several years ago, with a terrible work ethic.
I'm also slightly concerned about the structure of tests in 236. Sometimes insights to proofs come in seconds, sometimes several minutes, and sometimes sleeping on it works wonders. It all seems rather arbitrary. Will the test structure be able to accurately represent a student's level of understanding?
thoughts after first 2 weeks
I began the course with some uneasiness: I was never good at theory and proofs, so I believed that I preferred programming, rather than theory. It's also been a few years since I took csc165 and mat137, so I have not been doing rigorous proofs for a while.
We started with simple induction. In mat137 I was never really convinced that induction works. I just followed the general format without digging really deeply. So I didn't really understanding it fully, and naturally I didn't really believe that it works.
Somehow, after the way it was explained in 236, it just clicked. I think the "training" I had before, plus the way it is explained in lecture just made it click. This understanding made me feel really good. The way Danny explained the intuitive method of partitioning in the induction step was also very clear and very helpful.
Surprisingly, I actually enjoyed the process of working through problem set 1. It really solidified my understanding of PSI, and I got a pretty good grade for it :)
I have to say, after working through PS1, PS2, A1 (I've finished them all), I'm really starting to like theory.
We started with simple induction. In mat137 I was never really convinced that induction works. I just followed the general format without digging really deeply. So I didn't really understanding it fully, and naturally I didn't really believe that it works.
Somehow, after the way it was explained in 236, it just clicked. I think the "training" I had before, plus the way it is explained in lecture just made it click. This understanding made me feel really good. The way Danny explained the intuitive method of partitioning in the induction step was also very clear and very helpful.
Surprisingly, I actually enjoyed the process of working through problem set 1. It really solidified my understanding of PSI, and I got a pretty good grade for it :)
I have to say, after working through PS1, PS2, A1 (I've finished them all), I'm really starting to like theory.
Subscribe to:
Posts (Atom)
