Week 12

   It is the final week of the semester. The lecture was short. We learned about countability and get a preliminary understanding of induction. Comparing to the computability stuff, countability is easy to understand and straight forward., though the idea that the sizes of the set of natural numbers and the set of even natural numbers are the same was a little queer in the beginning. However, on the other hand, when we developed a '1 to 1' and 'onto' well-defined function that related to the 2 sets of numbers, it is easy to understand that each number in natural number set is corresponding to a number in  even natural number set, which means that the 2 sets have the same size.

   Finally, we went over the test review. I believe that I can solve logic problems and proving big-O problems with ease, but the algorithm and computability part is still challenging for me. I must go over the course note carefully and perhaps go to the office for help.

Week 11

There were no lectures or tutorials this week due to the fall break. Therefore I got more time working on Assignment 3. I found that proving big O and big Omega problems not so difficult since the TA went over the big-O problem thoroughly during the tutorial. For proving big-O problems, the first thing to do is to under-estimate the big-O function and over-estimate the function that we are going to prove; then we can easilly pick the number c that satisfy the condition.
However, I was stuck on the 6th question. It seemed that I need to pay attention to the lecture next week.

Week 10

   The second term test was back. I was satisfied that I got 27 out of 30 on this test. From the test, my proof structures were ok and my thoughts were on the right way. However, I did not explain some of the steps so it made the proof a little unclear. I used some statements that we had proved during lecture without explaining the work. In conclusion, I need to be more careful about the comment of each step; I need to show all the proving works for proving each step.

   During the lecture, we learned the 'fancy F' and general provings involving the big-O and big-Omega. The strategy for proving big-O functions is to under-estimate the big-O function and over-estimate the function we want to prove. In order to do that, picking a smart c value and B value is essential.
 
   We finally reached chapter 5. To be honest, I barely understand the concepts of computability, and I got comfused while dealing with the python function problem. It is not a good sign, I guess I need to go over the slides on the weekends again to gain more understanding.

Week 9

   We had the second term test this week. Though there were only 3 prooves on the test, I found one of them a little tricky. I've done the past term test and they were straight forward that I can finish them in 20 minutes. However on the test, the second question was kind of hard to find a way to prove. I spent about 30 minutes on that question and somehow found the way to prove. Hope I got the right answer.
   Besides the test, we've done more provings about the big-Oh. To prove a polynomial is in a big-oh of another polynomial, all we have to do is to pick a smart value of c and B. However, provings got more challenging while dealing with non-polynomials. It was easy to understand that an exponential function grows faster than polynomials, but it was a bit difficult to prove it. In that case, limits were introduced to prove it. Though I still not really understand the definition of limits (∀c∈R+, ∃n′∈N, ∀n∈N, n≥n′⇒g(x)/f(x)>c), this definition helps us to pick a smart value of n so we can sufficiently prove the statement.