Today was the last day of the semester as well as test 3. It wasn't too bad; possibly Prof. Heap was taking it a bit easy on us since the final is only a week away. I spent a lot of time studying last night for it since I didn't get enough review earlier in the week since I was still finishing up projects and tests for other classes. I was glad to see no questions with the pumping lemma on it. Although I understand the idea behind it, I think I'd be shaky if I had to do a proof of it on my own.
I'm sure I've mentioned it in a previous post, but I think that this class was overly packed with tests, assignments and problem sets. Three tests was probably a bit much, but I guess it got people to attend class all the way till the last day.
Overall though I was happy with this course. Going in at the beginning I was definitely not too excited about it since I didn't enjoy CSC165. But I must admit that I enjoyed many aspect of the class and some of the material. So as the semester comes to a close, so does this blog. On to the final exam.
Friday, December 5, 2008
Week 11 and 12
Weeks 11 and 12 I'm sure were busy for everyone. As the semester draws to a close, students have assignments, essays and tests to do, and professors and TA's have stuff to mark.
Week 11 we saw a lot of NFSAs and equivalence. There was some tricky stuff to learn regarding the state invariants, and transition functions. We talked a lot about epsilon transitions, subset construction and equivalence. It was interesting to see the equivalence of the regular expressions and FSA.
Week 12 we looked at the pumping lemma. It became a useful tool to use to show that a language isn't regular. We used it in some examples; one which showed that the language of binary strings with equal number of 0's and 1's.
And finally we started to talk about the final exam and completed TA evaluations.
Week 11 we saw a lot of NFSAs and equivalence. There was some tricky stuff to learn regarding the state invariants, and transition functions. We talked a lot about epsilon transitions, subset construction and equivalence. It was interesting to see the equivalence of the regular expressions and FSA.
Week 12 we looked at the pumping lemma. It became a useful tool to use to show that a language isn't regular. We used it in some examples; one which showed that the language of binary strings with equal number of 0's and 1's.
And finally we started to talk about the final exam and completed TA evaluations.
Problem Set 6 - Problem Solving
Prove that L, the set of binary strings of odd length, equals L(((0+1)(0+1))*(0+1)).
So I started this problem by reading and understanding the problem, simple enough step. I analyzed the regular expression in my head and jotted down some binary strings which were in the language L and compared them to the claim.
Since my test cases held, I began to try to think of some cases where a string in the language L didn't hold, but couldn't find any counter-examples. Next I began to think of ways in which I could prove this. I reread through some notes and figured that proof by cases would be best here. I then divided it up into two cases; Case 1: the string has length equal to 1 and Case 2: the string has length greater than 1.
I then went on to prove these two cases separately. At the end I reanalyzed my cases, wrote out a final copy and was done!
So I started this problem by reading and understanding the problem, simple enough step. I analyzed the regular expression in my head and jotted down some binary strings which were in the language L and compared them to the claim.
Since my test cases held, I began to try to think of some cases where a string in the language L didn't hold, but couldn't find any counter-examples. Next I began to think of ways in which I could prove this. I reread through some notes and figured that proof by cases would be best here. I then divided it up into two cases; Case 1: the string has length equal to 1 and Case 2: the string has length greater than 1.
I then went on to prove these two cases separately. At the end I reanalyzed my cases, wrote out a final copy and was done!
Tuesday, November 18, 2008
Quick Thoughts on Test 2 and FSA
Got back test 2 and the recent problem set. I was generally happy with the marks which was good. As the semester is coming to an end it seems like all the work is starting to pile up.
This week we've continued to look at regular expressions and finite stat automata. The idea is that we can use regular expressions as a way to express a language. We can design our own language to with different alphabets. We looked at some examples looking at binary numbers containing even or odd number of zeros. The language can further be manipulated by applying principles such as commutativity or distributivity to the regular expression to create another regular expression.
We looked at some DFSAs where we created a machine which would take in a string and would be able to tell us whether it was a valid string by traverserving between the states. We say an example where we created a machine that accepted a binary string and would enter an accepting state for an even number of 0's. It seems the hard part is how to construct a machine for a particular collection of strings; all won't be as obvious as the binary number example we looked at. We need to make sure it can correctly judge all strings of that language and properly determine which are valid and which aren't. It seems to that we need to derive some state invariants and transition functions to create a correct machine.
Also a quick thought; I've went to the TA general help hours a couple of times and I've found them pretty helpful. I think going to them helped my understanding a lot for assignment 2 as well as test 2. I would suggest going to any students needing a bit of help!
This week we've continued to look at regular expressions and finite stat automata. The idea is that we can use regular expressions as a way to express a language. We can design our own language to with different alphabets. We looked at some examples looking at binary numbers containing even or odd number of zeros. The language can further be manipulated by applying principles such as commutativity or distributivity to the regular expression to create another regular expression.
We looked at some DFSAs where we created a machine which would take in a string and would be able to tell us whether it was a valid string by traverserving between the states. We say an example where we created a machine that accepted a binary string and would enter an accepting state for an even number of 0's. It seems the hard part is how to construct a machine for a particular collection of strings; all won't be as obvious as the binary number example we looked at. We need to make sure it can correctly judge all strings of that language and properly determine which are valid and which aren't. It seems to that we need to derive some state invariants and transition functions to create a correct machine.
Also a quick thought; I've went to the TA general help hours a couple of times and I've found them pretty helpful. I think going to them helped my understanding a lot for assignment 2 as well as test 2. I would suggest going to any students needing a bit of help!
Monday, November 10, 2008
Test 2 Thoughts and Formal Language/Regular Expressions
I was pretty happy with Test 2. So hopefully that feeling stays once I get the mark back as well. I'm just a bit worried about question 3. I'm not sure my loop invariant was correct; and didn't really use it as part of my proof like I probably should have.
Today we continued working with Formal Languages and Regular Expressions. So far things have been fairly simple; regarding the operations and definitions. Just the klene star (*) has been a tad confusing so far. We also saw an interesting example of the regular expressions in the form of a finite state machine.
Today we continued working with Formal Languages and Regular Expressions. So far things have been fairly simple; regarding the operations and definitions. Just the klene star (*) has been a tad confusing so far. We also saw an interesting example of the regular expressions in the form of a finite state machine.
Sunday, November 2, 2008
Assignment 2 and Test 2
Last week was the due date for assignment 2. I thought that assignment 2 was significantly harder than the first. I had a lot of trouble with a couple of the questions particularly the Ternary Tree one which was carried over from the first assignment. I spent a lot of time drawing up trees and trying to push out a formula with not a lot of success. Monday before the due date I went to the TA help. They helped push me in the right direction, but I'm not too confident in my answer. I'm interested in seeing the solution for it.
This coming Friday is the 2nd test for this class. I'm hoping it isn't too hard/different from the examples seen in class and in the notes. It seems like every week there is something for this class. I do like the fact that the final is worth just 35%, but I think that 3 assignments, 6 problem sets, and 3 tests is a lot of work for a half-credit course.
This coming Friday is the 2nd test for this class. I'm hoping it isn't too hard/different from the examples seen in class and in the notes. It seems like every week there is something for this class. I do like the fact that the final is worth just 35%, but I think that 3 assignments, 6 problem sets, and 3 tests is a lot of work for a half-credit course.
Saturday, October 25, 2008
Midterms/Program Correctness
Finally just finished up all my midterms; was quite the busy week since I had a number of assignments thrown in there as well. And the cycles of tests and assignments begins again before finals.
Just finished week 7. We looked at program correctness; preconditions/post-conditions. Monday we had a guest lecturer. Nick from UTSC. I thought he was great. He was very friendly, funny and knowledgeable. I actually felt bad for him, he was up making some jokes, trying to engage the class but few people seemed impressed. Monday mornings perhaps?
The rest of the week we worked through some binary search examples and greatest common divisors; which were more proofs by induction!
Problem Set 4 and Assignment 2 are due Monday. Still have to finish up both of them. I started assignment 2 earlier this week; but still have to do a bulk of the work. I mostly read through the questions and jotted down some thoughts mostly to get my thinking process going.
Just finished week 7. We looked at program correctness; preconditions/post-conditions. Monday we had a guest lecturer. Nick from UTSC. I thought he was great. He was very friendly, funny and knowledgeable. I actually felt bad for him, he was up making some jokes, trying to engage the class but few people seemed impressed. Monday mornings perhaps?
The rest of the week we worked through some binary search examples and greatest common divisors; which were more proofs by induction!
Problem Set 4 and Assignment 2 are due Monday. Still have to finish up both of them. I started assignment 2 earlier this week; but still have to do a bulk of the work. I mostly read through the questions and jotted down some thoughts mostly to get my thinking process going.
Saturday, October 11, 2008
Test 1 Thoughts
Some quick thoughts on Test #1: 3 questions, 8 marks each. The first one was a binomial expression which I attempted to solve via simple induction. I'm fairly sure this is the right flavour to use for this question; except I got stuck on the induction step and couldn't figure out how to show P(n) --> P(n+1). I probably spent a little too much time on this question.
Question 2, with the Fibonacci sequence. I used complete induction. I don't totally remember the question. In my head I think i'm getting it confused with #1 and mixing the problems. I think it was F(n)^2 > 2n? Or something of that nature. Using complete induction, my proof went something like this; I showed the F(n) is the sum of F(n-1) and F(n-2) [by definition], which are both greater than 2(n-1) and 2(n-2) respectively [by IH]. Since F(n)'s predecors were both greater than 2n it should follow F(n) also.
Question 3, I'm drawing a blank on what the question was. I do remember running out of time since I spent a little much time thinking about #1's induction step. I think I started out using simple induction and then realized I should've used complete induction. I ran out of time to fix this and to finish the proof, but I had a structure of a proof and I put down some ideas of how to solve it.
Overall I felt prepared for the test, I just ran into a the problem of not being able to see the induction step for #1 which cost me some time. I always feel a little rushed when writting a 50min test. But I can't complain, everyone else is in the same boat and a few people seemed to have finished and left the room with some time to spare.
Question 2, with the Fibonacci sequence. I used complete induction. I don't totally remember the question. In my head I think i'm getting it confused with #1 and mixing the problems. I think it was F(n)^2 > 2n? Or something of that nature. Using complete induction, my proof went something like this; I showed the F(n) is the sum of F(n-1) and F(n-2) [by definition], which are both greater than 2(n-1) and 2(n-2) respectively [by IH]. Since F(n)'s predecors were both greater than 2n it should follow F(n) also.
Question 3, I'm drawing a blank on what the question was. I do remember running out of time since I spent a little much time thinking about #1's induction step. I think I started out using simple induction and then realized I should've used complete induction. I ran out of time to fix this and to finish the proof, but I had a structure of a proof and I put down some ideas of how to solve it.
Overall I felt prepared for the test, I just ran into a the problem of not being able to see the induction step for #1 which cost me some time. I always feel a little rushed when writting a 50min test. But I can't complain, everyone else is in the same boat and a few people seemed to have finished and left the room with some time to spare.
Wednesday, October 8, 2008
Assignment 1 Marks and Test Prep
Just got back the marks and feedback for A1. I was fairly pleased with my marks. Only question I really lost a lot of marks was 3b, since I wasn't too sure which part from 3a to use. But all in all I'm pleased with how things went.
Seems like A1 was due yesterday and now midterms are coming for all my courses. I'm not too worried for Friday. I've been keeping up with all the readings and lecture material so I should be fine. Just going to go over some exercises and through the slides. Time for some reading!
Seems like A1 was due yesterday and now midterms are coming for all my courses. I'm not too worried for Friday. I've been keeping up with all the readings and lecture material so I should be fine. Just going to go over some exercises and through the slides. Time for some reading!
Monday, September 29, 2008
PSet 2 and Assignment 1
Just finished a really busy weekend, had to finish writing up the problem set for Friday. The problem set wasn't bad. Took a little bit of scratch work to come up with k for the postage stamps. Followed by a proof using complete induction.
For part b) to prove that k is an impossible postage to create with 5-cent and 11-cent stamps was fairly simple too. The question gave a little hint that induction wasn't the way to go so I used a proof by contradiction. It seems the sample solution was a lot less formal in proving this but none the less arrives at the same conclusion.
Assignment 1 was definitely more challenging than the problem sets. I found myself thinking about the problems a lot more than for the problem sets. Number 3; the golden ratio definitely had me scratching my head for a big. Even after reading up on it a bit, I was still pretty stumped. I came up with a solution that associated the principle of well ordering but I'm not sure if I was 'hitting the nail on the head'. As for part 3b, I was just as baffled but of course took a shot as trying to prove it while using part a. I guess I will just have to wait until the sample solution comes out or when I get some feedback on my submission.
Oh and I mistakenly hand-wrote my assignment instead of typing it. I felt a bit dumb not knowing that it had to be typed; while everyone else in the lecture seemed to have typed theirs. In my defense no where on the assignment does it say that it must be typed. Only by looking at a specific post on the bulletin board by Prof. Heap does it say it must typed. Luckily the assignment wasn't due for another 11 hours and I had plenty of time to go type up my answers since all the hard work was already done.
For part b) to prove that k is an impossible postage to create with 5-cent and 11-cent stamps was fairly simple too. The question gave a little hint that induction wasn't the way to go so I used a proof by contradiction. It seems the sample solution was a lot less formal in proving this but none the less arrives at the same conclusion.
Assignment 1 was definitely more challenging than the problem sets. I found myself thinking about the problems a lot more than for the problem sets. Number 3; the golden ratio definitely had me scratching my head for a big. Even after reading up on it a bit, I was still pretty stumped. I came up with a solution that associated the principle of well ordering but I'm not sure if I was 'hitting the nail on the head'. As for part 3b, I was just as baffled but of course took a shot as trying to prove it while using part a. I guess I will just have to wait until the sample solution comes out or when I get some feedback on my submission.
Oh and I mistakenly hand-wrote my assignment instead of typing it. I felt a bit dumb not knowing that it had to be typed; while everyone else in the lecture seemed to have typed theirs. In my defense no where on the assignment does it say that it must be typed. Only by looking at a specific post on the bulletin board by Prof. Heap does it say it must typed. Luckily the assignment wasn't due for another 11 hours and I had plenty of time to go type up my answers since all the hard work was already done.
Sunday, September 21, 2008
2nd Week
Just finished up the 2nd week of classes and the first problem set. The problem set wasn't bad at all. It was very similar to the lecture which was good. It let's you know if you're really understanding the lecture material. It's easy to come to class and watch proof be written up and follow along; but it's a bit different when you have to do all the thinking and writing.
I'm sure glad the problem sets aren't like the problem sets in MAT137!
I've started up on problem set 2 but have yet to do much work on assignment 1. I'm kind of on the fence of how to manage my time between these two assignments as well as my other courses. Either way it all needs to get done. Hopefully I can finish up the problem set by tomorrow and get moving on assignment 1.
I'm sure glad the problem sets aren't like the problem sets in MAT137!
I've started up on problem set 2 but have yet to do much work on assignment 1. I'm kind of on the fence of how to manage my time between these two assignments as well as my other courses. Either way it all needs to get done. Hopefully I can finish up the problem set by tomorrow and get moving on assignment 1.
Monday, September 15, 2008
First Post
Just starting the second week of the course. Things are already starting to pick up in terms of course work.
The first week covered induction proofs. Not too bad, similar to CSC165 so far. I don't feel too bad about the material to this point; but am afraid of what the rest of the course holds.
The first assignment and first problem sets have both been posted. I've downloaded both but haven't had a chance to look at them yet. I'm going to get on it tonight. Hopefully they won't be too bad and similar to lecture material.
Not much else to say at this point. Will be updating soon.
The first week covered induction proofs. Not too bad, similar to CSC165 so far. I don't feel too bad about the material to this point; but am afraid of what the rest of the course holds.
The first assignment and first problem sets have both been posted. I've downloaded both but haven't had a chance to look at them yet. I'm going to get on it tonight. Hopefully they won't be too bad and similar to lecture material.
Not much else to say at this point. Will be updating soon.
Subscribe to:
Posts (Atom)