So in the beginning of this arduous journey, I wrote that I am bound by no identifier. Does this also apply to the concept of Big O? Perhaps. If I were to represent some sort of mathematical function, then perhaps I would be bounded by some function of one degree higher than myself.
With the lecture given a couple of weeks ago, our CSC236 class has been once again introduced to not only lower bounds, but upper bounds as well. We are able to know great things about functions if we happen to know its upper and lower bounds. For example, why would I ever want to use an algorithm if I know that its upper bound during a worse-case application is significantly higher than another algorithm? I do not know about others, but personally I prefer my algorithms to run smoothly, consistently and quickly. Thus, by looking at these bounds, I can determine the most effective algorithm for all my needs! Thus I am greatly eager to learn more techniques to make my life easier.
Another interesting thing that we have been spending a lot of time on is the concept of unwinding. This is yet another fun and useful tool to make life simpler. Instead of having to recurse through a recursive function, we are able to generate a closed-form version of an otherwise tedious formula. Consider the case where we have to use a recursive formula for n iterations where n is a really large number. Thus we have to spend the time it takes to use the formula once, m, n times. So we spend m*n time. Instead, we could spend m time in order to unwind the formula once which provides us with a formula that only takes k time, a value significantly smaller than m, to process. Thus this gives us a k*n + m time to solve the same problem! But since k is such a small number, let's say m / 5, then that simplifies the time-spent comparison between the two algorithms. So you have m*n without unwinding and m*(n+5)/5 with unwinding. You can see now that the difference in time can be astronomical if either m or n are really large numbers. Ahhh, what a time saver.
This class has definitely been one of my favourites this term, which is a surprise because I didn't really enjoy CSC165.
Until next time,
-ラムダ
Sunday, 28 October 2012
Sunday, 21 October 2012
The return of the Big O
So this past week, we've been returning to the main topic covered in CSC165 - upper bounds and lower bounds. They were a fun topic last year, and I expect them to be equally as fun (albeit much more difficult!) this time around.
Like always, I have prepared myself for this daunting task by reading through some of the textbook and compressing the important principles and details into a textfile for easy locating. This is becoming a habit of mine since I have never done this for any other class; I generally write down notes while reading. Since adopting this practice, I am now able to study anywhere (since I bring my laptop everything) and I can even give these files to others. Talk about hitting two birds with one stone!
At Thursday's lecture, we got our midterms back. Overall I feel good with my mark, although there is a small issue with my mark so I intend to submit a remark request. After looking over the term test 1 grading comments, I still fail to see where I lost the mark on question 2. It most definitely does not help that there is no red pen to be seen anywhere in the text, but I understand that the TAs have a lot of tests to go through and it would be extremely time consuming for them to write an essay on each. In fact many classes' TAs take an extraordinary long time to hand back tests and assignments, so I have to be grateful that ours were quick.
Assignment 2 has now been posted, and if I had learned anything from Assignment 1, it's to start early. Last time I had the experience of struggling with LaTeX and I got so frustrated in the end, I just went back to the good old MS Word. It came out fine so I'm not complaining.
That was pretty much my week in a nutshell, on to the next week (and another term test!).
-ラムダ
Like always, I have prepared myself for this daunting task by reading through some of the textbook and compressing the important principles and details into a textfile for easy locating. This is becoming a habit of mine since I have never done this for any other class; I generally write down notes while reading. Since adopting this practice, I am now able to study anywhere (since I bring my laptop everything) and I can even give these files to others. Talk about hitting two birds with one stone!
At Thursday's lecture, we got our midterms back. Overall I feel good with my mark, although there is a small issue with my mark so I intend to submit a remark request. After looking over the term test 1 grading comments, I still fail to see where I lost the mark on question 2. It most definitely does not help that there is no red pen to be seen anywhere in the text, but I understand that the TAs have a lot of tests to go through and it would be extremely time consuming for them to write an essay on each. In fact many classes' TAs take an extraordinary long time to hand back tests and assignments, so I have to be grateful that ours were quick.
Assignment 2 has now been posted, and if I had learned anything from Assignment 1, it's to start early. Last time I had the experience of struggling with LaTeX and I got so frustrated in the end, I just went back to the good old MS Word. It came out fine so I'm not complaining.
That was pretty much my week in a nutshell, on to the next week (and another term test!).
-ラムダ
Saturday, 13 October 2012
The storm subsides to reveal a sunny day!
Okay, maybe today isn't the clearest of days. Well, it's raining. So then what did I mean? Last week marked the end of several tests and assignments! But naturally, this next week means 5 more quizzes, 1 assignment and another term test. Hurray for me.
Anyway, Wednesday was the CSC236 term test and I went into it with ~1 hour worth of studying. Having said that, the previous week I had read through the textbook and made my own text document that highlighted each of the four methods of induction - I even wrote about this last entry. Therefore very minimal reviewing prior to the test was needed. I do feel this was an appropriate approach to the test considering that most of the content is learned through application so solving problems and understanding the material way ahead of time is extremely effective. Plus it leaves me time to relax and sleep the night before a test while others struggle and panic.
Being part of the evening lecture, I was surprised to hear from my day lecture classmates that there were only 3 questions. This made me wonder which type of induction would be missing from our test. What an interesting turn of events it was when I discovered that only Mathematical and Complete Induction were on the test. Needless to say that those two inductive methods were the ones I knew the best since I have years of experience using them. Plus they were the first ones learned in class so naturally they'd be the easiest. In general, the test was much simpler than I had anticipated - but you won't hear me complaining.
The second question on our test took the form of CI on Binary Trees. Luckily binary trees have very few inductive properties, the main one being that a root's children both form smaller subtrees. Thus we can use the subtrees with Complete Induction making this problem simple. Since the root's two children can each form a new tree with less than n nodes (n being the number of nodes in the entire tree), we know that they both contain exactly one more node than edge. Thus when we combine the two trees, we have exactly two more nodes than edges. Add in the root node gives us +3 nodes, but the 2 edges that connect the root node to each of the children gives us +(3-2) nodes. Thus we have exactly one more node than edge in the large giant of size n. Thus given that there is exactly one more node than edge in all full binary trees of size i such that 0 < i < n, then there is exactly one more node than edge in a tree of size n as well.
So moving onto the next task I suppose... Maybe it'll be more challenging.
-ラムダ
Anyway, Wednesday was the CSC236 term test and I went into it with ~1 hour worth of studying. Having said that, the previous week I had read through the textbook and made my own text document that highlighted each of the four methods of induction - I even wrote about this last entry. Therefore very minimal reviewing prior to the test was needed. I do feel this was an appropriate approach to the test considering that most of the content is learned through application so solving problems and understanding the material way ahead of time is extremely effective. Plus it leaves me time to relax and sleep the night before a test while others struggle and panic.
Being part of the evening lecture, I was surprised to hear from my day lecture classmates that there were only 3 questions. This made me wonder which type of induction would be missing from our test. What an interesting turn of events it was when I discovered that only Mathematical and Complete Induction were on the test. Needless to say that those two inductive methods were the ones I knew the best since I have years of experience using them. Plus they were the first ones learned in class so naturally they'd be the easiest. In general, the test was much simpler than I had anticipated - but you won't hear me complaining.
The second question on our test took the form of CI on Binary Trees. Luckily binary trees have very few inductive properties, the main one being that a root's children both form smaller subtrees. Thus we can use the subtrees with Complete Induction making this problem simple. Since the root's two children can each form a new tree with less than n nodes (n being the number of nodes in the entire tree), we know that they both contain exactly one more node than edge. Thus when we combine the two trees, we have exactly two more nodes than edges. Add in the root node gives us +3 nodes, but the 2 edges that connect the root node to each of the children gives us +(3-2) nodes. Thus we have exactly one more node than edge in the large giant of size n. Thus given that there is exactly one more node than edge in all full binary trees of size i such that 0 < i < n, then there is exactly one more node than edge in a tree of size n as well.
So moving onto the next task I suppose... Maybe it'll be more challenging.
-ラムダ
Monday, 8 October 2012
Study for quizzes, complete assignment 1, ?????, PROFIT!
So with two quizzes and assignment 1 finally complete, I can finally relax and eat turkey without care! Oh that's right, Happy Thanksgiving to all (Canadians)!.
After having done two quizzes, I now know the general way to approach them. This being do the tutorial problems as best as you can and then if you have problems, create an instance of the Tutorial class in order to call the haveTheTaExplainProblem() method. The method is extremely valuable. It takes the problem as a parameter and automatically computes the solution, returning valuable experience and knowledge. Since we know that the quiz will consist of one of the several tutorial problems, we can store the return value of the method in a variable so we can use it during the quiz. Neat!
Assignment 1 was very useful. Not only did it allow me to gauge my comprehension level in the course, but it forced me to apply several strategies from previous courses (CSC165). It was not terribly difficult, especially since we had such a long time to do it and many hints along the way.
With the midterm imminent, I have prepared myself by creating a small text file differentiating the types of induction and strategies for each of them. I have found this quite useful (at least for me) and I have even shared it with the closest of my friends (if you want a copy, you should get closer to me ;) ). Knowing when and how to use each style of induction based on the problem will enable me to take multiple perspectives on each problem, thus completing them much quicker. Then I have extra time at the end of the test to check over my answers!
One of the interesting problems I faced over the span of last week was assignment 1's question 4. While most struggled with it, I felt quite confident in my answer. I will share my insights without giving away the answers in case someone wishes to try it again.
So we begin by setting the predicate we will be proving.
P(n): A binary string of length n that begins and ends with the same bit has even number of occurrences of substrings from {01, 10}.
Well, what is the shortest length of a binary string? 0? Well if it were 0, then the string has no bits so it cannot start and end with the same bit. This is thus vacuously true, but it does not help our later induction. What about 1? Well, the substrings we care about are of length 2, so it has no instances of either, yet still begins and ends with the same bit. Let's make this our basecase. 0 is even since it is divisible by 2 (0 = 2n where n = 0).
For our inductive step, we should notice that there are two possible cases for this string: either the string begins and ends with the same bit, or it does not.
So naturally we separate the two cases. For the case where they begin and end with the same bit, we notice that there are two possible subcases as well. Either we can append another bit identical to the starting bit/ending bit, let's call it j. Or we append j complement, the other bit (if j = 1, then jc = 0)
In both cases, we know that P(n-1) by complete induction since this was our first case.
In subcase 1, we can use complete induction by noticing that without the new appended digit, we have an even number of instances of {10,01}. Thus by adding the new digit, j, we have a substring formed by the last two digits equal to "jj". We then note that "jj" is not in the set {10,01}. Thus the addition digit did nothing to change the number of instances, thus the number of instances is still even by complete induction. So P(n).
In subcase 2, we append jc to the end of the string. Firstly we notice that the starting bit and ending bit are now not equivalent, thus we declare this subcase to be vacuously true.
The rest is quite simple; we have another case with 2 further subcases. Can you complete the rest of the proof? Remember that if it does not start and end with the same bit, you must take the largest substring that satisfies the predicate. Using the largest substring, you know that there is no more instances of j after the last digit in the largest substring. Thus from then onwards, the digits are all jc.
Surely you all knew this much when you handed in assignment 1 though.
Either way, I wish you all luck with the upcoming term test! Enjoy what's left of your thanksgiving.
-ラムダ
After having done two quizzes, I now know the general way to approach them. This being do the tutorial problems as best as you can and then if you have problems, create an instance of the Tutorial class in order to call the haveTheTaExplainProblem() method. The method is extremely valuable. It takes the problem as a parameter and automatically computes the solution, returning valuable experience and knowledge. Since we know that the quiz will consist of one of the several tutorial problems, we can store the return value of the method in a variable so we can use it during the quiz. Neat!
Assignment 1 was very useful. Not only did it allow me to gauge my comprehension level in the course, but it forced me to apply several strategies from previous courses (CSC165). It was not terribly difficult, especially since we had such a long time to do it and many hints along the way.
With the midterm imminent, I have prepared myself by creating a small text file differentiating the types of induction and strategies for each of them. I have found this quite useful (at least for me) and I have even shared it with the closest of my friends (if you want a copy, you should get closer to me ;) ). Knowing when and how to use each style of induction based on the problem will enable me to take multiple perspectives on each problem, thus completing them much quicker. Then I have extra time at the end of the test to check over my answers!
One of the interesting problems I faced over the span of last week was assignment 1's question 4. While most struggled with it, I felt quite confident in my answer. I will share my insights without giving away the answers in case someone wishes to try it again.
So we begin by setting the predicate we will be proving.
P(n): A binary string of length n that begins and ends with the same bit has even number of occurrences of substrings from {01, 10}.
Well, what is the shortest length of a binary string? 0? Well if it were 0, then the string has no bits so it cannot start and end with the same bit. This is thus vacuously true, but it does not help our later induction. What about 1? Well, the substrings we care about are of length 2, so it has no instances of either, yet still begins and ends with the same bit. Let's make this our basecase. 0 is even since it is divisible by 2 (0 = 2n where n = 0).
For our inductive step, we should notice that there are two possible cases for this string: either the string begins and ends with the same bit, or it does not.
So naturally we separate the two cases. For the case where they begin and end with the same bit, we notice that there are two possible subcases as well. Either we can append another bit identical to the starting bit/ending bit, let's call it j. Or we append j complement, the other bit (if j = 1, then jc = 0)
In both cases, we know that P(n-1) by complete induction since this was our first case.
In subcase 1, we can use complete induction by noticing that without the new appended digit, we have an even number of instances of {10,01}. Thus by adding the new digit, j, we have a substring formed by the last two digits equal to "jj". We then note that "jj" is not in the set {10,01}. Thus the addition digit did nothing to change the number of instances, thus the number of instances is still even by complete induction. So P(n).
In subcase 2, we append jc to the end of the string. Firstly we notice that the starting bit and ending bit are now not equivalent, thus we declare this subcase to be vacuously true.
The rest is quite simple; we have another case with 2 further subcases. Can you complete the rest of the proof? Remember that if it does not start and end with the same bit, you must take the largest substring that satisfies the predicate. Using the largest substring, you know that there is no more instances of j after the last digit in the largest substring. Thus from then onwards, the digits are all jc.
Surely you all knew this much when you handed in assignment 1 though.
Either way, I wish you all luck with the upcoming term test! Enjoy what's left of your thanksgiving.
-ラムダ
Subscribe to:
Posts (Atom)