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