This week, we had our second midterms and also second assignment due. What a busy week! Guess I will take a break from studying this weekend... Anyways, I think I did pretty well on the test as well as on the assignment. I personally think that the assignment is harder and it took me and my partner quite long to finish it, Question 2 is alright but Question 1 really got us, especially Claims 1.3 and 1.4. Because we never did this kind of proof: for example, we knew that Claim 1.4 was wrong however when we negate the statement, we didn't know how to prove x=y. Thanks to Google, and thanks to professor that we now know that we have to prove x >= y and x <= y in order to prove they are equal.
During this week's lectures, we continued talking about Big O and Big Omega (but mainly Big O) and we started learning the actual proofs of Big O. As I've mentioned before, we have to start from definitions for most of the proofs. So, for Big O, the key point is to find an c and an B that make satisfy the definition. The Big O proof is sort of like limit proof in which you will have to work backwards to find the right number in both cases.
We've also learnt how to disprove the Big O statement, which is just proving its negation. However, the problem for me is not how to prove/disprove it but figuring out if the function satisfies the Big O or not.Therefore, I usually assume the function is Big O, and try to find an c and B that works,and if I can't, I will then disprove it. I think my technique is time-consuming,especially on a test, but I cannot find a better way to do it. If any of you know, please tell me!
No comments:
Post a Comment