Week 7: Program Correctness

What I've learned this week is that proving the correctness of a program can be a long and enduring task. I did not expect either of correctness proofs we did in class to be anywhere near as long as they were. The content of the proofs were not complicated in nature but having to describe what happens at every line of the code in different cases seems like it could become tiresome. What happens if we start having to prove the correctness of a program that's 40 or 50 lines long instead of the 5 or 10 lines we do in class? I'm pretty sure Danny won't make us experience that unless the program was loaded with if/else statements so it'd be, in essence, a 5 or 10 line code. Well, here's hoping.

I know I usually write a little bit more than I'm writing this week but, after having written 3 midterms last week and having not started 2 or 3 assignments that are due next week, I need all the time I can get.

Week 6: The Master Theorem

Thanks to Thanksgiving, we only had one less lecture this week. The topics we ended up covering were the time complexity of merge sort, monotonicity, and the master theorem. The proof of the time complexity of merge sort was a little more dense than I expected it to be but, looking back at it, it was pretty straight forward. First you prove a conjecture about a couple of points (in our case, 2^k for all natural numbers k) and then use the principle of monotonicity to solve for everything between those points.

To me, proving monotonicity doesn't seem to be any different than proving that a given function is always increasing. Before Danny gave us the definition of monotonicity that we were going to use in a proof, I expected that we were just going to strive to show that T(n) always existed and was well defined for any value of n. I guess proving that T(n) is always increasing also does this while giving us another helpful fact (that T(n) is an increasing function) at the same time.

The master theorem was revealed to us on Friday morning and it was interesting to say the least. I wouldn't mind seeing a proof for it (though I doubt I'll be able to understand the whole thing and I expect it's probably one of the longest proofs I've ever seen) because I wouldn't know where to start proving something like that. It seems to be very useful but I'm sure we'll see just how useful it is in the coming weeks.

Week 5: The Test

The term is rolling right along and we are now entering the midterm zone of the schedule. Over the next 3 weeks, I will be writing midterms in every single one of my courses. Some will be easy, others won't. But I just have to face them one by one and hope for the best.

The first of the midterms was the CSC236 midterm. In my opinion, it wasn't too bad. It was very fair and I thought it did a good job of testing the content of the first four weeks. So kudos to Danny for being able to merge 4 weeks of material into 3 questions. The one thing I didn't see there was the principle of well-ordering. Of the three "flavours" of induction, the PWO was the one that I was the least comfortable with. So, I guess that may have been a blessing in disguise.

The questions weren't very difficult in nature. I did not see all of the proofs right away (I actually don't think I saw any of the proofs right away) but after a little scratch work, the answer just appeared on my page. Hopefully that translates into success in terms of a good grade.

Week 4: Recursion

This week was all about the return of recursion. I honestly don't mind recursion. It's just another way to solve different types of problems. When I'm working on problems involving recursion, I like to try to trace the entire sequence in my head or on paper (well at least the beginning of the sequence) before I even start the problem. Occasionally, for complex situations, the recursion is hard to follow but I find that, most of the time, a simple (almost trivial) solution exists.

However, when we were working on the first exercise involving the Fibonacci sequence (where we had to determine what the sum of all Fib numbers from F(0) to F(n) was), I'll admit that I really did not see the solution. In my scratch work, I just tried to make a list of the sums from 0 to n for a few small values of n (ie. the sum for n = 1 is F(0) + F(1) = 0 + 1 = 1). That did not seem to lead me anywhere. Even after Prof. Heap drew up a table to record the values on the tablet, I really could not see any type of relation between F(n) and the sum of F(n) from 0 to n. When the relationship was finally revealed (where the sum of F(n) from 0 to n equals F(n+2) - 1), I felt like slapping my forehead because I was looking for a complicated solution where there was none. Sometimes, it hurts to overthink things.

Assignment 1 was due last Monday and I don't think I did too badly on it. The first question involving the sum of the angles in a polygon of n vertices was pretty straight forward. Divide a polygon of n+1 vertices into a triangle and a polygon of n vertices and apply the induction hypothesis. That took all of 5 minutes. Questions 2 and 3 took me a bit more time though. Especially trying to determine some type of recursive structure for the menus in question 2. Once again, I was overthinking the problem and the simple answer just passed me by. Hopefully I'll be able to kick the habit before the test. Question 3 didn't take as long. What confused me in the beginning was how to apply the principle of well-ordering to a question that involved no sets. I actually determined the answer to this question while lying awake in my bed early Saturday morning. It was one of those "Eureka!" moments. I'm hoping I'll be able to conjure up another one of those moments if I get stuck on the midterm next week.