Assignment 1
-
Find a concurrent algorithm in the literature. The algorithm should
not be trivial but also not extremely complex (since you are going to model,
implement and verify the algorithm in Assignment 2, 3 and 4). Concurrent
algorithms are applicable to various areas including databases, operating
systems, etcetera. You are suggested to find a concurrent algorithm in an
area of your interest. Preferably, the algorithm should be presented in a
refereed journal or fairly recent conference proceedings.
If you find a concurrent algorithm to accomplish x and that paper is
published in the year y, then you should try to find out if any
concurrent algorithms accomplishing x
(improving/simplifying/generalizing the former algorithm) have been published
after the year y.
-
Ask the instructor if the algorithm is appropriate. Email (a link
to) the paper describing the algorithm to the instructor (preferably include
the doi).
-
Write a report. In the 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.
You are encouraged to use LaTeX and BiBTeX to write your report. You may start from the
files assignment1.tex and
assignment1.bib.
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.