Week 10: Big-Omega, big-Theta, general properties

big-Ω proof
similar to big-O proof but
choose Magic Breakpoint B = 1,
then we can assume n ≥ 1
under-estimation tricks
➔ remove a positive term
◆ 3n² + 2n ≥ 3n²
➔ multiply a negative term
◆ 5n² - n ≥ 5n² - nxn = 4n²
over-estimation tricks
➔ remove a negative term
◆ 3n² - 2n ≤ 3n²
➔ multiply a positive term
◆ 5n² + n ≤ 5n² + nxn = 6n²

big-O proofs for general functions
1.If f grows no faster than g,
and g grows no faster than h,
then f must grow no faster than h.
2. nobody can write halt(f,n)
3. Reductions
If function f(n) can be implemented by
extending another function g(n),
then we say f reduces to g
def f(n):
 return g(2n)
g computable f computable =>
f non-computable g non-computable

Week 9: Big-Oh of polynomials, non-polynomials, limits

exercises of big-Oh proofs
 To prove polynomials: it’s all about picking c and B
   ➔ tip 1: c should probably be larger the
   constant factor of the highest-order term
   ➔ tip 2: see what happens when n = 1
   ➔ upper-bound the left
   side by overestimating
   ➔ lower-bound the right
   side by underestimating
   ➔ choose a c that connects
   the two bounds
To disprove, we prove the negation is true!
summary
➔ the ways we talked about of picking c and
B, the main point of them is that we know
how to show the bounding relation when
picking in these ways.
➔ these are not the only ways, you can be
more flexible when you are more familiar
with these types of proofs.
➔ In general, larger c or larger B don’t hurt

 prove big-Oh using limit techniques
to prove non polynomials we use limits - limit = infinity defined by
for all c in positive real number, there exist n' in natural number, for all natural number n bigger than n', the limit > c.
we take the limit of the f(n)/g(n) when evaluating f(n) in O(g(n)) for example, use limit rule above to show fn>cgn (fn/gn > c)
use L'Hopital's rule
lim fn/gn = f'n/g'n

Week 8: Counting steps, worst-case, formal big-Oh

Some others things about proofs
proof for statement with multiple quantifiers
∀x ∈ X, ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q
      assume generic x ∈ X
          pick some y ∈ Y
              assume generic z ∈ Z
                  pick some w ∈ W
                      assume P
                           …
                           then Q
                      then P => Q
                  then ∃w ∈ W, P => Q
             then ∀z ∈ Z, ∃w ∈ W, P => Q
         then ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q
     then ∀x ∈ X, ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q

How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

When the statement seems kind-of trivial but 

proving directly looks messy

➔ try contradiction

Back to Algorithms

formal definition of O, Ω
a function f(n) is in O(n) iff there exist c in positive real number, there exist B in natural number, such that for all natural number bigger than B, f(n) less or equal to cn. (f(n) grows slower than n)
➔ when finding upper-bound, it is OK to
over-estimate the number of steps
a function f(n) is in Ω(n) iff there exist c in positive real number, there exist B in natural number, such that for all natural number bigger than B, f(n) greater or equal to cn. (f(n) grows faster than n)
memorize the formulas! 

➔ when finding lower-bound, it is OK to
under-estimate the number of steps

Week 7: Sorting algorithm complexity, big-Oh

Now moving past the basics of proofs, we are getting into an interesting field of CS finally!
Sorting Algorithm Complexity! RUN FOREST RUN! oh, I mean Run Time Calculation.

BUT FIRST, let me take a selfie!
I mean go through what we had no time last lecture

Proof by cases
1) Split your argument into differences cases (make sure all cases together in disjunction is a tautology)
2) Prove the conclusion for each case

The famous example:
If you have a problem in your life
Case 1: You can do something about it
~ don't worry
Case 2: You can't do anything about it
~ don't worry
You can do something OR you can't do anything is a tautology
Conclusion ~ don't worry

Uniqueness
If m and n are natural numbers, with n NOT 0
then there is exactly one pair natural numbers (q,r) such that
        m = qn + r
divide m by n, the quotient and remainder are unique

NOW Algorithm analysis!
Worst Run Time - the maximum number of steps the algorithm will execute on input size n - O(something n)
1) But we don't really care about the number of steps, what we actually care about is how the number of steps grows as the size of input grows - that means, we don't care about the absolute number of steps, hence 0.5n^2 and 700n^2 are NO different. Constant factor does not matter!
2) we care about large input sizes, that is when n is very large, so n^2 and n^2+n+2 are NO different. Only the highest order term matters

O(f(n) is the asymptotic upper-bound
~The set of functions that grows no faster than f(n)

Best Run time - the minimum number of steps the algorithm will execute on input size n - Omega(n)
similar idea!

QUICK NOTE
In CSC165, sometimes we use asymptotic notations such as O(n²), and sometimes, when we want to be more accurate, we use the exact forms, such as 3n² + 2n. Depends on the question asked.

To find the exact forms, we need to examine the function......

Week 6: Cases, multiple quantifiers, limits

Proof about non-boolean functions
Boolean function - a function whose return value is True/False - example x>5
Non-boolean function - not a function of such as above - example x^2
Floor for x - the largest integer that <= x
Steps to proof one is correct
1) fully understand the definition
2) breaks the definition into predicates
3) play around with those predicates
4) proof!

Proof something false
To disprove a statement S, just proove NOT S
1) negate the statement properly
2) prove the negation

Proof by puns (SERIOUS PROOF)
A cow have four more legs than no cow.
No cow has five legs.
Therefore, a cow has nine legs.

Proof by intimidation (ALSO VERY SERIOUS TECHNIQUE)
Trivial!!!!!
or
Don't be STUPID, of course it's true!

Proof by intuition (WHO DOESN'T)
I have a dre... I mean I believe....!

Proof by clever variable choice (BE SMART ABOUT IT)
Let A be the number such that this proof works...

Proof by hasty generalization (WELL IF IT WORKS IT WORKS)
Well, it works for 17, soooo~

Proof by tautology/begging the question (FOR ALL THE BELIEVERS)
God exist because the BIBLE said so!

Proof by convenience
It would be nice if it were true, so.....

Proof by beautiful typesetting (...Yea)
Because the proof looks good and is typed in LaTex...

Proof by *%^*% (Can't read)
I^$#%&*^$&^#

Proof about limits
OK I am done with limits, so they are like out of my limit...
but I will say this
Wise choices are often found by backward search
DON"T freak out unnecessarily!

Week 5 Term Test ~ Contradiction, existence, sequences

Proof using contrapositive

the proof for P IMPLIES Q also proves NOT Q IMPLIES NOT P, and vice versa

Hence we can prove P IMPLIES Q by proving its contrapositive 

Use when the reverse direction is easier to prove than the original

Proof using contradiction

Assume predicate logic P, then by P and some axioms we come to a contradiction, hence NOT P

Proof for existence

Find a single example, show the predicate logic applies

Proof about a sequence

It is not much different as proving a regular expression, the key is to take the sequence definition as predicates, often works better if you write out the first 10 terms of the sequence to visualize it.

Week 4 Bi-implications, Transitivity & Mix quantifiers

Review 1:  P IMPLIES Q is equivalent to NOT(P) OR Q
WHY?
For P IMPLIES Q to be true, we must have either Q being True or P being False;
i.e they have the same value on the Truth Table

Review 2: NOT(P IMPLIES Q) is equivalent to P AND NOT(Q)
WHY?
For NOT(P IMPLIES Q) to be true, we must have P being True while Q being False

Bi-implication: P IFF Q
This is the combination of P if Q and P only if Q, hence, P if and only if Q
in other expressions: (P IMPLIES Q) AND (Q IMPLIES P)
or: (NOT(P) OR Q) AND (NOT(Q) OR P)
or: (P AND Q) OR (NOT(P) AND NOT(Q))

Negation: (P AND NOT(Q) OR (Q AND NOT(P)); the negation of (P IMPLIES Q) AND (Q IMPLIES P)
PROOF: By demorgan's laws, distributive law, and identity law
P XOR Q- P or Q, but NOT both

Transitivity:
Note 1: If P IMPLIES Q, all Q are in P
Hence, (P IMPLIES Q) AND (Q IMPLIES R) means Q is in P, R is in Q, therefore R is also in P, that is
P IMPLIES R
PROOF: By contradiction

Mixed Quantifiers
Note: if all quantifiers are the same, the order doesn't matter
Otherwise, it does

Class example:
For every woman, there is a man who is her soul mate. (the man can be different for each woman)

vs

There is a man, every woman is his soul mate. (the man is the same man for all woman)

Throw Back Lecture 1.1

Prove the statement “A being true implying B being true implies 

C being true” is true if and only if either A is true and B is 

false or C is true.

Prove

(A IMPLIES B) IMPLIES C      IFF      (A AND NOT(B)) OR C

1. (A IMPLIES B) IMPLIES C

2. (B OR NOT(A)) IMPLIES C

3. NOT(B OR NOT(A)) OR C

4. (NOT(B) AND NOT(NOT(A))) OR C

5. (A AND NOT(B)) OR C

1 = 5

PROOF

WHY PROOF? - It is important for ... science!

WHAT IS PROOF? An argument that can convince robots! logical, careful and precise

HOW TO PROVE?

1. Find a proof - understand the problem, be creative, understand your own ideas

2. Write up the proof - carefulness and precision

direct proof of universally quantified implications

Find direct implications/equivalences from P(x) to Q(x)

How to be good at proofs? PRACTICE

Follow Polya’s problem solving scheme

◆ understand the problem

◆ devise a plan

◆ carry out the plan

◆ look back

◆ acknowledge when, and how, you’re stuck

Week 3

Here are what I learn in week 3...

Conjunction (AND, ∧) noun
“the action or an instance of two or more
events or things occurring at the same point
in time or space.”
To put this in perspective, P(x) ∧ Q(x) means
1)P(x) intercept Q(x)
2)P(x) = True and Q(x) = True
3)The interlocked part of the circles on a Venn Diagram of P(x) and Q(x)

Disjunction (OR, ∨)
"Combine two statements by claiming that at
least one of them is true."
To put this in perspective
1)P(x) union Q(x)
2)P(x) = True, Q(x) = True, or P(x),Q(x) both equal to True
3)Both circles of the Venn Diagram of P(x) and Q(x)
If you want to mean P(x) or Q(x) but not both - that's exclusive-or!

Negation (NOT, ¬)
NOTHING fancy about it, get it?
Literally mean NOT
BUT, you can move a negation further into a bracket by changed the universal quantifier into existential quantifier and vice versa
example:
1)NOT(all Koreans are good at playing League of Legends) = there exist a Korean who is NOT good at playing league of Legends
2)NOT(there exist a chicken who loves eating dog) = all chicken NOT love eating dog.

Parenthesis
1) they are important - you basically need them for every connectives you have (conjunction, disjunction, implication, etc)
2) what happens in the parenthesis stays in the parenthesis (you are have two xs in two parenthesis and they won't mean the same thing)

Truth Table
"Enumerate the outputs over all possible
combinations of input values of P, Q" - and how many other variables you have.
In this case
Input = either True or False
P, Q... are all predicates
You draw a table, where your predicates are in the first few columns, and the predicate logic you want to check are in the following columns.
Now base on the combination of True and False of your variables, you check whether the predicate logic involving those variable are True or False.
It has as many rows are 2 to the power of the number of predicates you have.
1) If a column is all True, then the predicate logic is a tautology
2) If a column is all False, then the predicate logic is unsatisfiable
3) Otherwise, it is satisfiable
4) If two column have the same truth values, then they are equivalent

De Morgan's law
Basically, if you have a negation of a conjunction, NOT(P AND Q)
                                      it can be turn into NOT(P) OR NOT(Q)
similarly NOT(P OR Q) is equivalent to NOT(P) AND NOT(Q)
*Note, you just break the bracket, apply negation to both elements, and change AND to OR

Laws 
*For a full list of laws to be used in CSC165,
read Chapter 2.17 of Course Notes
But for those who want to know some
Conjunction and disjunction have the following laws
1) commutative - P AND/OR Q is equivalent to Q AND/OR P
2) associative - where put the bracket is not important for the same sign
3) distributive - P AND (Q OR R) is equivalent to (P AND Q) OR (P AND R)
4) identity - P AND NOT(P) is False, P OR NOT(P) is True
5) idempotent - P OR P, P AND P are equivalent to P

This is all from week 3.............. a little shorter than last week?

Week 2

Ok, to actually make use of this blog thing, I will make it into my review notes, starting..... now!
From last week we learned ...
Universal quantifier: ∀, “for all” (∀x means - for all x) literally
Existential quantifier: ∃, “there exist"(∃x means - there exist a x) literally
Hence....
NOT ∀x means not all x, and
NOT ∃x means there exist no x.

Quantifiers are followed by predicates (P,Q,R,P(x),Q(x),R(x)) or conditional (P IMPLIES Q), so they makes sense this this way...
∀x, P - for all x, P is true
∃x, (P IMPLIES Q)  - there exist a x, where (P IMPLIES Q) is true

This week.... Visualization with Venn Diagram
Venn Diagram, invented by Venn, is (for now) two interlocked circle within a big rectangle.
The rectangle symbolizes the background set, all the elements required by the predicates and more.
Each circle represents a predicate.
The interlocked area represent where both predicates are true.
Hence, we can use the Venn diagram to represent relations between any two predicates EASILY!
Say X mean false, O mean true, P and Q are predicates, z are background data.
X in P means no z JUST in P, it could be in both P and Q though
O in P means there exist z in P
X in the interlocked area means no z is in both P and Q
O in the interlocked area means there exist z in both P and Q

Now about set relations
1) set can be empty - null
2) A union B - A, A and B, B
3) A intercept B - A and B
4) A is a subset of B - all x in A are also in B
5) A is not a subset of B - there exist some x in A that are not in B
6) NOT A - B, other xs

Differences between sentences and statement - statement is a quantifiable sentence, thus can be evaluated to be true or false. Questions are obviously not statements.
Predicates are symbolized statements - P(x) = x wants to be my friend, for example
We can quantify predicates with quantifiers - ∀x, P(x) = everyone wants to be my friend, you see?

Now we are ready for implication
If P, then Q is the same sentence as P IMPLIES Q. P is the antecedent, Q is the consequent
But here the trick is , for P IMPLIES Q to be true, we just need to not prove it false.
                                                    The only way to prove it false is when P is True yet Q is False.
In all other cases, P IMPLIES Q is considered true.
Furthermore, just because P IMPLIES Q, does NOT mean Q IMPLIES P, i.e. the converse of P IMPLIES Q is not true. (NOT Q IMPLIES NOT P is true though, this is called the contrapositive)
Simple example.
If I love you, then I will make you breakfast.
This also means - If I don't make you breakfast, I don't love you.
But this doesn't mean - if I make you breakfast, then I love you. That's absurd! See?

Now, vacuous truth...
Remember how I said "for P IMPLIES Q to be true, we just need to not prove it false.
                                                    The only way to prove it false is when P is True yet Q is False"
Thus when P is never gonna be True, the statement P IMPLIES Q is vacuously True!

Equivalence! is equivalent to - if and only if
Before we go that far, let's look at what only if means - only if P, then Q
This means 1) P is the only condition where Q is True, which means 2) if Q is true, P must also be true
e.g. Q IMPLIES P
Hence only if is the reverse implication of if!
If P then Q - P IMPLIES Q (P is the sufficient condition for Q)
Only if P then Q - Q IMPLIES P (P is necessary condition for Q, not necessarily sufficient!)
*Quick Note:
Q if P = If P then Q,
Q only if P = Only if P then Q.

Now, what's If and only if P then Q?
P IMPLIES Q and Q IMPLIES P, hence it is P = Q in predicate logic sense

Something weird...
If both P and Q are always False, in the same way as before, we can't prove - that when P is True, Q is not, NOR when Q is True, P is not. Hence P if and only if Q is considered true!

This is all from week 2........................................Finally'

Week1 Standard Format

{ what's something new you learned this week in class?
Really want to answer honestly ~ nothing, because CSC240 ruined my life.
But hence I also know the point of this, I would say that I learn
1. CSC165 is the base of all math for computer science, which is the base of mostly everything else in computer science
2. We need to be interested in the course to do well
3. Computer code needs to be super precise
4. How to solve a problem
        understand - plan - carry - review
5. Universal quantifier (For All) and existential quantifier (There Exist)

{ what's something you enjoyed this week in class?
The professor is REALLY funny, because he uses memes correctly
Which IS really important for me because that's how I can sit through a 3 hours long class starting at 6pm on a Tuesday night

{ what's something that challenged or frustrated you this week?
NOthing, I am God (jk, 240 ruined my life)

{ how confident do you feel about material covered this week?
VERY

{ how does course material relate to other classes or interests?
I love logic, philosophy for the win, PHL245.

{ what was one of your achievements this week
Met a new friend, his name is Sue Yong, like he is gonna sue me, if I call him So Yong

{ how did your tutorial/test/assignment go this week?
Didn't happen, sorry, nothing interesting here to say.

A math problem...
John is twenty years younger than Amy, and in
five years' time he will be half her age.
What is John's age now?
ANSWER: 15
LOGIC: 2x+20+10=2x+30=3y, x+5=y, hence, x = 15, y = 20

Another math problem...
Let A, B, and C be three statements.
The statement “A being true implying B being true implies C being true” is true if and only if either A is true and B is false or C is true.
Is it true?
(A -> B -> C) <-> A and NOT(B) or C
ANSWER: FALSE
LOGIC: if A is true and B is false, then A being true implying B being true is false also