Countable and Uncountable

On week 9, we learned how to determine whether a set is countable or uncountable. A set is countable if and only if it is listable. For example, rational numbers are countable because they can be listed. Also, the number of elements that a countable set has is no larger than the size of natural numbers. Interesting enough, the size of even natural numbers is equal to the size of natural numbers.  However, the size of real numbers between 0 and 1 is beyond the size of natural number. No matter how you list them, I can find a number that does not appear on your list. This means that the real numbers between 0 and 1 are not listable, therefore they are uncountable.

Computable and Non-Computable

There was a fall break on week 11, so we had only 2 lectures on that week. We learned the difference between computable and non-computable. If f is a well-defined function and we cannot compute f(x), then f is non-computable. Otherwise it is computable. Also, we can use reduction to prove a function non-computable.

Big-Omega and Theta

On week 10, our professor introduced big-Omega and theta. We tried to solve more complicated examples. For instance,  ∀f, g ∈ F, f ∈ O(g) => g ∈ Ω (f) is a typical implication about big-Oh and big-Omega. When the proof is getting longer, the structure becomes very important. The steps we write should be clear and every line needs to be explain in detail.

Proof and Disproof of Big-Oh Statements About Polynomials

On week 9, we learned how to prove and disprove big-oh statements about polynomials. To disprove an big-oh statement, the trick is that we need to negate the statement and find an n which  consists with B and c. In some case, we have to use limit and L'Hopital's Rule in order to pick a correct n.

Big-Oh

On week 8, our professor introduced the concept of Big-Oh. However, I missed Monday's lecture because I went to a wrong classroom. I noticed I was in a statistic class after class began. I was too shy to get out. At least, I understood what that professor said and I thought I learned that kind of things in data management course in  high school. I was smart enough to understand the annotated slides on course website, but I was pretty sure that I missed something on Monday. That might be very important...

Inference and Counting Lines

On week 7, we summarized some rules of inference. I was familiar with them because I had used them for several weeks. After that, our professor introduced some basic sorting strategies and explained how to count lines or steps with his example of linear search.

I did not use the way I learned to count steps on the quiz because the numbers were small and I thought to count directly was more efficient. But I wouldn't do it again anyway because I did not get full mark.

Proof by Case and Disproof

On week 6, I learned how to split a statement and prove it step by step. It is an useful technique to solve some problems. Later on, we covered the concept of disproof. It was about proving a claim false. To do so, we first negate the claim, then we prove the negation true. We only had 2 lectures due to the Thanksgiving Day.