Find an algorithm in the literature. The algorithm should either be concurrent or it is a sequential algorithm for which you proposed a concurrent version. The algorithm should not be trivial but also not extremely complex (since you are going to implement the algorithm in Assignment 2). Concurrent algorithms are applicable to various areas including databases, operating systems, etcetera. You are encouraged to find an algorithm in an area of your interest. Preferably, the algorithm should be presented in a journal or conference proceedings.

Ask the instructor if the paper and algorithm are appropriate. Email the doi of the paper describing the algorithm to the instructor by September 22.

Once your paper has been approved by the instructor, add your paper to the list below. Ensure that the reference in complete, that is, make sure that all relevant information is included. Attach a hyperlink to the title of your paper, linking it to the doi (something like http://dx.doi.org.ezproxy.library.yorku.ca/10.1109/TC.1980.1675680).

Write a report. In the introduction of your report, describe why the algorithm is of interest and why it is important. Feel free to use arguments found in the literature, but rephrase them in your own words and add proper references. Also briefly discuss related work (published before and after the paper you chose). In the main part of your report, describe your algorithm using pseudocode. If you have found a description of the algorithm in pseudocode in the literature, you may use that description. However, do not forget to mention the source. Also explain the algorithm in your own words. This implies that you do not copy parts of the paper. Feel free to include examples. If the examples are not your own, then mention the source.

Use LaTeX and BiBTeX to write your report. You may start from the files assignment1.tex and assignment1.bib (remove the suffix .txt from the file name). Skeletons of various types of entries of a BiBTeX file can be found in sample.bib. Numerous tutorials on LaTeX and BiBTeX can be found on the web. If you have any questions, feel free to contact the instructor.

The report should be roughly between 3 and 8 pages. These bounds are not absolute (but one page is definitely not enough and 20 pages is too much).

As the audience of your report, consider your fellow students in the course. myassignment1.pdf contains a sample. The corresponding LaTeX and BiBTeX files are myassignment1.tex and myassignment1.bib, respectively (remove the suffix .txt from the file name).

• Franck van Breugel:
  Carla Schlatter Ellis. Concurrent Search and Insertion in AVL Trees. IEEE Transactions on Computers, 29(9): 811-817, September 1980.

• Markus Solbach:
  W.N. Martin, Jens Lienig and James P. Cohoon. Island (migration) models: evolutionary algorithms based on punctuated equilibria. In, Thomas Back, David B. Fogel and Zbigniew Michalewicz, editors, Handbook of Evolutionary Computation, pages C6.3:1-C6.3:16, January 1997.

• Mohamad Alsabbagh:
  Gavin Lowe. Concurrent Depth-First Search Algorithms. In, Erika Ábrahám and Klaus Havelund, editors, Proceedings of the 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 8413 of Lecture Notes in Computer Science, pages 202-216, Grenoble, France, April 2014. Springer-Verlag.

• Amir Rasouli:
  Christopher M. Vigorito. Distributed Path Planning for Mobile Robots using a Swarm of Interacting Reinforcement Learners. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, pages 782-789, Honolulu, HI, USA, May 2007. ACM.

• Eros Gulo:
  Vincent Garcia, Eric Debreuve and Michel Barlaud. Fast k Nearest Neighbor Search using GPU. In Computer Vision and Pattern Recognition Workshops, pages 1-6, Anchorage, AK, USA, June 2008. IEEE.

• Vassil Halatchev:
  R. Agrawal and J. Shafer.Parallel Mining of Association Rules. IEEE Transactions on Knowledge and Data Engineering, 8(6):962-969, December 1996.

• Amgad Rady:
  Mikhail Fomitchev, Eric Ruppert. Lock-Free Linked Lists and Skip Lists. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, pages 50-59, St. John's, Newfoundland, Canada, July 2004. ACM.

• Yuping Lin:
  V. Turchenko and V. Golovko. Parallel Batch Pattern Training Algorithm for Deep Neural Network. In Proceedings of the International Conference on High Performance Computing and Simulation, pages 697-702, Bologna, Italy, July 2014. IEEE.