week.six

reminder: problem set #3 due on friday!

on monday, i ate turkey?

on wednesday, we touched on a recursive sorting algorithm - mergeSort. in particular, we were interested in determining the T(n) of mergeSort. we achieved this by the technique of "unwinding" .through expanding/unwinding T(2^k), we were able to obtain the gernal expression:
2^k + kd2^k = n + dn(lg(n))
moreover, we proved the claim (using PSI):
\forall k \in N, T(2^k) = 2^k + kd2^k = P(k)
also, we touched on the topic of "non-powers of 2" (floor & ceil in between powers of 2). we also wanted to prove that non-powers of 2 are monotonic in relation to each other. the flavour induction was PCI. overall, i didn't have too much of a problem understanding the materials discussed in this class - just might take reading it over to understand it more.

on friday, yet again i was late - must've been because of the week after thanksgiving, so law of inertia still applied to my physique.but, this time it wasn't because i slept it - it's because of the doggone 207 A1. consequently, i did not hand in problem set #3 because i completely forgotten about it. down with procrastination from now on...i hope. we got our tests back at the end of class - i didn't do so bad (considering i was 25 minutes late =P). in short, the class talked about the master theorem of time complexity of mergeSort. i will definitely go through the class slides...