CS 1510 Midterm 2

Fall 1999

1.

(a)

(5 points) Define ``common CRCW PRAM''.

(b)

(5 points) Explain how to AND n bits in $O(\log n)$ time with n processors on a EREW PRAM.

(c)

(5 points) Compute the efficiency of the above algorithm. Start with the definition of efficiency and show your work.

(d)

(5 points) According to the folding principle one could implement this algorithm on n^1/3 processors so that it ran in how much time? Start with the definition of ``the folding principle'' and show your work.

2.

(20 points) A square matrix M is lower triangular if each entry above the main diagonal is zero, that is, each entry M_i,j, with i < j, is equal to zero. Show that if there is an O(n²) time algorithm for multiplying two n by n lower triangular matrices then there is an O(n²) time algorithm for multiplying two arbitrary n by n matrices.

3.

Consider the following problem. The input consists of n points in the Euclidean plane. The output should be a recti-linear polygon of minimum perimeter such that every one of the n points in on the boundary of the polygon. In a recti-linear polygon every side must be parallel to either the x or the y axis.

(a)

(5 points) Define the performance ratio of an algorithm A in the context of this problem.

(b)

(15 points) Give a polynomial time algorithm for this problem that has performance ratio at most 2. For full credit, you must prove that your algorithm has performance ratio 2. Note that your polygon need not be simple, that is, it can have edges that cross.

4.

In this problem we consider the NP-complete subset sum problem. The input is n positive integers $x_1, \ldots, x_n$ and an integer L. The goal is to determine whether there is a subset of the x_i's that sums to L.

(a)

(5 points) Prove or disprove that an algorithm that solves this problem in time O(nL) is a polynomial time algorithm. Start with a definition of polynomial time algorithm.

(b)

(15 points) Assume that subset sum is the only NP-complete problem that you know. Show using a reduction that the following problem is NP-hard. The input is n positive integers $x_1, \ldots, x_n$ and an integer L. The goal is to determine whether it is possible to partition the x_i's into three different subsets A, B and C, such that each subset has same sum, $\frac{1}{3}\sum_{i=1}^n x_i$. Note each x_i must be in exactly one of A, B or C.

NOTE: I will award some partial credit on this problem for setting up the reduction correctly, even if you can't correctly construct an appropriate input translation.

5.

(20 points) Give a parallel algorithm for this problem that runs in time O(1) on a common CRCW machine with the number of processors polynomial in n. The input consists of text array $T[1], \ldots, T[n]$ and a pattern array $P[1], \ldots, P[m]$. The problem is to find the first occurrence of the pattern in the text. That is, find the smallest i, such that $T[i]=P [1], T[i+1]=P [2], T[i+2]=P [3], \ldots, T[i+m-1]=P [m]$, where $1 \le i \le i+m-1 \le n$. Of course if no such i exists, your algorithm should recognize that also.

6.

(20 points) The input to this problem is n points $x_1, \ldots, x_n$ on a line. A good path P has the property that one endpoint of P is the origin and every x_i is covered by P. Note that P need not be simple, that is, it can backtrack over territory that it has already covered. Assume a vehicle moves along this path from the origin at unit speed. The response time r_i for each x_i is the time until the vehicle first reaches x_i. The problem is to find the good path that minimizes $\sum_{i=1}^n r_i/n$, the average response time. For example, if the points are x₁=1 x₂= 8 and x₃=-2 and the path visited the points in the order x₁, x₃, x₂, the average response time for this path would be 1/3 + (1+3)/3 + (1+3+10)/3.

Give a polynomial time algorithm for this problem.