After what seemed like an endless stream of induction proofs and flavours, we have finally moved on to the second major topic of the course: Algorithm Analysis. In particular, we were working on the analysis of recursive algorithms.
As a precise person, the way we analyzed complexity in CSC165 didn't sit well with me. I couldn't always come to terms with us just dismissing all of the constant time operations with a wave of the hand. It seemed like a cheap trick to me, a simplification that ruined the usefulness of our answer.
I only began to understand when I looked at complexity in a new light: I compared it to limits in calculus. When you have a limit going to infinity, only the largest degree terms have an effect on the value of the limit. In a very similar way, as the size of the problem grows arbitrarily large, only the fastest growing term is going to have a major effect with how efficient our algorithm is. This connection helped me to rationalize 'throwing away' the constant terms.
As for recursive algorithms, I find the whole unwinding process to be a simple but powerful tool to get some intuition on closed forms and time complexity (I feel dumb for never thinking of it myself!). I'm still struggling with it somewhat, though. It seems pretty straightforward to do with recursions that cut the problem into parts (like mergeSort), but I'm having difficulty using it on problems with other types of recursions, like where the problem size is reduced by subtraction. I'm sure more practice will get me on the right track with this.
Everyday it seems a thorough understanding of recursion is becoming more and more important for success in CS. The folks at Google seem to agree!
Saturday 27 October 2012
Wednesday 17 October 2012
A1 (and not the steak sauce)
Way back in the day of CSC165 (like, 6 whole months ago!), I have a feeling my TA didn't like me very much. Whenever an assignment was due, I would fire up my scanner and throw in whatever paper I managed to scribble my proofs on to. The result was a huge, disorganized and fairly illegible PDF. This year, I decided to give my TA a break and dive in to the exciting world of typesetting.
I decided to use LyX (a LaTeX based document processor), as it seemed the most user-friendly. At first, I was a little overwhelmed by the whole system. I found myself spamming the enter key and tab, wondering why my white space wasn't appearing! It wasn't until I generated the PDF that I had that "oohhhh" moment, and finally began to understand the whole WYSIWYM paradigm.
As for the content of A1, I can't say I was surprised. The assignment was longer, and the proofs more complicated, than those of CSC165, but in that class we had an assignment nearly every week. The first three problems seemed very similar to those in we have seen in lecture, with only minor changes (for example, ternary trees instead of binary).
The fourth problem seemed to be the most unusual (and the most interesting). Originally, I had tried to simply solve the claim as given, but the induction step of this claim was too difficult for me to resolve. I was lost until I reread the question, and finally took the hint that I needed to change the claim. After considering all types of binary strings, the proof was laying right there in front of me, and with some cases and a little ingenuity I think I was able to bring it home.
It seems weird that a stronger claim would be easier to prove than a weaker one, but one thing I learned is that in mathematics, you can't always trust your instincts.
I decided to use LyX (a LaTeX based document processor), as it seemed the most user-friendly. At first, I was a little overwhelmed by the whole system. I found myself spamming the enter key and tab, wondering why my white space wasn't appearing! It wasn't until I generated the PDF that I had that "oohhhh" moment, and finally began to understand the whole WYSIWYM paradigm.
As for the content of A1, I can't say I was surprised. The assignment was longer, and the proofs more complicated, than those of CSC165, but in that class we had an assignment nearly every week. The first three problems seemed very similar to those in we have seen in lecture, with only minor changes (for example, ternary trees instead of binary).
The fourth problem seemed to be the most unusual (and the most interesting). Originally, I had tried to simply solve the claim as given, but the induction step of this claim was too difficult for me to resolve. I was lost until I reread the question, and finally took the hint that I needed to change the claim. After considering all types of binary strings, the proof was laying right there in front of me, and with some cases and a little ingenuity I think I was able to bring it home.
It seems weird that a stronger claim would be easier to prove than a weaker one, but one thing I learned is that in mathematics, you can't always trust your instincts.
Saturday 6 October 2012
First Impressions
Hi reader, welcome to my SLOG, or "courSe LOG"(Ya, the acronym is a bit of a stretch). In these posts I will talk about my experience in CSC236, Introduction to the Theory of Computation at U of T. For my first post*, I thought the best thing to do would be to discuss my expectations entering this course, and how the course has or hasn't lived up to them.
To be completely honest, I wasn't very intimidated coming into this course. I've always been interested in math, and am doing a mathematics major along with my CS major. The biggest consequence of this would be that my (school) life now revolves around proofs, proofs and proofs! It was my hope that seeing them all day, everyday would help me to become somewhat competent at writing them.
The first two weeks of the course were pretty straightforward. Mathematical Induction, Complete Induction, I'd seen it all before. My first "huh" moment came in week 3, when we began studying the Well-Ordering Principle. After being introduced to it, my first thought was something along the lines of "Ok...so?". The principle itself was easy enough to understand, one of those obvious things you take for granted, but I couldn't figure out why this thing was important or how to use it to prove claims. After working through a couple examples, though, I think I'm beginning to see its use, particularly to make contradictions. Even in a theory course, it seems practice can be super helpful!
And with that, I wish you all well. Come back soon, I promise I'll write about A1 and my (mis)adventures with LyX.
-Jake
*Yes, I realize October might be a bit late for first impressions, but such is the life of a procrastinator. Also, it helped me to judge the course after actually doing work in it.
To be completely honest, I wasn't very intimidated coming into this course. I've always been interested in math, and am doing a mathematics major along with my CS major. The biggest consequence of this would be that my (school) life now revolves around proofs, proofs and proofs! It was my hope that seeing them all day, everyday would help me to become somewhat competent at writing them.
The first two weeks of the course were pretty straightforward. Mathematical Induction, Complete Induction, I'd seen it all before. My first "huh" moment came in week 3, when we began studying the Well-Ordering Principle. After being introduced to it, my first thought was something along the lines of "Ok...so?". The principle itself was easy enough to understand, one of those obvious things you take for granted, but I couldn't figure out why this thing was important or how to use it to prove claims. After working through a couple examples, though, I think I'm beginning to see its use, particularly to make contradictions. Even in a theory course, it seems practice can be super helpful!
And with that, I wish you all well. Come back soon, I promise I'll write about A1 and my (mis)adventures with LyX.
-Jake
*Yes, I realize October might be a bit late for first impressions, but such is the life of a procrastinator. Also, it helped me to judge the course after actually doing work in it.
Subscribe to:
Posts (Atom)