Wednesday, March 09, 2005

The Absolute Best Partitioning

Wow was today a beautiful day outside. It's like our reward from God for enduring so much bloody rain because it was so sunny and so breezy that it felt just perfect. If it was like this everyday Austin would be Heaven. Back to the topic at hand though: I was struck by one of my nerdy revelations today in CS class so I thought I'd share the inspirational algorithm. If you have a large number of elements to sort and you want it done fast a great method to turn to is Quick Sort. For those of you who have forgotten, this means that you pick a pivot, you partition the set into two sets that are greater than and less than the pivot, and then you do it again. Once you get to seven elements, you do an insertion sort. This is N log N time and constant space, and what's really intriguing is the magical number seven. If there are 7 elements you pick the middle point to be the pivot, if it's between 7 and 40 you find the median from the first, last, and middle values to be the pivot, and if you have more than 40 elements you basically do the same thing by just separating it out. How did they know it's 40 or 7 though? What makes them so magical? One day I'll figure that out and post about it, but I'm sure there's some complex proof behind it along with empirical evidence.

The most effective partitioning algorithm is also pretty sweet because you basically head towards the middle from either end trying to swap elements that belong on whichever side of the pivot and along the way you also swap pivot elements themselves to either end (depending on which side your on). Then, you swap them to the middle in a quick pass. Now that is some smart partitioning, and it's blazingly efficient in terms of how much it speeds up the algorithm itself. If you want to see the partition code click here and if you want to see the quicksort itself click here.

Those of you less tech-savvy can pull off your earmuffs because I have some technology news that you may actually understand. Samsung has proven that they are on fire this week since not only have they unleashed that new LCD, but they've also announced that they'll be unveiling the world's first 7 megapixel camera phone. The phone also features some other attractive multimedia features and while little other than the dimensions of the phone have been released you can bet that it would break your piggy bank. Another cool innovation of today is called the TDA and it's like a PDA but it relies on your thumbs rather than those tiny plastic pens. The price is surprisingly tame and I really think that they're on to something with that idea. Why should I stop there when I also found an article about arm-wrestling robots. So far they're not too powerful, but its a step in the right direction for uses of electroactive polymers. And lastly, I thought I'd share some pictures of the upcoming Mini Mozilla application that would allow Palm users to trash their IE for a neat alternative.

I have a decent selection of premium movie news to share today. There is some strong speculation that Jor-El for Superman Returns has been cast, and the actor is none other than former Jor-El Marlon Brando! Yes, amazing he is still breathing and still acting. Keanu Reeves is slated to be the lead in Rob Cohen's The 8th Voyage of Sinbad, which is only notable because Cohen is finishing up an interesting action flick called Stealth and Reeves may have started a trend of doing good movies (like A Scanner Darkly). Yahoo! Movies put up some new production photos and storyboards from Sin City so I thought I'd show off one of the cooler shots:

Now that's accuracy

I finally found the Comic Con video that made me fall in love with the movie last year so I thought I'd link it since it's what Rodriguez showed Frank Miller to get him to allow the production of the film. There's more new media online today as well. A new picture of The Fountain has surfaced and though it's nothing special it's better than nothing for this promising movie. The final Revenge of the Sith poster has been released just in time for tomorrow's premiere of the official trailer during the OC (it'll be really ironic how many nerds tune it just to see the trailer). Peter Jackson put up a video in his production diary for his remake of King Kong with a behind-the-scenes look at Naomi Watts in the giant's hand. This movie has some potential so I wish him the best on it.

I have more randomness than usual before I conclude. There has been an idea posited of charging 5 cents for mp3s rather than the standard dollar. Apple actually listened and the principle is that much more people would buy music than currently since it would be so cheap and it would make up for lost revenue, but the idea was proposed to be piloted in Canada and the industry up there is not happy. I think it's a neat idea though. Sony is apparently revealing the PS3 to their executives next week and the excitement continues to build over the supposed powerhouse, next-gen console. In the meantime we'll have to settle for cool games like X-Men Legends 2, which should be sweet considering how nice the first game turned out. I was messing around on Newgrounds yesterday and found this bunny clip that I thought was totally awesome. It's quite violent but it's all animated and really well done so give it a look see if you're not easily mortified.

And now for some Cheddar X:
1. What was your first concert?
It was the Sprite Liquid Mix tour with Talib Kweli and The Roots and a few other acts, but I mainly went for those two and it was kickass.

2. What was your first concert you were "dying" to go to?
I haven't gone to many concerts yet, but I was really hyped up to see 3 Doors Down and Our Lady Peace.

3. What was your first album?
The first CD I ever got was Ace Of Base's The Sign from one of my aunts. I listened to it quite a bit because I was a big fan of them when I was little and still hold on to the CD for the memory.

4. What was the last concert you went to?
3 Doors Down and Our Lady Peace! I really wish I hadn't missed Incubus.

5. Who would you most like to see in concert (alive or dead)?
Coldplay! I may actually give my left nut to see them in concert because they are so amazingly talented.

6. Where is the best place you've seen a show?
Cynthia Woods Mitchell Pavillion in Houston I suppose. I really need to see more concerts, huh?

No comments: