Parallel computing				8.11.2010
Exercise 2


The following obligatory X1 exercise replaces standard exercises 6 and
7.

The answers to X-exercises have to be unique for every student. No
copies of the same answer are allowed. The answer has to be sent via
email by Sunday 4:00 pm (the previous day). You will receive an
acknowledgment upon successful processing. Answers will be graded. The
answer must also contain a short self-evaluation in which you describe
whether the algorithm works, nearly works, or does not probably work;
how efficient it is, etc. A correct and proper self-evaluation is worth
one point (in case of a proper answer).

Send your answer (a plain text file) to sjuva@cs.uef.fi with a subject
PAR_X1_email@address.domain  (with underscores), and the answer (with
self-evaluation) as the body of the message (no attachments). At
simplest, using program mail at cs.uef.fi:

    /usr/ucb/mail -s PAR_X1_email@address.domain sjuva < answer.txt 

where email@address.domain is the email address you have in WebOodi, and
answer.txt is the text file containing your answer. If you wish to use
another email address, please let me me know beforehand by email. This
first X-exercise is also a rehearsal and a test of the automatic
processing system.

X1) Let us assume that N persons (e.g., 32) sit in a circle, each person
    has a display (or a paper or a blackboard) on which only (s)he can
    write and all others can see it simultaneously. Moreover, each
    person has a unique ID (1..N), and all persons know all IDs. This
    essentially formulates a CROW PRAM. The persons may have some local
    memory (in their heads), but the others can not see it.

    At the beginning, all persons have an integer (0-99) in their displays.

    Write an algorithm for counting the sum of all values. At the end of
    the algorithm the result must be on displays of all persons.
    Estimate also the execution time of your algorithm (in seconds). 

    Write the algorithm so that it is can be executed with any set of
    average humans (non-computing professional, but literate and
    calculation-able). Use statements like "add the number on display
    ID+1 to your own number and show it on your display".

    Write an algorithm that works in o(N) addition steps (note:
    little-o, i.e., less than N). Thus you may not use algorithm:
    "everyone reads all values, counts the sum, and displays the
    result". Remember also that N/c is not o(N).

    a) The displays can contain at most 10 integers at a time (at the
       beginning, the inputs take one position). The persons may not
       speak or otherwise communicate together, just use the displays.

    b) The displays can contain only 1 integer a time. The persons may not
       speak to each other, but they can raise and lower their left
       hands (and, obviously, see the hands of other people). You can
       assume the any person can quickly inspect whether all hands are
       down or not.


 8) What are the time complexity, used number of processors, and work of
    the following parallel algorithm (as a function of N)? The
    computation result should be the same as if all loops were
    sequential. Which PRAM variant is required? How to modify the
    algorithm to be executed in an EREW PRAM.

    for i := 1 to N pardo
	for j := 1 to N pardo
		A[i, j] := 1;
    for i := 1 to N do
	for j := 1 to N pardo
		for k := 1 to N pardo
			A[i, j] := A[i, j] + k;


Write the following algorithms either in algorithm notation, or in
English/Finnish with simple and precise steps. Use PRAM notation (shared
arrays), and concentrate on data. Draw a picture of all exercises.

Let us consider a voting problem where the input is a shared array of N
elements, each having a random integer element 1..N. The result of the
algorithm is the integer which had the most occurences in the array.

 9) Write a fast algorithm for the voting problem using STRONG CRCW PRAM.
    What are the time complexity, work, and efficiency of your algorithm?

10) Write a fast algorithm for the voting problem using any other CRCW
    PRAM version than STRONG CRCW. What are the time complexity, work,
    and efficiency of your algorithm?