Our project explores the parallel implementations of well known algorithms to see how they differ from sequential implementations, both in terms of design, results and efficiency. In particular, we compared the sequential and parallel implementations of breadth-first search, merge sort, 2D closest pair and image convolution.
This project's zip file includes a folder containing Jupyter notebooks. These notebooks may not run directly on your local machine and are intended to be uploaded and executed on Google Colab, as support for the multiprocessing library in Jupyter on Windows OS is limited.
Additionally, we have provided some graphical results obtained by time analysis on our local machine. Alternatively, you are welcome to run the Python files provided on your own machine to generate the results yourself.
There is also a python script for visualising the Closest Pair problem. Feel free to run it on your own machine.
To use the Jupyter notebooks, simply upload them to Google Colab and run them there.
To use the Python files, open them in an IDE like Visual Studio Code and run them from there.
If you would like to contribute to this project, please submit a pull request.
- Parallel BFS Implemenation:
Blelloch, G.E. and Maggs, B.M. (2010). Parallel Algorithms. School of Computer Science, Carnegie Mellon University. pp. 22-24 - Sequential Closest Pair Implementation:
syphh. (2021, July 24). closest_pair.py [Gist]. GitHub. http://gist.github.com/syphh/b6668694edacf8cc987f89bf1270125c