Week 10.

Last week's lecture was pretty nice (except the disappointing test mark). I always liked DFSA. I like their names too. "Deterministic automaton". It has a nice sound and reminds me of automatons in some expansion of Age of Mythology and Syberia II.
We also learned the formal definition of a DFSA which was very interesting. I always liked the formalizations of intuitive concepts like functions, graphs, trees, DFSA's. Every time I read about one of them, I am happily surprised by how complete it is and how closely it matches the intuitive notion. Also, it gives a reassuring feeling (since now things can actually be proved about them without relying on hand-waiving (which I always found troubling)) and a feeling of empowerment since it is a discovery that math is much broader and more powerful than the 12 years of studying algebraic manipulations and simple R->R functions might have led us to believe.
Although DFSA's aren't really new to me. In fact, we did an example where we had to construct a DFSA that accepted only strings containing the substring "110" (or maybe some other substring of length three, I don't remember the exact one). It brought back good memories of CSC148 and the O(n) substring searching problem. Since thursday I have been trying to remember the algorithm used for creating the DFSA for a general substring. So far, I am unsuccessful.

Unfortunately I will not be able to go to class on the 20th until 7:30. I am reading ahead to compensate.

Week 9.

So we got the results of the second assignment this week and all I can say is wooooohooooooooo! Hopefully I did well in the second test - I already wasted the 6% on the first test.

Finally we are learning new things. So far I like regular expressions and formal languages (just as I thought I would). The downside of this is that now I can't rely on my usual studying schedule - I have to make more room for CSC236. Sudden changes like this are never good.

Week 8, part 2

The second reason is that I never much liked proving correctness and time complexity bounds. Correctness isn't so bad, but all time complexity proofs that we have done so far have been fairly simple, but very long. Even in math, I never liked proofs that took so much longer to write formally than to go through in your head.

I find that whenever I try to participate in the lectures (i.e. answering questions), it's much easier for me to pay attention, and I get much more from the lecture. The downside of that, is that inevitably I say something really stupid and embarrassing from time to time. For example, last time I said "it must reach 0" (when we were doing loop termination proofs, and were asked what was so special about decreasing sequences of natural numbers) and if I remember correctly, Danny corrected me and said that it has a smallest element.

Although that's not really relevant; every sequence of natural numbers has a smallest element by the principle of well ordering. What we need to prove termination is that it's finite, and that's what the "decreasing" part gives us.

Week 8, part 1.

Well, this has been a ridiculous week (as a testament to that: as of now, I have spent 40 consecutive hours without any sleep at all).
I have to say, these last few lectures haven't been very interesting to me, for two reasons. Most of it was done in csc165 (not just the concepts - even a lot of the examples). In fact, the only things I can think of from this course, that weren't treated in csc165 are: the master theorem, the equivalence of the 3 principles, and the "find a decreasing sequence of natural numbers" method for proving loop termination (which, by the way, was explained very well. I didn't really fully understand it until yesterday).
And since it feels like someone is drilling a hole in my head, I will continue this when I wake up.

Week 7.

I did not go to week 6's lecture (I had to finish my 207 assignment) so I felt it would have been somewhat dishonest to write a blog entry. I also had nothing to say. But this week went pretty well, even though there was nothing really new. The gcd algorithm and it's proof would have been much more interesting if I hadn't encountered them about 5 times before. It would be hypocritical to complain about the slow pace of the course; however, since if the workload was any heavier I would not be able to keep up.

Week 5.

Grade-wise, this was a good week in CSC236, but I am a bit disappointed because I could have done better. I did not get 8/8 in the problem set because the "P(n)" predicate symbol was missing. But the statement of the predicate I was trying to prove was still there, so this annoyed me.

I was fairly happy with assignment 1, but in the second question I had forgotten to prove that my algorithm for generating the cycles produced every possible menu.

I thought the test was easy. Two of the questions were very straightforward induction. I am a bit concerned with my argument of a certain point in the other question, but I doubt it will affect me much.

I was very pleased with the explanation of how one could get the closed form formula for calculating the nth Fibonacci number. It disturbs me when I see some result that is "pulled out of a hat" in math books.

Week 4.

The week 4 lecture was ok. Well, at least the first two hours were. The stuff about recursive functions and the Fibonacci numbers was pretty interesting. The Fibonacci pattern (the one with the sum of the first n numbers) was pretty easy to guess, especially since Prof. Heap had posted it in his blog a few days before the Thursday lecture.

In the third hour it became very hard for me to pay attention, but I think I'm getting better in this respect (two weeks ago I spaced out after just one hour).

At some point, when we were proving the time complexity of the recursive binary search, the lecture became slow and the class was not contributing at all. And then Prof. Heap stopped talking for about 10 minutes. I thought we had angered him (it reminded me very much of a lecture in first year where no one had done the required reading, and the professor got very disappointed and dismissed us all). I felt really bad. Then, it turned out that we were supposed to be jotting down our attempts at solving a problem, like usual. I had not been doing anything, and so I felt even worse.

These evening sessions are killing me.