Ideas for a student parallel programming project

Question

I am looking for a parallel programming project in C (possibly using pthreads or, possibly, OpenMP) for the class. This will be done by a group of four and will take about 4 weeks. I thought it would be interesting to attack some NP-complete problem with a more complex algorithm, such as a genetic algorithm with simulated annealing, but I'm not sure if it will be a big enough project.

Did anyone know of any cool issues that could benefit from a parallel approach?

Answer 1

I remember the “training” project at our university about parallelizing alpha-beta-trimming algorithms. Alpha beta itself is not too complicated and has a rather big complexity. If you parallelize it, you will need to set up some signal / data transmission in order to benefit from parallelization. Otherwise, some threads were too often or too deep in branches that were already considered too bad for other threads. I think this might be a good option.