WEEK 5 ~ 6 ~ 7
Hello everyone, welcome back to my csc165 course Slog. I know that I am missing some weeks, so this post is going to be week 5, week 6, and week 7 all together, but let’s agree that those are not common weeks, they are pre-midterm, during-midterm, and pos-midterm weeks, so I just had time to breath again during the pos-midterm week, sorry about that, and let’s move on.
(Note that my midterms were distributed during week 5 and 6)
WEEK 5
CLASS
Week 5 we learned more about proof techniques, like contrapositive, contradiction, existence, and how to prove a sequence.
Most of that proof techniques relies on concepts learned before. Contrapositive means that if I prove a sentence, then its contrapositive is also true, so if I prove that P=>Q, ¬P=>¬Q. That can save a lot of time if a question ask us to prove a sentence, and if we identify that the next question is the contrapositive of the previous question we can just cite the previous question. But remember that this works both ways, and if you’re having troubles to prove in a way, try the opposite direction, instead of P=>Q, prove ¬Q=>¬P.
Contradiction is also known as a special case of contrapositive, that means one of the predicates is not clear. When a predicate is implicit we can assume that this predicate came from the common sense, in a situation P=>Q where P is implicit and we have =>Q, it turns to be “common sense”=>Q, and using contrapositive we can say ¬Q=>”wrong idea at common sense (false)”. Since we are talking about common sense, that proof is also called “reductio ad absurdum”, and if you want to know more, check this link (http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI6.html)
The existential proof, we just need to find one example of what we are trying to prove, it seems easy at the first sight, but it is not, just check all linear algebra where you need to find a single set of solution, then you will see that this kind of proof can be truly complex.
Proving sequences is similar to any other studied before, the difference is that we need to think beyond and work with the definition of the sequence, what requires more mental effort.
TUTORIAL
The tutorial during the week 5 was quite easy, but also important, it was focused on the structure of the proof, the main foundation of the knowledge of proof was being built.
WEEK 6
CLASS
Before week 6, we saw how to prove “binary” thing, if a statement is true or not true(false), but when we have want to prove something more complex than 0 or 1?! well, that was the focus that week, proving non-boolean functions.
We already know tons of non-boolean functions, for example, x² or |x|. Remember that this is a function itself, and not a variable. Since it is a function, to prove that, we just need to go back to the definition of the function, then use it to our purpose, and prove using one of the techniques learned before, but the definition is what you need to rely, since it is the only thing we know that is true and can help to prove what you want.
Another point in class was how to prove something is false, that is “easy”, if a friend claim “P”, for you to say it is wrong just negate it (“¬P”), but it is not enough, your friend could just say “¬(¬P)”, and this is pointless, to avoid the “endless” conversation, you should prove “¬P” using one of the techniques learned before, just remember to negate it correctly.
Proof about limits is something that I didn’t get it yet. By now, I am trying to understand limits and those greek letters that we should not freak out. So, I will update as soon as possible where and how I found the solution of my problem.
TUTORIAL
No tutorial at week 6.
WEEK 7
CLASS
During week 7, the main key was the introduction of Algorithm analysis and Asymptotic notation, and how to understand and identify those concepts.
Algorithm analysis is the act of analyzing the algorithm and understanding how this algorithm will behave and how much time it will take to do the task, especially, when the this algorithm process a huge amount of data. Also, since we have a fixed function, we can compare different algorithms to choose what is best for us to do an application. The function that we end up with after analyzing the algorithm is the running time, and it does not mean a specific number, instead, we use an input of size n, and we want n to be as large as possible. To analyze the algorithm we just need to count the steps and figure out a formula that represents that algorithm with n as input. But I used to question myself why we ignore low-order terms when analyzing, and the answer is that when the n is really large, low-order terms makes no difference, for example, we analyzed an algorithm and we found that R(n) = n³ + n, but we ignore n, so, let’s see with a big number if “+ n” makes any difference. Let’s say that n is 1000.
Then,
n³ = 1.000.000.000
n³ + n = 1.000.001.000
So, the 1000 more at the second formula correspond to 0.0001% of the first, and that amount can be discarded.
To find the Asymptotic notation, we use O(f(n)) to represent the upper-bound. On the example presented it would be O(n³). Later we will discuss the lower-bound and the tight-bound.
TUTORIAL
Tutorial this week was similar to the last week, the difference was that we should do a complete proof, not only the structure, and that makes the proof subject more clear.
#I hope you liked, and don’t forget to check the week 8 (soon)
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.
