Eleventh/Twelfth Lecture - November 25th 2014

There was no eleventh lecture because of reading week, so I went to Vegas for a couple of days (for business).

Let's skip the python stuff that we covered in class today, I will find them in the powerpoints later.

One interesting technique that we learned was induction. For example, once the initial domino falls, all of dominos fall. (all of i in D, di falls) So this implication that we use is apparently not the most simple nor the fastest. Here's proof by induction. It uses a base case and a simple inductive step.

Anyway, sLog, it's been a good run, time to study for finals.

Tenth Lecture - November 11th 2014

Annnnnnnd, results for Term Test 2 are out. As expected, I didn't do well, but the class average was surprisingly low too. Anyway, there is always the final exam.

Just a recap of the method used to develop big-O proofs. Since the initial function will not grow faster than the second equation, you want to under-estimate the "variable" on the right side while over-estimating the "variable" on the left side of the big-O. Then finally, you put them together and pick a c value large enough to make the right side an upper bound.

Now, for proofs with big-Omega, you're doing literally the exact opposite, while picking a c value small enough to make the right side a lower bound.

As a summary, this is important to remember.

After this, we proceeded to prove general statements instead of functions. Um, don't know how to put this in words, but use c' and B' wisely. Here's how you do it.

Ninth Lecture - November 4th 2014

Today's term test went horribly. The second proof was exactly the same as the one I did in the assignment but I had no idea how to do it on the test so I think I failed. But then again, it's only worth 6% in the long run so getting 50% on it will still get me 3% of the 6% in the bigger picture, so I guess it's okay. Moving on...

We learned proofs for the big O. There are two tips that I will put on here so I can remember it for future references.

➔ tip 1: c should probably be larger than 3 (the constant factor of the highest-order term)

➔ tip 2: see what happens when n = 1

➔ if n = 1

◆ 3n² + 2n + 5 = 3 + 2 + 5 = 10 = 10n²

◆ so pick c = 10, with B = 1 is probably good

◆ double check for n=2,3,4…, yeah it’s all good

Also, this is super important. I was confused in my tutorial on Monday about choosing the c and B values but this draws it very well - especially if you're a visual learned.

Here is the negation 

Finally, here are the golden rules to doing big-O proofs with "some Calculus".

Eighth Lecture - October 28th, 2014

To begin, this is probably the most important thing I learned today. This structure is important to follow on tests and assignments, and it works even when you have no idea what you are doing. Also, assignment 2 is due next Monday but I'm confident in most of my proofs.

Now, moving onto a bit of review from the past few weeks.

1) How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

2) Assume two integers a < b

➔ a ≤ b - 1 # two integers differ by at least 1

3) When the statement seems kind-of trivial but

proving directly looks messy

➔ try contradiction

Today we learned about the definitions of big-O and Omega, as well as the worst case analyses of two algorithms (which I didn't quite understand).

In short, big-O expresses the relationship between two functions; where the first function is ultimately upper-bounded by the function shown after the big-O; this means that the initial function also grows no faster than the final function. Big-Omega is the exact opposite. The first function is lower-bounded by the second function expressed after big-Omega.

Seventh Lecture - October 21st, 2014

Today's lecture felt a little long, but I'm going to start this journal with a review for proofs, as that's what assignment 2 and test 2 are all about. The three types of proving structures that were in the notes were:

1) Proof by cases
- splitting your argument into different cases
- prove the conclusion for each case

This is especially important to remember when the quantifier is "For all", because you can find the different types of the variable and prove all of them to prove "all" of the variables. For example, in the case of "For all of n that is a natural number, n^2 + n is even." There is n and n+1, and one of them has to be even, so their product must be even.

Case 1: n is even, then n is even.

Case 2: n is odd, then n+1 is even.

For reference, this proof is important to remember in the future.

2) Proof <=>:

-  to prove the implication to be True, you can prove the forward implication, or disprove the reverse implication
- also, remember to use additional "made-up" variables to substitute for things within an expanded equation in the proof... not sure how to explain this in words but the variable "k" in the following proof is a good tool

That is the proof for the forward implication. The following is the disproof of the reverse implication, which has the same end goal.

3) Patterns of interference

There are two categories of interference rules:

1) Introduction: smaller statement => larger statement

- Negation introduction
         - Assume A
         - ...
         - Contradiction
         - Not A

- Conjunction introduction
         - A
         - B
         - Therefore, A ^ B

- Disjunction introduction
         - A
         - A v B
         - B v A

         -(nothing here)
         -A v not A

- Implication introduction
         - Assume A
         - ... B
         - Therefore, A=>B

- Equivalence introduction
         - A=>B
         - B=>A
         - A<=>B

- Universal introduction
         - Assume a is an element of D
         - ....
         - P(a)
         - Therefore, for all of x in D, P(x)

2) Elimination: larger statement => smaller statement

After typing all of the above examples in introduction, I realized that you can't really tell the vertical subtraction methods that Larry used in his slides, which are actually very helpful in visualizing the process. So for Elimination, I will give the examples in images.

Sixth Lecture - October 14th, 2014

After receiving the grades of our first test today, I became more confident in myself for this course. This week we learned about proofs with non-boolean functions and limits. Non-boolean functions are those that do not return True/False, for example, x^2>x or |x|, or most importantly, the floor of x. In short, the floor of x takes the lower integer value of x when it is a decimal. For example, to floor x when x is 3.5, it would result in 3. And floor 3.99999 is also 3. But to floor 4, it is 4. You cannot apply a quantifier to the floor of x as it is a function. I'm going to write a simple proof involving the floor of x so I can remember this down the road.

Enough about floors. I also learned about proving limits. I guess something to always remember when proving or disproving limits is to keep your mind open. For example, to prove something True, you can sometimes just disprove the contradiction, especially in cases where the contradiction uses an existential quantifiers. And, always make smart decisions when setting a variable as a value to prove True or False.

Fifth Lecture - October 7th, 2014

Today was our first term test and I think I did fairly well. The questions were similar to the practice test that Larry emailed us so I was quite prepared for something of similar format. Even if I did not do well, here is how I will make myself feel better:
"Proof:
assume you left all questions blank
# that’s pretty bad!
 then you get 20% # rule on test paper
 assume class average is 70% # pretty high!
 then you are 50% below average
 in this term test # 70% - 20% = 50%
 then this term test weighs 6% of final grade
 # according course info sheet
 then you are 3% below average
 in term of final grade # 6%x50%=3%
 then it is below are the acceptable
 margin of error # 5% in physics
 then it is totally acceptable"

Anyway, for the rest of the lecture, we talked about proofs. It was a fascinating concept because it filled in the gaps from my previous tutorial. The first example of proving that all n that are odd means that n^2 is also odd. The use of substitutions (variable k = 2j^2 + 2j) made a lot of sense to prove that n^2 = 2k +1 which follows the same format for all natural numbers that are odd (n = 2j + 1).