CSE 305 - Tutorial 2 - PRAM complexity model

Consider the following problem:

Input: an array \(A\) of length \(n\) consisting of \(1\)’s and \(0\)’s

Output: the index of the leftmost \(1\) if there is at least one, and \(-1\) otherwise

1. design an algorithm in EREW PRAM model with complexity \(\mathrm{O}(\log n)\)

2. design an algorithm in CRCW PRAM (consistent mode) model with complexity \(\mathrm{O}(1)\)

Hint: compare with the algorithm for computing maximum from the lecture.

Solution. Let us consider the following algorithm:

1. Create a new array \(B\) of length \(n\).
2. For \(i = 1, \ldots, n\) in parallel, set \(B[i]\) to be \(i\) if \(A[i] = 1\) and \(n + 1\) otherwise.
3. Compute \(c\), the minimal value in \(B\).
4. If \(c \neq n + 1\), return \(c\). Otherwise, return \(-1\).

Clearly, the leftmost one, if exists, will yield the minimal value in \(B\) less than \(n + 1\), so the algorithm is correct. Complexity-wise, we see that the first two steps have constant complexity in both EREW and CRCW. The last step, as we know from the lecture, has complexity \(\mathrm{O}(\log n)\) and \(\mathrm{O}(1)\) in EREW and CRCW, respectively. Therefore, we get the required complexity.

Consider the following problem:

Input: a string \(S\) of length \(n\)

Output: True if \(S\) is a palindrome, and False otherwise

1. design an algorithm in EREW PRAM model with complexity \(\mathrm{O}(\log n)\)

2. design an algorithm in CRCW PRAM (consistent mode) model with complexity \(\mathrm{O}(1)\)

Solution. Let us consider the following algorithm:

1. Create a new array \(B\) of length \([n / 2]\).
2. For \(i = 1, \ldots, [n / 2]\) in parallel, set \(B[i]\) to be \(1\) if \(A[i] = A[n - i]\) and \(0\) otherwise.
3. Compute \(c\), the minimal value in \(B\).
4. Return True if \(c = 1\) and False otherwise.

Similarly to the previous problem, this algorithm solves the problem within the required complexity for both EREW and CRCW.

Let us give a more direct solution for the CRCW case using much fewer (check this!) processors.

1. Create a variable res and set it to True
2. For \(i = 1, \ldots, [n / 2]\) in parallel: if \(A[i] != A[n - i]\), set res to be False
3. return res

Each step of \(\mathcal{O}(1)\).

Consider the following problem:

Input: an array \(A\) of length \(n\) in which \(A[i]\) is the cost of a stock on \(i\)-th day

Output: the maximal amount of money you can earn is you buy stock on some day and sell it on one of the subsequent days

Design an algorithm in EREW PRAM model with complexity \(\mathrm{O}(\log n)\).

Hint: use divide-and-conquer approach. Note that it could be convenient if the recursive call will return not only the answer to subproblem but also minimum and the maximum on the interval.

Solution. We will present a recursive algorithm Aux solving the following subproblem:

Input: Integers \(i < j\)

Output: For the days from \(i\)-th to \(j - 1\)-st, the following numbers: minimal and maximal prices of the stock, and the maximal amount which can be earned.

You are ecnouraged to justify yourself that the following divide-and-conquer aproach solves this algorithmic problem:

1. If \(j - i = 1\), return \(A[i], A[i], 0\).
2. Let \(m_1, M_1, p_1\) and \(m_2, M_2, p_2\) be the results of the algorithm Aux for the pairs \(i, (i + j) / 2\) and \((i + j) / 2, j\).
3. Return \(\min(m_1, m_2), \max(M_1, M_2), \max(p_1, p_2, M_2 - m_1)\).

If we do the Aux computations at the second step in parallel, then the parallel complexity of the whole computation on an array of size \(n\)
denoted by \(T(n)\) will satisfy the recurrence \(T(n) = T(n / 2) + \mathrm{O}(1)\). Unfolding this relation as in the lecture, we obtain \(T(n) = \mathrm{O}(\log n)\).

Another solution. Let us form an array filled with numbers \(A[i] - A[j]\) for \(i > j\). This can be done in parallel in \(\mathrm{O}(\log n)\) (check this!). Then we can compute the maximum in \(\mathrm{O}(\log n^2) = \mathrm{O}(\log n)\).

Consider the following problem:

Input: an array \(A\) of length \(n\)

Output: the number of distinct elements in the array

Design an algorithm in EREW PRAM model with complexity \(\mathrm{O}(\log n)\).

Consider the following problem:

Input: an array \(A\) of length \(n\) of integers

Output: an array \(B\) containing the positive elements of \(A\) in the same order as they are in \(A\).

Design an algorithm in CREW PRAM model with complexity \(\mathrm{O}(\log n)\). Write your solution (with the description of the algorithm and complexity justification) on Moodle.

Implement a function AltSumParallel(begin, end, num_threads) which computes the alternating sum of the elements between the begin and end iteratirs, that is, the sum a[0] - a[1] + a[2] - ..., using num_thread threads.