Proof by Cases and Big Oh

A fairly interesting method of proving proofs was brought up today!

Proof by cases.

In essence, by dividing a problem into sub-problems that cover all possible cases for the large problem, we are able to "chunk down" the problem, making it more feasible to tackle it.  With the instance of math problems for instance, by separating the possibilities with cases like when x > 0 or x <= 0, it makes it far easier to prove an implication.

But having finally finished doing proofs, we also were introduced to run-time!  Which boils down to the number of "steps" (i.e lines of code) that were run for a given function with a particular input.  This enables us as computer scientists to tackle more theoretical issues without constantly having to work around physical limitations like current computer processing speed.  I'm excited to see what we'll learn next week, as we're finally learning something with such an obvious and direct connection with programming.

Personal Experience with CSC165: How I found the course so far.

Not that much new material, so I might as well talk about how my experience with the course so far.

While intimidating to begin with, the course has really slowed down in terms of pace.  When we were being introduced to conjunctions and the various quantifiers, it was fairly quick and a bit challenging at times.  But it feels like the proof lectures are bloated, and are extremely repetitive.  It's strange to get "taught" things like proof by contradiction, and how to disprove statements etc. when this was already expected of us to be able to do three classes ago.  I suppose it's to emphasize the importance of being able to write formal proofs.

It also may simply be a change in curriculum.  I was very surprised to see a near complete absence of proving equivalent statements on the test.  I don't think we needed to use a single law, which was 90% of what I had on my cheat sheet.  There was also a shocking lack of proofs, given their coverage in the tutorial classes.  That said, I've been told CSC165 used to be ridiculously difficult, with averages from even just two years ago as low as 50.5%.

While I'm happy to see the course not be it's former demonic student-slaying past, it's a bit dry and uninteresting to listen to something like 3 weeks of the same material.  Still, there's a lot of course left, so I hopefully we can learn some more interesting concepts soon!

Mid-term and Proofs

Mid-term Finished Confetti!

    As promised!  Mid-term went well, or at least I think it did.  The thing that caught me off-guard was how exceedingly similar it was to the provided past mid-term, so as long as you reviewed that one you were set.  That said, it's worth pointing out a single mistake in the first section could take that juicy 100% to a modest 75%, if you were to confuse any two python functions.

    But as to not dilly-dally, we also jumped right into proofs after our test was over and the various ways to do them!  And we went over arguably one of the most important methods of proofs there are:  Proof by contradiction.

    At first glance, it's difficult to prove things that are a bit more abstract in concept, or seem tedious to run through every possible combination of.  Are there an infinite number of prime numbers?  Is the square root of 2 irrational?  Indeed, by proving there is a contradiction in the opposite, you are thereby proving the original statement to be true.

    One of the simpler examples provided in class was the following statement:  There are five boxes, that all together contain a total of 51 balls.  Prove that at least one box has 11 balls.  This may seem tricky to prove at first, but becomes reasonably trivial if we merely use proof by contradiction.  By assume that every box has at most 10 balls (for the statement to be false), we can immediately then show the 5 boxes can only have a maximum 50 balls (10 * 5), thereby demonstrating a contradiction!
   

Making this image may or may not have taken longer
than the time to make any of my blogs

Pre Mid-Term Thoughts

    So the mid-term quickly approaches for CSC165H1, and while I'm nervous I'm definitely eager to get it out of the way so I can focus on other things as well!  What I found interesting going over the lecture notes is indeed how far we've progressed.  What once looked like a myriad of nonsensical-mathematical hieroglyphics has become our proverbial playground which we manipulate with the laws we know well and true (or just use our aid sheet cough).  While I still hesitate to say I can easily do formal proofs, the manipulation of implications, conjunctions, and the like seems surprisingly straight forward.

    Had a bit of issue though with understanding the importance of the order of variable declaration.  I had actually been under the impression until now that "Some x in X, all y in Y" was the same as "All y in Y, some x in X".  It's a very nuanced distinction, but an important one to know before the mid-term.

   Apologies for a fairly dry (and short) blog this week, obviously a bit busy doing various assignments and preparing for mid-terms and the like.  But hopefully next week there will be happy confetti pictures over the success of the midterm!

The Manipulative Nature of Manipulation Rules

As we dwelve deeper and deeper into the myriad of logical equations, it helps a great deal to be able to recognize certain patterns, and to understand what, and what is not actually equivalent to one another.  And so with the introduction of conjunction, disjunction, as well as negation, it becomes more and more important to know these logic laws like the back our hands!

Maybe not the approach I had in mind.

The manipulation laws are actually quite intuitive, and don't really need that much memorization as long as you know what you're looking for.  I found them  to be very similar to the rules of addition/subtraction, so below are some of my analogies I came up with:

Identity: P ∧ (Q ∧ ¬ Q) ⇔ P
P + ( X + (-X) ) = P

Commutative: P ∧ Q ⇔ Q ∧ P
P + Q = Q + P

Associative: (P ∧ Q) ∧ R is ⇔ P ∧ (Q ∧ R)
(P + R) + Q = P + (Q + R)

DeMorgan's: ¬ (P ∧ Q) ⇔ ¬ P ∧ ¬ Q
-(P + Q) = -P + -Q

Naturally this doesn't cover all of the laws, such as the quantifier distributive and idempotency, but it helped me easily recognize some patterns, especially if I treat the conjunction/disjunction symbol like a plus or minus sign!

Start of CSC165: Ambiguous Sandwiches

    Hello TA, and presumably anyone else who's bored enough to read this.  This is the weekly SuyLoG, where I'll be posting thoughts, feelings, and problems that arise throughout CSC165.  I'll be your guide into the tumultuous mind of yours truly, as I try to decipher the hieroglyphics that we call quantifiers and the like.

These are things that mean things.

    Thankfully, in the first two weeks we started out nice and slowly, easing into the course by discussing things like the importance of ambiguity vs. precision.  Intuitively, I think we all expect that being completely precise would be the ideal.

In truth however, as anyone who has written a computer program might profess, being precise can often being exceedingly tedious, whether it's having to look up the exact name of a function, or trying to track down that ever-elusive semi-colon.

Ah, the joys of the high-precision language of programming

    So practically speaking, being ambiguous is fine, because we can use context clues to quickly and effectively understand what is trying to be conveyed.  But sometimes, the ambiguity of our language can cause confusion.  Like in sandwiches.

High in deliciousness, cholestrol,
and confusion.

    A seemingly innocuous sentence.  "The sandwich tastes delicious".  But from the perspective of computer scientists, this sentence lacks pertinent information, or what we call an open sentence.  This means we can't evaluate the sentence without more information.  While you may be tempted to say that if S is a set of sandwiches, and D is a set of a delicious elements, then the statement claims:
Some elements in S are in D.  WRONG.  

    Because the sentence doesn't want any old sandwich, it wants the sandwich.  And seeing as we don't know what sandwich they're talking about, we can't evaluate it!

    But wait, this is where things get confusing.  Where do we draw the line in the sand, and say that the sandwich has been fully specified (and therefore we can evaluate it).  If we were to say "This or That sandwich was delicious", then surely it's implied we should know what sandwich they're talking about.  But does that not also apply to "the" sandwich?  In fact, even taking it to the next level like "The bologna sandwich I just ate was delicious", might not be accurate enough.  Perhaps he ate two sandwiches at once, and you have no idea which sandwich he was referring to!

    Of all the things to be confused about in a Computer Science course about mathematical expression and reasoning, you really wouldn't think it'd be a sandwich.