Correctness

We started proving the correctness of recursive algorithms this week. I'm starting to realize how powerful induction is. Almost anything can be expressed in an "inductive" way.

Sometimes though it can be a bit tricky to find out how to break it down to that form. Danny showed us this in class when proving the greatest common factor algorithm. Simplifying the two numbers into one by specially relating the two (for all m, for all n > m) helped turn it into a simple one variable induction process. This was a new way of seeing it for me.

Danny mentioned that recursive programs are easier to prove correct than iterative programs. This was at first kind of against my intuition since I have a better picture of what going on in an iterative program (recursive programs that branch off into stacks of trees and whatnot are especially confusing to follow along). However, now it seems this is actually true. For correctness we don't need to follow through with the whole recursion. Instead we just need to worry about the top most layer, which is really simple. For iterative programs, however, I'm guessing the complexity comes from the fact that we actually need to worry about ALL the iterations not just one of them.
Things will get clearer next week.

Post Term Test blues

I had my term test on Friday and I am disappointed with the outcome. There were three questions in total and the first two seemed simple enough. The last one however, threw me in for a loop for a good 20 minutes or so. The worst part is that, with less than a minute left to go I figured out it was actually the simplest one. I spent most of the time attacking it with induction but as it turned out I just had to know how to count! Ironic how I always preach "think outside the box" to everyone in any situation with the slightest relevance to it. Oh well, nobody's fault but mine (heh pointless thing to say but I do love Led Zeppelin). Hopefully the TA can decrypt my scribbled attempts and sympathize a little bit.

The test did it's job though. I was brimming with overconfidence after the Assignment 1 marks were handed back and I slacked off during the week before the test.

Now problem set 3 is due and my week is absolute HELL. I have at least one piece of work due for each of my courses. All on Friday (except one). Need to get cracking. Not to mention I have some catching up to do on program correctness since I missed the first two lectures last week. I will post again after this hellish week is over.

First Impression

So this is my first blog. I'm kind of late in starting it but I think I needed this time to gain some experience with the class and reflect back on it.

Danny's lectures are quite informative and fun to be in. I really enjoy his practice of sparing 10 minutes of class time every now and then to let us go think about a problem and then discuss the solution with the rest of the class. I find this particularly useful since it instills a sense of competition among us students to come up with a better and more efficient solution quickly. I've never treated assignments in this way. Those were always (and still are) just a work session, no matter what the topic. It also gives me a better idea of what he expects from us better than a handout or rubric of some sort would.

Another thing I really like is Danny's availability on the boards. I couldn't make it to the tutorials for Assignment 1 but it wasn't a problem at all since all my questions were answered by Danny or some of the other students on the board.

All that said however, I have to say I found the first three weeks a bit slow. I thought a bit too much time was spent on induction than necessary. This sentiment is probably not be shared by everyone though. I should probably read ahead on the upcoming topics but I never manage to get around to it. I'm hoping the pace picks up a bit more.

Anyhoo that's enough rambling for now. I'll post again after another week of classes.