Andrew Jesaitis ::

So here’s my baseline bracket for 2011. Pretty standard bracket based on Sargarin rankings.

I did tweak it to have BYU lose to Florida in the Sweet 16, rather than have them advance and lose to Pitt in the Elite 8. I think it is a pretty safe assumption that BYU shot themselves in the foot by suspending Davies. Interestingly, this assumption isn’t showing up in the Vegas lines (yet). I would think that BYU would be so heavily underbet that that you might be able to get nice odds on them, but that’s not so.

Lastly, I’ll mention that in most pools, I’d probably actually pick Duke or Kansas to win the tournament. Although I think Ohio will take the whole thing, I think that they are a poor bet. Since Ohio State are the heavy favorite, you’d likely have to either spilt the pot or you’d lose on previous picks. Whereas, if you pick either Duke or KU, you have a much better shot of taking the whole thing based on you being the only one in your pool to pick the winner. Think about this for a second. If Ohio has a 60% chance of winning but you have to split a hundred dollar pot, your expected winnings are only $30. But, if Duke has a 40% chance you can expect a $40 payout because you didn’t have to split the pot. This is basically the theory that Niemi, Carlin, and Alexander came up with in this awesome paper a couple years ago.

Recently in my numerical methods class, I recieved the following question:

Find the generalized solution for “sum” in the following code:

int sum = 0;
for (int i= 1; i <= n; i++){
    for (int j= 1; j <= i; j++){
	for (int k= 1; k <= j; k++){
	    sum++;
	}
    }
}

Interestingly, there is very little on Stackoverflow about finding the number of iterations of nested for loops. To me this means the answer has little practical importance to 99.9% of code out there. You know what that means? It makes the questions a great math problem (i.e. not practical and deceptively simple).

The algebraic solution is pretty straightforward. But, here's what I've found about algebraic solutions from majoring in math. Most people reguritating the formula actually don't understand it. I mean really understand the "why" of the solution. There's that 1% of math geniuses who get it from straight algebra, but most of us (myself included) don't automatically have an intuitive feel of what the equation is actually saying. So here's the algebraic solution:

I actually didn't derive the solution from a summation of a summation first, however. I did something cooler.

We know that one for loop runs n times.

And we can figure out quickly how many times two nested for loops run.

for (int i= 1; i <= n; i++){
    for (int j= 1; j <= i; j++){
        sum++;
   }
}

This is just the sum of:

And you probably remember that neat little graphical proof of this summation. We make a triangle with 1 X in the first row, 2 X's in the second, and so on. Then we turn it into a rectangle using O's. For example:

XOOOO
XXOOO
XXXOO
XXXXO


Now the key thing to note is that we added an "O" to the bottom row. Thus the "area" (or number of elements) of the rectangle is:

And the number of X's (what we are after) is half that:

Okay now let's extend that idea to 3 nested loops. We can now think of the trangle as being made of numbers representing the depth in the z-dimension at that point. So our triangle becomes:

1
21
321
4321

Now imagine if what this would look like if we drew it in 3-D with X's. It'd look like a triangular pyramid!! Now what would the dimension of the pyramid be if we are calculating the volume similarly to how we calulated the area of the triangle. Well we know it is n units tall in the y-dimension, and (n+1) units wide in the x-dimension.

We just need the z-dimension. Well (n+1) is a good guess, but we actually have to add two triangles to make our shape into a rectangular prism (one in the z-dimension and one in the y-dimension). Then we are going to cut off parts of it to get our triangular pyramid (check out http://nrich.maths.org/1408 for a good graphical derivation of the volume of a triangular pyramid). So we have a triangular pyramid with dimension (n)x(n+1)x(n+2) and using that volume formula you learned in 7th grade we have:

Et, Voila! Our formula! No algebra required.

The real value of this derivation comes in the from thinking about the data structure that would be traversed by this triplely-nested for loop: an array of dimension NxNxN where elements with an index greater than the row and/or column and/or "depth" do not exist.

Okay, </math nerd blog>.