Due: Wednesday, December 16, 2020.

Turn in: source code including a short readme file with compilation and running instructions. Also, turn in a short report (1-2 pages) describing the idea you implemented and how you applied parallelism to solve the problem.

Presentation: last week of class. Optional for 5 extra credit points. Prepare a small presentation (5-10 minutes) of the projects for our zoom session in the last week of class.

Ideas for Projects

1. Output server. Starting from the hello program (or another one), write an output server in MPI and test it.
The server is waiting for messages from the workers and writes them out in the order in which it receives them. The messages must be strings of fixed size. For the workers you must implement a write function that takes a string of any size and outputs it by sending the server as many messages as necessary. Write a small test program for it.

2. The philosophers problem. Implement a solution for the philosophers problem using MPI.

3. Quicksort. Implement a parallel version of the function quicksort in MPI using the logarithmical data spreading method, similar to the pthreads version that we've seen.

4. The bucket sort. Implement the bucket sort function as described in the C243 textbook or slides, and as seen in Class Exercise 2.

5. Distributed dictionary. Implement a simple version of a distributed database in which the program disposes of a dictionary of words that is read and distributed to the workers. Then the master asks the user for a word, determines which worker has the part of the dictionary where the word could be found, then sends the word to that worker for spell-checking. The procedure can be repeated until the user enters a special kind of word to finish.

6. Graph Dept-first Search. Implement a parallel version of the depth-first search algorithm in a graph.

7. Network Topology. Implement a broadcast in a tree, hypercube, or torus network in MPI and compare the performance with the linear one. See slides for the tree and textbook, page 41, for the others.

8. Maze Generator. Implement a parallel version of a maze generator algorithm based on Prim's algorithm from graph theory. Appropriate for a student who had a computer graphics or games programming class.

9. Textbook exercises. The end of chapters in the book contain exercises which can be used as inspiration for projects.