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!).
-ラムダ
Subscribe to:
Posts (Atom)