Parallel computing					22.11.2010

Exercise 4

Draw a picture of each task. Specify the time complexity, number of
processors, and work of each algorithm.

16) Analyse the time complexity of A) merge by ranking and B) mergesort
    using the previous merge if we have a) N^2 processors, b) N
    processors, c) any number (P) of processors. In case c, the result
    will be a function of N and P. Use the parallel P-ary search
    algorithm (exercise 18) for ranking.

17) Write a PRAM algorithm that finds the location of the longest common
    subsequence of two strings (character arrays). E.g., in strings
    "subsequence" and "timequestion" the longest common subsequence is
    "eque", and the locations are 5 and 4 (or 4 and 3 if you use
    0-indexed arrays). You may not use CRCW PRAM. If you make an O(N)
    algorithm, sketch how to make it faster.

18) Write an algorithm for parallel "binary search" (handouts page 100).
    The algorithm returns the position (rank) of an element x in a
    sorted array A. Do not use CW variants. The algorithm is actually a
    (P+1)-ary search as it divides the input with P division points on
    every iteration. Pay attention to the indeces and make the indexing
    work with any N or P.

The following obligatory X2 exercise replaces standard exercises 19 and
20.

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 simo.juvaste@uef.fi (i.e.,
sjuva@cs.joensuu.fi) with a subject  PAR_X2_email@add.re.ss  (with
underscores), and the answer (with self-evaluation) as the body of the
message (no MIME attachments, no HTML). At simplest, using program mail
at cs.uef.fi:

    /usr/ucb/mail -s PAR_X2_email@add.re.ss sjuva < answer.txt 

where email@add.re.ss is the email address you have in WebOodi (or given
to this course), 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.

X2) Write a PRAM algorithm to find the longest continuous sequence of
    1's in a binary array. It is enough to return the starting index of
    the sequence. E.g., for array [1 0 1 1 1 1 0 1 0 0 0 0 0 1] the
    return value would be 3 (2 if you use 0-indexed arrays). You may not
    use CRCW PRAM.  State the execution time, number of processors used
    and work of your algorithm.

    Grading is made on basis of correct functionality, readability,
    time, and work of your algorithm. For full 6 points, the algorithm
    should be O(logN) time and O(N) work. For 4 points, the algorithm
    should be either o(N) time and O(N) work, or O(logN) time.