SLOG #7

    This week we covered the calculations and proofs for the upper boundary and the lower boundary of the worst case scenario for an insertion sort algorithm. Both proofs were fairly easy to follow after accepting the fact that we can find the value of a variable after it has already been introduced, and fill that value in for the assignment statement at or near the beginning of the proof. However, I imagine writing similar proofs on different algorithms to be far more difficult than just following the professor's steps, because counting the number of possible repetitions for each line can get tedious very quickly with nested while loops and boolean operators (not, and, or) inside their loop conditions.     One question I have in mind is the precision to which we calculate the boundaries. When Professor Heap did the big-Oh proof, he arrived at a step WIS(A) ≤ 1 + 5(n - 1) + 1 + (n - 1) * (3i  + 1), then he said, since n > n - 1, then it's fine to write the next line as ≤ 1 + 5n + 1 + n(3i + 1). I find this somewhat unfitting in a rigorous process such as computing the upper boundary for the steps a program takes to execute. When we arrived at the polynomial an^2 + bn + c, every term was changed to have variables raised to the highest degree, so the result was  an^2 + bn^2 + cn^2. Then, every term in that polynomial can be considered equally as important, thus when we see n - 1 as n, we may miss the actual number of steps for the worst case scenario by quite a lot. 
    For this particular example, if I wanted to expand 1 + 5(n - 1) + 1 + (n - 1) * (3i  + 1), I could write i as (n - 1), since i starts from 1 and goes up to n -1 (n being the length of the list). Then I would have
WIS(A) ≤ 2 + 5(n - 1) + (n - 1)*(3(n - 1) + 1)
WIS(A) ≤ 2 + 5n - 5 + (n - 1)*(3n -2)
WIS(A) ≤ 2 + 5n - 5 + 3n^2 -5n + 2
WIS(A) ≤ 3n^2 - 1
WIS(A) ≤ 3n^2
    So the upper boundary is actually 3n^2 instead of 11n^2, less than 30% of what was originally estimated.
    Now, as I was doing the above expansions I realized we only needed to prove an existential statement, so we need not to be so rigorous after all. Go me.
    Also I'm lost as to what the breaking point (B) of WIS(A) ≤ 3n^2 is, perhaps it's zero? In retrospect, maybe I shouldn't have expanded that polynomial.

SLOG #6

    This week we finished up the lectures on writing proofs and had a brief introduction on comparing different numbers of steps two programs take to complete a similar task. We were given the equations g(n) = n^2, f(n) = 3n^2 + 50, h(n) = 15n^2 + n, and we were told that they are all the same. That sounded quite bizarre to me because how can they be the same if the last function grew over 15 times faster than the first function. Then professor Heap's justification cleared up a lot of my confusion. He explained that since the highest degree in all of these functions are n^2, then their growth rates are relatively similar compared to something of a lower or higher degree, such as n^5.
    We ended off Friday's lecture with another problem-solving session. The problem describes a situation where a person is faced with two drawers, one being empty while the other has 64 pennies. If either one of the drawers contains an even number of pennies, then that person can take half of the pennies from that drawer and put it into the other drawer. If both drawers contain an even number of pennies, then the person can make a choice of from which drawer he should take away half the pennies and put it into the other. The question asks if  it  is possible to perform the above operations in such a way that one of the drawers ends up containing any number of pennies in range [0, 64].
    After coming up with some scenarios my intuition tells me that it is possible for the pile size in a drawer to be any number within range [0, 64], but I have no idea how to prove it. So far I have noticed that for every pile size that is equal to or smaller than 32, there is a corresponding pile size that is equal to or greater than 32, which suggests that if I could prove that pile sizes [0, 32] are feasible then pile sizes [0, 64] must also be feasible. So how can I prove pile sizes [0, 32] actually all exist? I tried to apply the concept of reducing the range again so it changes from [0, 32] -> [0, 16] -> [0, 8] -> [0, 4] -> [0, 2] -> [0, 1] so that I only have to prove pile sizes 0 and 1 exist, but I'm not very convinced that this is correct, because it's not as straight-forward as going from [0, 64] to [0, 32]; it is very clear that if one drawer has 1 penny then the other must have 63 pennies, not so clear when the range is changed around so many times. So I will have to look for another solution.

SLOG #5

    This week's material is once again focused on proofs. I found that most of the material was easy to follow and understand, though I may experience difficulties writing them out on my own. However, I still have trouble trying to figure out exactly what's going on with one of the examples in lecture.

    The problem I'm referring to is to prove that for all e in the set of positive real numbers, there is a d in the set of positive real numbers, that for all x in the set of real numbers, if |x - 3| < d, then |x^2 - 3^2| < e. I'm confused as to what the question is asking because there seems to be no relationship between e and d. How is it that the absolute value of (x - 3) is smaller than d implies the absolute value of x^2 - 3^2 is smaller than e? To understand this question better, I tried to look at it like a limit question, where I pick e first as a upper and lower bound, and then I must choose a d that is within the bounds, but not the reference point itself. This perspective helped me a little in perceiving the problem. I can sense a relationship between d and e now; I have to define a d such that for all the possible values of e, whenever |x-3| < d is true, |x^2 - 3^3| < e must be true, which means d has to be some value that depends on e in order to make the implication true. The next part that I am confused about is the content of the proof. Due to my lack of practice with absolute value inequalities, I'm not comfortable in taking numbers out of them. Specifically, I don't understand why d * |x + 3 - 3 + 3| is less than or equal to d* (|x - 3| + 6), because it looks to me that they produce the same value, so they should be equal. Also, the professor arbitrarily chose a number (1) that d is no larger than, so eventually was defined as the minimum between 1 and e/7. Does that mean I can choose any arbitrary number I like, as long as I change the denominator?

    There are still some questions left in my mind, and I will seek the answers during next week.

SLOG #4

    This week's material is all about proofs: structure of proofs, actual content of proofs, and comments that help explain the proofs. The proof structures originally seemed very redundant to me, that they serve only the purpose of visual formality, and are otherwise utterly useless, but I now understand that it is important for me to familiarize myself with the train of thought following the proof structures: when I assume or assign something, I am then in the domain where something is certain to be true. I can see how that can simplify and clarify the process of drawing a conclusion as I exit the domains, one by one, all while stating that the content inside supports the assumptions, until I declare the concluding proof.

    One thing that confused me was the second question on the tutorial, which states: prove that for all x in the set of natural numbers, if (there is a y in the set of natural numbers such that x can be written as x = 3y + 1), then (there is a y in the set of natural numbers such that x^2 can be written as 3y + 1). The correct structure included assigning a y0 to be x = 3y0 + 1, and assigning a y' that depends on x and y0 (Let y' =... #some value that depends on x and y0). At first, I didn't understand why I needed two separate variables to write into the proof structures. Then, I realized that it's because they are indeed two distinct representations of different numbers when I got around doing the actual proof. (3y0 + 1)^2 gives 9y0^2 + 6y0 + 1, and then we just have to set y' = 3y0^2 + 2y0, then x^2 would be equal to 3y' + 1. 

     We left off Friday's lecture at an unfinished proof that there is an infinite amount of prime numbers. What we have is "pretend this is a finite set of prime numbers, all the numbers in the set of prime numbers are multiplied together, add 1 to the product, a new number that cannot be divided by any number in that set of prime numbers is created..." However, the fundamental theorem of arithmetic says all integers greater than 1 is either a prime number or a product of prime numbers. Since that newly created number cannot be divided by any number in the set of our finite prime numbers, then either that number is prime and not in the set, or that number can be divided by some other prime number which is not in the set. Because there is always a number to add to our finite set of prime numbers, our assumption that the set is finite is false.

SLOG #3

    This week's material is not as difficult for me to understand compared to that of the previous two weeks. The idea of transitivity is quite easy to accept because it is easy to illustrate "if A is a subset of B, and B is a subset of C, then A is a subset of C" using diagrams. I can draw three different circles of varying sizes and call them A, B, and C. Then if A is inside B, and B is inside C, it naturally follows that A is also inside C. The concept of mixed existential and universal quantifiers should have particular orders in a claim was also relatively easy for me to grasp, mostly because it was discussed in my second tutorial for this course.  A specific question asks to translate the English statement "every course has a prerequisite" to symbolic expression. The answer is, for all x in C, there exists a y in C, C(y,x). A student asked whether it would be correct if the order of the quantifier was switched. I must admit I was actually shocked to hear the teaching assistant say "no". To me, the quantifiers originally seemed to act like phrases that set up conditions for a claim, so of course the order in which the conditions are listed shouldn't matter. Then, as the teaching assistant explained in detail of why the following a particular order is important, it became clear to me that there indeed is a difference between "all courses have a prerequisite" and "a course has every course as its prerequisite".

    Although I reflect this week's material was picked up easier than that of the previous weeks, it isn't without any trace of obstacle. For example, I find the process of proof a challenging task for me, mainly because while it is easy to describe, vaguely, in words why some patterns or sets behave the way they do, it is a totally different story when I try to write it out in precise words or symbols. In the lecture, we examined the process of proving the square of an odd number is odd. At first glance, the statement seemed blindly obvious to me, but I struggled to find a precise and convincing way to express why and how that statement is true. The professor had to go through a meticulous, or even cumbersome process of assuming domain, defining natural odd number, defining natural even number,incorporating rules of adding and multiplying natural numbers, and finally substituting a single variable for an operation between two variables to mirror the definition of an odd number, all to prove a very simple statement. I must imagine how much more complex the process would be to prove a not-so-obvious statement, and it honestly overwhelms me.