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

CSC165H1 SLOG4 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG4

In this week’s lecture I have learned something more challenging than language of Math which is proof. According to course note, basically, proof is an argument that convinces someone who is logical, careful and precise and it is a tool in order to help you to understand why something is true. In the three hours lecture, I not only learn about what are proofs, but also the form and detail of proofs.

The form and method of proof is what I grasp well in this week’s lecture. To start, proof form is used to describe what method do you use in your step of proofing a statement and make the audience more easily to understand. Assuming I do not write any explanations in my proof form, the audience will certainly get confused if they have limited math knowledge, because the methods which I use to proof the statement are based on my math knowledge; therefore, they will not understand what I am trying to say unless I provide my explanations in my proof form clearly. For example, a question which is asked to proof ‘if n is odd, then n^2 must be odd’. There is a step which is square both sides in order to get some algebra. If I write the method in English or our symbolic form, the audience will understand this step sufficiently. As a result, proof form is an essential part of proofing.

Another thing which I learn very well is using contrapositive method to proof. The contrapositive method is a useful tool, because is hard to proof in original direction sometimes. For instance, when I proof something that is odd, but it is hard to proof in normal direction; therefore, we can proof not even instead of odd.

The hardest thing I have learned in this week is contradiction which I will ask TA in this week’s tutorial. Overall, professor teaches me some useful tips about course material and hopefully I will get a great mark in term test.

Forth slog
Mingyu Liu

CSC165H1 SLOG3 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG3

This is the third time of writing SLOGs for CSC165, in this week's lecture, we have finished talking about the language of MATH which is called 'Bi-implication'. Initially, professor posts some slides in order to review the former lecture which is a means to place a foundation for further lecture as well as recall my memories. For example, P => Q is equivalent to -/P v Q and -/(P => Q) is equivalent to P ^ -/Q. I believe this part provides me a great tip which I can be used for exercises in the lecture after. Then our professor talks about bi-implication which can be utilized to translate from conjunction of two disjunctions and also from disjunction to conjunction. The method of doing that requires mathematical ways which are distributive way. After bi-implication, the lecture also covers the negation of bi-implication which is a little difficult than bi-implication because it requires 'De Morgan's law'; therefore, I believe this part is what I grasp well in this week's lecture.
Moreover, transitivity and proof which I believe to be not that difficult. For example, the transitivity of this expression (P(x) => Q(x) ^ (Q(x) => R(x)) is P(x) => R(x). the reason why it is not difficult, because professor uses a visual way to teach us the definition of transitivity which means that if P implies Q and Q implies R, then Q must include P and R must include Q; therefore, R includes P for sure. For the proof part, professor teaches us about how to find the chain with ^ and v. For example, if there are no particular features in the expression, you will just have to start from downward to upward; otherwise, you can start from upward.
The interesting part of this week's lecture is that the professor makes a small activity of lecture which requires a group of three people and thinks the problem together. This is absolutely interesting because it improves the interaction between the lecture and students.
In conclusion, we have finished the language of math in this week's lecture and the difficult part which I encounter is mixed quantifiers. According to the professor, the language of math is not only for using symbols but understanding and expressing in a logical way. Finally, I hope my first test will be good.

Third slog
Mingyu Liu

CSC165H1 SLOG2 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG2

In the lecture of this week, Professor Danny Heap continues to teach us about language of math which mainly concentrates on conjunction, disjunction, negation and Demorgan's laws. i will start with the first topic which the Professor has covered in the lecture. Conjunction is news to me; therefore, my primary aim is to understand it by knowing its definition which is combining two statements by claiming they are both true. For instance, there are for two statements which are both true. The first statement says that car 'X' is red and the second statement has a saying which is car 'X' is a Ferrari; therefore, the conjunction of these two statements is called Car 'X' is a Ferrari and red. This is a case which is told by using human language, but using mathematical language is far more different to express. in human language,  we use 'and' to combine two statements while we use symbol '^' to combine statements in Math. This means that 'statement 1' and 'statement 2' is the same as 'statement 1' ^ 'statement 2'.

After the introduction of conjunction, professor also talks about disjunction which we use 'v' to describe it in Math and 'or' in human language. i understand it in a different way which is that treating disjunction as a set of 'union'. For example, 'Statement 1' V 'Statement 2' equals to 'Statement 1' U 'Statement 2'. Negation is what I grasp well in this week's lecture which using 'not' and the symbol '-\' to prove statements that are negative. For example,'Not all red cars are Ferrari'can be written in this way: '-\(Axec,R(x)=>F(x)).

Professor also teaches us some useful tips which are changing 'not all... ' In 'There is one that is not... 'and 'there does not exist... 'to 'all...are not'. These tips are useful because we can understand what the question requires us to do both quickly and efficiently; therefore, the way of solving the problem is just change the word simply.

There are no difficulties of this week's lecture, but the exercise of TUT is a little bit difficult for me. For instance, question number two of exercise which makes me encounter some problems which is that I initially write all the answers to get true, but the correct answers are different. After the teaching of TA, I find out during TUT.

In conclusion,lectures and tutorials of this week continue the topic of how to change human language into mathematical expression. Professor does superb work to help me understand the lecture and TA  helps me to resolve the problems of exercise with patience. Next week, I will continue to collaborate hard in both lecture and tutorial.

Second slog
Mingyu Liu

CSC165H1 SLOG1 BY MINGYU LIU

Mingyu Liu @ CSC165H1 SLOG1

I will start at something I have leaned something new in this week's lectures.
Professor begins with visualization with Venn Diagram contains two essential symbols which are "X" and "O". The meaning of first symbol "X" is that there is no element in this area, for instance, if there is no element in the intersection area of "P" and "Q", "X" is what you need to indicate this situation. The second symbol "O" contains meaning which is there are some elements exist in somewhere, for example, if there has some elements in the intersection area of "P" and "Q", writing "O" in the intersection area indicates there are elements in the intersection area.

Predicate and implication is what I grasp well in this week's course. Predicate simply indicates that you can use the easy way to write "X" is in the set "L" into "L(X)" which is exactly the same. Moreover, "L(X)" without specifying "X" is an open sentence which means that "X" can be substituted for specifying the "X". Implication contains assumption and conclusion which can be submitted in "P=>Q". The most important thing of implication is that assumption requires conclusion, but the assumption does not cause conclusion.

The most difficult part in the lecture of Tuesday is statement and sentences. The reason why it is difficult because the difference between sentences and statement is confusing. For example, A statement is a sentence but it is a sentence that is not open. However, sentence is not always a statement. Due to the confusion, when I am facing exercises, I cannot really determine which one is the sentence and statement.To solve this problem, I will do some exercises and ask professor if necessary.

The teaching style is exactly what i enjoy the most during this week's lecture, because instead of using tedious definition to teach students, professor replaces traditional course material by using an idiom which is called "Sometimes there are more than one way, even in math. Some ways are more commonly used than others." In my opinion, students are more attracted by interesting instead of boring teaching style. Professor uses idiom which to make students focus on course; therefore, students grasp knowledge better in course when they are interested in course.

When I was doing my exercises this week, I first confused about where should I put each letter which is A, T, P in the correct posion into Venn Diagram. The tutorial actually is really helpful which helps me to understand my question. For example, A be the set of all possible python programs which mean that A indicates the rectangle of the Venn Diagram.

In conclusion, lectures and tutorials of this week were superb experience which taught me how to utilize a mathematical expression to transform human language into simple mathematical language, and also, use Venn Diagram to verify statements. Difficulties did occur in this week which are the differences between statements and sentences. Overall, CSC165 is an interesting course which definitely deserves time to study hard.

My very first Blog
Mingyu Liu