Week 11 - Thursday Nov 20, 2008

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.

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!

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.

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...