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.

Week 8

Things get more complicated from this week. We learned the formal definitions of O(n²), Ω(n²) and θ(n²). The prof made an analogy of which compared O(n²) with the growing size of chicken and turkeys. This time, I get a better understanding of '700n^2 is no larger than 0.5n^2'. However, the challenging part is to calculate the steps that the maximum slice function takes in the worst case. There are so many while loops that I can hardly figure out the steps for each loop. And the proving part is easier after finding out the solutions to the problems. 
Another great challenge is the penny pile problem. After reading through the instruction, I can easily reach the number 48. However, the follow up question was much more difficult to solve. The number of possible ways to transfer the pennies are huge, and a tree diagram might be a good choice to visualize the problem.      

Week 7

   In this week, we finally finished proving stuff. Proving is actually not that hard as long as I understand the statement. The challenging part for me is the structure. I notice that sometimes my prooving steps are not complete. I often forget to introduce the quantifications and conclude in the end.
I also learned more proving techniques and rules. I find that proof by case is extremely helpful which provides a more easier method for proving. Introduction and elimination rules are also essential, which help me to reach my target statement faster and easier.
   A new unit was introduced this week as well--Algorithm Analysis and Asymptotic Notation, which sounds really computer scientific. We got an idea of how bubble sort and merge sort work through the experiment. It was interesting that the larger the input size is, the advantage of merge over bubble becomes bigger. On the other hand, it is quite odd that "0.5n²and 700n² are no different" according to my existing mathematic knowledge. And there might be more challenges to understand the asymptotic notations. I must pay much attention to the lecture in order to get a better understanding :)

Week 6

 The test was back before the lecture. Though my mark was above the class average, I still have to work harder. It was really regrettable that I forgot to indicate the negations for Q1 part(a) so I did not get 100%. But overall, this test encouraged me that the tests in University are not that difficult and I have the ability to do well; it also warned me to pay more attention to every questions and not to miss anything.
 The lecture this week was still about proves, and non-boolean functions were introduced. After this lecture, I feel comfortable about the structure of proving. I found that proving is quite easy when I understand the definition and get a basic idea of the methods of proving. I also learned how to disprove a statement, which was quite similar to proving a statement. I can just negate the statement and prove the negation is true.
 It seems that we will finish proving next week. I am excited about learning new stuff.