Test 3 was quite predictable. I didn't really study for it, but made a comprehensive crib sheet that got me through it. Again, I had everything that I needed on the sheet, so I should be fine.
The last test was again quite uncomfortably comfortable, because I know now that the final exam will be ominously challenging, much more than any of the tests or assignments thus far. So far we have just basically been asked to copy from the notes onto tests, or onto tutorial problem sets. I think that the final will challenge us a lot more and make us think of proofs on our feet. I wonder if I should just memorize all the different kinds of proofs, which would probably get me a decent grade, or if I should try and understand the process too.
I think that as far as proofs go, I have an idea of a structure and the importance of a structure. I think that would be a pretty useful tool in any sort of documentation scenario ( Thesis maybe?) I think a lot more time could have been spent on floating point representation, as that is one of the topics that I am still quite fuzzy about. Well, 2 weeks to the final, I can finally start catching up on my reading.
I wish I had updated this blog a little more often, and I might continue blogging on it for cdc236. It kept me on track, and made me think about csc165 with a little bit of existential insight, which I enjoyed. Until next semester then.
Tuesday, December 7, 2010
Double Elimination - How many rounds?
Here is my problem solving episode.
Solution:
1. Understanding the problem:
At each stage, the number of people added to the losers bracket is half of the number of people at the stage on the winners bracket.
2. Devising a plan:
After round 1, 4 players go into the semi-final bracket, and 4 go into the first round of L.
After round 2, 2 players are out of L, and 2 more go in.
After round 3, 1 player goes from W to L.
After round 4, This is the winner of L.
After round 5, This is the winner of W and L.
3. Carrying out the plan:
What we learned from the previous example is that,
The number of players initially in the losers bracket, lets say N(initial) = n/2
The next would be n/4, and the next n/8 and so on.
The total number of rounds initially would be L(initial) = ceil(log2(players)) # using the math prereqs( 2^c = b => log_2(b) = c)
so with 8 players initially, we have ceil(log28) = 3 initial rounds.
Now after every round, n/2^(2*round number) gets added to the losing bracket. To take this into account, we take the initial number of rounds in L, and calculate the next number of rounds by doing the same process. i.e, The extra number of rounds would be:
In a single elimination tournament, you need ceil(log2(players)) rounds. (2 players, 1 round; 3-4 players, 2 rounds; 5-8 players 3 rounds, etc.) In double elimination, players get a second chance. After losing in the winners' bracket, they enter a second bracket, and the winner of that emerges as a tournament finalist. How many rounds are there in the losers' bracket?
Solution:
1. Understanding the problem:
- Unknown: Number of rounds in losers' bracket. Let's call it L.
- Let's call the winning bracket W.
- Data: we know that in a winning bracket, W = ceil(log2(players))
- Figure:
- Separate and conquer:
At each stage, the number of people added to the losers bracket is half of the number of people at the stage on the winners bracket.
2. Devising a plan:
- Find a connection:
After round 1, 4 players go into the semi-final bracket, and 4 go into the first round of L.
After round 2, 2 players are out of L, and 2 more go in.
After round 3, 1 player goes from W to L.
After round 4, This is the winner of L.
After round 5, This is the winner of W and L.
3. Carrying out the plan:
What we learned from the previous example is that,
The number of players initially in the losers bracket, lets say N(initial) = n/2
The next would be n/4, and the next n/8 and so on.
The total number of rounds initially would be L(initial) = ceil(log2(players)) # using the math prereqs( 2^c = b => log_2(b) = c)
so with 8 players initially, we have ceil(log28) = 3 initial rounds.
Now after every round, n/2^(2*round number) gets added to the losing bracket. To take this into account, we take the initial number of rounds in L, and calculate the next number of rounds by doing the same process. i.e, The extra number of rounds would be:
ceil(log2(L(initial)))
So for our example of 8 players, ceil(log2(L(initial))) = ceil(log2(3)) = 2 extra rounds.
Therefore, in conclusion, the total number of rounds would be the addition of these two calculations to get:
Total L = ceil(log2(L(initial))) + ceil(log2(n))
4. Looking back:
Let us check this with our intuition:
for 16 players L = ceil(log24) + ceil(log216) = 2 + 4 = 6 rounds. Which is correct.
for 128 players L = ceil(log28) + ceil(log2128) = 3 + 7 rounds. Which is correct.
Source: http://www.gottfriedville.net/mathprob/misc-dblelim.html
Note: even though this problem is already solved, I found it very interesting, and applied Polya's problem solving method to try and formulate it.
Therefore, in conclusion, the total number of rounds would be the addition of these two calculations to get:
Total L = ceil(log2(L(initial))) + ceil(log2(n))
4. Looking back:
Let us check this with our intuition:
for 16 players L = ceil(log24) + ceil(log216) = 2 + 4 = 6 rounds. Which is correct.
for 128 players L = ceil(log28) + ceil(log2128) = 3 + 7 rounds. Which is correct.
Source: http://www.gottfriedville.net/mathprob/misc-dblelim.html
Note: even though this problem is already solved, I found it very interesting, and applied Polya's problem solving method to try and formulate it.
Thursday, December 2, 2010
Induction, Big Oh and Lies that computers tell us
December is here. I haven't posted in a while, so this one is gonna be a sweeping update.
The past few weeks, we have been focusing on Induction, and how to prove the property of a certain entity through proving it true for all such entities. It makes sense. I think... I enjoy the structured proofs of induction. It's not very complicated and you know what you have to begin with and where you want to get to. It's more of a puzzle than knowing the math pre-reqisits. I enjoyed doing the last three tutorial problem sets, and I think they went well.
Big Oh is something that I took to quite well. Again, the proofs that we deal with in class seem quite structured. It is kind of interesting to categorize functions according to their growth rates. Wondering what happens as something gets really really big, is something that is a universal phantom that everyone thinks about some time or the other in their lives. It kind of reminds me of this poem we did in school once.
How vague are all the mysteries
Which bind us to our earth;
How far they send into the heart
Their tones of holy mirth;
However, even though it kind of takes away from the imagination of math, the proofs feel safe, because you are in the realm of what you know, and you know what you need to do. I guess that makes it comfortable. So far, I would describe CSC165 as comfortable. I don't think CSC236 will be the same story though. That is left to see...
Most recently, we have been learning about expressing numbers in certain bases, and floating point representation of numbers. This is something familiar to me from my engineering years, although it was quite confusing back then. representing numbers in a different system shows its useful nature, but there is always the problem of compatibility and if you treat your mind as a system, then where is the balance between the number system of the mind, and that of the computer.
I also liked the idea of relative errors. Again, it's such a simple concept, just finding a percentage of the error with relation to your function, but it has such great implications. I like relativity because it's intuitive, especially when you talk about it in simple numbers. Einstein might be rolling over in his grave. So much for a lifetime of work...
p.s I hope to post more often between now and the 20th. Sometimes inspiration might just come in the form of a couple of more marks. No harm in being honest in a course about reflection and proofs.
The past few weeks, we have been focusing on Induction, and how to prove the property of a certain entity through proving it true for all such entities. It makes sense. I think... I enjoy the structured proofs of induction. It's not very complicated and you know what you have to begin with and where you want to get to. It's more of a puzzle than knowing the math pre-reqisits. I enjoyed doing the last three tutorial problem sets, and I think they went well.
Big Oh is something that I took to quite well. Again, the proofs that we deal with in class seem quite structured. It is kind of interesting to categorize functions according to their growth rates. Wondering what happens as something gets really really big, is something that is a universal phantom that everyone thinks about some time or the other in their lives. It kind of reminds me of this poem we did in school once.
How vague are all the mysteries
Which bind us to our earth;
How far they send into the heart
Their tones of holy mirth;
However, even though it kind of takes away from the imagination of math, the proofs feel safe, because you are in the realm of what you know, and you know what you need to do. I guess that makes it comfortable. So far, I would describe CSC165 as comfortable. I don't think CSC236 will be the same story though. That is left to see...
Most recently, we have been learning about expressing numbers in certain bases, and floating point representation of numbers. This is something familiar to me from my engineering years, although it was quite confusing back then. representing numbers in a different system shows its useful nature, but there is always the problem of compatibility and if you treat your mind as a system, then where is the balance between the number system of the mind, and that of the computer.
I also liked the idea of relative errors. Again, it's such a simple concept, just finding a percentage of the error with relation to your function, but it has such great implications. I like relativity because it's intuitive, especially when you talk about it in simple numbers. Einstein might be rolling over in his grave. So much for a lifetime of work...
p.s I hope to post more often between now and the 20th. Sometimes inspiration might just come in the form of a couple of more marks. No harm in being honest in a course about reflection and proofs.
Sunday, November 14, 2010
November begins... the 3pm coffee crash...
We're almost there.
It's Thursday night, nearly midnight. I have a fever and my throat feels like it has needles through it, and is on fire simultaneously. I sit in front of my computer screen, staring blankly at the CSC165 website calendar. I find the energy to print out some lecture slides... They are all out of order and confused. My head begins to hurt, contemplating whether to ditch the test which is now less than 12 hours away. It's now 1am. Still haven't done anything. I grab my coat and go out to meet a friend for a time-out at the 24 hour Tim Hortons. Sit and chat till 2:30am. Complain about how nothing ever works out the right way in life.
Get back home by 3am. Decide to sleep for a couple of hours. Wake up at 10am, 3 hours later than I intended to. Feeling terrible. Contemplate ditching the test again. Somehow find the courage to scribble down a cheat sheet and think about induction. 11:30am, pack my bag and cycle to the Health Services office. Book an appointment for the afternoon. Get a cup of tea from MB, and head to BA1180.
So glad I decided to do the test, even though I can hardly hold up my pencil. All of the proofs are on my cheat sheet. Thank god!! What a fun morning.
Assignment 2 wasn't very interesting. Don't really feel like reflecting on it. Something about universal and existential claims and proof structures. Got the gist of it. Keep looking back to see if the marks are up. Why does it take so long?
Seems like I haven't been for a lecture in the longest time. Perfect comeback lecture - open problems. Feels like my mind wants to explode. I consciously shut down when Prof. Heap starts talking about paradoxes. The last thing I need on my mind right now is a mathematical paradox. I feel good about my position going into the last 1/3rd of the course, grades wise. Still a little lost about what I'm trying to gain from this class though.
Seems like we are learning about a hopeless battle with confusion. Way to crush clarity. I think I need a messiah... anyone?
It's Thursday night, nearly midnight. I have a fever and my throat feels like it has needles through it, and is on fire simultaneously. I sit in front of my computer screen, staring blankly at the CSC165 website calendar. I find the energy to print out some lecture slides... They are all out of order and confused. My head begins to hurt, contemplating whether to ditch the test which is now less than 12 hours away. It's now 1am. Still haven't done anything. I grab my coat and go out to meet a friend for a time-out at the 24 hour Tim Hortons. Sit and chat till 2:30am. Complain about how nothing ever works out the right way in life.
Get back home by 3am. Decide to sleep for a couple of hours. Wake up at 10am, 3 hours later than I intended to. Feeling terrible. Contemplate ditching the test again. Somehow find the courage to scribble down a cheat sheet and think about induction. 11:30am, pack my bag and cycle to the Health Services office. Book an appointment for the afternoon. Get a cup of tea from MB, and head to BA1180.
So glad I decided to do the test, even though I can hardly hold up my pencil. All of the proofs are on my cheat sheet. Thank god!! What a fun morning.
Assignment 2 wasn't very interesting. Don't really feel like reflecting on it. Something about universal and existential claims and proof structures. Got the gist of it. Keep looking back to see if the marks are up. Why does it take so long?
Seems like I haven't been for a lecture in the longest time. Perfect comeback lecture - open problems. Feels like my mind wants to explode. I consciously shut down when Prof. Heap starts talking about paradoxes. The last thing I need on my mind right now is a mathematical paradox. I feel good about my position going into the last 1/3rd of the course, grades wise. Still a little lost about what I'm trying to gain from this class though.
Seems like we are learning about a hopeless battle with confusion. Way to crush clarity. I think I need a messiah... anyone?
Thursday, October 28, 2010
October Ends
There are times when you are fortunate enough that you take a course that you can see happen in the real world. A few weeks ago, I was walking to the Koffler Building, through the BA walkway, and at the top door to the entrance of Koffler was a bright red sign that read "DO NOT ENTER BUILDING IN ALARM".
We had spoken about linguistic ambiguity in class and I couldn't help but chuckle and wonder. How can ambiguity be so prominent in our communications, even though we believe ourselves to be an intellectually clear-headed being. How much of what we say actually gets interpreted the way we want it to. So often, we display who we are by what we say, and what if that persona has been lost in translation? Food for thought...
Meanwhile, we have started doing proofs in class. The most recent being an Epsilon-Delta proof, which completely mystified me. The assignment will definitely be a challenge.
I have also been thinking about the kind of problem that I want to tackle on this blog. I came across a video of a very interesting method of multiplication, and I have to say, it completely baffled me. It got me to think, could there be a way to prove the method through structured steps like the ones we have learned. Here is the video. If anyone out there knows how it's done, do comment and explain. I'm stumped.
Monday, October 18, 2010
Logic
Aah, so this is my first post, and I'm late. But I guess losing 1 mark is better than losing 8.
So being forced to blog is definitely unusual, and I'm wondering how it will affect the blogging nature that I've created for myself, but I guess time will tell. So let's talk logic.
It might seem logical that if you go to class, and do the homework, and go to tutorial, and read the material, that you would be doing well at the course. I just read my first grade for Assignment 1 and realized that it was all a comfortable illusion. I guess getting bad marks should be commonplace now, being at UofT for over two years, and I wonder now, if I would react the same way to my first assignment in my first year.
It's a subconscious blow to your motivation I guess and being the sentimental type to begin with, I've let that hurt my entire outlook on Uni. Oh well, I guess being stoic is the only way to turn. I've got to keep on moving and loosen up those tight mind muscles.
So first post of hopefully many more, with some insight into CSC165 to follow.
So being forced to blog is definitely unusual, and I'm wondering how it will affect the blogging nature that I've created for myself, but I guess time will tell. So let's talk logic.
It might seem logical that if you go to class, and do the homework, and go to tutorial, and read the material, that you would be doing well at the course. I just read my first grade for Assignment 1 and realized that it was all a comfortable illusion. I guess getting bad marks should be commonplace now, being at UofT for over two years, and I wonder now, if I would react the same way to my first assignment in my first year.
It's a subconscious blow to your motivation I guess and being the sentimental type to begin with, I've let that hurt my entire outlook on Uni. Oh well, I guess being stoic is the only way to turn. I've got to keep on moving and loosen up those tight mind muscles.
So first post of hopefully many more, with some insight into CSC165 to follow.
Subscribe to:
Posts (Atom)