The End is in Sight!

Finals are almost over!

So we decided to celebrate,

BY MAKING PIE.

And then smothering it in chocolate and eating it.

It was very tasty. And quite over-brandied. ('s all good, eh?)

Just like exam season SHOULD be.

Here's to the final week!

Cheers!

A Note on Procrastination

Warning: this is yet another random post that has absolutely nothing to do with logic (in fact, it's quite illogical). But that's ok, since we're officially not being graded for content anymore, eh? (Oh look at me being all Canadian. Only took 3 years!)

On with it.

If I was getting tested on dancing or napping or recently watched movies on Friday, I think I'd ace it. Unfortunately, Finance requires quite a bit more effort than that. I know that. Really. I do. Trust me.

I just don't act on it much. This unfortunate feature has been labeled Procrastination (capital P. Always). One of my shortcomings, that, but hey, nobody's perfect eh? Moreover, I'm not alone in my misery: this often-fatal disease affects a larger percentage of the population than most would believe (unless you're guessing 100%, then you're pretty much spot-on.) It is characterized by an illogically optimistic outlook on life (often brought on by blatant ignorance of reality and all it entails), and shirking of any and all current and future responsibilities.

Most affected victims live in a blissful, imaginary realm called Tomorrow.

It often proves difficult for captives to escape until - at earliest - the day before a looming deadline or - at worst - never. Even so, these momentary flashes of reality escape provides prove to be so traumatic for the escapees that they are erased from memory immediately after the deadline (exam) has passed (or in some unfortunate cases, beforehand) leading to more continuous, repetitive and quite acute cases of Procrastination in the future.



A cure has yet to be uncovered. The future looks bleak.
To all fellow Procrastinatees, I salute you.

Week the Last: Some Definitions

So I've slacked a bit in this blogging business lately. In my defense, I had nothing to write about (still don't really, but I feel I've kind of got to write something at this point so here's hoping it's slightly more substantial than mere gibberish.)

So, what's been happening since last I wrote? (Good question, wish I knew.) Well, I do remember we had the second (and last, bar the final) test of the course, and the second assignment due as well. We got the marks back too, which goes to show just how absent I've been. Both went quite well (I'm being modest; I feel I deserve a pat on the head or something at this point.) so I'm (super) happy (ecstatic) with that.

In class we've been doing proofs with "Big-O", Omega and Theta. In lieu of recreating massively long-winded proofs here, I'll simply write the definitions for future reference:

Big-O:
formally, there exists a 'c' and 'B' such that for every 'n', if n >= B --> g(n) <= c*f(n)
in English, if g belongs to O(f), that means that g grows no faster than f. In other words, f is an upper bound of g.
Omega (aka the horseshoe):
formally, there exists a 'c' and 'B' such that for every 'n', if n >= B --> g(n) >= c*f(n)
in English, if g belongs to Omega(f), then g grows at least as fast as f; f is a lower bound for g. In other words, it's basically the opposite of the Big-O (yay opposites!!)
Theta (the halved egg):
formally, there exists a 'c1', 'c2' and 'B' such that for every 'n', if n >= B --> c1*f(n) <= g(n) <= c2*f(n)
in English, g grows at the same rate as f. f is both an upper and lower bound for g.

Boy, will I have fun with those tonight while working on assignment 3! All joking aside, while I do need more practice before I'm fully comfortable with them, they're not all that bad. They just look super funny (drawing horseshoes is harder than I thought).

All this aside, there is at least one more problem that I hope I'll get a chance to blog about before this course finishes and I lose the artificial excuse to do math for fun. Danny introduced the "Penny Piles" problem a few weeks back, which has proven quite fun to work on, but less fun to complete (and, being a bit of a perfectionist, I must say that it's part of the reason I've delayed writing for so long.) Perhaps I'll have time after this week finishes to sit down and write it nicely. Or, more likely, I'll get eaten alive by a mixture of exam season, alcoholism, sugar/caffeine overdose, and/or blatantly ignoring reality. Who knows.

At least Danny eased some of our worries a while back by saying "A&S arranges their exam schedules in such a way that most of my students are sleep deprived when they write the 3-hr exam, so I don't have to make it more gruesome than that." Small mercies.

Let's hope Robarts implements "puppies-and-kittens-stress-relief" one of these days (the procrastinating liars). Till then, here's a kitten to de-stress with:

(kitten is not mine, nor is the pic)

Cheers!

In Hindsight, Diagonals.

So I've not posted for a while... 2 weeks' worth of lectures to be precise. Well, in hindsight week 6 and 7 involved Lots of Proofs (with Caps). Well, definitions of different types of proofs. Not much to say about that; I'm sure you can read about proofs by contradiction or by case or by pretty much anything in any Logic (or Math) textbook till your eyes fall out if you so desire.

So, instead, let's talk about Diagonals!

On the Friday before we all dispersed to various corners of the earth (or continent, or simply to our rooms) for Reading Week, we spent the lecture working on another rather fun problem (this time involving drawing on paper, not folding it!) It goes as follows: you are given a rectangular grid of (mxn) squares, with m and n representing positive whole numbers. If you draw a diagonal line from the upper left corner to the lower right, how many grid squares will this line pass through the interior of?

Let's remember good ol' Polya.
Step 1: the problem - we want to find the number of squares the diagonal passes through. More specifically, we want a general formula for finding this number, given m and n.
Step 2: devise A Plan - first, obtain grid paper; then, draw! More specifically: start small, draw a few rectangles and try to find a general trend between m, n, and the number of diagonal squares (let's call it d.)
There's a few things in particular that we can pay attention to: if m = n, we know the diagonal will pass through m squares, because it will pass exactly through the intersections of the horizontal and vertical grid lines.
Similarly, we don't care if m > n or n > m, because the diagonal will still be the same length, and still pass through the same number of squares.
Next, if either m or n is 1 (for simplicity let's assume it's m), we know that the diagonal will pass through n (in this case) squares.
Armed with these observations, we can then begin drawing some examples, and trying to find similarities:

Step everything-else-jumbled-together: As you can see in the quite hazy (apologies, but you'll survive) picture above, I started with small examples, and tried to find patters based on the difference between m and n, and whether they were even or odd. I (eventually) found a few patterns:

1.) Regardless of the difference between m and n, with a little algebra the number of squares the diagonal passed through was clearly (m + n - 1), when m and n did not have a common divisor other than 1 (as seen in the examples of m = n - 2, m,n = odd , and m = n - 3. In both cases gcd(m,n) = 1). In these cases, the diagonal did not pass through any intersections of the horizontal and vertical grid lines.

2.) In cases where the rectangle we drew could be broken into smaller ones (ie when the diagonal did pass through some of the vertical and horizontal grid intersections), the problem was a bit different. You can see some of these cases by looking at the 2x4, 4x6, 6x9, and 9x15 rectangles. Take the 4x6 one, for example: we can easily see that this large rectangle can be broken into 4 smaller 2x3 rectangles (let's say a = 2, b = 3), of which the diagonal will pass through the top left and bottom right ones. Therefore the number of squares the diagonal passes through is 2x (# squares passed in 2x3), which is 2(a + b - 1) = 2a + 2b - 2 = m + n - 2, since m = 2a, and n = 2b. Similarly, the 6x9 rectangle can be broken into 9 smaller 2x3 rectangles, of which the diagonal will pass through 3. Therefore d = 3(a + b - 1) = 3a + 3b - 3 = m + n - 3, since m = 3a and n = 3b. We can see through more examples (or simply by sitting down and turning your brain on for a bit) that this trend holds for all such rectangles. Therefore, the above trend, (m + n - 1), can be rewritten to work for all rectangles as:

d = (m + n - gcd(m,n)) (QED.)

So to recap:
Polya's a decent bloke to listen to when in a pinch, and, considering this question took a few days of staring blankly at paper and tracing squares when it should have only taken a few minutes of deep (well, superficial, but still), meaningful insights, Hindsight really is a B****!

Some memorable quotes:

On talking of variables used in proofs: "Just the fact that they're in a familiar alphabet and don't....REEK of Calculus so much should make it easier."

On talking about Natural numbers used in proofs: "We're computer scientists; we let 0 into the exclusive club of natural numbers. So do Calculus people, who are narrow minded, so that should say something..."

And finally, seemingly on life in general: "Just take a break and draw some pictures!" to which I'll say, after doing this proof, I don't want to even contemplate the existence of pictures for a few weeks.

Looking forward to the next long-winded blabbing session. Till then, cheers!
Pip

The Logic of Like

(Warning: the following ramblings involve a high probability of dangerous to near-fatal overflow of possibly quite putrid cheese. They also have about zero relevance to CSC165, because on (frequent) occasion my brain wanders away from the astoundingly brilliant thralls of logic (so... whoops). Prepare yourselves accordingly - I'd suggest with a well stocked wine cellar. Well, except for you unfortunate underage firsties...which may be the majority of people in this class. Ah well, not like you'll read this anyway, but still, sucks to be you guys!)

So, I missed the mark by about 2 hours (because every sane person'd rather code stupid CSC148 projects than go out and get drunk with people right? Though I shouldn't complain, since I dabbled in both today), but Happy Free-Chocol - er...I mean Valentine's day! That one. (But also "Free Chocolate Day." And also "Sh**Ton-of-Consumerism Day." And also probably many, many others.) Yes.

So, I've got a story.

Unlike what an apparent majority of people and TV shows like to say, I actually had a great experience in High School (and no lockers were harmed during the course of my adolescence.) It probably helped that my parents shipped (well, bussed) me off to a private school for a few years, which had an impressively competent (and interesting!) set of teachers.

My favorite was probably the math teacher. For being completely grey-haired, he was an incredibly chipper and completely dorky guy (on the rare occasion that it snowed more than a centimeter in winter, he'd take his preschool-aged kids out and make TI-83 calculators instead of snowmen (complete with graphs!) and then - predictably - take pictures to show to the gaggle of estrogen-laden teenagers in his Calculus classes. "Right on!" (yep, he also talked like a wanna-be surfer. Don't ask why. Nobody knows.))

Anyways, it was during one of these glorious Calculus-ignoring occasions when he nonchalantly pulled out an unhealthily-pink napkin heart-stamped containing illegible scribbles out of his pocket, leaned against the table at the front of the classroom, and imparted the following story to the amassed flock of girls about an event that had happened at his daughter's preschool the other day.

On the day in question, he'd arrived to the school early, and found that his daughter's class was in the process of reading a story. He figured he'd wait, since there were only 10 more minutes or so, and went to sit down in a nearby corner to twiddle his thumbs for a bit. It was after a few minutes of sitting that he noticed one of the boys in the class - a friend of his daughter's - edging closer, and finally coming to sit down next to him. 

"Hey there, buddy, how's it hanging?" He tried, only to get an enormous soul-wrenching sigh from the boy. 

"Mister," the boy said morosely, "how do you know when you like someone? Cuz I think I may be half in like with your daughter."

"Half in like?" He asked. "What do you mean by that?" (and, ever the opportunist, fished out the gaudy pink napkin and a pen from his pocket to transcribe the sure-to-be-amusing response.)

"Well," the boy began, thinking deeply, "I like playing with your daughter at recess the best, and when I'm with her and she smiles I get a warm fuzzy feeling in my tummy. It's getting warmer every time I see her. I don't think it's full like yet, only half like, but  I think maybe that'll change one day. Anyway, I just wanted to let you know that's how I feel." The boy finished, and quickly shuffled away as class ended and children dispersed, leaving my professor quite speechless.

"And that," my professor concluded to the enthralled mass of girls in Calculus, "is probably the best definition of 'like' and 'half like' I have ever heard, and it was said more concisely by a 5-year-old than any adult ever could!" (The girls, predictably, sighed and squealed like the fangirls they were.)

Cheesy as it is (and man is it! It's almost painful writing it), I still remember this story every Valentine's day, and like my prof, all I can think is "Well said, little guy. You'll go far with that logic." (It certainly won over every girl in my class! Hats off to the future him for his luck with the ladies.)

Valentine's isn't special (though it does involve chocolate, and that - if nothing else - has merit.) Even so, hope you all had a good day (and happy chocolate hunting tomorrow - yay sales!) Cheers.

Week the Fifth (in Hindsight)

Aaaaand it's all about proofs! Though it was cut short by that test I mentioned (which went decently, I thought, in case you were hanging off the edge of your seat in anticipation.) Still, 2 lecture's worth of material is enough to lay a decent introduction to the methodology of proofs (...that's not to say, however, that I'll have much to write about this week. I've a feeling that this post, like the week's lectures, will be cut rather short.)

Onwards! As mentioned last time, Danny's rather obsessively preached the importance of structure in the proofs. (I think that part of the lecture has by far overlapped all others at this point.) But in between the indentations, he's also mentioned a few examples of actual proofs, and showed us how to go about tackling them.

Memorably, sometimes proving things in one direction is easier than in the other (for instance, proving that for any real number n, n being odd implies n^2 is odd is much easier than proving that n^2 being odd implies n is odd.) In cases like these, it is therefore useful to think of a way to invert the problem. Lo and behold, the contrapositive exists! (So use it. QED.)

Also memorably, in trying to prove things like "there exist an infinite number of primes," you can use proof by contradiction (assume the opposite is true - there is a finite number of primes - and try to disprove that.) So, it goes something like this:

Counter: there exists a natural number n such that n is larger or equal to the largest positive prime number.
           assuming that the universe's primes are all in the finite set P = {p1, p2.........pk},
           you can deduce that there is a number m that is the product of all these prime numbers
               (m = p1*p2*...*pk), and is a natural number since all primes are natural and this set is  
               closed under multiplication.
           then m is some number that is ultimately greater than 1 (since p's are greater than 1)
           then m + 1 is greater than 1 (because of above)
           then there exists a prime number p that exactly divides (m + 1) (since every natural number
               greater than 1 has a prime factor - if prime, itself, or if not, its composites)
          and p must also exactly divide m, since m is the product of all prime numbers
          then p must exactly divide ((m + 1) - m), or 1
          which implies p = 1
          but under the definition of prime numbers (one which has only 2 natural numbers that divide
               it), 1 is NOT prime, so that's a CONTRADICTION
and therefore the original claim must be true. (Yay!)
...which is probably a better proof of this problem than the following:

In case you're ever stuck on a problem, here's some useful advice from Danny: "I look up and to the left quite often, because that's where answers seem to come from." (it does explain all those thousand-yard stares during exams.)

Week the Fourth

I've come to a conclusion: recursion is a bloody pain in the arse (though, admittedly, a rather beautiful one if done right.)

This, however, has nothing (yet?) to do with CSC165. It's quite possible that most of these ramblings won't, because this post is a week late and will therefore probably manage to center itself on the reason of lateness (aka the comp sci test we had yesterday morning, which involved - you guessed it! - recursion!! Grumble.)

Ah, what I'd give to be a Time Lord....

But I'm not. Moving on. This (well, last) week we talked about Limits, and Proofs (and probably a lot of other things that I may have forgotten to write down.)

Taking a Limit, apparently, is like waging a dismal, complex, one-turn war against your horrendously evil arch-nemesis, in which they try to make you look ridiculous by picking an epsilon which gives you a seemingly-impossible target, and you in turn laugh in their face with maniacal glee as you cleverly choose a delta in response that crushes their hopes as efficiently as dropping a one-ton brick on a piece of packing foam (which is to say, completely.) At least, that's the gist I got. It also gives a whole new meaning to "nice guys finish last" - after all, if you're the 'nice' guy picking the delta you'd better ensure you're choosing after the epsilon is set by your dashingly evil alter-ego. (as Danny eloquently put it: "Switching epsilon and delta: that is DEADLY. Don't. Do. It.") And that was, as far as my memory allows, the majority of Wednesday's lecture.

On Friday, we began fluttering about the topic of Proofs. I say 'began' to hopefully signify that I know close to nothing about this so far, and therefore have very little to say on the subject beyond the fact that apparently the TA's and Danny will be pickier with our structuring of the proof than Python running a Pep8 on a file (which is to say, excessively so.) Beyond that, I'll relay, as always, some of Danny's insights:

During our first proof of the course (n odd implies n^2 odd): "I inevitably get asked, 'Sir, what's your definition of an even number?'...as if it's up to me!" well, he said that, but he still gave us a darn good definition (even num = 2*n, odd = 2*n +1)

About proofs in general: "Some students come to me and say: 'I'm not really comfortable proving this; can't I use logic?' And that's great, because it implies 'Hey, here we have proofs, and over there we have logic, and they have NOTHING to do with each other!' " (They do. Hence the course. Oh Danny, thank god you have a sense of humor.)

And finally, for a bit of fun: "Impatience: the second cardinal rule of programmers." Which leads me back to thinking of CSC148, but hey, it was bound to happen. Thank god that test is over though. Now to worry about the one tomorrow for this course! Thankfully, I'm feeling relatively confident so far. We'll see how it goes, I suppose. Cheers!