Concerning Correctness

Well, we've been handling correctness lately. It's always been kind of neat to me, representing sort of a meshing and intersection of the worlds of purely theoretical and logical thought with normal code. At first, I still couldn't really appreciate the necessity of proving the correctness of code, but over the last little while I've come to realize that it generally makes the bizarre cases something should be handling a lot more apparent just by writing it out in the context of a proof, as opposed to some IDE. In any case, I've found it generally not too rough, though I have had a bit of trouble rationalizing the need for loop invariants to myself, when it seems they're usually something like n is always a natural number, which *seems* self-evident, but I imagine it's necessary when trying to prove more complicated code.

Considering Complexity

I hated it in CSC165, and I still hate it here. I understand that the time complexity of an algorithm is one of the most important things in computer science for obvious reasons, but I still have trouble with it. In any case, I've been reading my old CSC165 notes over and over again and ditto the course notes, along with a lot of poring over the relevant parts of the course notes. I'll have this in hand eventually, and if not, well at least it seems to be much less a focus of the course than in CSC165.

Midterm Madness

Well, the midterm was this morning, and it didn't go too badly I think. The first question about the Fibonacci sequence was a breeze, almost suspiciously so, but unless I've really gotten bad at reading trick questions then that was fine. The second question, I realized 15 minutes after the test, I pulled some real bull algebra on, so I know I screwed that up, but at least the structure is there, so here's hoping for part marks.

The third question about sets was something more interesting! I stared at it for a good 15 minutes or so, having gotten as far as writing down that all sets have 2^n subsets and that each following set's subsets were those of the previous + subsets containing the element n. With two minutes left on the clock, I had a revelation (though it might have been wrong, I felt pretty good writing it down and remain confident it was a valid proof). By complete induction and partitioning S into S_1 and S_2, where S_1 is S less all the subsets containing {n}, and S_2 is S less all the subsets without {n}, you get two subsets of equal size, and better yet, you know S_1 is just the set of subsets of S:{1,..,n-1} and thus by the I.H. has 3 * 2^n-3 subsets. S_2 being the same size means it will have the same number of valid subsets, so the total will end up being 3*2^n-3 + 3*2^n-3 = 3*(2^n-3 + 2^n-3) = 3*(2^n-2)

Exactly what was needed. That was a fun proof.

I still feel pretty stupid about the algebra in question 2 though, because for some idiotic reason I wrote down 3^n+1 = 3^n + 3^n instead of 3^n + 3^n + 3^n or 3*3^n. Hopefully there'll be some mercy, because I think I did end up pseudo-legitimately showing that 3^n + 3^n > 2*(n+1)^3, so it follows 3^n + 3^n + 3^n could only be larger as well. Oh well, all in all it could've definitely gone a lot worse.

Now with that midterm out of the way and nothing due immediately after the weekend, time to enjoy the long weekend and go party before thanksgiving.

Regarding Recursion

I've always found recursion to be my favourite subject, and this has yet to change. Recursive functions always seem to end up more efficient than the vanilla / iterative alternative, and most of all just seem incredibly elegant to me. Proving recursive functions seems to have a natural flow to it similar to the functions themselves.

Whoever originally came up with the idea of automatically reducing a problem down to near-nothingness to solve the most complicated of things must have been a real genius.