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