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: