Even though the marks are not out yet, I know I somehow screwed up the second term test. The first question of the test was a two-part question about recurrence relation--the first part is to use repeated substitution or unwinding to solve for the closed form of the recurrence relation, and the second part is to prove that the closed form is correct using induction. I'm very familiar with both of these types of questions, yet I failed to get the closed form of the recurrence relation because I couldn't figure out the closed form for the sum/series at the very end. I believe it was something like: 1+4+16+64+... = 4^0 + 4^1 + 4^2 + 4^3 + ...
As a result, I could not prove that my closed form was correct by induction--simply because I did not have the correct closed form. Moreover, since the term test has only two questions, it's kind of like "you either get an A or a C"--you screwed up one question and there goes half the marks.
The second question was to prove that some recurrence relation is in Big Theta n squared or something. This is very similar to the last question--which I believe I did it correctly--on the second assignment. On the term test, though, I forgot the very last step where you simply create the final, suitable upper/lower bound. For example, from the BigO part of the question on the second assignment, when you get T(n) <= 2 + log n, you just say that this is less than or equal to 2logn + logn = 3logn for n >= 2 simply and obviously because 2 <= 2logn for n>= 2.
So I did really bad on the term test and would be lucky to pass the test. I didn't see this coming but kind of deserved it though--I barely studied before the test because I had no motivation at all. Nonetheless, I will be looking forward to picking it up and doing well on the last three or four quizzes and preparing for the final exam. Bring it on!!
No comments:
Post a Comment