vivi's CSC236 SLoG

Continuing formal languages, we looked at equivalent regular expressions and then finite state automata. Again, I've looked at finite state machines before while studying regular expressions last year so what Prof. Heap was describing in class was very straightforward. The only new part would be describing and essentially "drawing" the machine in words. Once it's explained, it's pretty easy to write out and understand though. I find it the easiest to draw first and then put it into words and definitions. I wonder how we're going prove that these DFSA's actually represent the regular expression?

So I finally decided to try printing out slides for once, and as expected, it beats copying down notes by a landslide. 

Midterms always turn out to be better than I had thought. Maybe with the exception of Stats...

Iterative program correctness requires a bit more work than recursive correctness. Although a bit trickier, I still prefer this over recurrences and time complexity. The lectures this week were pretty interesting. I am finding myself having trouble determining loop invariants, however. I tried reading the book, and even it says that determining these things just requires practice and thinking. There is no mechanical way of finding it unfortunately :( Also, I am not looking forward to proving iterative correctness on tests. After the double loop example we did in class, I can easily see myself rushing to write out a proof as there are so many steps. Hmm. I can't believe everything we've been doing so far involves induction. I knew we were going to work with induction, but I didn't realize that pretty much our entire course is based on it. 

Unfortunately, I missed the Monday lecture with the guest lecturer because I was frantically studying for another midterm. Anyway, we looked at program correctness this week. I think compared to the material we were covering the last couple of weeks, I find this a lot easier to take in and understand. There is something about time complexity that I just despise. Program correctness, on the other hand, feels more straightforward. I just need to follow the code and check if the postcondition is satisfied or not given the precondition. 

It has been a very stressful and busy midterm period. Although it's still not quite over yet for me, I am going to take some time and try to catch up on my slogging.

As I've mentioned before, I missed Week 5's lectures, and I am still having trouble understanding how to deal with closed form expressions. I had no trouble with Problem Set 3, but the notes on developing a closed form expression for the Fibonacci function haven't exactly 'clicked' for me. Perhaps the midterm stress is the cause, but I do have to admit that I haven't really sat down and investigated it thoroughly.

We looked at the complexity of merge-sort and the Mast Theorem last week. I really need to print out the slides and write on them instead. There were many slides of just text last week, and I tried to write them all down. In the end, I had "see slides online" written after trying to copy everything down, and I didn't get to hear anything Prof. Heap said as I was too busy writing. It's probably better that I print the notes, read them before lecture, and then just follow along the lecture. It's so simple, yet I feel that I need to continue writing up my notes since that is how all my notes for this class have been so far. Anyway, we proved that the time complexity of merge-sort was nlogn. We actually took the code and came up with a time complexity of which we proved by building on several smaller proofs. Or.. I think that's what we did. To be honest, I am somewhat lost at the moment in the course. As things die down, I think I will be able to make sense of everything again. Hopefully.

Well, besides catching up on the course, there's also another problem set and assignment due next Monday. I've looked at the problem set, and it should be somewhat similar to what we did in Wednesday's lecture. I'm having a bit of trouble wording what I want to say though. In fact, throughout this course, I seem to have some problems with the way I present anything. I'm going to have to work on that. The assignment.. won't be too bad, I hope.