Week 11

We finished the topics of proving and disproving Big Oh, Big Omega, and Big Theta from last week.

This week's contents:

1. Algorithm  
2. Some terminologies (new vocabularies) 
3. Reduction 
4. Infinite does not always equal to Infinite
5. 1 - 1 and onto 
6. Countable

First of all, most of us interested in computer because we want to solve problems in a systematic and logic ways. Enable for our devices to implement our solutions/programs, it will need algorithm to perform the tasks. Algorithm is defined as sequences of executable steps. Alan Turing,  a British computer scientist, who was widely known for his concepts of algorithms and computations, invented the first general purpose computer model which is called Turing machine. Moreover, Turing came up with the proof that there would be uncomputable problems  on any reasonable computing models/devices. In modern times, we realized that even using different modern programming languages, such as Python, C++, Java, and etc., to implement the problems would not work.

Secondly, we learned some new terminologies from following example.

 

Computable: a program/problem that can be solved by algorithms. 

Noncomputable: a program/problem that can't be solve by algorithms. 

Following, reduction was introduced. Let's start with an example: assume I know function f is non-computable, but I was given well defined function g. What I can do next is to extend (by adding some extra executable steps) the function g then build function f, which this step can be shown as an implication ( g computable => f computable). Next, we say f reduces to g, using the rule of contrapositive (not P => not Q), which we have f non computable => g non computable.

Next,  infinite does not always equal to infinite. Here's the reason why,  sets A and B have infinitely many items if they each have more items than any finite number. However, having more than any number isn’t the same as saying they have the same size as each other.  Basically, it means two sets (either finite or infinite) have the same size (same amount of numbers /items). By matching them up(by counting) in two ways ( 1 - 1 and onto). 

Furthermore, 1 - 1 and onto are terms that we use when we describe a function. 

In  1 - 1, it simply means that no two elements in x are mapped to the same element in y. 

On the other hand,  the term onto means when every element in y is covered (even if there is/are extra value(s) in set X. Additionally, there is also an occasion which we call correspondance when onto and 1 - 1 both exist in the case.  

Lastly, we were introduced with Cantor's diagonal proof, commonly known as diagonization. By doing a diagonal proof, it allowed us to know the fact that not all sets are countable. All rational numbers are countable. All real numbers are not countable. (More details were introduced in week 12).

Week 9

This week nothing new was taught really because we did our term test on Wednesday, which I believed I did quite poorly on it... (need to work harder)

Anyway, due to the test, so we spent this week on proving and disproving more Big Oh, Big Omega, Big The Theta examples/statements,  just so we could get more familiar with methods to solve these type of questions and also memorizing the individual definition of Big Oh, Big Omega, and Big Theta.

Week 10

This week we ended the topic about analyzing bounding a sort and linear search. We focused on proving the worst cases (both upper bounds and lower bounds). More importantly, I have finally understood how to analyze (finding steps) of codes during the tutorial section with Jason.

Following picture was an example that we did in tutorial section:

Furthermore, we did some proof exercises:
During the lecture, we were given an example of big Oh. 

In this case, n^2 was the function.
f : N -> R^>=0 : the function that takes in a natural number and return a non-negative real number.
The rest of the function basically told us that n^2 or f(n) was upperbounded by cn^2 (beyond the breaking point B).

Next, we learned to disprove this Big Oh example by negating it then proving it true.
So the negation of n^3 <= c3n^2 to n >= B and n^3 > c3n^2.
We chose a value for n, but before that we have some logical steps to write down.
We broke n^3 down into n times n^2. Since n^3 > c3n^2, then we could comment that n > 3c so n^3 > c3n^2 was true. Now, we introduced ceiling. Ceiling was a symbol that had the opposite meaning of floor. When we used floor, for example, floor 3.249 ( a random number I picked) then we got the answer of 3 because floor meant the largest integer that was less than or equaled to x. On the other hand,  ceiling 3.249 then we got the result of 4 because ceiling meant that we rounded up the number in the first digit by 1. Therefore,  we came up with the result that n >= ceiling 3c + 1 and n > 3c at the same time. Then we got n >= B and n^3 > c3n^2.

In addition, Big Omega was introduced, which we were given with this example.

As you could noticed, this example was very similar to the Big Oh example. There were two differences, first one was that we changed the symbol of Big Oh (O) to the symbol of Big Omega (Ω) and second one was that we changed from ≤ to ≥ between f(n) and c(function - differed in different cases)

Following, we were introduced with a new bound, which it only happened when the functions were bounded above and below by the same function. 

 

In this case, we combined two concepts into 

 

Last,but not least we were introduced how to prove a non-polynomial example.

General procedure of solving: 

1. Prove the limit of using some rules we learned in calculus. For example, L' Hospital Rule 

2. Translate the limit into its definition with c and n' 

 

3. Relate this definition to the definition of Big-Oh.

then we got

Week 8

In the lectures of this week, we expanded bit more on the analysis and proof of worst cases. Also, the second term test would happen next week on Wednesday on proofs of various claims. I would be preparing for it by redoing some examples that we did in lectures and also the past test from last year.

Next, on previous week, we mentioned briefly about why we as computer scientists cared about worst speed. This week, we expanded a bit more on proving worst cases.

First of all, we started with linear search.

 

In the example above, we tried to find the running time of this code by counting steps. We wanted to idealize time of counting the number of steps for a given input. 

Worst Case - Upper Bound and Lower Bound:

 

Upper Bound and Lower bound of a program:

1. tp(x) stood for the time that required to count the steps of the program.

2. C stood for a constant value.

3. B stood for a break point (what we used to determine whether the tp(x) was upper bounded or not. 

U(n) = n^2 because 

U = n, so n(n) = n^2

Therefore,  we could conclude that tp(x) was upper bounded by cn^2 and tp(x) was also lower bounded by cn^2. 

In conclusion, we now knew that:

Big Oh(n^2) meant the set of functions that would grow no faster than n^2

Big Omega(n^2) meant the set of functions that would grow no slower than n^2 

When set of functions that were in both upper bound and lower bound, then we ended up having Big Theta(n^2), which it meant the set of functions grew as fast as n^2

Week 7

This week, I finally understood materials that I didn't fully understand from last week under the helps of my tutor. I learned about sorting, worst case, upper bound, and lower bound. I knew that as a programer, I want to find the worst case/speed of a program. Upper bound meant the case that can't be any worse than it. Lower bound meant the case that was the least worst. That's being said if the shorter the running time of a program was, meaning that more efficient the program was for computer (device) to run; therefore, a better performance. Moreover, the running time depended on how long the program required to count all of its steps. Furthermore, an example of worst case complexity graph was shown below.

The function y = x  represented the given input of the program.
The function y = logx + 1 represented the lower bound (at least as bad) of the program (least time consuming)
The function y = x^3 + x^2 - 1 represented the upper bound (can't get any worse) of the program (most time consuming)

 

 Additionally, we mentioned introduction rules, insertion sort, and selection sort.

We found that steps required for insertion sort and selection sort on list of size n were no more than some quadratic functions of n. All quadratic formulas were varied from substantial constant factors, but we as computer scientists didn't care because all quadratic formulas were the "same" - they were all in O(n^2). 

**** Big Oh stood for upper case and Big Omega stood for lower case ****