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)\).

3. Refine your solution from the previous bullet to use \(\mathrm{O}(n)\) processors.

Solution. For the first two bullets, 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 linear number of 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 if 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)\).

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 encouraged 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)\) (we can start with creating \(n^2\) copies of the input array in logarithmic time, and the compute the differences in one step). Then we can compute the maximum in \(\mathrm{O}(\log n^2) = \mathrm{O}(\log n)\).

Yet another solution. Since min is an associative binary operation, we can compute an auxiliary array \(B\) such that \(B[i] = \min\limits_{j=1,\ldots, i}A[j]\) in \(\mathrm{O}(\log n)\). Then we can compute the final result by computing \(\max\limits_{i = 1, \ldots, n} (A[i] - B[i])\) in \(\mathrm{O}(n)\) time.

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)\).

Solution.

1. Create \(n^2\) copies of the input array in \(\mathrm{O}(\log n)\) time.
2. Use them with \(n^2\) processors to fill a matrix \(B\) such that \(B[i, j] = 1\) if \(i < j\) and \(A[i] = A[j]\) and \(B[i, j] = 0\) otherwise. This takes \(\mathrm{O}(1)\) times.
3. Compute array \(C\) such that \(C[i] = 1 - \max B[i, j]\) (takes \(\mathrm{O}(\log n)\) time).
4. Return the sum of the elements in \(C\) (takes \(\mathrm{O}(\log n)\) time).

The correctness algorithm follows from the fact that \(C[i] = 1\) if and only if \(A[i]\) is the rightmost among all the elements with the same value. So the sum of the elements in \(C\) is precisely the number of distinct elements in \(A\).

Consider the following problem:

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

Output: the length of the longest continuous subarray consisting of \(1\)’s

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

Hint: use the jumping pointer technique from the lecture.

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)\).

Consider the following problem:

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

Output: True if the array is sorted in the increasing order, 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)\)