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