Importance of the Order of Quantifiers

I remember at the beginning of CSC165, there was a stark warning to pay attention to the order of quantifiers in writing a claim. It seemed obvious at the time, but finally in A3 I still erroneously proved a claim by mixing up the claim.

Fo all e in R+, there exists d in R+, for all x, y in R+, |x-y| > d => |x+y| > e

From the second assignment, I'd been confused about how to prove a claim when there are different variables in the antecedent and consequent, but I fortunately learned that the way to connect the two was to write one of the variables in terms of the other (d, e in this case).

Remembering this, I excitedly got to work with the first version of my proof:

|x+y| <= e => |x-y| <= d # contrapositive

Assume |x+y| <= e

Let d = |x+y|

Then |x-y| <= |x+y|

-x+y <= -x-y

x-y > x+y

x /> x+2y # x, y in R+

Well that didn't quite work out as I'd expected...

I have no idea what I "proved" there. I thought this implied that the claim was false for a while (since that's what I'd "proved" here), until I was told that the "d" I'd picked here depends on x and y, and that can't happen if d come before x and y in the quantifier (before they're introduced), but that means I can use e.

Now it makes a lot more sense. The informal version of the proof can be written in one line:

|x-y| <= |x| + |y| # the addition of two positive numbers will always >= the subtraction of the same numbers

= |x + y| < e = d # letting d be e

Sometimes the simplicity of proofs really quite amaze me. When I was first exposed to proofs in MAT137, I'd always thought constructing proofs of my own would be out of my reach since the lines seem to have come out of nowhere. Now I see it just takes a bit of manipulation that comes with creativity and attentiveness to really understand each component of the claim, and the rest will follow. Additionally, the proofs that we've been introduced to in this course so far actually aren't as arbitrary as I'd initially thought. They actually all follow a set structure and method, and this realization has definitely made proofs a lot less intimidating.

A Few Types of Proofs in CSC165

Just wanted to write a little reference post for myself regarding the proofs we've covered so far in this course with a few tips regarding each.

1. Equality proofs

- Determine whether or not to prove or disprove claim, and write the appropriate negated claim if the goal is to disprove

- Read the claim carefully and make use of each part

- Try to make intuitive sense of what the claim is trying to say before attempting to prove/disprove, to figure out which route to take

e.g.

For all x in R, for all y in R, x >= y => floor(x) >= floor(y)

Assume x in R, y in R, x >= y # this claim is true

Then floor(y) in Z

Then floor(x) in Z # since the claim beings with universal quantifier, cannot prove by "picking" variables

For all z in Z, z <= x => z <= floor(x)

By definition floor(y) <= y # of floor function

Then floor(y) <= y <= x

Then for all z in Z, z <= x => z <= floor(x)

Pick z = floor(y) # since z is given in definition, using definition of floor function to prove claim

Then floor(y) <= x => floor(y) <= floor(x)

2. Big-O proofs

- Write out claim in symbolic form

- Determine whether to prove/disprove, only pick the variables for components that are existentially quantified

- Don't forget to restate claim using Big O notation at the end (i.e. then polynomial in O(polynomial))

e.g. Write a detailed structured proof that 7n^3 - 4n + 1 in O(8n^4 - 5n^2 + 3n)

There exists c in R+, there exists B in N, for all n in N, n >= B => 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Pick c' = 1

Pick B' = 8

Assume n in N, n >= B

Then 7n^3 - 4n + 1 < 7n^3 + 1 <= 7n^3 + n^3 = 8n^3 <= n(n^3) # n >= 8 = n^4 < 3n^4 = 8n^4 - 5n^4 < 8n^4 - 5n^2 < 8n^4 - 5n^2 + 3n

Then 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then n>= B >= 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then there exists c in R+, there exists B in N, for all n in N, n >= B => 7n^3 - 4n + 1 <= C(8n^4 - 5n^2 + 3n)

Then 7n^3 - 4n + 1 in O(8n^4 - 5n^2 + 3n)

3. Polynomial implications

- Assume antecedent and try to get the consequent working forward from the antecedent

- For existential variables, leave blank and work forwards first, then fill in the value

e.g. For all x in Z, (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Assume x in Z

Assume y in Z, x = 3y + 1

Let y' be such that x = 3y'+1 # leave blank until proof is complete

Then x^2 = (3y + 1)^2 = 9y^2 + 6y + 1

Then 3(3y^2 + 2y) + 1

Then 3y' + 1

Then there exists y in Z, x^2 = 3y + 1

Then (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Then for all x in Z, (there exists y in Z, x = 3y + 1) => (there exists y in Z, x^2 = 3y +1)

Proofs Using Definitions

With A2 due on Monday, I spent the weekend grinding through the rest of the proofs that I'd yet to complete.

There were two things that clicked for me during this assignment.

Days before I began tackling this assignment, I'd read over the assignment and its requirements briefly. We'd covered the floor function in class in a previous lecture, but I didn't completely understand the definition at the time. In fact, I was fascinated that so much could be said and contained with just a few symbols. Since A2 required a good understanding of this definition, I finally had to look closer, which brings me to my first realization:

1. Each symbol is crucial to understanding the symbolic statement (i.e. definitions, claims)

I'd struggled for about 15 minutes before I succumbed to inquiring about whether or not there was a mistake in the definition for the floor function presented in the assignment.

Namely, in the definition,  \forall z \in\mathbb{Z}, z \leq x \Rightarrow z \leq \floor{x}, if I set:

z = 3.2

x = 3.4

Then z \leq x, but z \geq \floor{x}. I was confused. Then I realized that z can only be an integer; I'd missed an integral part of the definition.

Armed with this knowledge, I went onto tackle Claim 1.1

\forall x \in\mathbb{R}, \forall y \in\mathbb{R}, x \textgreater y \Rightarrow \floor{x} \geq \floor{y}

This was the first time I'd used a definition directly to prove a claim.

My first attempt consisted of trying to manipulate x > y in some way so that x = y, which would then satisfy \floor{x} \geq \floor{y}. Bad attempt - that would only prove the equality and ignore the inequality.

In my second attempt, I saw that I had to somehow make \floor{y} in \floor{x} \geq \floor{y}, z, from the definition, so that z \leq \floor{x}. Eventually, seeing that z \in\mathbb {Z}, since \floor{y} \in\mathbb{Z}, letting z = \floor{y}, the proof was devised at last.

\begin{proof}

  Assume $x \in\mathbb{R}, y \in\mathbb{R}, x > y$

    \\\quad Then $\floor{y} \in\mathbb{Z}$

    \\Then $\floor{x} \in\mathbb{Z}$

    \\Then $\forall z \in\mathbb{Z}, z < x \Rightarrow z \leq \floor{x}$

    \\By definition, $\floor{y} \leq y $

    \\Then $\floor{y} \leq y < x $

    \\Then $(\forall z \in\mathbb{Z}, z \leq x \Rightarrow z \leq \floor{x})$

    \\Pick $z = \floor{y}$

    \\Then $\floor{y} \leq x \Rightarrow \floor{y} \leq \floor{x}$

    \\Then $\floor{y} \leq y < x \Rightarrow \floor{y} \leq x \Rightarrow \floor{y} \leq \floor{x} $

    \\Then $x \textgreater y \Rightarrow \floor{x} \geq \floor{y}$

    \\Then $\forall x \in\mathbb{R}, y \in\mathbb{R}$

\end{proof}

(As a side note, I've yet to fully comprehend the LaTex syntax. I definitely need to brush up on that knowledge before attempting my next assignment.)

The most enlightening part of the assignment was perhaps in understanding what Claim 1.2 was asking for. 

\forall x\in\mathbb{R}, \forall e \in\mathbb{R}^+, \exists

  d \in\mathbb{R}^+, \forall w\in\mathbb{R}, |x-w|< d

  \Rightarrow |\floor{x}  - \floor{w}| < e

After more than half an hour of scouring around the web for inspiration, and speaking with another student, it finally became clear that the claim is the definition of the continuous function, which brought me to the second thing that clicked during this assignment. 

2. The delta epsilon proof for continuous functions

Having taken MAT137 last year, I remember having first been exposed to this rigorous definition. I was so confused with the introduction of proofs at that time. However, following this assignment, it finally made more sense (and as I'd become more familiar with reading symbols throughout CSC165, I wish I'd taken this course prior to taking MAT137).

Essentially the claim said that the floor function was a continuous function, which is clearly false. However, the challenge remained to disprove the claim. 

This assignment has definitely helped in solidifying my knowledge of the ways in which one can approach a proof (e.g. there had been multiple instances where I'd 'picked' a value to prove in an universal claim, and where I attempted to prove an existential claim using a universal method, terrible). Being precise is so crucial in math and CS, and it looks like I'll just have to keep practising to adopt a more keen eye.

Overall, I'm happy to say that I'm finally starting to gain an intuitive understanding of how proofs are approached and to gain an appreciation of rigour in math.

Making Sense of Implication vs. Conjunction

We've begun CSC165 with symbolic logic. I'm still working to get used to mathematical logic, which has exhibited differences to the logic we use on a day-to-day basis.

So far, one of the things that has confused me the most was what implication means. Particularly, why P(x) => Q(x) is equivalent to the expression (not P(x) and Q(x)), why it includes the area outside of P(x) and Q(x) and the rest of Q(x) that doesn't overlap with P(x), and why can't P(x) => Q(x) be expressed as (P(x) and Q(x)) since the two expressions mean the same thing.

P(x) => Q(x)

After seeking ample explanations, I finally come to terms with the use of implication vs conjunction:

- P(x) AND Q(x) implies everything in the universe is in P(x), and additionally includes elements that are ALSO Q(x) in addition to being P(x) with no additional associations (i.e. outside of these spaces) 

- P(x) IMPLIES Q(x) means you're acknowledging there are elements outside of P(x), that a subset P(x) exists in universe, and if an element is in the subset P(x) then it's also in Q(x), HENCE the area in Q(x) that doesn't overlap with P(x) is highlighted, and the area outside of both P(x) and Q(x) is also highlighted

I found a good example from Stack Overflow that further clarified this difference:

Q:

Some dogs bark ∃x (dog(X) Λ bark(x))
All dogs have four legs ∀x (dog(x) -> have_four_legs(x))
My question is: is it possible for the second example to be: ∀x (dog(x) Λ have_four_legs(x))
And why can't the first example be: ∃x (dog(X) -> bark(x))

A:

Well ask yourself this: Are implication and conjunction equivalent? No. Your last statement says that all x's are both dogs and have four legs. While that does mean that all dogs have four legs, it also means that everything is a dog.

http://stackoverflow.com/questions/5060247/when-to-use-conjunction-and-when-to-use-implication-first-order-logic 

A lesson on reading comprehension

We're now officially in the final exam period of the semester. Before I write a reflection on the whole semester, I thought I'd first reflect on some of the skills that are not technical in nature but crucial for success in technical subjects that I've come to reinforce through CSC148.

Throughout all of the labs, exercises, and questions we've done in CS, I've realized that none of the exercises are particularly challenging in nature. All of the questions can be solved by applying a concept we learned in class or simply through logic. Their difficulty actually arise largely from a lack of understanding of what it is that the question is asking you to do. In the past when I've been told to read carefully, I've always shrugged it off considering it as a mistake only 'amateurs' can make. From partaking in the labs this semester, I've come to take the advice of reading carefully to heart. There were definitely more times than I'd like to admit where I just stared at a piece of instruction in a lab handout in perplexity, unable to decipher how I'm supposed to approach the problem without a piece of information, only to have my partner point out to me that a paragraph in the beginning of the lab already addressed the lack of that piece of information. I made my own life harder than it has to be.

In one of the exercises involving binary trees (when we were first introduced to trees), the exercise asked us to do some kind of recursion through a tree, and I was immediately overwhelmed having assumed that each mention of 'tree' in the exercise pointed to non-binary trees. Then a friend told me to read the beginning of the exercise, and of course, the exercise specified that we're only working with binary trees.

Reading technical material is different from reading a story. Whereas in a story, your eye recognizes different sentence structures and your brain can interpret the general meaning of passage without taking to heart the weight of each word, in technical readings, each word is crucial to the understanding of the text.

Lesson learned.

Sorting Fun

Sorting. A big area of computer science due to its usefulness in a number of algorithms. Sorting is the process by which the elements in a list are put in a determined order. In selecting the method to sort a list of items, it's important to consider the efficiency of the sort in handling the cardinality, as well as the conditions of the input elements. One sort could be more efficient for a larger-sized input where another sort could be more efficient in handling smaller-sized inputs. On a similar note, a sort may perform better or worse depending on the order that the elements of the list are already in.

In essence, two things occur in a sorting algorithm.

1 - Two elements are compared against each other.

2 - The elements are exchanged as necessary.

Here are two examples of sorts:

Quick Sort

Quick sort is a sorting algorithm that involves recursion. A 'pivot' value is selected and from there on, the list is broken up into two halves where all values bigger than the pivot exist on the right of the pivot, and all values smaller than the pivot exists on the left of the pivot. These sorted sublists are recombined and the sorting algorithm continues until the whole list is combined.

A note on efficiency:

The efficiency of quick sort depends on the pivot that you select, as well as the aforementioned 'condition of the input elements' (i.e. is this list sorted already). If a 'good' pivot is selected, this means the list is split at each step into halves that are approximately equal, then quick sort would perform in the efficient way that is hoped. In contrast, a 'bad' pivot would see the list being split up into uneven parts, in which more work would have to be done in the half that contains more values (in the worst case, you would get one half of size 1, and the other of size n-1). From this, it's easy to see that if a quick sort is run on a list that's already been sorted, if the pivot point that is chosen is the first value of the list, it would be the worst-case scenario in terms of efficiency using the quick sort.

Merge Sort

Merge sort is similar to quick sort in that it also relies on recursion and the splitting of the list into halves. However, merge sort begins by splitting the list into two halves that are of equal cardinality. This splitting continues down to the base case. Along every step of the way, the smaller element is taken between the two lists and joined together. The process continues until the entire list is sorted.

--

In class, we learned about the Big-O notation which goes into conveying the efficiency of the worst-case scenario. Initially I found the concept of the Big-O hard to grasp (because after all, there are so many different algorithms, and so many different ways to implement them, how is Big-O supposed to standardize the expression of efficiency?). From scouring about, I came to learn that essentially, the efficiency of any algorithm can be modelled as a function of its input size. The Big-O notation expresses the worst-case scenario of the algorithm by  extracting the part of the function that causes the function to grow the fastest.

Up until now, my exposure to computer science has mainly been in application. Big-O notation has been in essence the first time I've seen the integration of some real math (and this is only the very tip of the ice berg) with computer science. I hear that Big-O notation is something that is touched upon more in CSC165, but a lot more in depth in second year. It's also in second year that we begin getting introduced to other types of notation, such as Big-Omega for expressing the best-case scenario. It will be interesting to learn more about exactly how an algorithm is optimized to perform efficiently, and through mathematical means.

Week 6 - Toughest week thus far

Last week in class we had our formal introduction to recursion. At the beginning of the course, our prof showed us a sneak peak into the wonderful (with this week's experience I'd attest as mostly horrendous) world of recursion:

def sum_list(L: list) -> float:
    """
    Return sum of the numbers in possibly nested list L
    
    >>> sum_list([1, 2, 3])
    6
    >>> sum_list([1, [2, 3, [4]], 5])
    15
    """
    
    return sum([sum_list(x) if isinstance(x, list) else x for x in L])

That was the first time I'd come across recursion, and after some in depth tracing, I thought I'd figured it out. Through Exercise 4 this week, I've come to experience in full both the wonders and aforementioned absolute horrors of recursion.

In our exercise this week, we were asked to construct a list representation of a binary tree from a preorder list traversal and inorder list traversal (serving as the parameters to the function).

For instance, given:

preorder traversal [10, 6, 8, 12, 11, 15] and
inorder traversal [8, 6, 12, 10, 11, 15]

Our function is to take these two lists to construct:

[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]

Illustrated as follows:




From this, it's evident that preorder traversal traverses the binary tree in the sequence of node, left subtree, right subtree, and inorder traversal traverses the tree in the sequence of left subtree, node, right subtree.

There are a number of inferences that I made first considering this problem.

1. The first value in preorder is the parent node of the tree, thus in inorder, all the values that preceeds the first value described in preorder will be on the left of the parent node, or in other words, they will be in the left subtree.
2. You can guess that the point at which recursion should stop (even before having identified exactly how recursion should occur) is when you get to the leaves, at which point, the [1] and [2] values are None (i.e. these nodes have empty subtrees). That's a hint for the base case.
3. The same kind of recursion occurs for the left subtree as well as the right subtree. There needs to be some way to connect the results of recursion from the left subtree and from the right subtree together in the end.

At the core, to the seasoned programmer, this is really all there is to it. However, since it was my first time working on recursion, this problem confused me profusely.

My first attempt yielded the following result:

def make_tree(preorder, inorder):
    
    if inorder.index(preorder[0]) == 0:
        nested_list = [preorder[0], None, None]
        return nested_list
        
    else:
        tree_list = [preorder[0], make_tree(preorder[1:], inorder), make_tree(preorder[1:], inorder)]
    
    return tree_list

>>> [10, [6, [8, None, None], [8, None, None]], [6, [8, None, None], [8, None, None]]]

As compared to the correct result:
[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]

Alright, so I got the first few values correct, but needless to say, this was incorrect. My idea here was that I noticed on the outmost layer that the first value was the value at [0] of preorder, and the second and third value were nested trees, so I knew I had to have recursion for those two parts. From what I knew of recursion, some 'work' or change has to be made to descend into the next level of recursion, and it logically made sense that the new preorder list in my next level of make_tree would take on the values after the value at [0] (since it was already written down). I didn't know what to do with inorder though, so I just left it there to test.

For the base case, based on #2 of the inferences I made above, I knew the Nonetypes had to be incorporated for those leaf values, but (in retrospect) I was still thinking in my iterative ways, so I assumed the base case to be [preorder[0], None, None]. I saw that the point at which the first element in the preorder list becomes the first element in the inorder list is the point that we've reached the leaves of the tree, hence inorder.index(preorder[0]) == 0.

Because I wasn't 100% sure about how to approach this problem, I put together what I knew and without a full understanding of what I wrote, derived my first attempt.

After having exhausted all of my available brainpower, it was time to get help. After much consultation with a friend that's a much more experienced programmer, I slowly gained intuition of how to choose a correct base case. Attempt 2 is as follows:

def make_tree(preorder,inorder):
        
    if len(preorder) == 0 and len(inorder) == 0:
        return None
    
    elif len(preorder) == 0:
        return [inorder[0],None,None]
    
    elif len(inorder) == 0:
        return [preorder[0],None,None]
    
    else:

            left = make_tree(preorder[1:inorder.index(preorder[0])], inorder[:inorder.index(preorder[0])])

            right = make_tree(preorder[inorder.index(preorder[0]) + 1:], inorder[inorder.index(preorder[0]) + 1:])
            
    return [preorder[0], left, right]

After weeding out the unnecessary elif statements, I finally arrived at the correct code.

def make_tree(preorder, inorder):
        
    if len(preorder) == 0 and len(inorder) == 0:
        return None
        
    else:
        left = make_tree(preorder[1:inorder.index(preorder[0]) + 1],
                         inorder[:inorder.index(preorder[0])])
                
        right = make_tree(preorder[inorder.index(preorder[0]) + 1:],
                          inorder[inorder.index(preorder[0]) + 1:])

           
    return [preorder[0], left, right]

This exercise (part a and b) took me a few hours to complete, and the biggest challenge for me was in trusting that recursion will work. This is where the magical part comes in. If you read the code, it's very intuitive. It makes sense that the same process through each of the subtrees would generate a nested result, that [preorder[0], left, right] gives exactly what it looks like will give. The difficulty in recursion lies in my inability to accept this simplicity. To understand a concept, I must see each step and understand it thoroughly, and so in completely this exercise and other recursion exercises I came across, I always had to trace through the whole code to the base case before I would believe it works.

The biggest challenge for me in the recursion I encountered in this exercise is in knowing how to incorporate the right side recursion of a tree or list with the left side. I seem to always get the left side to 'work', but I can't get my head wrapped around how I should go about the right side.

I thoroughly hope an understanding of recursion will come with practise. For now, I am just ecstatic that I got the desired result for this exercise.