Projects

Due: week 14.

Common requirements

Each student or team of 2 students will take one project. It is ok to take a theme that is not listed below (but check with the lab advisor before starting).

Each project will have 2 implementations: one with "regular" threads or tasks/futures, and one distributed (possibly, but not required, using MPI). A third implementation, using OpenCL or CUDA, can be made for a bonus.

The documentation will describe:

• the algorithms,
• the synchronization used in the parallelized variants,
• the performance measurements

Themes

1. Compute the Hough transform of an image.

2. Find correlation between an image and translations/rescalings of a second image.

3. Find the shortest solution for a 15 puzzle problem.

4. Find an n-coloring of a graph.

5. Generate a school timetable through exhaustive search.

6. Generate a school timetable through genetic algorithms.

7. Simulate n-body problem.