Reflection on Proof-Writing in general

I wasn't really comfortable with proof-writing until I went through the assignment. I did the test shortly after and felt really good about it, so I think I learned well. The thing I found most challenging was managing multiple variables and trying to make sense of them together. For example, if a statement starts with "for all x in R, for all e in N, there exists a d in R+" or something. (I also realized that the unfamiliar greek symbols make a problem seem way more difficult than it actually is.)

I think that the best way for me to tackle this problem is to try and break apart the different declarations into separate pieces of information, and use number lines when needed to make comparisons.

Sorting Algorithms

I've done a lot of sorting algorithms work from CSC148, so it was interesting to get to look at those algorithms in greater detail in this class.

I thought this link was really cool:
http://9gag.com/gag/aPyoG4P

You'll see that the image includes insertion and selection sort. It also provides a good representation of why best-case (nearly sorted) analysis isn't very helpful, since most algorithms finished that very quickly.

Geometric Mean Problem

This week, I wanted to try to solve on my own one of the problems we didn't go over the solution for. This is from a couple of weeks ago:

"Prove that for every pair of non-negative real numbers (x,y), if x is greater than y, then the geometric mean, sqrt(xy) is less than the arithmetic mean, (x + y)/2."

y < x
0 < (x - y)
0^2 < (x - y)^2
0 < x^2 - 2xy + y^2
4xy < x^2 + 2xy + y^2
xy < (x+y)^2 / 4
sqrt(xy) < (x + y)/2

I'm not comfortable enough yet with proof structures, but there's the math! This sort of algebraic problem-solving I find really fun.

Reflection on the Term Test

I thought the test was really easy after finishing, and my test results agree with my feelings. I finished the test 10-20 minutes early and got to sit there for a while. I think the reason the test was easy was because it was basically the exact same thing as the past test. I hope that the next test will hold this pattern.

Enemies and proofs

I had some trouble understanding the whole enemies analogy for explaining statement analysis. I understood pretty easily that it mattered what order the for all and there exist clauses were placed in, but I didn't understand how that related to the idea of an enemy choosing. For that reason, I initially couldn't do that part of the past test where we had to analyze a lengthy statement and its negation and choose which one was correct.

How I've come to understand it (and I'm not sure if this is correct) is equating "there exists X" to "I choose X" and "for all Y" to "my enemy chooses Y". If my interpretation is correct, here's why: for all clauses are selected by the enemy because proving a proof entails showing that it holds true not in any case, but in the worst case. We can rely on our enemy – the devil's advocate who will choose the worst case in order to prove us wrong – to reliably represent the for all clause. By contrast, we are allowed to choose there exist variables because there is a lot more flexibility in what those variables can be (since there only needs to exist one example). So, we needn't an enemy to choose the worst case for that.

The paper folding problem

I thought this was a really cool exercise, and I'm glad I figured out a deterministic set of instructions. I took some time after class to translate these instructions into a python program, which I've included as follows:

def pattern(n):
    if n == 1:
        return 'D'
    return rotate(pattern(n-1)) + "D" + pattern(n-1)

def rotate(pattern):
    result = ''
    for ch in pattern:
        if ch == 'D':
            result = 'U' + result
        elif ch == 'U':
            result = 'D' + result
    return result

Program testing showed results that matched up with the originally recorded results:
>>> print(pattern(1))
D
>>> print(pattern(2))
UDD
p
>>> print(pattern(3))
UUDDUDD
>>> print(pattern(4))
UUDUUDDDUUDDUDD
>>> print(pattern(10))
UUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDUUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDUUUDUUDDDUUDDUDDDUUDUUDDUUUDDUDDDUUDUUDDDUUDDUDD

Natural language and symbols

As we learn about symbolic notation, I'm finding it really interesting to think about how I communicate in english.

A really interesting word was "unless." X unless B translates to X if not B, according to the slides.
if (not X):
B

"Unless you can pay, don't touch that" would translate to the following:
if (not ableToPay):
do not touch

I think that making conversions like this really helps my understanding of what these different words mean, and how to interpret natural language sentences into precise "math language."

Another interesting set of words are "and" and "or." Let's do some more natural language conversions!
- I am part of math club AND science club
=> I am (part of math club) AND (part of science club)

But what about the following:
- Members of the math club and the science club can attend the fair.
So in this case, converting it to symbolic notation with an "and" would not be true to the intended meaning. In actuality, one would use an "or" in order to be precise, since the statement is attempting to say that both clubs' members can come. I wonder if our normal english language use should adapt to this precision.