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.

WEEK 4

Hello everyone, welcome to week 4 post for csc165 course. That week was terrific, proving anything is the basic of any science or non-science subject.

CLASS

Before start writing my thoughts about the class, just a reminder that the first midterm is next week, as usual, I am completely crazy, but let’s see how we can manage that, good luck to everyone, and don’t forget the aid sheet, if you need some reference, check the link with old exams here (update: The old midterm can be found here). If I have some time int he future and before the exam, I will try to summarize information about the previous final exams.

On week 4 we had, Bi-implication, Transitivity, Mix quantifiers, and the star of the week Proofs.

Just to clarify, all writing on those posts are explanations or thoughts that helped me to memorize or learn concepts, even if you don’t find what I think in any book, it doesn’t mean it is wrong or that I am 100% right.

So, let’s begin with bi-implication, that I think to be only a special case of the implication itself, or the “if and only if” thought, and it is represented by P <=> Q, and is the same of (P => Q) /\ (Q => P), and using implication we find that it is the same of (¬P \/ Q) /\ (¬Q \/ P). Following some laws, it can be found the identity, and also the exclusive OR with the negation of the bi-implication.

Transitivity is a basic property on set theory, and says that if A is related to B, and B is related to C, then A is related to C. Basically, if (A => B) /\ (B => C), we can assume that A => C.

Mixed quantifiers is the “evolution” of what we’ve been using so far, instead of one set X, now we can use set X and set Y, and as many sets as we wish to express what we want to say. Also, it increases the complexity of the predicates we can use.

Now, let’s focus on Proofs. It does not matter if is one way or another, if you believe something when someone proves it is wrong or true. Every one need to prove something on the daily life. So, you use an argument that is precise enough for the situation. In the science case, it is necessary to be precise enough, but if you’re trying to convince your friend that the new restaurant is awesome you don’t need to be as precise as a mathematician.

To get the proof, first you need to completely understand the problem and spend time to discover the truth of the proof. After, you just need to write the proof. Believe me, you’re going to spend the most part of the time thinking (or discovering) a way to prove, so, be imaginative.

In other to write a proof in a precise way, the scientific community uses some well know structures, and for now, on week 4, we are going to learn the direct proof of universally quantified implications. Don’t be scared, the name is huge, but if you break it, then it is not so scary, just think that as parts:

1. Direct proof…
2. Universally quantified…
3. implications…

The only unknown part that we didn’t studied before is the number 1, and it is self explanatory.

In order, to prove that R => T, we should remember something that I said at the beginning about the bi-implication (if A=>B and B=>C, then A=>C). In that case, if we put our values inside the bi-implication, R should be A, and T should be C, and to prove that implication we need to think of a B, where B is know to be TRUE. In fact, we need to find a chain, and that slide from class is perfect to show a chain, and also, show the fully sentence:

But no proof is equal to another, it could have the same structure, so the only thing that can make you truly learn is practicing.

TUTORIAL

The tutorial was great, we made some progress toward learning proofs and the questions were some how challenging, and the quiz was just one question which could be solved with laws explained during the tutorial, I had no trouble to go through the tutorial this time.

#I hope you liked, and don’t forget to check the week 5 (soon),
#I am finally up to date with my posts, I am so happy :D
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.