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!