CSC165 sLOG 9

  As I have already say goodbye to test 2 and chapter 3, I have no reason not to pay more attention on chapter4 regarding algorithm analysis and asymptotic notation. In lecture, pro introduced the upper bound and lower bound for the input with the size of n in worst case. Then he provided us some examples about Wis belongs to big Oh. f(n) belongs to O(g(n)) means there exists a real number c and a natural number B for every natural number n, if n is no less than B, then f(n)less or equal to c times g(n). c is a multiplier ,B is a breakpoint, so that you can go far enough to the right the function is bounded above by cg(n). In terms of limits, this says that as n approaches infinity, f(n) is less than cg(n) once you find the appropriate c.At the beginning, I found the big Oh problem is not easy to do. But after some practices in lectures and tutorials, I become more and more familiar with these kind of problems. It also requires you to be good at writing proof structure. By the way, it is important to remember that for every while loop, we need to execute one more step for the first line!
   Regarding polynomials for big Oh problem, f belongs to O(g) when the highest-degree term of g is no smaller than the highest -degree term of f. Furthermore, logarithmic functions are in big Oh of any polynomials, whereas exponential functions are not in big Oh of any polynomials.When proving some big oh questions regarding exponential functions, it is useful to use the meaning of limit. We also learnt big Omega problems, which is the opposite to big Oh by definition. This time the role of c is to scale g down to below f.

CSC165 Slog 8

   It has been a busy week for my studying for CSC165 cause we have the second midterm this week regarding chapter3: proof. I spent a lot of time doing practices for proof and review the course materials like the course note, the web problems, lecture slides and past tests.Since we have learnt calculus in MAT135 and MAT136, it is not that difficult for us to deal with mathematical problems when proving. However, it was a headache for me to write appropriate comments maybe it is because my first language is not English. So my whole aid sheet I brought to the test was filled with different kinds of comments. We have three questions in test2, the last one is a little bit hard. Even now I am not sure whether I got it totally right and I am eager to know the result. I think I still need to do more practices for proof cause I am not skilled at it.
  Recalling assignment 2, I think the questions are more complicated than that on test 2. Some of them are a little tricky and you have to think about it for a while especially the last question. The great common divisor thing is kind of hard to comprehend and it needs you to be very logic to figure it out. When I see the official answer, I found out that our solution for the gcd question is not good enough even though we tried very hard to prove it. Anyway, I like proofs even though I have to say goodbye to it for now and learn something more complicated-the big O!

CSC165 Slog week7

This week, the professor lead us to study several proof cases. Firstly, we learnt proof about limits. That example make me very confused.From an existential quantification, I am not sure how to pick a number which satisfied the requirement from the question. Then the professor told us to calculate y^2 - pie^2 first and then find out the scope of that number we should pick. Therefore I finally figured it out under professor's guidance. Afterwards we learnt how to prove by cases.The question is: for every natural number n, n^2 + n is even. A natural approach is to factor it as n(n+1), and then consider the case where n is odd, then the case where n is even. Because both cases are proved to be true, the statement is true. Moreover, we learnt some new things like allowed inference and sorting strategies. For inference, I knows how to make conclusions by studying conjunction elimination, existential instantiation... For sorting strategies, I found that the steps required for insertion sort and selection sort on lists of size n were no more than some quadratic functions of n. They are all in O(n^2). When counting costs, we learnt that we should always consider the worst case. To conclude, the professor gave us several examples of counting steps.