The Course Towards a True Proof Never Did Run Smooth - Week 12

This week my focus has been mainly on the third and final assignment. As the course is coming to an end, I have been giving a lot of thought to all the different things I have learned. While overall, I feel like I have made a lot of progress, there are certain types of proofs that I continuously get caught up in. Any problem dealing with limits has proved to be quite a challenge. The first encounter with the epsilon delta proofs was quite overwhelming and while I made some progress in handling those type of proofs, I still feel that there is a lot more work that needs to be done. Furthermore, we have now been introduced to some calculus rules while dealing with limits. I do not have a lot of experience with calculus so now dealing with calculus in proofs feels like a very difficult challenge.

In general, developing an intuition about what a limit actually is can be quite difficult. I had a general idea, but it was still difficult to wrap my head around what a limit really is. I went to office hours this week to try and get a better grasp at what is going on.  Danny helped me out and gave me a written English sentence to try and understand what it means when a limit is approaching 0. He told me that the ratio you are using gets as close as we want to 0 provided we choose an “n” big enough.

Using the formal definition of a limit, we get:

"c e Â⁺, $n_c e À, "n e À, n ³ n_c Þ (ratio that has a limit that approaches 0) < c.

This fits the loose definition that Danny gave me and brings more understanding to the more formal way of putting it.

This assignment has allowed me to practice these types of questions and forced me to try and gain a better understanding of what a limit is. I don’t think by the end of the course, I will have a full grasp but I will definitely know a lot more than when I first came in. That in itself makes it worth the effort.

An infinite deal of nothing...or something? - Week 11

This week we have been discussing uncomputable functions. Specifically in lecture today we began to discuss the problem of cardinality. In turn, this came down to the question of how do you count infinite sets? In counting, we have come up with two key methods to ensure that we are not over or under-counting. These methods work for finite sets but it becomes more problematic when dealing with infinite sets.

The two rules of counting are as follows:

1) You have one-to-one matching

2) You map only once something from your domain to your range

For infinite sets it is much harder to apply these principles. When we are trying to compare the size of two infinite sets we can determine if one is actually larger than the other. If they are the same size, we can match them up in such a way that they have a one to one ratio. However, some infinite sets are not countable. The definition for being countable is having a one to one match up with the natural numbers. While the set of irrational numbers are countable, the set of real numbers are not.  Due to this fact, we can say that infinity of the real numbers is larger than the irrational numbers.

I find these concepts to be incredibly interesting but it is taking some time to wrap my head around the details. I think it is a good way to finish up this class as it is opening the doors to interesting future topics without overwhelming us with an overload of information. I look forward to hearing more about infinite loops…I just hope that my future code is not responsible for them!

Proving NOT (n3 \in O(3n^2): We Know What n^3 Is But Not What It May Be - Week 10

In this week’s first lecture we were going over how to prove or disprove that a polynomial is in Big O. While last week the focus was primarily on proving that a polynomial had a growth rate no faster than the polynomial inside the Big O, the start of this week has been focusing on disproving this. Proving something in Big O seems more straight-forward than disproving for these cases. While neither is particularly hard, it feels as if there are more considerations for the negation.  To prove this type of question, you must subtract values that are decreasing the value of the polynomial and multiply terms by n to increase it for comparison. For the polynomial in big O, you can do the same type of modifications to decrease it until the two formulas are easily comparable. Then it is fairly simple to pick B and c.

Disproving it takes a few more steps and I believe a little more thinking. Here is one example of this type of question.

We were asked to disprove n³ e O(3n²):

$c e Â⁺, $B e À, "n e À, n ³ B Þ n³ £ c*3n²

The negation of this is as follows:

"c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

Assume c e Â⁺ and B e À       # generic c, B to introduce "

                Pick n = B + é3cù + 1. Then n e À.

                Then n ³ B        # added some non-negatives to B

                Then n³ = n * n²

                Then n³ > 3cn²     # since n > 3c

                Then n ³ B Ù n³  > 3cn²

Conclude "c e Â⁺, "B e À, $n e À, n ³ B Ù n³ > c*3n²

While this question is a very simple example of the much harder proofs we will be doing, it does show that when choosing n, many things must be considered. The value of n must be greater than or equal to B and the formula itself must take into account the other polynomial and c. Furthermore, as n must be a natural number and c does not have to be, flooring or taking the ceiling is also necessary. In the end, we know that n³ is a polynomial to the third degree, but we don’t know (until we prove it) that n³ is not in the Big O of 3n².

Runtime is the Most Beautiful of Dreams and the Worst of Nightmares - Week 9

This week we continued on with runtime proofs and while I realize the importance of understanding runtime, I continuously struggle with it. While working through the basics of polynomials seems more straight-forward, actually creating the equation based on the code is very difficult for me. While we have had a couple examples in class, it is still hard to see the relationships between multiple while loops in a single function. Some of them seem fairly simple with a run-time of n to the power of however many while loops exist, others are not that simple with a j based on an i and a k that do not behave as expected. In those cases I am not even sure how to begin to understand the relationships between the while loops.

In this week’s tutorial, we had to come up with a formula for a function. I tried to emulate the formula we had done in the previous week. I worked with a couple other people in tutorial and we had all assumed that the middle loop ran for 3n + 1, while the outer loop ran another n amount of times. We tried to multiply them together but the relationship between the two was more complicated. It needed a summation between the two. In the end, the answer was 3n(n-1)/2 + 4(n-1) + 2. While our TA did a good job of explaining why this was the case for this particular example, I believe I would have trouble recreating something similar in the future.  Thus, runtime can be both wonderful and horrible in practice but it can also be this way when trying to calculate the runtime.