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