Ideas for student parallel programming project

Question

I'm looking to do a parallel programming project in C (probably using pthreads or maybe OpenMP) for a class. It will done by a group of about four students, and should take about 4 weeks. I was thinking it would be interesting to attack some NP-complete problem with a more complex algorithm like a genetic algo with simulated annealing, but I'm not sure if it would be a big enough project.

Anyone knew of any cool problems that could benefit from a parallel approach?

Answer 1

I remember a 'learning' project at our university about parallelizing alpha-beta pruning algorithms. Alpha-beta pruning itself isn't too complicated and has quite large complexity. If you parallelize it you'll need to install some signaling/data sharing to really benefit from the parallelization. Otherwise some threads would go too often or too deep into branches that already were considered too bad by other threads. I think that can be a good use case.