SLOG #6: Big-Oh Confusion

We have moved on from general proofs to proofs including big-Oh. I'm still trying to master proofs, let alone proofs that include more Greek symbols. I feel terrible for admitting this, but I've just been blindly copying notes in class. And all the calculations with inequalities involve grossly overestimating or underestimating (why do we do that?). 

In terms of proof techniques, I think I can finally say 'I get most of it'.  http://csc165wendezhou.blogspot.ca/  summarizes the different proof techniques (under week 6) pretty well. Before reading their blog, I forgot about proof by contradiction. So far I haven't been able to prove one of the questions on the assignment yet. Perhaps I should give proof by contradiction a try. 

Proof techniques: 

- direct proof

- proof by contradiction

- proof by contrapositive

- proving a negation

- proof by cases 

SLOG #5: Proofs, and general thoughts on progress of the course so far

For the past couple of weeks, we've been learning about proofs and proof structure. I’m guessing that correct structuring of proofs is very important in this class because we've been focusing on that in tutorial as well. It’s actually not too bad once you learn and apply the structure rules. There’s a certain symmetry to it.  There's too much information on proof structuring to type out in this blog. I find that chapter 3 in the course notes nicely summarizes everything learned in class.

Self-Reflection

Boy, does time fly! Now’s a pretty good time to do some self-reflecting so that I can make the remaining month I have left in this course meaningful and productive.

To start on a positive note: I've been able to get perfect on the past few tutorial quizzes. It may not seem to be much to most people, but considering that I failed the first couple quizzes, it's very reassuring to see that at least I'm making improvement. 

The bad news: I’m starting to get really confused again in class. Ever since we started sorting strategies and bounding and the ‘worst case’, I've been pretty lost. I know that I should probably go to prof office hours to get help, but professor Heap’s office always has a long line-up and I have class during half of office hours. Perhaps asking the TA’s in the CS help center is a more reasonable approach.

Midterm AND assignment due next week! I’m actually really stressing out… Not sure how I’m going to manage so much work. My goal is to work on CSC165 for at least four hours a day until the midterm. Doing the practice problems and reading over notes is a good way to prepare. 

    

SLOG #4: Epsilons and Deltas

I don’t really enjoy epsilon-delta proofs (mainly because I find them to be confusing), but I find that the process of breaking it up into parts to be helpful in understanding them. Technically, we were supposed to know these for the first midterm, but I realized that I didn’t quite fully have a good grasp on it walking into the test. Thankfully, these were not tested (phew). But who knows, it might be on the exam!

In class we did an example where the lim (as x → 0.6) of x^2 = 0.36

In epsilon-delta terms, this is written as:

∀ e ∈ ℝ⁺, ∃ d ∈ ℝ⁺, ∀ x ∈ ℝ, |x – 0.6 | < d ⇒ | x² – 0.36| < e

The definition of a limit of a function is as follows:

Let f be a function defined at least on an open interval (c – p, c+p) except possibly at c itself.

lim (as x→ c) of f(x) = Lif for each e > 0, there exists a d > 0 s.t. if 0 < |x – c| < d, then |f(x) – L| < e.

1.       First we should find a d. Let e > 0. We want a d > 0 s.t. if 0 < |x – 0.6| < d, then |x² – 0.36| < e.

Find a connection between |x² – 0.36| and |x – 0.6|:

x² – 0.36 = (x + 0.6)(x – 0.6)

|x² – 0.36| = |x + 0.6| |x – 0.6|

2.       Take x within 0.1 of 0.6 (So let your enemy choose an e)

If |x – 0.6|< 0.1, then 0.5 < x < 0.7 and |x + 0.6| ≤ |x| +|0.6| = x + 0.6 < 1.3

Thus if |x – 0.6|< 0.1, then |x² – 0.36|< 1.3|x – 0.6|

3.       If, in addition, |x – 0.6|< e/1.3, then |x² – 0.36|< 1.3(e/1.3) = e

This means that d = min{1, e/1.3}

4.       To see that d works:

Let e > 0. Choose d = min{1, e/1.3} and assume 0 < |x – 0.6|< d

Then |x – 0.6|< 1 and |x – 0.6|< e/1.3

Then |x² – 0.36| < 1.3|x – 0.6|

Since |x – 0.6| < e/7, |x² – 0.36|< 1.3(e/1.3) = e

I also found khanacademy videos on epsilon and delta to be pretty helpful (link: https://www.khanacademy.org/math/differential-calculus/limits_topic/epsilon_delta/v/proving-a-limit-using-epsilon-delta-definition).

We also discussed in class that the order of the quantifiers in this proof cannot be switched around.

SLOG #3: Review of Test 1 Material

REVIEW OF TEST 1 MATERIAL

·         Universal claims (") - claim about all objects

®     to verify: consider every element in the domain and show that they satisfy the claim

®     to falsify: provide a single counter-example

·         Existential claims ($) - claim about some objects

®     to verify: show at least one example

®     to falsify: show there are no examples

·         SETS:

®     P Í Q "P is a subset of Q", "Every P is a Q"

-        To prove: show every element of P is an element of Q

-        To disprove: Find at least one element of P that is not an element of Q

®     P Ë Q "Some P is a Q"

-        To prove: find one P that is a Q

-        To disprove: Show that every P is not in Q

·         IMPLICATIONS:

®     IF antecedent, THEN consequent

®     can also be shown by antecedent Þ consequent

®     to disprove, show an example where P is True and Q is False.

®     note: "If...then..." tells you nothing about causality. For example, "If it rained yesterday, then the sun rose today" is true, but rain did not cause the sun to rise.

®     for antecedent, look for words such as: if, when, enough, sufficient

®     for consequent, look for words such as: then, requires, must, need, necessary, only if, when

·         CONTRAPOSITIVE:

®     the contrapositive of (P Þ Q) is (¬Q Þ ¬P)

®     "all non-Q are non-P"

·         CONVERSE:

®     the converse of (P Þ Q) is (Q Þ P)

·         NEGATION:

®     negation inverts the truth value

®     When negating a statement:

-        Existential quantifiers turn into universal quantifiers, and universal quantifiers turn into existential quantifiers

-        use manipulation rules, such as DeMorgan laws and distributive laws (for full list see Course notes pg.29)

®     Example: ¬($ xÎD, P(x) Ù Q(x)) Û (" xÎD, ¬P(x) Ú ¬ Q(x))

·         VACUOUS TRUTH:

®     Whenever the antecedent is false, and the consequent is either true or false, the implication as a whole is TRUE

®     the set where the antecedent is true is empty(vacuous), and hence a subset of every set

·         TAUTOLOGY, SATISFIABILITY, UNSATISFIABILITY

®     Tautology: you can't dream up a domain, or a meaning for predicates P and Q that provides a counter-example, since the truth tables are identical

®     Satisfiable: true for some choice of domain, predicates P and Q, and values of domain elements, ex: (P Þ Q) Û (Q Þ P). Saying that a statement is satisfiable only tells us that it is possible for it to be true, without saying anything whether or not it is also possible for it to be false

®     Unsatisfiable (or Contradiction): something for which no domains, predicates, or values can be chosen to make it true

***note: This SLOG was supposed to be posted before the test, but I ran into some password and username trouble with my account for the past couple weeks. 

SLOG #2: Thoughts on Assignment 1

Assignment one is finally completed (thank goodness). Overall, I found the assignment to be a fair representation of the concepts we have learned so far. When I say fair, I mean that it was all based on material that we were supposed to know. But that doesn't mean I found it easy...

I found myself struggling (a lot) with a select few questions. I don't think I'm speaking for myself when I say that question four was one of the most challenging questions. In fact, it was a three-day process for me.  The first day I just tried to understand what the question was asking me to do. Eventually I had some kind of a vague idea but I was too tired to act upon it. The next day I came up with a solution for 4(a), which I thought was correct until I went to see a TA in the CS help centre, and he pointed out a major flaw in my reasoning. Darn. But turns out I was close to the answer, because inspiration came while I was in the subway. I tried switching around the sets I assigned to D, P, and Q, and my example worked! The frustrating problem came when I started part (b). I couldn't think of any examples that made one statement true and the other false. My examples either made both true or both false. I went to prof office hours but I still had trouble thinking of an example. Finally on the third day, I went through the course notes again to see if I had missed any information. It then occurred to me that maybe I didn't know the truth table as well as I thought. Here's the piece of information that is now drilled in my head: if P is false and Q is true, P Þ Q is TRUE, and PÙQ is FALSE. I have to admit, it felt pretty good finally checking off that question.

Progress so far: I still find every week to be a challenge. But because of that, I find myself dedicating more time to study for this course. Let's see, what else... OH, I still have to figure out the paper-folding problem.