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