Searching the Depth First Way

Today in CS class we had one of those 'wow' moments. Those of you apathetic towards programming can skip this paragraph. So when searching a graph, depth first is where you go to the farthest depth you can and then keep trying again and breadth first is where you go through each possible depth in waves. He wanted to represent the graph first and after shooting down our adjacency matrix idea he accepted a ragged array of the possibilities from each place. The real world example graph he gave was of routes on an airline. Now for the algorithm. We were all stuck on the recursive backtracking mindset and then he led us towards the conclusion of using a stack for depth first, and it was amazing how well it works. You basically maintain the elements you can go to from each point on the stack and as you push them on you also keep track of them on an array of visited elements. So check this out:
boolean DFS( int[][] a, int s, int v)

{  Stack x = new Stack(); //max length is a.length
   boolean[] b = new boolean[a.length];
   x.push(s);
   b[s] = true;
   while( !x.isEmpty[] )
   {  int i = x.pop();
      if( i == v ) return true;
      for(int j = 0; j < a[i].length; j++)
      {  if( !b[a[i][j]] )
         {  x.push( a[i][j] )
            b[a[i][j]] = true; } } }
      return false; }

Is that not badass? I was just sitting there in awe for a while staring at the code because the amazing part is that if you replace the stack with a queue and use enqueue() and dequeue() rather than push() and pop() you have the breadth first search algorithm! It's a relatively efficient solution (memory wise particularly) and it's so simple! Gotta love good code.

While I'm on nerdy stuff why don't I just keep babbling. Mozilla released a new version of Firefox today for added stability and a few security fixes. It sounds like the ALA is against blog people according to this opinion piece. I think people are blowing things way out of proportion and in any case bloggers wouldn't be a threat to the mass media if those people actually did their jobs right. Microsoft is finally getting the hang of anti-piracy by requiring buyers of PCs that come with Windows to answer questions before allowing them to install the OS. This is a loophole that's been abused for a while and they have every right to ensure the legitimacy of their software usage. Those of you who hate floaters will like this article pointing out that groups like Mozilla are starting to look into ways to fight that annoying crap. The Wired Rave Awards are now online to recognize innovators in everything from hybrid cars to music technology and even includes the creator of RSS. It's a great read if you have a few minutes to spare browsing it.

Not a whole lot of movie news today, but there are some things of note. Yahoo! Movies got the exclusive teaser trailer to The Amityville Horror and I've got to say that I'm quite impressed. It started to remind me of The Others but as it progressed it reminded me of my favorite horror movie: The Shining (awesome book, too). Speaking of horror movies, Shaun of the Dead star and co-writer Simon Pegg said a few words about being on the set of Land of the Dead (the new Romero flick) so fans of either should check it out. I also have some bad movie news, a bunch of nut jobs are making a Napster movie. They want it to be a biopic about Shawn Fanning, and I think it's going to bomb if they go through with it. Allow me to cushion the blow by mentioning that Doug Richardson has been confirmed by Bruce Willis to be working on the screenplay for Die Hard 4.0. It's always exciting to hear the possibility of an action movie done right. And finally, the Golden Schmo winners are up and many of my votes got the award or runner-up. I was severely disappointed that neither Will Ferrell movie won best comedy. Obviously the only movie awards that matter will be Sunday night.

Alright I'm almost done here. Since I'm on a two day streak of articles on lawsuits I might as well mention eBay getting sued for price gouging auctions. That guy is so stupid and he had better lose because he doesn't even understand how eBay actually works. At least the economy is going strong, or somewhat strong at least. We're in good shape if we have annual growth of 3-4%, and since 3.8% is in that range we're on the right track and maybe we'll finally his prosperity in a year or two. Those of you curious about the PSP launch titles can check those out here along with their box arts.



The American box comes with the PSP, a 32MB Memory Stick Duo, headphones with remote control, a sampler disc, Spider-man 2 for the first 1 million buyers, battery pack, AC adaptor, soft case, and cleaning cloth. Remember that it can also play movies and there are more accessories.

Now for Friday's Feast:

Appetizer - Name something that makes you scream.
Easy: Christian fundamentalists.

Soup - Who is a musician you enjoy listening to when you want to relax?
Coldplay all the way 8-) Chris Martin has the coolest voice and the music is just so melo.

Salad - What was the last book you purchased?
Hearts in Atlantis by Stephen King at that crazy Barnes and Noble sale.

Main Course - If you could live one day as any historical figure, who would it be, and what would you do?
Now this is a tough one. I know so many historical figures but it's hard to pin one person down as having a day to bask in. For lack of a better example, I'll say the day Tim Berners-Lee created the internet. What an amazing accomplishment to have under your belt!

Dessert - Tell about a time when you were lost. Where did you end up? How long did it take you to get back to where you were going?
The last time I was physically lost was at orientation in July and I ended up just asking someone for help. The last time I was metaphorically lost was sophomore year in high school when I just had a few life problems to deal with. I managed to solve some of them through some mental determination and the rest by losing weight. Still though, I can't kick cluttering :(