CSC165H1 SLOG11 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG11

This is the last class of CSC165 and in this last SLOG I will continue to talk about the slide of professor Zhang. There are actually four parts in this week’s class which are composed by the tips of assignment 3, countability, induction and the review for final exam.

Tips for Assignment3:

In assignment 3, I think it is the most difficult assignment I did in this semester. Fortunately, Professor Larry gives us some tips in order to solve the questions within the assignment 3. In question one of assignment 3

in this question, we are basically want to prove or disapprove that if ∣X-Y∣>d, then ∣X+Y∣> e. When we look at ∣X-Y∣, ∣Y-X∣is equal to ∣X-Y∣; therefore, ∣X-Y∣< ∣X+Y∣.

For question 3 and 4, the definition of limit is needed in these two questions:

This means that no matter how larger c is, f(n) can be larger than c.

No matter how small c is , f(n) can be smaller than c.

When our group solves question 3 and 4, these two tips provide fairly important message when solving the problems.

Countability

Firstly, professor asks us to compare the size of two sets

In order to compare their size, we can compare the length of these two groups which means that the sizes of the two are the same.

How about compare ‘natural number’ list and ‘even natural number list’? The answer is not only confusing but also interesting which is that the sizes of these two are identical. Professor provides us a real-life example. Considering a coin which is shown below.

We know each coin has one and only one tail; therefore, set of coins and set of coin tails are of the same size.

This means that if there is a mapping from X to Y like the coin problems, then we have the absolute value of X is equals to the absolute value of Y.

There is another important element which is called countable within the countability. This means that when we count numbers, we do 0, 1, 2, 3, 4, 5, and 6… which are all enumerating natural numbers; therefore, the set of N is countable and, any set A that satisfies the absolute number of A less or equal to the absolute value of N is countable. For example, the set of integers is countable; the set of rational numbers is countable.

In conclusion, in this week’s lecture, we only touch the surface of countablilty, but it is an very interesting material to learn. After this blog which is the last blog of CSC165, I will continue work on the review of CSC165.

eleventh slog

Mingyu Liu

CSC165H1 SLOG10 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG10

Although we do not have any lecture in this week, I want to write this slog because there are some questions I left over in last week tutorial. In this week’s slog there is one question I would like to solve.

We have to underestimate and overestimate in order to pick a ‘c’. C must be large enough to make the right side an upper bound

Let’s prove!

In conclusion, it is time to prepare final, so the next slog will be about review previous lectures.

Thank you for reading!

Tenth slog

Mingyu Liu

CSC165H1 SLOG9 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG9

I want to apologize firstly about this slog is posted later than usual. In this week’s slog, I would like to make some change which is that posting some questions which I feel less confident to solve, the answer for these questions are wrote by me and also will be posted below questions. In this way, the more questions I practice, the more benefits I will gain. Let’s get started!

First question:

Firstly, I will do some recap about how to prove this question. A function of f (n) is in Ω (n^2) if and only if

This means that the set of functions that grows no slower than n^2.

Secondly, the next step of proving this question is to use the method of overestimating and underestimating which is shown as followed image:

As professor told us in this week’s lecture, when we prove about Ω (n^2), we have to pick a c which is small enough to make the right side (Ω (n^2)) a lower bound; therefore, pick 1/18 to be c fits perfectly in this case.

Thirdly, it is time for proving!

Second questions:

In this week’s module, professor Zhang taught us a whole new proof which is prove some general statements about big-oh.

This is the definition of proving some general statements about big-oh, which means that the set of all functions that take a natural number as input and return a non-negative real number.

The thought of this proof is as followed:

We want to find B’’, C’’, f (n) <= c’’h (n) beyond the breakpoint B’’; therefore, beyond the B’’ and B, we have B’’ = max (B, B’’), and also, c’’ = cc’

My proof:

In conclusion, these two questions are what I confused of. Because of fall break, I will continue to work on this week’s lecture slide and practice more in the following week. 

Ninth slog

Mingyu Liu

CSC165H1 SLOG8 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG8

After term test two, we are having an exercise lecture, which involves exercises of big-oh proof and proof by using limit techniques. In this week’s slog, I would like to recapture the examples of this week’s lecture.

In order to prove big-oh, we have to understand the definition once again from last week’s lecture which is shown in this image:

This means that beyond the break point B, f(n) is upper-bounded by cn^2 which indicates that f(n) is grown slower than cn^2.

When we grasp well the definition of big-oh, it is time for us to learn further according to big-oh:

This is a notation of O (n^2) being a set of function which consist of two parts exactly. The first one is that functions that take in a natural number and return a non-negative real number.

The second one is known as the definition of big-oh which means that beyond the breakpoint B, f(n) is upper-bounded by cn^2. As a result, if you want to prove big-oh correctly, the set of functions in the first criteria must satisfy the second criteria.

Exercises:

1: c should be larger than 3, because the constant of the highest-order term.

2: when n = 1, 3n^2+2n = 3+2 = 5 = 5n^2

Therefore, B=1 and c=5 is good to solve the problem.

3n^2 + 2n : N -> R ^>=0  #3n^2+2n >= when n is natural number

Pick c=5, then c is belonging to R+       #5 is a positive number

Pick B = 1, then B is belonging to N      # 1 is a natural number

         Assume n is belong to N

                  Assume n >= 1

            Then 3n^2 +2n<= 3n^2 +2n *n

                        =5n^2 = cn^2

            Then 3n^2 +2n <= cn^2

        Then n>=B -> 3n^2 +2n <= cn^2

….introduce antecedent and quantifiers (omitted)….

When we know how to prove big-oh, disprove seems important for us.

First, we have to negate it:

Then we prove the negation and the process is like I did in the previous exercise.

In conclusion, in this week’s lecture, I believe I grasp well on proving and disproving big-oh, but the only thing I have to work on is proof of big-oh by using limit techniques which I will illustrate in next slog.

Eighth slog

Mingyu Liu

CSC165H1 SLOG7 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG6

In this week, professor first introduces some scary announcements which are that A2 will be due on next Tuesday and test 2 will be held on the day that is followed. Although I think CSC165 is a challenge course for me, I do not consider dropping the course.

Tips for Assignment2

When we try to prove a statement with multiple quantifiers, there are some useful tips for us to solve the problems. For example, the symbol which indicates all can be written in to ‘assume generic’ in the process of proof. The symbol which means any can be treated as ‘pick’ or ‘let…be’. Moreover, when we see the statement of ‘if P then Q’, we can easily change it into assume P then Q. These tips have its capabilities to make proofing easily.

Lecture of this week

This week’s lecture is based on the definition of ‘O’ and ‘Ω’ and the worst case analyses of two algorithms.

The definition of ‘O’ and ‘Ω’

Form last week’s lecture we have known that O (n^2) means a set of function that grow no faster than O (n^2). Assuming we have a function ‘7n’, which is a linear function; therefore, the function ‘7n’ must be included in the set of O (n^2), because the function ‘7n’ grows no fast than O (n^2). There is another element which has to be presented first which is the breakpoint B. Breakpoint is very simple to understand by using graph to imply. As image 1 indicates that the function f (n) is at the lower position compared with the function cn^2 after the breakpoint B; so the purpose of breakpoint B indicates that after break point B, if f(n) is upper-bounded by cn^2, then it must grow faster than cn^2 and if f(n) is lower-bounded by cn^2, then f(n) is slower than cn^2, no matter f(n) is at what position before breakpoint B. after introducing the breakpoint B, the formal definition can be written in this way: a function f(n) is in O (n^2) if and only if .

The definition of ‘Ω’(n^2) is the opposite version of ‘O’(n^2) which is set of functions that grow no slower than n^2; therefore the definition could be written in this way:

This is image 1

Analyzing a sorting algorithm

A sorting algorithm basically means that grow a sorted list inside an unsorted list. For example, an unsorted list which is [1, 3, 4, 5, 2], through sorting algorithm, this list must be written into this way: [1, 2, 3, 4, 5]. The working principle is removing an element from the unsorted part and inserting it into the correct position in the sorted part.

In conclusion, this week’s lecture and tutorial went very well, because I can see my improvement in this week. Professor slows his speed of processing the lecture which makes me much comfortable and confident to learn.

Seventh slog

Mingyu Liu

CSC165H1 SLOG6 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG6

We finally finish the last part of Proof of Math in this week’s lecture which is proof by cases, and we are taking steps to learn algorithm analysis and asymptotic notation. This week is extremely interesting because it is all about computer science instead of boring Math; therefore I feel comfortable in learning this week’s lecture.

I believe that there are no difficulties in the material this week, after learning proof for three weeks; the last part of proof is easy for me. The concluding part of proof is called proof by cases which can simply understand as splitting your argument into different cases and prove the conclusion for each case. The important thing to remember before going anywhere further is that a valid proof must cover all possibilities which mean that you just have to consider all possible cases of one given proof. For example, to prove if you have a problem in your life, then no need to be concerned. In order to make your proof valid, you have to initially consider all possible cases in the question. As we can see in the question, there are totally two cases containing in this question which are ‘YES’ and ‘NO’; In this two cases, proof can be written like this, you have a problem in your life, can you do something about it? Cases 1, which indicate YES, then you do not need to worry about this. However, case 2, which indicates NO, is also that need not be concerned about this. This example seems funny, but it actually illustrates valid proof is equal to consider all cases. In other words, if you cannot review all possible cases, your proof will be meaningless.

After Larry gives us some examples and exercises of proof by cases, he then allows us to review all proof patterns. Basically, two categories in proof patterns, the first one is named introduction rules which you can simply understand by making smaller statement into a larger statement. For instance, in conjunction introduction, assuming C is red and C is fast; therefore C is red and fast.

Another rule is elimination rules. This rule is the reverse version of the introduction rules which mean that making a larger statement into smaller statement. For instance, in negation elimination prove the car is not red is false, we can get the car is red.

The latter part of this week’s lecture is algorithms. Bubble sort and merge sort are two sorting algorithms. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are located in the wrong order (reference from Wikipedia). Merge sort is somewhat working to divide a list into two parts and set it in order. Through observation, we learn that merge sort is faster than bubble sort and with larger input size; the advantage of merge  sort over bubble sort becomes larger. Running time is what Larry also introduces this week. Basically, we count the number of steps of a function, but it depends on the input will execute how many steps. This part is only an introduction of algorithm this week. I will continue to learn the algorithm next week further.

In conclusion, this week’s lecture covers proofs and algorithm which is not so difficult for me. For proof, Larry provides me a small but useful tip which I feel extremely helpful is that practice is one of your most important weapons for solving proof, because the more times you practice, the more familiarities you will get with proof patterns.

Sixth slog
Mingyu Liu

CSC165H1 SLOG5 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG5

The beginning of this week’s slog, I am going to start with the material which I grasp well. It is called non-Boolean function which means that a function that is not return True or False.In other words, the function will return to neither True nor False statement. For example, ‘X > 5’ is a boolean function, but x^2 is non-Boolean function. The symbol of non-Boolean function is written in this way ‘LXJ’ which means floor of ‘x’. I will provide an example to further explain what this symbol does. Assuming you want get the largest integer of 3.5, the symbol ‘LXJ’ is what I suggest to use. If you write your function by doing ‘L3.5J’, your function will return to ‘3’ which is the largest integer of ‘3.5’. One more thing that the professor wants us to remember is that ‘LXJ’ is not a variable. This means that you cannot write a equation like for all ‘LxJ’ is in R, because a quantifier is not applicable to ‘LXJ’.

After non-Boolean part, professor also teaches us about prove something false which means that disprove something. The simple way of understanding this part is using an example which is that ‘how to disprove all cars are red? Just prove there is a car that is not red’. Some tips from professor are that make sure to negate it correctly firstly, and then prove the negated statement, finally draw examples to obtain intuition.

In this week I have learned about proof about non-Boolean functions, proof something false and proof about limits. I believe the most difficult part in this week is ‘prove about limits’; therefore, I will continue working on this part on the weekend.

Fifth slog
Mingyu Liu