week.four

reminder: term test #1 on october 10, 2008!

so a1 was due today. and like my other assignments i've had in 165, i've probably flunked it =(. it was pretty difficult having to derive some proofs for the claims in that assignment. i should start utilizing office hours for the sake of passing second year with flying colours.

on monday, we touched on familiar subject in mathematics: the fibonacci sequence. more specifically, we proved the claim P(n): the sum of the first fibonacci nums is F(n + 2) - 1. the flavour of induction chosen to prove this claim is PCI. the proof is broken down into two cases: n <>= 2. through mathematical manipulation, we were able to carry out this proof by nothing also that F(n + 2) = F(n) + F(n + 1) (by definition of fib sequence). i am never too fond of the fibonacci sequence in general, but seeing that it's been brought up myriad of times in computer science and mathematics courses alike, i guess i have to learn to, if any, love it.

on wednesday, we continued a little bit with fibonacci summation. but more specifically, today's lesson was on time complexity. and we applied this topic to the case of "zero-pair free binary string" (i.e.: the case where there exists no pair of 0's in the binary string). after doing some test cases for this case's time complexity (0 <= n <= 3), we discovered that the recursive nature of the function zpf(n) implies that its time complexity function, T(n), would also be recursive. furthermore, T(n) has the same behaviour as that of a fibonacci sequence. seeing how time complexities could also be recursive caught my attention because in 165, time complexities were calculated by steps - how much work every line/loop does determine it's T(n). also, the process of unwinding is something new that was introduced. it will take practice to get comfortable with unwinding for me because it's a long process to "unwind" and the deriving a general expression for it - it gets tedious and i get lost easily in the midst of it.

on friday, quite honestly, i arrived to class yet (TGIF too early...), but i was able to come in when prof heap was unwinding the T(n) of recBinSearch(), which, in short, looks awfully similar to Fib(n). i'll be sure to check out the slides to go over it again...