Well it looks like I'm going to get the opportunity to parallelize a program not even related to my parallel class, in fact, it's for Theory of Computation. The definition of a "Busy Beaver" Turing machine can be found a number of places, but basically it's a finite state machine that has an endless tape (in our case, a left-bound endlessly right tape) that reads and writes 0's and 1's and at some point comes to a halt, while keeping track of how many 1's it was able to write. Parallelizing this actually shouldn't be that hard, we're going to use the round robin approach, using a master and a slave to organize and balance work and the load. I'll report back and let you know if we managed to finish it and what kind of results we saw.
UPDATE (11/20/2006)
Our attempt wasn't completely successful, or at least as far as we were able to tell it wasn't. We get to have one more go at it though, and we're hoping to be able to utilize this as a really good tool for testing and speeding up output. Will update again more on this and explain what went right and what went wrong.
UPDATE(12/20/2006)
So we never really tried to finish up the parallelization on this. After some thought we decided it didn't make a whole lot of sense to pursue it the way we were trying. It might be possible to parallelize some of it, and get almost linear speed up; indeed we sort of performed this manually by starting the program at various starting places on multiple computers. And we did win our busy beaver contest in the class (a value of ~3300 written to our single left bound tape, beating the competition by roughly 1000), so we must have done something right.