Week 9 and Week 10

These two weeks have been intensive with concepts, ranging from proving more quadratic functions to Big-Omega and Big-Theta. By far, I have seen that the course is progressively more difficult. So, I know that I will have to spend more time rereading my lecture notes and trying to understand the logic hidden in the various problems involved in mathematical reasoning.

One concept I learnt during Week 9 is that of a loop guard. A loop guard is just a step that a part of code takes to move a function along and help it execute. For example, in code, an initialization statement for a variable is a loop guard, as it is run through only once. An example of this is max = 0 or i = 0. I found the proofs about quadratic functions to be quite challenging, so I decided to include the proof for one of the functions.

7n**6 - 5n**4 + 2n**3 Î O(6n**8 - 4n**5 + n**2), it uses the O(n**2) notation to prove it.

Here is the proof:

Choose c = 9/2. Then cÎℝ+.

Choose B = 0. Then BÎℕ

Assume nÎℕ  # typical ℕ

      Then n >= B  # antecedent

             Then 7n**6 - 5n**4 + 2n**3 <= 7n**6 + 2n**3             # 5n**4 <= 0

                                                                        # add 7n**6 + 2n**3 to both sides

                      <= 7n**6 + 2n**6           # 2n**3 <= 2n**6 

                                                               # "nÎℕ

                      = 9n**6 <= 9n**8         # 9n**3 <= 9n**6 x n** 2    "nÎℕ

                         = c2n**8             # c = 9/2

                      = c(6n**8 - 4n**8)        # -4n**8 <= -4n**5

                      <= c(6n**8 - 4n**5)   <= c(6n**8 - 4n**5 + n**2)

                        # add 6n**8 - 4n**5 to both sides of 0 <= n**2

              f(n) <= c(6n**8 - 4n**5 + n**2)

       Then n >= B Þ f(n) <= c(6n**8 - 4n**5 + n**2) 

Then "nÎℕ, "                      # introduce "n                           "

Then $BÎℕ, "                  # introduce $B                               "                 

Then $cÎℝ+, "                                                                       "

------------------------------------------------------------------------------------------------------------------------

This is one of the various proofs that we were and are taught to write for quadratic functions. It is a lengthy process, and it is also confusing. It even confused me as there were so many steps that seemed like they were arbitrarily thought of and included. One of these steps was the changing the degree of a variable so that it will be higher. This is the reason why I know that rereading these proofs and understanding them is important. Furthermore, I know that something like this will appear on the exam, so this is necessary to know, not just important.

In the 10th week, we were taught about the role of logarithmic and exponential functions in proofs. We were also taught how L'Hopital's rule applied into proofs, and I find it amazing that mathematical equations such as these can be expressed through proofs. However, I find it equally frustrating that I do not understand how the proof progresses. I also wonder how quite a lot of people in my lecture session are able to understand this concept and offer the next step to the proofs' solutions. Knowing that this is the first time that we've seen these kinds of proof statements, I wonder how they understand what values to use for variables, for example, and I don't. 

Additionally, we were taught the notation for Big-Omega, Ω(g). It is almost the same as the notation for Big-Oh, except that here, f(n) >= cg(n). In Big-Oh, f(n) <= cn**2. We were also taught about the bound that was formed by combining Big-Oh and Big-Omega. This bound has the symbol Q. As usual, some proofs related to these concepts were taught to us, which looked fairly reasonable for me to understand. However, if I was given a similar question like this, I would most likely not be able to do it. This is why I am rereading my notes and trying to improve my understanding in the course material. 

So far, I have been challenged and intimidated by the course material, despite my efforts to makes sense of the material. As well, I am apprehensive of the material included on the final exam, as well as the level of difficulty of the exam.