CS 1510 Midterm 2

Fall 2001

1.

(a)

(5 points) Explain how to compute the logical OR of n bits $x_1, \ldots, x_n$ in $O(\log n)$ time with n processors on a EREW PRAM.

(b)

(5 points) Explain how to compute the logical OR of n bits $x_1, \ldots, x_n$ in time O(1) time with n processors on a common CRCW PRAM.

(c)

(5 points) State one of the many different equivalent versions of the folding principle.

(d)

(10 points) Give an example of a running time T(n, p) of a parallel algorithm with the property that if you multiply the number of processors by four, then you halve the efficiency. Start by defining efficiency, and make sure to justify your answer.

2.

Consider the following 3-PARTITION problem which asks if you can partition the input into 3 sets with equal sum:

INPUT: positive integers $x_1, \ldots, x_n$ with $L = \sum_{i=1}^n$

OUTPUT: 1, if you can partition the input into three parts, each with sum L/3 and 0 otherwise.

Note that each number must be in exactly one of the three partitions.

(a)

(20 points) Given an algorithm for this problem with running time polynomial in n+L.

(b)

(10 points) Prove or disprove that the algorithm from the previous part is a polynomial time algorithm. For full credit your proof must be formal, but you can get partial credit for a convincing informal argument.

(c)

(20 points) Prove that the 3-PARTITION problem is NP-hard using the fact that the following PARTION problem is NP-complete

INPUT: positive integers $x_1, \ldots, x_n$ with $L = \sum_{i=1}^n$

OUTPUT: 1, if you can partition the input into two parts, each with sum L/2

3.

(20 points) Show by reduction that if the decision version of the SAT-CNF problem has a polynomial time algorithm then the decision version of the 3-coloring problem has a polynomial time algorithm. Recall that the input to the SAT-CNF problem is a Boolean formula in conjunctive normal form, and the problem is to determine if the formula is satisfiable. Recall that the input to the 3-coloring problem is an undirected graph and the problem is to determine if each vertice can be colored by one of three colors in such a way that no two adjacent vertices are colored the same.

4.

(20 points) Design a parallel algorithms that merges two sorted arrays into one sorted array in time O(1) using a polynomial number of processors on a CRCW PRAM.

5.

(20 points) Consider the following problem. The input consists of a sequence $R = R_0, \ldots, R_n$ of non-negative integers, and an integer k. The number R_i represents the number of users requesting some particular piece of information at time i ( say from a data-base server, a name server, a www server, etc). If the server broadcasts this information at some time t, the the requests of all the users who requested the information strictly before time t are satisfied. The server can broadcast this information at most k times. The goal is to pick the k times to broadcast in order to minimize the total time (over all requests) that requests/users have to wait in order to have their requests satisfied.

As an example, assume that the input was R = 3, 4, 0, 5, 2, 7 (so n=6) and k=3. Then one possible solution (there is no claim that this is the optimal solution) would be to broadcast at times 2, 4, and 7 (note that it is obvious that in every optimal schedule that there is a broadcast at time n+1 if $R_n \ne 0$). The 3 requests at time 1 would then have to wait 1 time unit. The 4 requests at time 2 would then have to wait 2 time units. The 5 requests at time 4 would then have to wait 3 time units. The 2 requests at time 5 would then have to wait 2 time units. The 7 requests at time 6 would then have to wait 1 time units. Thus the total waiting time for this solution would be

3 * 1 + 4 * 2 + 5*3 +2*2 + 7*1