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
Mingyu Liu
