Week 12

A set is countable only when it can be described as a list (because a countable set can be count in a way that is 1-1 and onto). The set of rational numbers, Q, is countable because a 1-1 and onto function can be specified from N --> Q, where N is the set of natural number.

Then, a Cantor's example is showed for the uncountable sets:
"To show that the set of in nite decimals in [0; 1] was bigger
than the natural numbers, Cantor showed that any so-called list
of these numbers would always miss entries" (form slide w12)

A specification of a function is its behavior on every step.

Python functions are countable because every python function can be written in UTF-8, which is out of 256 characters. "Each string can be converted to a different number by treating each character as a digit in base 256. This gives us an onto function from N to the set of python programs".

Then, an introduction of induction is given.
First, we have an assumption for example: P(n) for all n
Then, we get the base statement: P(k) is true
Then, we prove the P(n) => P(n+1) for all n greater or equal to k
Then, we know that for all n greater or equal to k: P(n)

Week 11

This week we learned how to distinguish whether a function is computable or not.
Some functions are not computable because the solutions are infinitely long, and some other functions are not computable because they are just not.

For example,
def halts_or_not(f, I):
      "return true if the function will halt, false otherwise"

This function is not computable. Why?
Consider this function:
def test(f):
      while halts_or_not(f,f):
             pass
      return True

Then halts_or_not(test, test) only halts when it doesn't halt. By contradiction, we know the function halts_or_not is not computable.

Then, the idea of 1-1 and onto is introduced. Two infinite sets have the same size only when they can be matched up in a way that is 1-1 and onto. Here's the definition of 1-1 and onto:

 Then, when |A| <= |N|, where N is the set of natural number, we say A is countable.

Week 10 non-polynomials and big-Omega

When proving functions about non-polynomials, we prove the function using l'Hopital rule and limit as we learned last week.

Then, the definition of big-Omega is similar to the definition of big-oh except for just one character:

For big-Oh, it's a function bounded above and big-Omega is a function bounded below. So for a function in both big-oh and big-Omega, we have:

Then we also had some examples of proofs, and you can find them in slide of week 10.

Week 9

This week, we had some examples of proving a function is in O(another function).
For example, to prove a function is not in O(n square), we need to prove:

And to prove a function is not in O(n square), we need to prove the negation of the above expression.

This is the way to prove polynomial functions.

Then, we know logarithmic functions are in big-Oh of any polynomial, whereas exponential functions (with a base bigger than 1) are not in big-Oh of any polynomial.
So, to prove exponential function is not in big-Oh of n square:

Week 8 More asymptotics

As we learned last week, we are counting the steps in the worst case of a function.
For big-oh of n square:

Week 7

The first thing we learned this week is how to prove a claim false.

For example:

           Claim: all x in X, all y in Y, P(x, y) => Q(x, y)

           To prove this claim false, we can prove: {all x in X, all y in Y, P(x, y) => not Q(x, y)} or                   {exist x in X, exist y in Y, not( P(x, y) => Q(x, y))}. But we cannot prove {all x in X, all y in                Y, not(P(x, y) => Q(x, y))}.

Then we learned some allowed inference. By these inferences, we can have faster ways to prove or disprove claims.

These are some examples of inferences, and there are actually more inferences that can be found in slides of week 7.

Different sorting strategies have different efficiency, which is the speed of a function that ignores hardware, programmer virtuosity. The speed we count is in the worst case in the course CSC165.

Week 6 Different kinds of proofs

This week, we learned many different kinds of proofs. Like non-boolean proof, limit proof, and proof for a sequence and also prove by cases.

To prove or disprove a statement about sequence, we just use the skills we learned in last week. But for proving non-boolean statements, we learned some new skills. We are use the non-boolean functions and we can also break down the functions to make it more precise, and then we can only use part of the functions.

Then, we can also proof a statement by cases. If a implication can be true in several different conditions, then we need to prove each of the conditions to show the implication is true. And for some "or" statement, we also need to prove it by cases. For example, there's a general format in notes: