March 27 week 9

I had some confusion about big-oh and big-omega, originally I thought in order to disprove  big-oh statement , you would have to prove big - omega. which is clearly wrong. Some function can be true in both big-oh and big-omega. it just simply means that the function is bounded above and below. I just realize from the assignment 3 question 1 and 2. I think proving polynomial statements are pretty easy, We just need to determined the highest-degree term in big-oh / big-omega . 

In big-oh , if the highest -degree term is greater or equal , then the statement is true , otherwise disprove it by negating the statement.  

In big-omega  ,is the opposite. if the highest - degree term  is smaller or equal , then the statement is true , otherwise disprove it by negating the statement.

However , I still have trouble understand non-polynomials statement and using limits , L'hopital  rule. to prove it.

March 20 week 8

I just want review the stuff during this week's tutorial .

So the definition of  O is    /Exist c in positive real number , /Exists b in natural number , /For all n in Natural number , n>=b => f(n) <= O(g(n))

During tutorial we have to proof  5n^4 - 3n^2 + 1 <= c(6n^5 - 4n^3 + 2n) , which is pretty obvious if we think in mathematical way, but we need to prove it. lets put the structure aside for now and focus on the actual prove.   

 

5n^4 - 3n^2 + 1 <= 5n^4 + 1 # when we remove negative term , we get bigger number 

                          <= 5n^4 + 1 # we want remove the 1 , so multiply  n^4 , thus n>= 1

                          <= 5n^4 + n^4

                          <= 6n^5 # we now multiply n again .

                         #now we start from the other side

c(6n^5 - 4n^3 + 2n) >= c(6n^5 - 4n^3) # we keep the negative term , so the number always smaller

                                >= c(6n^5 - 4n^5) # when the negative term gets bigger , the number itself gets smaller 

                                >= c(2n^5) # simplify 

                                >= 3(2n^5) # i pick c = 3.

                               >=6n^5

      #we we have 5n^4 - 3n^2 + 1 <= 6n^5 <= 3(6n^5 - 4n^3 + 2n)

      #implies 5n^4 - 3n^2 +1 <= 3(6n^5 - 4n^3 + 2n)   , c = 3 and b = 1 (since n>=1)

I'm not sure if I done this correctly until the tutorial solution is posted ,  for whoever reading my slog  please feel free to leave a comment to correct me.

also , http://csc165blog1.blogspot.ca/ this blog actually contains really helpful note .

11 March week 7

I still have lots misunderstanding and confusion about the recent lecture , however I rather kept it aside for now and focus on the upcoming midterm. Review all the proof example in lecture and tutorial , and probably do some previous test. When I check my assignment 2 solution , i did pretty well. The only problem might be question 6 , I understand the logic thinking behind it but couldn't express it in mathematical way. So this might be things I really need to be aware of.

March 3 week 6

 "A HUGE WAVE OF EXAMS IS APPROACHING", things are getting very busy and frustrating.
Unfortunately, I miss my tutorial last week due to dentist appointment , especially when I plan to ask few questions on the assignment.As we go deeper into the proofs , things start getting bit more challenging for me and I had some difficulty on the assignment too but I think I can manage it.  Since upcoming midterm would be mainly on proofs and the assignment likely going to worth more than the second midterm , its about time to put some hard works into these proofs.

P.S , I had some concerns about the test format. In last test, there is big chunk of mark that concentrate into  question 1. If i remember correctly , question 1 itself are worth more than 50% of the test . It seems unreasonable that if the second term use the similar  format which concentrate majority marks into one proof.