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.

WEEK 3

Hello everyone, welcome to week 3 post, a continuation of week 2 material about the language of math.

CLASS

This week we covered Conjunction, Disjunction, Negation, Truth table and manipulation laws.

Conjunction and Disjunction are used to put together two or more predicates (for more about predicates, check week 2). Conjunction is the “and” and Disjunction is the “or”, and their symbol are “^” and “v” respectively. Again, sets has a really important role understanding those two. First, “and” can be intersection, and “or” can be union. Nothing more to talk about, just basic set concept.

We already talk about how to negate a predicate on week 2, but now we are talking about a whole statement, and instead of negating all the statement, we should negate just particular predicates inside the statement, for example:

How not to do:

How it should be done:

while negating a statement, always remember the quantifier table from week 2.

Another element that can be used is parenthesis, and we should be careful, it works similar to basic equations, but we should remember that what happens inside parenthesis does not affect or can be reflected to another parenthesis, and what is inside parenthesis is called “scope”. Also, parenthesis help us to organize the idea of the statement, during the class the following slide was presented:

Furthermore, the truth table was presented as a solution where we should deal with more than two predicates, since the Venn Diagram does not help us to understand properly when a large number of predicates is showed, for example, below we have more than two predicates, and it is quite confusing.

To help us with that and show all possible outputs, we use the truth table:

But we should focus on the special cases, that can be used to say interesting things about the statement, and this slide showed us a good picture of those special cases:

Moreover, we have some laws, and they are De Morgan’s Law, table example below. Also, commutative, Associative, and distributive laws are applicable.

TUTORIAL

The tutorial had some trouble, some people in the class had difficult to understand and solve the questions, but I need to say that is not easy to know how to apply what we learned in class to another problem that is completely different from the example that we saw during the class, but we need to think bigger and know that the language math can be applied almost to everything that we say on our daily life.
I had some problems to solve some part of question 2, but the truth table can be a great ally to solve most of the questions without the need to think in an example and try to deduce something from that. So, just go to the truth table, and let it do the job. After that you can think a good example to present your answer.

#I hope you liked, and don’t forget to check the week 4.
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.

WEEK 2

Hello everyone, this post will be dedicated to the second week of class, a lot of material was covered. Also, we had our first tutorial followed by the quiz. So, let’s start with the class.

CLASS

The material covered was:
- Quantifiers, verify/falsify
- Sentences vs statements
- Predicates
- Implications and equivalence

In my opinion, the most relevant content was Quantifiers, Predicates and Implications, those were the keys to understand the content of week 3 (…shush, no spoilers).

At the beginning I was really scared about that math language, all those symbols and I never thought I could make sense of what it was trying to tell me, but now it is some how easy, but don’t be fooled, it is not easy, and also is really helpful if you have some understanding about set notation. The image below was used to demonstrate how the math language looks like.

The quantifiers are divided into Universal and Existential, and they were putted together in a really helpful table with how to verify and falsify, and the table is some how self explained.

A really amazing tool to not get lost when trying to verify or falsify is the Venn Diagram, where you can represent the sets and graphically shows what is empty or not.

Right after, the battle between what is a sentence and what is statement begun, it is quite easy to mix both because a statement is a sentence, but the opposite is not always true, but in the end it is very simple. In a statement, the object of the sentence is quantified, that is all. For example, if I say “The planet is beautiful” is planet quantified?! yes…no?! If you compare to that another sentence it gets easier to know which one is sentence or statement, and the another sentence that is a statement can be “All birds can fly”, just remember that what is being analyzed is which one is a statement and not if it is true.

The Predicate is something a little bit complex, but can be explained using very simple examples, using the bird example I can say the P = “The birds that can fly”, so “Bird x can fly”, then P(x), and “P(x)” is a predicate. So it is a full sentence compressed in two letter, it can save a lot of paper, can’t it?!
If I would like to negate it, just use that symbol “¬”. Now, you can easily know what I want to say with that “¬P(x)”. It can get a lot more complex, and sometimes more information about the sets should be provided.

Implication is the base to construct more complex thoughts mathematically speaking, and to anyone familiar with any computer language it should be easy peasy. Basically, “IF P, THEN Q” or “P => Q”, so P implies Q. But, be careful, since it does not mean that P causes Q, and some weird sentences can come out, like the one presented in the class “If it rains yesterday, then the sun rose today.”, and it is true. Also, some interesting rules came out, converse and contrapositive. So, tons of everyday sentences can be translated just with the symbol “=>”.

Following implication we were presented to Equivalence, that in my opinion is just a special case of Implication, it simply is an implication that works both ways, so “P => Q” and “Q => P” merged into “P <=> Q” or “P iff Q”, in english you read “if and only if”. Back into the bird example, bird P and fly Q, “P <=> Q” if it is a bird, it can fly, and if can fly, it is a bird, so it can fly if and only if it is a bird. (I know, it is getting complex, I thought the same, but it needs some time and thinking to get into my mind.)

TUTORIAL

The tutorial was all about the Venn Diagram, and how to verify and falsify. Nothing I could not handle, but surprisingly during the quiz, that was composed by two questions I didn’t answer the first one correctly, and that is the warning, it can be very simple, but we are dealing with small letters and simple graphics that can represent a whole world, so it should be treated very carefully. I will show the question below and say exactly what happened, so everyone can be aware.

I will write just the key sentences of the question one:

• U is the set of all students currently enrolled at UofT;
• P is the set of all students enrolled in a programming course;
• L is the set of all students enrolled in a linguistic course;
• Claim: “all students enrolled in a programming course at UofT are also enrolled in a linguistics course at UofT”.

-> Prove the claim is correct.

Well, in a really fast thought I answered that “To prove it is correct, all students should be enrolled in both courses.”.
When I walking back home after the quiz I realized how wrong I was. Basically, the statement was a simple “P => L”, and not “P <=> L”, and just some time after the quiz I knew that my first question was wrong, mainly because of impatience, but most of all, due to the inability I had to transform a statement and detect what I was dealing with, if it was a “if P, then L” or “P if and only if L”. Sadly, it was too late.

#I hope you liked, and don’t forget to check the week 3 (soon), 
#I am actually late with my week post, so I hope I can finish week 3 by the end of monday, 29 Sept.
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.

WEEK 1

Hello everyone, here I am to speak about the first week of class, it is going to be pretty short, since we had no tutorial, and just an introductory class was presented, but I have some points to discuss.

CLASS

My first thought about the class was, another late night class when I will be tired and just think about going home, then everything changed when I saw the internet meme, to be more precise, that one:

I don’t think I need to say that I realized that this class was not going to be like any other, and I highly hope that I am right.
But suddenly I was possessed by the same feeling of boredom that I felt at the beginning when the “Why?” slide was presented, because that is exactly what everyone else say when try to explain why math is important:

I know that I should have more faith in it, since I am at the university, but my feelings from high school are not easily replaced, and I will probably need some magical experience of enlightenment to break my fear of math, but do not worry, because one slide before we were presented to some information about specific fields and what kind of math each one is related. This information is something that I will keep for my life, because I was finally presented to something that tells me exactly where I am going to use math, thank you. It would be awesome if the professor could present some real examples about that utility and obligatory math for those fields of study, but for now, any concrete information that is more than the usual is enough to break the ice where my “faith in math” was kept. If you have any doubt check the slide below, it is beautiful.

Closing the introduction portion of the class, that is how we should feel about math at the end of this course (let’s hope it is true):

After that, the class it self started and those points were presented:

- Precision
- Problem solving
- Quantifiers

if you need to check the lecture to remember anything it is available here.

LAB

No lab this week, sorry guys.

#I hope you liked, and don’t forget to check the week 2.
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.

WELCOME

Hello everyone, welcome to my Slog. I was thinking of what should be the best way to organize each post, and after reading the slog documentation I decided to adopt it partially. So, I will try to structure each post as much as possible, but I can’t promise, since when I am writing I use to just let my instincts take over, but as I was saying, the structure that I have in mind is the following:

• First Part - Subjective thoughts about classes and/or any material
• Second Part - Thoughts about exercises/labs and any interesting problem-solving situation.
• Last Part - Conclusion/non-related course writing*

*Since it is a blog, why don’t write something about ourself, or at least something not related to the course, for example, experiences/events/activities at the university?! Well, it is just a plus, because a student week is not just an infinite stack of classes.

I will make sure the non-related course material to be easily identified at the end, so if the reader is not interested on that part he/she can just skip it.

Once again, welcome to my slog.

#Don’t forget to check the week 1 post,
#Questions, comments, suggestion?! Write it below, I will answer as soon as possible.
#Thank you.