So the time has come for me to finish writing this SLOG. CSC236 is coming to an end in around one week and this is the final barrier between me and the exam. You may be wondering why I haven't been writing frequently these days. Aside from exams and last minute assignments, I have been intrigued by this particularly statistical problem: the pile of pennies. I found it while wandering through Piazza and Professor Heap's problem solving website. I've been working on trying to determine which numbers in the set [0, 64] can be obtained and which have not. In this episode, I will be sharing my results.
This is the question:
You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using the following two operations:
L - If the left pile has an even number of pennies, transfer half of them to the right pile. If the left pile has an odd number of pennies, operation L is disallowed.
R - If the right pile has an even number of pennies, transfer half of them to the left pile. If the right pile has an odd number of pennies, operation R is disallowed.
What about arranging things so that one of the piles has other numbers in the range [0,64]?
Well right off the bat, we know that we can obtain 64, 32, 16, 8, 4, 2 and 1 through repetitive operation executions on the same drawer. We also have the other drawer that has: 0, 48, 56, 60, 62, 63.
After trying to guess and check my way through the list while writing down the combinations of Ls and Rs, I realized it was quite tedious. I then thought, isn't this problem kind of like recursion? If we consider the step before we achieve the number we desire, wouldn't that be our base case? If the number of items in the drawer is equal to n, then we know that our desired number is on the next step and we're done.
I then thought, what about combining these techniques? What if we noted which combinations were obvious (ie. 64, 32, 16, etc) and then worked backwards through the problem (double the number we want) until we reached an obvious state? So let us try that.
For 3 pennies, we double it: 6. Then performing an operation on the drawer with 6 yields our desired number, 3. Double 6 again. 12. 24. 48. But 48 is an obvious state we achieved earlier! Taking 64-0, performing an operation gives us 32-32 and then performing it again gives us 16-48! Then we just perform it the other way, 40-24, 52-12, 58-6, 61-3. Thus we achieved our 3!
If we were to consider this, we can now add all the "process states" (combinations that we achieved on our way to our desired solution) to our list of obvious states. Now it makes our next number that much easier.
Let's try 5. 5 becomes 10, becomes 20, becomes 40. But we achieved 40 during our search for 3. Thus we can achieve 5. Now add the "process states" to the list of obvious states.
6. 12. 24. 48. 48 is an obvious state.
7. 14. 28. 56. 56 is an obvious state.
9. 18. 36. In this case we have not achieved an obvious state. So let us think more. In a drawer with 36, the other drawer has 28. Note however that 28 is an obvious state. This is important because we don't care if the drawer we want is an obvious state, but that the combination of drawers is an obvious state. Thus we can achieve 9 from 64-0. Let's just do the entire process. 9-55, 18-46 36-28, 8-56, 16-48, 32-32, 64-0.
Following this method, we can repeat all the steps for the remaining numbers, remembering to note obvious combinations along the way. This makes every subsequent computation simpler. While this is an informal proof, we have used our intuition to deduce a method of proving each of the combinations. 64 mini proofs will not take that long but should we have more pennies then a inductive proof will be better suited.
Well my friends, I hope you have enjoyed the journey through CSC236 and I thank you all for tagging along with me. I have enjoyed this course and found the material very stimulating albeit too simple at times. Overall it is a vast improvement over CSC165 from last year. I will be moving forward into CSC265 next semester and will hopefully see you all there!
Thanks for reading!
-ラムダ
Wednesday, 5 December 2012
Sunday, 25 November 2012
One More Week to Go!
Yep yep my fellow CSC236ers, we only have one more week of classes (with the exception of the Mon/Tues classes)! It's sad to see the semester pass by so quickly (wow!). But with this means that Christmas and the holidays are soon coming. This time of year always makes me nostalgic as I reminisce about my younger years helping decorate the house/opening gifts/etc. They are precious memories that will be a part of us until we die (of course unless you don't celebrate, in this case substitute some other holiday you celebrate).
Recently I went through to calculate my current marks in all my courses to see what kind of position I am in for the upcoming finalｓ, and I must say that I am quite happy. I had thought before about whether Computer Science was the field for me - whether it was something that I liked or whether it was just something that I had a affinity for. Turns out that it is both, and that's definitely reassuring. I hope to keep the momentum going through this next semester, and I look forward to working and talking with you guys (since you're in 236, you're most likely studying CS as well). Nothing really interesting for me to report this blog entry. I have heard that my TA is apparently the only TA who has yet to submit the marks for A2 so I am a bit impatient. Even so I know the TA has a life so I will wait, no worries.
Well, that's all for me this time.
-ラムダ
Recently I went through to calculate my current marks in all my courses to see what kind of position I am in for the upcoming finalｓ, and I must say that I am quite happy. I had thought before about whether Computer Science was the field for me - whether it was something that I liked or whether it was just something that I had a affinity for. Turns out that it is both, and that's definitely reassuring. I hope to keep the momentum going through this next semester, and I look forward to working and talking with you guys (since you're in 236, you're most likely studying CS as well). Nothing really interesting for me to report this blog entry. I have heard that my TA is apparently the only TA who has yet to submit the marks for A2 so I am a bit impatient. Even so I know the TA has a life so I will wait, no worries.
Well, that's all for me this time.
-ラムダ
Friday, 16 November 2012
Three more weeks until exams...
Well the time for all students everywhere to be bucking down to study... Yeah riiiiight. We all know that we will end up waiting for the last minute before starting to study, pulling all-nighters and ruining our health with junk food and lack of sleep.
I suppose at this point in time, we somewhat know what our mark will be like going into the exam. As for the test we wrote last week (I ranted about it last post), I performed just as well as I had thought considering it was not up to the difficulty I had expected and hoped for. I was also informed that my remark request for term test 1 ended up having no change - I guess getting a perfect 100% in this class is now impossible. Such a shame. All that remains is two more quizzes, the results for assignment 2, this SLOG and the final exam! Time remaining dwindles and now it is crunch time.
Last week's tutorial quiz and problems were based on last week's lecture so it wasn't very easy for me to study for the quiz. Even so, the professor made the concept of DFSAs quite clear in lecture. With the guidance of the TA during tutorial itself, the subsequent quiz was no problem at all. I hope. With this last tutorial, that puts the evening class ahead of the morning class in terms of content and the number of quizzes completed. However I suppose this is better than having to attend classes afterwards to make up (haha!).
A noteworthy question that came up during this previous week was probably the first question of the tutorial problems. As I recall, the goal was to create a finite state machine that will accept strings that conform to a particular set of rules. The interesting tool that was used to do this was the Automation Simulator - it was simply a graphical representation of the machine. Using circles as states and headed-lines to connect the states, we were able to effectively show how each character affects the acceptability of the string (since a FSA processes only one character at a time). Therefore during the tutorial problems and the quiz, it was quite simple to draw out the possible states: a string with an even number of 1s and an even length, a string with an even number of 1s and an odd length, a string with odd-odd and a string with odd even. Using the statistics method of determining the number of possible permutations, this was a simple task.
Subsequently, we can draw out a table of values - should the next digit to be processed be a 0 (the language was {0, 1}), then we know that the length switches from odd to even or even to odd, and the number of 1s remains consistent. Similarly, should the next digit be a 1, the length switches states and the number of 1s also switches states.
Now we know this, we have our transition function (as represented above), language, acceptable states and starting state, and the set of states (all 4 given in the question). Thus we have our quintuple of parameters. Therefore we have defined our machine! Very simple.
Anyway, with all 236 assignments out of the way, I can relax.
Until next time,
-ラムダ
I suppose at this point in time, we somewhat know what our mark will be like going into the exam. As for the test we wrote last week (I ranted about it last post), I performed just as well as I had thought considering it was not up to the difficulty I had expected and hoped for. I was also informed that my remark request for term test 1 ended up having no change - I guess getting a perfect 100% in this class is now impossible. Such a shame. All that remains is two more quizzes, the results for assignment 2, this SLOG and the final exam! Time remaining dwindles and now it is crunch time.
Last week's tutorial quiz and problems were based on last week's lecture so it wasn't very easy for me to study for the quiz. Even so, the professor made the concept of DFSAs quite clear in lecture. With the guidance of the TA during tutorial itself, the subsequent quiz was no problem at all. I hope. With this last tutorial, that puts the evening class ahead of the morning class in terms of content and the number of quizzes completed. However I suppose this is better than having to attend classes afterwards to make up (haha!).
A noteworthy question that came up during this previous week was probably the first question of the tutorial problems. As I recall, the goal was to create a finite state machine that will accept strings that conform to a particular set of rules. The interesting tool that was used to do this was the Automation Simulator - it was simply a graphical representation of the machine. Using circles as states and headed-lines to connect the states, we were able to effectively show how each character affects the acceptability of the string (since a FSA processes only one character at a time). Therefore during the tutorial problems and the quiz, it was quite simple to draw out the possible states: a string with an even number of 1s and an even length, a string with an even number of 1s and an odd length, a string with odd-odd and a string with odd even. Using the statistics method of determining the number of possible permutations, this was a simple task.
Subsequently, we can draw out a table of values - should the next digit to be processed be a 0 (the language was {0, 1}), then we know that the length switches from odd to even or even to odd, and the number of 1s remains consistent. Similarly, should the next digit be a 1, the length switches states and the number of 1s also switches states.
Now we know this, we have our transition function (as represented above), language, acceptable states and starting state, and the set of states (all 4 given in the question). Thus we have our quintuple of parameters. Therefore we have defined our machine! Very simple.
Anyway, with all 236 assignments out of the way, I can relax.
Until next time,
-ラムダ
Sunday, 11 November 2012
Resting Time... Lest We Forget.
On the topic of CSC236's most recent test, I have no feelings other than complete disappointment. 236 is one of my favorite classes, and yet when the test barely scrapes the surface of the content learned, it really grinds my gears. There was a substantial amount that could have been tested, yet there were only two questions that took 20 minutes to complete tops. I even had time to check over my answers three times before leaving. Overall I didn't find it challenging enough considering it was supposed to be a term test.
As of now, it is the long-awaited Fall Break! Hurray! Four days of minimal work! Aside from CSC207's Assignment 2 that is. Definitely going to sleep in, catch up on work and have fun. I hope that all you readers are in a similar position. Don't forget to stay warm and wear a poppy.
Until next time,
-ラムダ
Sunday, 4 November 2012
Calm before the storm Pt 2
So the lectures given in the past 2 weeks have been somewhat confusing, ,mainly because I had to miss one of them in order to pick up my kendo gear over at the AC. Luckily, however, over the rest of the week I managed to get my facts straight and now I am confident in the new techniques that were taught, such as how to use unwinding, how to find closed-form solutions and how to find upper and lower bounds. Furthermore I have familiarized myself with Gauss' technique and now know how to effectively use the Master Theorem. Inadvertently I have also been studying for the upcoming term test! How nice it is to know that as a result of regular reviewing, I won't have to cram or study for extended periods of time for the test!
With assignment 2 now out of the way, I can focus on working on my 207 assignment 2 and my STA247 assignment 3. The storm has yet to arrive.
The interesting part of assignment 2 for 236 was the second question. Many of my friends were struggling to solve it and yet I did not understand why. I shall outline my procedure here in case any reader did not solve it.
So our problem involves binding a given T function and showing that it is bounded by big theta of lg(n). lg(n) is of course log(n) base 2. We first note that we have previously done similar questions involving ceilings and floors by substituting n for some power of 2 (2**k). So, it is natural to proceed similarly. Since we cannot assume n is a power of 2, let us bind it. Let n' be the smaller power of 2 larger than or equal to n where n is >= 2. So then it is clear that n'/2 < n <= n'.
Since we have proven that T is non-decreasing (this is an extremely easy proof to make so I will omit it), and we know that n <= n', then we can state that T(n) <= T(n'). Note that we now have our starting inequality - it should always involve T(n) and something that we can manipulate. So then using the definitions of T(n'), we have:
T(n) <= 1 + max{T(c(n'/2)), T(f(n'/2))}. Note that T is non-decreasing.
T(n) <= 1 + T(c(n'/2)). Note that (n'/2 = 2**(k-1)) is an integer so ceiling functions don't do anything.
T(n) <= 1 + T(2**(k-1)). Let us unwind the inequality n times.
T(n) <= k + T(2**(k-k)).
T(n) <= k + 1. Note that n' = 2**k, then k = lg(n').
T(n) <= lg(2n) + 1. Note that 2n > n'.
T(n) <= lg(2) + lg(n) + 1.
T(n) <= lg(n) + 2. Note that lg(n) > 1 since n >= 2. Set c = 4 or more.
T(n) <= 4*lg(n)
There is our upper bound. Letting b = 2, c = 4, then n >= b implies that T(n) <= c*lg(n).
Attempting the lower bound is very similar except we use n'/2 instead of n' since we know that n'/2 < n. Also note that n' < 2n. Then we have:
T(n) > T(n'/2)
T(n) > 1 + T((n'/2)/2) only if n'/2 >= 2 can this be possible, then n' >= 4 so n >= 4.
T(n) > 1 + T(2**(k-2))
T(n) > (k-1) + T(2**(k-1-(k-1))) through unwinding k-1 times.
T(n) > k - 1 + 1
T(n) > k
T(n) > lg(n'). Note that n' > n and lg function is always increasing.
T(n) > lg(n).
There is the lower bound. Letting b = 4, c = 1, then n >= b implies that T(n) <= c*lg(n).
Well bloggers, I am off to work on 207. Until next time,
-ラムダ
With assignment 2 now out of the way, I can focus on working on my 207 assignment 2 and my STA247 assignment 3. The storm has yet to arrive.
The interesting part of assignment 2 for 236 was the second question. Many of my friends were struggling to solve it and yet I did not understand why. I shall outline my procedure here in case any reader did not solve it.
So our problem involves binding a given T function and showing that it is bounded by big theta of lg(n). lg(n) is of course log(n) base 2. We first note that we have previously done similar questions involving ceilings and floors by substituting n for some power of 2 (2**k). So, it is natural to proceed similarly. Since we cannot assume n is a power of 2, let us bind it. Let n' be the smaller power of 2 larger than or equal to n where n is >= 2. So then it is clear that n'/2 < n <= n'.
Since we have proven that T is non-decreasing (this is an extremely easy proof to make so I will omit it), and we know that n <= n', then we can state that T(n) <= T(n'). Note that we now have our starting inequality - it should always involve T(n) and something that we can manipulate. So then using the definitions of T(n'), we have:
T(n) <= 1 + max{T(c(n'/2)), T(f(n'/2))}. Note that T is non-decreasing.
T(n) <= 1 + T(c(n'/2)). Note that (n'/2 = 2**(k-1)) is an integer so ceiling functions don't do anything.
T(n) <= 1 + T(2**(k-1)). Let us unwind the inequality n times.
T(n) <= k + T(2**(k-k)).
T(n) <= k + 1. Note that n' = 2**k, then k = lg(n').
T(n) <= lg(2n) + 1. Note that 2n > n'.
T(n) <= lg(2) + lg(n) + 1.
T(n) <= lg(n) + 2. Note that lg(n) > 1 since n >= 2. Set c = 4 or more.
T(n) <= 4*lg(n)
There is our upper bound. Letting b = 2, c = 4, then n >= b implies that T(n) <= c*lg(n).
Attempting the lower bound is very similar except we use n'/2 instead of n' since we know that n'/2 < n. Also note that n' < 2n. Then we have:
T(n) > T(n'/2)
T(n) > 1 + T((n'/2)/2) only if n'/2 >= 2 can this be possible, then n' >= 4 so n >= 4.
T(n) > 1 + T(2**(k-2))
T(n) > (k-1) + T(2**(k-1-(k-1))) through unwinding k-1 times.
T(n) > k - 1 + 1
T(n) > k
T(n) > lg(n'). Note that n' > n and lg function is always increasing.
T(n) > lg(n).
There is the lower bound. Letting b = 4, c = 1, then n >= b implies that T(n) <= c*lg(n).
Well bloggers, I am off to work on 207. Until next time,
-ラムダ
Sunday, 28 October 2012
Lambda's Upper Bounds
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,
-ラムダ
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, 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.
-ラムダ
Tuesday, 25 September 2012
Welcome to the dwelling of the mysterious and anonymous Lambda.
I can be defined as a second year at the University of Toronto studying a Specialist in Computer Science, Minor in Economics and a Minor in Statistics. Why am I overachieving? Because I can. If you think that you have limits in your capabilities, you are sadly wrong. You are only bound by what limits you set. I am bound to no identifier.
Follow my journey through CSC236 overcoming all the barriers and obstacles placed in my way as I strive to obtain my goals. I am Lambda; possessing many functions, yet never more than one at the same time. I can do everything, yet nothing until my intentions are declared in a simple statement.
For now, I intend to defeat this week's quiz.
I can be defined as a second year at the University of Toronto studying a Specialist in Computer Science, Minor in Economics and a Minor in Statistics. Why am I overachieving? Because I can. If you think that you have limits in your capabilities, you are sadly wrong. You are only bound by what limits you set. I am bound to no identifier.
Follow my journey through CSC236 overcoming all the barriers and obstacles placed in my way as I strive to obtain my goals. I am Lambda; possessing many functions, yet never more than one at the same time. I can do everything, yet nothing until my intentions are declared in a simple statement.
For now, I intend to defeat this week's quiz.
Subscribe to:
Posts (Atom)