~~NOTOC~~

====== Assignment 1 ======

===== Find a concurrent algorithm =====

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

===== Ask the instructor =====

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

===== Add your paper to the list =====

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 =====

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 {{public:assignment1.tex.txt|assignment1.tex}} and {{public:assignment1.bib.txt|assignment1.bib}} (remove the suffix .txt from the file name). Skeletons of various types of entries of a BiBTeX file can be found in {{public:sample.bib.txt|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.
===== List your paper =====

  * Franck van Breugel:\\ Carla Schlatter Ellis. [[http://dx.doi.org.ezproxy.library.yorku.ca/10.1109/TC.1980.1675680|Concurrent Search and Insertion in AVL Trees]]. //IEEE Transactions on Computers//, 29(9): 811-817, September 1980.

  * Shouzheng Yang:\\ Hunt G.C., Michael M.M., Parthasarathy S., Scott M.L. [[http://dx.doi.org.ezproxy.library.yorku.ca/10.1016/S0020-0190(96)00148-2|An efficient algorithm for concurrent priority queue heaps]]. //Information Processing Letters//, 60(3): 151-157. November 1996.

  * Loutfouz Zaman:\\ Thomas Umland [[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.2387|Parallel Graph Coloring using JAVA]]. In, P.H. Welch and A.W.P. Bakkers, editors, //Architectures, Languages and Patterns for Parallel and Distributed Applications//, volume 52 of //Concurrent Systems Engineering Series//, pages 211-218, Amsterdam, April 1998. IOS Press.

  * Elise Cormie:\\ Vladimir Lanin and Dennis Shasha. [[http://portal.acm.org.ezproxy.library.yorku.ca/citation.cfm?id=324493.324589&coll=DL&dl=GUIDE&CFID=5753246&CFTOKEN=91142545|A symmetric concurrent B-tree algorithm]]. In //Proceedings of 1986 ACM Fall Joint Computer Conference//, pages 380-389, Dallas, TX, USA, 1986. IEEE.

  * Steven Xu\\ P. A. Franaszek, J. T. Robinson, and A. Thomasian. [[http://dx.doi.org.ezproxy.library.yorku.ca/10.1109/ICDE.1991.131456|Wait Depth Limited Concurrency Control]]. In //Proceedings of Seventh International Conference on Data Engineering//, 92-101, 1991.

  * Xiwen Chen\\ R. Setia, A. Nedunchezhian, S. Balachandran. [[http://www.hipc.org/hipc2009/documents/HIPCSS09Papers/1569250351.pdf|A new parallel algorithm for minimum spanning tree problem]]. In //Proceedings of the 16th annual IEEE International Conference on High Performance Computing//, pages 1-5, Kochi, India, December 2009. IEEE.

  * Vladimir Magdin:\\ Xavier Messeguer. [[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.514|Skip trees, an alternative data structure to skip lists in a concurrent approach]]. //RAIRO Theoretical Informatics and Applications//, 31(3): 251-269, May 1997.

  * Mohammed-Ali Khan:\\ Hsi Chang and S. Sitharama Iyengar. [[http://dx.doi.org.ezproxy.library.yorku.ca/10.1145/358105.358191 |Efficient algorithms to globally balance a binary search tree]]. //Communications of the ACM//, 27(7):697-702. July 1984.

  * Calden Wloka:\\ Y.T. Kotb, S.S. Beauchemin, and J.L. Barron.  [[http://dx.doi.org.ezproxy.library.yorku.ca/10.1109/CRV.2007.49|Petri Net-Based Cooperation in Multi-Agent Systems]].  In //Fourth Canadian Conference on Computer and Robot Vision//, pages 123-130, Montreal, QC, Canada, May 2007. IEEE.

  * Andrew Milner:\\ R.V. Nageshwara, V. Kumar, [[http://dx.doi.org/10.1109/12.9744|Concurrent Access of Priority Queues]]. //IEEE Transactions on Computers//, 37(12):1657-1665, Dec. 1988.