Airplane Boarding Algorithms
Posted 10 Jul, 2006 at 00:30 by kael in /Math | Permanent link
Ever wonder what the most efficient algorithm is for arranging passengers boarding an airplane? You're not alone! This paper is a mathematical analysis of the topic of airplane boarding algorithms. Well, two of them.
Comments (0 comments so far)
Rampant innumeracy
Posted 12 Jan, 2005 at 13:41 by matt in /Math | Permanent link
Apple, j'accuse!
One of the taglines for the new iPod shuffle: "240 songs. A million different ways." Now, not considering for the moment whether an MP3 player with no playlist display is really a smart direction -- after all, it's not like Apple's is the first one -- my mathematical sense is highly offended by their slogan.
The total number of ways of ordering 240 objects is 240!, which is, um, not a small number. A very big number, in fact. Roughly, it's 4.07×10468. (Thank you, Mathematica.) So saying that there are "a million different ways" (not even "at least"!) is a criminal understatement. For comparison, if you want to have a million different ways: get yourself a portable CD player, find a CD with ten tracks on it, and hit "shuffle". (Even then you're overshooting the mark by a factor of 3.6 or so, but at least you're in the right ballpark.)
Comments (0 comments so far)
Netmasks and Snow
Posted 06 Jan, 2005 at 09:35 by brent in /Math | Permanent link
I came up with what I think is a simple way to determine if a netmask is valid. If the netmask is represented as an unsigned 4 byte integer, let's call it nm, then if ((~nm) + 1) & (~nm) == 0 then nm is a valid netmask. Just to go in a bit of detail, a valid netmask is a set of 1's followed by a set of zeroes. so if a bit sequence of 01 appears in the netmask, the netmask is invalid.
So ~ is the bitwise complement, + is the standard integer add, and & is bitwise AND. So if the netmask is valid, ~ will flip the bits so it's a sequence of zeroes followed by a sequence of ones. Add one to that and you flip the bits again for all the ones to zeroes and the first zero to a one (or overflow the 4 bytes resulting in a zero value). If the netmask is valid, if you bitwise and that value now with the bitwise complement, you should now get zero.
If the netmask is invalid on the otherhand, then there is a 01 sequence somewhere. When you bit flip you get 10. When you add 1, that zero ensures the 1 is still there (no carry will get it to zero). So when you bitwise AND it with the bitwise complement, you will get 10 in that location which is certainly non-zero.
And it is currently snowing outside, so it looks like I'll have to wear shoes today (snow in sandals just doesn't work).
Comments (0 comments so far)
Wavelets
Posted 04 Jan, 2005 at 00:35 by brent in /Math | Permanent link
Somebody shoot me. I did such a nice post for Matt then promptly overwrote it.
It went something like: Hey Matt! Just saw your post and did some digging on the web. As I recall (unreliably) I heard of wavelets being used for image and audio compression (lossy however) by dropping less significant terms and storing the rest.
Anyway, the sites of which I can now only dig up two of the four (though the other two sucked anyway since they were only book references):
www.wavelet.org -- includes digest and discussion forum
http://www.stardrive.org/math/Wavelets.htm -- has some visible math going on
Happy New Year to danglers and danglees. Also a belated Happy Seshmas (Seasonal Economic Stimulus Holiday). If you missed your opportunity, go out and shop. The economy will still thank you.
Not sure how many more posts I'll be able to do for a little while. Evil Empire action is kicking up and that means keep an eye on your molten cores.
Comments (0 comments so far)
Wavelets
Posted 13 Dec, 2004 at 18:51 by matt in /Math | Permanent link
If anyone reading this could point me in the direction of a gentle introduction to wavelets, and specifically their role in image enhancement, I'd be most grateful. I'm apparently going to be telling a bunch of high-school and junior college teachers about them at a workshop in six months' time. This means that I need to know something about them within that span of time.
Comments (0 comments so far)
Quirk of the day
Posted 18 Nov, 2004 at 14:03 by matt in /Math | Permanent link
My spell-checker is constantly suspicious about the perfectly proper plural vertices
, but lets Dijkstra
pass without comment.
Comments (0 comments so far)
At the moment...
Posted 10 Nov, 2004 at 19:56 by kael in /Math | Permanent link
This.
It's not so much that any one thing on there doesn't make sense to me, it's just that after half an hour of staring at it, I realized that I had to uncross my eyes, and break out the old text books to refresh my memory on some things to remember how they worked.
This, in turn, lead me to this.
Which is ironic, because I used to slurp up that wiki like it was going out of fashion when I was a geek by trade.
"Quaternions came from Hamilton ... and have been an inmixed evil to those who have touched them in any way. Vector is a useless survival ... and has never been of the slightest use to any creature." - Lord Kelvin