The course is over, and the final exam looms over the horizon of my every thought, like an inescapable eventuality. So it's a good as any to reflect back on CSC236H1F as a whole.
Lectures were fun and easy-enough to follow; perhaps the only CS lectures I didn't mind attending. The tutorial/quiz system was very fair. I had the weekend to familiarize myself with the topic, and then I got to see a similar question to the quiz being worked through. The assignments were posted far-enough from their due dates, and so I had a pretty decent time-frame to work through them. Their level of difficulty (and sometimes the type of questions) were unlike anything seen in lectures or tutorials, but that is usually the case with problem sets. The mid-terms were somewhere between the assignments and the quizzes in terms of difficulty and length. The second mid-term was a little too focused on a single concept, and the two questions were very closely related. It just felt like if you were not good at that one concept, you could forget about getting a good mark on that test (which I did!).
Now, in my head, I understand every concept in this course, and I was on top of my game pretty much for the whole semester. But I certainly feel like my mark doesn't reflect that. So what happened? I honestly don't know. Even though it really doesn't feel like it, this course might end up being my lowest mark so far in university.
There is still hope though. I'm hoping that the final won't be too challenging, and that I can improve my mark by doing good on that.
And that's that. Thanks for reading.
Wednesday 5 December 2012
A Series Convergence Problem - Cont'd
This is a continuation of the last post.
4. Looking back
I went and slept on the problem, and I'm not exaggerating, woke up with an epiphany about the problem. All night I dreamt about series and floating sigma signs. Other than the sheer weirdness of waking up with a solution to a math problem, especially one that wasn’t that hard, I did realize that there was a much simpler and more intuitive solution to the problem! The approach that I wrote up in the last post is perhaps a little brute-forcing the way to a solution. This new solution uses an evident truth about series to prove the condition in one step. Here:
Assuming a_n converges.
Since (SIGMA)a_n converges, then ((SIGMA)a_n)^2 must also converge.
Since a_n => 0, then ((SIGMA)a_n)^2 >= (SIGMA)a_n^2 >= 0.
Then by the pinching theorem, (SIGMA) a_n^2 converges.
Then, given that a_n converges, then (a_n)^2 must converge.
Solutions are either valid or invalid, but I somehow feel this is a better solution. If only you had the time to sleep on every problem in the world…
4. Looking back
I went and slept on the problem, and I'm not exaggerating, woke up with an epiphany about the problem. All night I dreamt about series and floating sigma signs. Other than the sheer weirdness of waking up with a solution to a math problem, especially one that wasn’t that hard, I did realize that there was a much simpler and more intuitive solution to the problem! The approach that I wrote up in the last post is perhaps a little brute-forcing the way to a solution. This new solution uses an evident truth about series to prove the condition in one step. Here:
Assuming a_n converges.
Since (SIGMA)a_n converges, then ((SIGMA)a_n)^2 must also converge.
Since a_n => 0, then ((SIGMA)a_n)^2 >= (SIGMA)a_n^2 >= 0.
Then by the pinching theorem, (SIGMA) a_n^2 converges.
Then, given that a_n converges, then (a_n)^2 must converge.
Solutions are either valid or invalid, but I somehow feel this is a better solution. If only you had the time to sleep on every problem in the world…
Tuesday 4 December 2012
A Series Convergance Problem
I don't know why, but I have just overcome with the urge to write up a SLOG
post about problem-solving, specifically a problem of mathematical
nature. So let's waste no time, and get to it!
If you remember from my first post, one of my favorite courses from last year happened to be MAT137. And one of my favorite topics in that course had to do with proofs regarding the convergence/divergence of various series. As such, I decided to dig through my stuff from last year, and find a question that I didn't get around to attempting to solve last year. A lemma from the textbook caught my eye, whose proof was left to the students as an exercise:
Instead of chicken scratches on a piece of paper, I decided to take the organized approach Prof. Heap referred to in the SLOG handout.
1. Understanding the Problem
Let's think about what it means for a series to be convergent. Mathematically, this means: For all ε > 0, there exists there exists some N’ in N(natural numbers), so that for all n >= N’, |a_n| < ε. So knowing nothing about sequence “a_n,” I would have to somehow show that the same thing is true about sequence “b_n = (a_n)^2”. This condition certainly doesn’t seem impossible.
2. Devising a Plan
This problem looks simple enough, but it is a bit different from the other series behaviour problems I've solved so far. From my recollection (which, I admit, is a bit wonky), either the sequence "a_n" on which the series is based on is usually explicitly given, or the formula for the series can either be: a) manipulated to a sum that has easily provable behaviour, or b) can be linked with a function whose end-behaviour can be proven using a variety of theorems. But in this case, I know nothing about the series or the sequence "a_n" on which the series is based on.
I have a few ideas about how to manipulate the relationship |a_n| < ε or - ε < a_n < ε, to get some facts about (a_n)^2, namely multiplying out the inequality by “a_n” throughout. Then, I believe, I could use the pinching theorem to justify the condition for “b_n = (a_n)^2”.
3. Carrying out the Plan
Assuming a_n converges.
Then |a_n| < ε.
Then - ε < a_n < ε.
Then – ε(a_n) < a_n(a_n) = ((a_n)^2) < ε(a_n).
Then it suffices to show the two series bounding (a_n)^2 converge for (a_n)^2 to
converge.
For – ε(a_n): – ε(– ε) > – εa_n > – ε( ε).
For ε(a_n): ε(– ε) < εa_n < ε( ε).
So (a_n)^2 is bound between – ε( ε) and ε( ε).
So –ε^2 < - εa_n < (a_n)^2 < εa_n < ε^2. And by the pinching theorem, (a_n)^2
converges.
Then, given that a_n converges, then (a_n)^2 must converge.
And there you go! It was that simple. I wish I did this last year, so I could totally feel like a mathematics prodigy.
If you remember from my first post, one of my favorite courses from last year happened to be MAT137. And one of my favorite topics in that course had to do with proofs regarding the convergence/divergence of various series. As such, I decided to dig through my stuff from last year, and find a question that I didn't get around to attempting to solve last year. A lemma from the textbook caught my eye, whose proof was left to the students as an exercise:
Assume that some series (SIGMA)a_n is convergent, and that an => 0 for all n in N(natural numbers). Prove that the series (SIGMA)(a_n)^2 also converges.
Instead of chicken scratches on a piece of paper, I decided to take the organized approach Prof. Heap referred to in the SLOG handout.
1. Understanding the Problem
Let's think about what it means for a series to be convergent. Mathematically, this means: For all ε > 0, there exists there exists some N’ in N(natural numbers), so that for all n >= N’, |a_n| < ε. So knowing nothing about sequence “a_n,” I would have to somehow show that the same thing is true about sequence “b_n = (a_n)^2”. This condition certainly doesn’t seem impossible.
2. Devising a Plan
This problem looks simple enough, but it is a bit different from the other series behaviour problems I've solved so far. From my recollection (which, I admit, is a bit wonky), either the sequence "a_n" on which the series is based on is usually explicitly given, or the formula for the series can either be: a) manipulated to a sum that has easily provable behaviour, or b) can be linked with a function whose end-behaviour can be proven using a variety of theorems. But in this case, I know nothing about the series or the sequence "a_n" on which the series is based on.
I have a few ideas about how to manipulate the relationship |a_n| < ε or - ε < a_n < ε, to get some facts about (a_n)^2, namely multiplying out the inequality by “a_n” throughout. Then, I believe, I could use the pinching theorem to justify the condition for “b_n = (a_n)^2”.
3. Carrying out the Plan
Assuming a_n converges.
Then |a_n| < ε.
Then - ε < a_n < ε.
Then – ε(a_n) < a_n(a_n) = ((a_n)^2) < ε(a_n).
Then it suffices to show the two series bounding (a_n)^2 converge for (a_n)^2 to
converge.
For – ε(a_n): – ε(– ε) > – εa_n > – ε( ε).
For ε(a_n): ε(– ε) < εa_n < ε( ε).
So (a_n)^2 is bound between – ε( ε) and ε( ε).
So –ε^2 < - εa_n < (a_n)^2 < εa_n < ε^2. And by the pinching theorem, (a_n)^2
converges.
Then, given that a_n converges, then (a_n)^2 must converge.
And there you go! It was that simple. I wish I did this last year, so I could totally feel like a mathematics prodigy.
Sunday 25 November 2012
REGEX and FSAs
Slow and steady wins the race. Slow and steady. I don't know if that has anything to do with the topic(s) at hand, but writing it just felt right.
The course is fun again. I'm thoroughly enjoying the intuitive approach FSA-related problems need to be solved. Unlike recurrences and algorithm complexity and correctness proofs that are very rigid, FSAs are very open-ended. For example, the ability to choose useful loop invariants or pre/post conditions can only be learnt by repetition, and going through very similar algorithms over and over again. However, I have been able to solve a FSA-related problem on the first attempt. REGEX seem very much in the same vein as FSAs. They seem very clear and easy to grasp, but I just have no idea what to expect in terms of proofs relating to the concepts we've learnt about them so far.
So the signs are certainly encouraging. After an embarrassing algorithm-complexity-ridden midterm (lowest mark of my entire academic life, kindergarten included), I am really hoping to make a comeback in this course through A3 and the final. A3 is 50-50 split between FSAs (or is it DFSAs?) and algorithm correctness, so it is the perfect oppurtunity for me to practice my self-proclaimed profficiency in FSAs, and get completely comfortable with algorithm-related proofs in preparation for the final exam.
Let's hope all goes well.
The course is fun again. I'm thoroughly enjoying the intuitive approach FSA-related problems need to be solved. Unlike recurrences and algorithm complexity and correctness proofs that are very rigid, FSAs are very open-ended. For example, the ability to choose useful loop invariants or pre/post conditions can only be learnt by repetition, and going through very similar algorithms over and over again. However, I have been able to solve a FSA-related problem on the first attempt. REGEX seem very much in the same vein as FSAs. They seem very clear and easy to grasp, but I just have no idea what to expect in terms of proofs relating to the concepts we've learnt about them so far.
So the signs are certainly encouraging. After an embarrassing algorithm-complexity-ridden midterm (lowest mark of my entire academic life, kindergarten included), I am really hoping to make a comeback in this course through A3 and the final. A3 is 50-50 split between FSAs (or is it DFSAs?) and algorithm correctness, so it is the perfect oppurtunity for me to practice my self-proclaimed profficiency in FSAs, and get completely comfortable with algorithm-related proofs in preparation for the final exam.
Let's hope all goes well.
Sunday 28 October 2012
Algorithms/Lectures Rant
I must apologize in advance, as I suspect these posts are becomes increasingly tedious and poorly written.
The new car smell on CSC236 is wearing off, and it is revealing itself as what it really as: a course about algorithms! Who saw that coming. And I'd be lying if I claimed to be on top of things at the moment. So far, a combination of the knowledge I acquired in the lectures, a review of the annotated slides, and a review of the Course Notes got me through any topic. But times are changing. I cannot follow the lectures completely, because at some point, they all become dialogues between Prof. Heap and a couple of students who grasp the material. It is totally and absolutely my fault for not voicing this in lectures, but hey, I have an image to maintain! As a result, I think I am going to make use of Prof. Heap's office hours a lot more in the coming weeks. The annotated slides are only useful if you have a good pre-existing understanding of the material from the corresponding lecture, which is not always the case anymore. And the lecture material seems to be beginning to diverge from the Course Notes. Understanding everything in the lecture is become more and more key, and at the same time, harder and harder. At least for me.
In other less depressing news, I spoke to Prof. Heap about the structure of my proofs on the term tests (see Week 2), and he told me that they seemed valid to him!! That was such a sigh of relief for me. At least two extra marks, here I come!
The new car smell on CSC236 is wearing off, and it is revealing itself as what it really as: a course about algorithms! Who saw that coming. And I'd be lying if I claimed to be on top of things at the moment. So far, a combination of the knowledge I acquired in the lectures, a review of the annotated slides, and a review of the Course Notes got me through any topic. But times are changing. I cannot follow the lectures completely, because at some point, they all become dialogues between Prof. Heap and a couple of students who grasp the material. It is totally and absolutely my fault for not voicing this in lectures, but hey, I have an image to maintain! As a result, I think I am going to make use of Prof. Heap's office hours a lot more in the coming weeks. The annotated slides are only useful if you have a good pre-existing understanding of the material from the corresponding lecture, which is not always the case anymore. And the lecture material seems to be beginning to diverge from the Course Notes. Understanding everything in the lecture is become more and more key, and at the same time, harder and harder. At least for me.
In other less depressing news, I spoke to Prof. Heap about the structure of my proofs on the term tests (see Week 2), and he told me that they seemed valid to him!! That was such a sigh of relief for me. At least two extra marks, here I come!
Monday 22 October 2012
Recurrences and the mid-term
I got my mid-term back and I can't really say I am happy with my mark. I lost 3 marks, all for starting my proofs with an existential assumption (ex. "Assume there exists n in natural numbers, such that P(n)"). I absolutely believe that such an assumption is valid at the start of a proof, especially given that the proof is preceded by a base case. I think that differentiating between "Assume there exists n such that P(n)" and "Let there be n such that P(n)" is not very intuitive. What does "be" mean anyways? Doesn't it signify the existence of the subject? In any case, I plan to go and speak to Prof. Heap during his office hours, so that I can either be proven wrong, or make sure that a re-marking appeal is a reasonable option for me (really hoping for the latter).
Other than that, I'm hanging on the course material with the skin of my teeth. These recursive functions are tricky, and doing proofs about them requires a level of trial and error, and certain tricks, that I'm not completely comfortable with. I've been referring to the Course Notes a lot more lately to help me grasp the material. Some steps and assumptions in the Course Notes seem very arbitrary at this point to me. For example, splitting the coefficient 'k' in knlog(n) (MergeSort) to two separate constants 'c' and 'd', was something that I could not have come up with on my own, even if I stared at the problem (proving the upper bound for the runtime of MergeSort) for a year. Hopefully by spending more time going over the Course Notes, things will get better soon.
Other than that, I'm hanging on the course material with the skin of my teeth. These recursive functions are tricky, and doing proofs about them requires a level of trial and error, and certain tricks, that I'm not completely comfortable with. I've been referring to the Course Notes a lot more lately to help me grasp the material. Some steps and assumptions in the Course Notes seem very arbitrary at this point to me. For example, splitting the coefficient 'k' in knlog(n) (MergeSort) to two separate constants 'c' and 'd', was something that I could not have come up with on my own, even if I stared at the problem (proving the upper bound for the runtime of MergeSort) for a year. Hopefully by spending more time going over the Course Notes, things will get better soon.
Thursday 11 October 2012
Bounds, Well-ordering, and A1
We're already a month into the semester! They say time flies by when... actually time flies by all the time. Before I know it, I will be a broken down old man. But for now, I will continue to distract myself from my mortality by doing things like going to school, and learning about computers.Which swiftly bring me to the topic at hand: my favorite course of all time, CSC236!!
I was perhaps ten minutes into the first CSC236 lecture of the year, when I high-fived myself out of pure joy. I was really glad that I had taken MAT137 over MAT135 ("Calculus!" not "Calculus") last year. When I told my friend about my experience of extensively using induction last year in relation to limits, behaviours of functions, bounds on series, and a lot of other stuff, the response that I got was a blank stare. So while a few of my friends struggled for the first few classes to wrap their minds around the concept of induction itself, and why it is valid at all, I certainly felt like I had a head-start in the course.
By the time "Well Ordering" had arrived, the course was beginning to get a tiny bit more challenging. Even though I had used the same principle in the aforementioned math course in relation to bounds and sequences, the "round-robin tournament" proof done in class by Prof. Heap threw me off. While I understood the logic of the proof, it still felt invalid to me. So I went home, read over the annotated slides (by the way, THE GREATEST IDEA OF ALL TIME), and I still felt that the proof was invalid. So I did what any scholar in this day and age does: I loaded up Wikipedia. More specifically, the "round-robin tournament" page. It turned out that I had a false understanding of what a round-robin tournament was to begin with. My understanding was that the tournament is a elimination-style one-match-at-a-time tournament, while that is not the case at all. Either I had a lapse of concentration in the lecture and the concept was explained, or that everyone knows what a round-robin tournament is and I just had a gaping hole in my knowledge. In any case, everything was back to normal.
I felt like I was ready for the final exam right then and there... but then Assignment 1 happened. Three straightforward questions which collectively took 45 minutes, and then a monster in the form of question 4. Binary strings. Occurrences of 10s and 01s. I must have written 3 or 4 separate proofs for that question, but none of them felt completely valid to me. It was Friday, the assignment was due that night, and I was stuck. I didn't know what to do. It was actually Prof. Heap's hint in class about starting out with a stronger claim that gave me the idea. So like any geniuses I've seen in the movies who get a great idea in the middle of a class, I got up and left and knocked over everyone's papers and almost tripped on someone's bag, walked to the closest window and took out a marker and started writing on the glass. OK, none of that happened, but I finished my proof after class, and just to make sure that my approach was valid, I went to the extra office-hours on Friday, and indirectly, and without getting into too much detail, explained my approach, and Prof. Heap indirectly, and without getting into too much detail, replied that it sounded valid.
I must apologize for having such a long post, and I feel for Prof. Heap and the TAs who have to read several hundred of poorly written, very similar posts about students doing proofs. But hey, that is what you get when you shut down the alternative "Student Tweets" assignment, which would've made life easier for all parties involved.
Stay tuned for a preview from next week's episode of SIAMAK'S CSC236 SLOG:
.
.
.
Mid-term exam!!! Was it a success or failure? Find out if this student aced the test, or if he was dealt a tough hand! Next week on SIAMAK'S CSC236 SLOG.
I was perhaps ten minutes into the first CSC236 lecture of the year, when I high-fived myself out of pure joy. I was really glad that I had taken MAT137 over MAT135 ("Calculus!" not "Calculus") last year. When I told my friend about my experience of extensively using induction last year in relation to limits, behaviours of functions, bounds on series, and a lot of other stuff, the response that I got was a blank stare. So while a few of my friends struggled for the first few classes to wrap their minds around the concept of induction itself, and why it is valid at all, I certainly felt like I had a head-start in the course.
By the time "Well Ordering" had arrived, the course was beginning to get a tiny bit more challenging. Even though I had used the same principle in the aforementioned math course in relation to bounds and sequences, the "round-robin tournament" proof done in class by Prof. Heap threw me off. While I understood the logic of the proof, it still felt invalid to me. So I went home, read over the annotated slides (by the way, THE GREATEST IDEA OF ALL TIME), and I still felt that the proof was invalid. So I did what any scholar in this day and age does: I loaded up Wikipedia. More specifically, the "round-robin tournament" page. It turned out that I had a false understanding of what a round-robin tournament was to begin with. My understanding was that the tournament is a elimination-style one-match-at-a-time tournament, while that is not the case at all. Either I had a lapse of concentration in the lecture and the concept was explained, or that everyone knows what a round-robin tournament is and I just had a gaping hole in my knowledge. In any case, everything was back to normal.
I felt like I was ready for the final exam right then and there... but then Assignment 1 happened. Three straightforward questions which collectively took 45 minutes, and then a monster in the form of question 4. Binary strings. Occurrences of 10s and 01s. I must have written 3 or 4 separate proofs for that question, but none of them felt completely valid to me. It was Friday, the assignment was due that night, and I was stuck. I didn't know what to do. It was actually Prof. Heap's hint in class about starting out with a stronger claim that gave me the idea. So like any geniuses I've seen in the movies who get a great idea in the middle of a class, I got up and left and knocked over everyone's papers and almost tripped on someone's bag, walked to the closest window and took out a marker and started writing on the glass. OK, none of that happened, but I finished my proof after class, and just to make sure that my approach was valid, I went to the extra office-hours on Friday, and indirectly, and without getting into too much detail, explained my approach, and Prof. Heap indirectly, and without getting into too much detail, replied that it sounded valid.
I must apologize for having such a long post, and I feel for Prof. Heap and the TAs who have to read several hundred of poorly written, very similar posts about students doing proofs. But hey, that is what you get when you shut down the alternative "Student Tweets" assignment, which would've made life easier for all parties involved.
Stay tuned for a preview from next week's episode of SIAMAK'S CSC236 SLOG:
.
.
.
Mid-term exam!!! Was it a success or failure? Find out if this student aced the test, or if he was dealt a tough hand! Next week on SIAMAK'S CSC236 SLOG.
Subscribe to:
Posts (Atom)