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.
-ラムダ
Sunday, 25 November 2012
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,
-ラムダ
Subscribe to:
Posts (Atom)