We started with a proof that was owed from the week before. Professor Heap proved the correctness of the DFSA we saw last week (accepting binary strings that are multiples of three). The proof used structural induction on string x.
We continued the lecture with NFSAs. We saw that every regular expression has an FSA (if we allow empty transitions) and that every NFSA defines a DFSA.
We also looked at the cartesian product method (if you paid attention to that then Problem # 4 on Assignment # 3 was easy to do).
Assignment # 3, the last assignment for this course was due Monay, Nov 24 (so it was due yesterday as I am posting this on Tuesday, Nov 25). I found this HW the easiest of the three. The hardest problem for me was Problem # 2, where we had several regular expressions and we had to prove whether or not the regular expressions denoted a language L (L was the set of all binary strings with an even number of 1s). Most of the times I can see if a regex denotes a language with a certain property but I have a hard time proving it. I guess that's always the case. I am getting better though because Problem Set # 6 dealt with this thing and Problem # 2 of Assignment # 2 and we saw an example of this in class. Practice makes perfect.
Tuesday, November 25, 2008
Thursday, November 13, 2008
Week 10 - Nov 13, 2008
We got Test 2 back today and I got exactly what I thought I would get. Not bad but not as good as Test 1. The important thing is that I know what my mistakes are and I also know how to avoid them. That's all I have to say about Test 2.
In the lecture this week we saw DFSA (Deterministic Finite State Automata). Drawing states and arrows seems fun!
I really liked that fact that you can represent a language using a DFSA quite easily. We saw how hard it was to express (L1 \intersection L2) using a regular expression but we came up with the DFSA for it fairly easily. L1 was the language that contained all binary strings with an even number of zeroes and L2 the language that contained all binary strings with an odd number of ones.
We did not see a proof of the correctness of the DFSA but it's something we will see next week. The professor felt that it was too late for that proof and that it was better suited for the first hour of next week's lecture. Couldn't agree more!
Tuesday, November 11, 2008
Week 9 - Thursday Nov 07, 2008
Test 2!
We had test #2 this week and I found it very fair. There were three problems all of them not hard. Professor Heap really knows how to write fair tests. It's as simple as that.
Of course, I ran out of time and didn't have time to finish Problem 3 but that's pretty much the case with all of my tests. I really need to learn how to: 1) manage my time during a test more efficiently and 2) leave out the extra details from my answers.
Other than the test, we started on Chapter 7 that deals with Languages, Regular Expressions and FSAs. Problem Set #5 is due this week and it has to do with the new material. I read the notes and I find the subject very interesting but a little bit confusing too. We will see how things will evolve. I am looking forward to the next lecture.
We had test #2 this week and I found it very fair. There were three problems all of them not hard. Professor Heap really knows how to write fair tests. It's as simple as that.
Of course, I ran out of time and didn't have time to finish Problem 3 but that's pretty much the case with all of my tests. I really need to learn how to: 1) manage my time during a test more efficiently and 2) leave out the extra details from my answers.
Other than the test, we started on Chapter 7 that deals with Languages, Regular Expressions and FSAs. Problem Set #5 is due this week and it has to do with the new material. I read the notes and I find the subject very interesting but a little bit confusing too. We will see how things will evolve. I am looking forward to the next lecture.
Tuesday, November 4, 2008
Week 8 - Thursday Oct 30, 2008
This week we continued looking at the correctness of algorithms. We moved from recursive correctness to iterative correctness. I don't have much to write today. I would just like to say that I found the iterative case much harder than the recursive case. I don't know why the idea is very similar. Just go through the code line by line and prove it works, prove that it does what we want it to do.
Test 2 is on Thursday and I am a little worried because I do not feel well prepared. I still have a day to study but with three other assignments due in the next two days I am trying to juggle everything and so far I seem to be terrible at juggling...
Monday, October 27, 2008
Week 7 - Thursday Oct 23, 2008
Week 7 is gone. Time flies, that's for sure. I survived the worst week of this semester so I am happy about that.
The deadline of Assignment 2 was approaching and I was glad I solved the ternary trees question a long time ago. It seemed that it was the hardest problem and it took everybody quite some time to figure it out.
In the lecture we saw the correctness of algorithms. We looked at the binary search algorithm and we proved it's correct and we did the same with Euclid's algorithm for the gcd.
Test 2 is coming up (in about a week) so I need to review the material.
Sunday, October 19, 2008
Week 6 - Thursday Oct 16, 2008
Week 6 is already gone. Time really flies and that's not a bad thing as this week, i.e week 7, I have 4 midterms in three days, I have and three assignments.Too much work!
Anyways, the lecture was shorter this week because the morning section missed the Monday lecture, it was Thanksgiving day. No complaints there, it was nice to finish at 20:00 instead of 21:00.
We talked about two things:
1) The time complexity of merge sort (n*log(n)).
2) The master theorem.
The master theorem basically gives the time complexity for divide-and-conquer algorithms. If you can write the time complexity of an algorithm in a specific recursive way then you can use the master theorem to get a bound on the time complexity of the algorithm.
We also got Test 1 back and handed in Problem Set 3. Problem Set 3 was not hard, you just needed to follow an example we saw in class and then you could get the closed form that was needed. I learned that a finite sum is not considered closed form if it grows in n. I was wrong to think that infinite sums are not considered closed-form but finite are.
Test 1 went OK. I made a stupid mistake that I now realize I was doing often when I was using the principle of complete induction. Need to be more careful from now on. Other than that, I was happy with my test.
I think I am writing just to avoid studying for CSC260 so I better stop here.
Anyways, the lecture was shorter this week because the morning section missed the Monday lecture, it was Thanksgiving day. No complaints there, it was nice to finish at 20:00 instead of 21:00.
We talked about two things:
1) The time complexity of merge sort (n*log(n)).
2) The master theorem.
The master theorem basically gives the time complexity for divide-and-conquer algorithms. If you can write the time complexity of an algorithm in a specific recursive way then you can use the master theorem to get a bound on the time complexity of the algorithm.
We also got Test 1 back and handed in Problem Set 3. Problem Set 3 was not hard, you just needed to follow an example we saw in class and then you could get the closed form that was needed. I learned that a finite sum is not considered closed form if it grows in n. I was wrong to think that infinite sums are not considered closed-form but finite are.
Test 1 went OK. I made a stupid mistake that I now realize I was doing often when I was using the principle of complete induction. Need to be more careful from now on. Other than that, I was happy with my test.
I think I am writing just to avoid studying for CSC260 so I better stop here.
Friday, October 10, 2008
Week 5 - Thursday Oct 09, 2008
Attempt #2
Firefox crashed on me and took my post with it to the realms of the unknown. This re-post is going to be significantly shorter than the previous one because I am still mad at Firefox...
Week 5 ended and Test 1 is a thing of the past. This week we looked at structural induction, a flavor of induction that I found both more challenging and more interesting. We also looked at more recursive formulas and their closed forms. Specifically we saw how the Fibonacci sequence is related to the golden ratio. Interesting stuff I tell you! It makes me want to see Pi again...
As for test 1, I found it fair. I finished just on time but it was mainly because of the way I function which is not the optimal way a human being should function.
I solved one of the questions using combinatorics and I am sure it was because of the ternary trees problem on the Assignment. For a couple of weeks now all I do is count stuff and make sure I subtract the duplicates! I think I did well, I will see if the TAs agree with me sometime soon.
Have a great weekend and happy thanksgiving to all!
Firefox crashed on me and took my post with it to the realms of the unknown. This re-post is going to be significantly shorter than the previous one because I am still mad at Firefox...
Week 5 ended and Test 1 is a thing of the past. This week we looked at structural induction, a flavor of induction that I found both more challenging and more interesting. We also looked at more recursive formulas and their closed forms. Specifically we saw how the Fibonacci sequence is related to the golden ratio. Interesting stuff I tell you! It makes me want to see Pi again...
As for test 1, I found it fair. I finished just on time but it was mainly because of the way I function which is not the optimal way a human being should function.
I solved one of the questions using combinatorics and I am sure it was because of the ternary trees problem on the Assignment. For a couple of weeks now all I do is count stuff and make sure I subtract the duplicates! I think I did well, I will see if the TAs agree with me sometime soon.
Have a great weekend and happy thanksgiving to all!
Subscribe to:
Posts (Atom)