Week 7 and 8 - Big OOOOOOOOOOO

For the last two weeks we have been talking about a brand new topic - algorithm analysis and big O. What do we want from these complicated stuff? We want to see how our program runtime depend on our input sizes, what if the input size grows really large, how would our program run time fare up? 

Ideally, we want our program to run as fast with a small input as with a huge input, and to eliminate the cases that it grows exponentially, therefore, we must come up with a way to measure our program runtime. It is called big O.
Because we can generate an approximated runtime formula from our code, we can calculate the level of growth it has, for example x^2 + 100x +5, we can try to think what would happen if the input size x is really huge, almost if it is approaching infinity. If we set lim x->inf, the 100x and 5 hardly matters compared to x^2, they matter so little that in high school calculus we simply eliminates them. This is also how we handles it here, the function we had grows at a level of x^2, it would not grow much faster or slower compared to it, so we dubbed it O(x^2) and Omega(x^2), and if a function belong to both O and Omega, we call it theta.

A precise definition of big O is 

that if we can choose a multiplier and a breaking point so that a function f upper bounds our function g after that point, our function grows no faster than f, It is big-Oed by f.
for Omega, we just have to change the <= sign to >= sign.
When we estimate the runtime of a function, we do it by evaluating the runtime of the inner loop first,  then come out one by one, we can slightly overestimate when we are trying to find big O, because if the over-estimated runtime doesn't grow faster than a function, our original sure doesn't. The opposite goes for Omega, we underestimate the runtime so if our underestimation grows no slower than f, our original which grows >= underestimation definitely grows no slower than f.

Folding

It is a fine autumn dusk, I am sitting in a knowledge-filled hall in an old, prestigious university, holding a piece of paper, titled

Folding

folding is an interesting problem, I've played with papers when I was little, and folding them seemed so fun, until I dive into patterns. The task of folding is basically to fold a paper...... and generalize a pattern of creases.

*This is to present a different explanation to the one we talked about on class, which involves recursion, in "an up becomes ^^v, and down becomes vv^"*

The pattern wasn't hard to observe, we called a ^ an up, a v a down. Basically, the pattern is, if you count left, right, in-between as spaces, if you fold it again, the spaces are filled with up, down, up down, up down sequence.

CSC165 - Week Five and Six - Test & Proof

Did not create a blog post cuz there was a test,

Tests are always like bombs, right?

We talked about all kinds of proofs, but that's not the focus...

The test is.

Okay, the test wasn't that hard, it feels more like a 'welcome to university, see? you can do well' test, the class average is at 80%+, which is a very generous mark, even when compared to some of my high school tests *cough* that averaged at 60%.

Proofs are the primary indicator of the rigorous part of mathematics and computer science theories, they are the foundation to every theorem we use today. In a short sentence, Proofs are to be written in a completely sealed format, variables are declared and initialized in the front, assumptions are made, deductions are written indented after the assumption, the structure of proof can be easily related to...

REDDIT!

Like every discussion thread, a proof looks like a completed indented block.

We also learned contrapositive proofs and proofs by contradiction, and touched on limit.

Contrapositive proof:

Biggest hint to contrapositive proof: contrapositive and original is equivalent

wtf is that a hint? Yes, that means proving contrapositive equals to proving original, ... Oh yea cause they are the same. When proving contrapositive is easier than proving the original, using contrapositive proof is a really smart approach.

Proof by contradiction:

This is harder to comprehend compared to other proofs, basically in this one P => Q you assume Q to be false, then by smart manipulation you get Q is true, which contradicts Q is false, which means Q must be true.

Proof something is false == proving its negation to be true, using above methods.

Limits:

Greek..

epsilons and deltas are like nightmares that never goes away, we defined limit in a rigorous sense, for every little distance to f(x), there must be a little range from x that if x is inside that range, f(x) is inside its boundary.

To prove limit, we have to write out the actual delta epsilon equations, and by manipulating the epsilon part, we seek to get ourselves some delta, so that we can see how small the delta should be so that epsilon is satisfied, usually the value of delta is related to epsilon.

CSC165 - Week four - Bi-implications, Transitivity, Mixed Quantifiers, Proof

It's the fourth week into my university journey, and 1/3 into the semester, who would have believed that?
In this week's lecture, we learned bi-implication, transitivity, mixed quantifier and proof.
Bi implication is just a two-way if...then statement.

P(x) <==> Q(x)

 We turned it into a conjunction of two disjunctions

not P(x) or Q(x) and not Q(x) or P(x)

, and a disjunction of two conjunctions.

not P(x) and not Q(x) or P(x) and Q(x)

We looked at transitivity, which means when p is related to q, and q is related to r, then p is related to r. We learned that transitivity is always true by reducing its negation to a contradiction.

((P=>Q)^(Q=>R)) => (P=>R)

neg= (P=>Q) and (Q=>R) or not(P=>R)

=(not P or Q) and (not Q or R) or (P and R)

which is a contradiction

Next up we talked about mixed quantifiers, and how when we mix two different quantifiers, the statement's meaning is twisted when we change the order of the quantifiers. 

for example:

let x,y be real numbers,

1) for all x, there exists a y, y>x

2) there exists a y, for all x, y>x

these two sentences have the same quantifiers, but because we

changed the order of the quantifiers, they mean different things.

1) for every real number, there is a bigger number

2) there is a real number greater than all other real numbers

obviously we can see that statement 1 is true and statement 2 is false,

the only difference is the order of the quantifiers

We finished the lecture by talking about proof, proof is an extremely important concept in science, nothing is to be believed until its proven.

a proof can be worked top-down or bottom-up, and if we can connect some statement like linking some nodes and connect top and bottom, we can prove it.