CS 1510 Midterm 2

Fall 1997

1.

You know that lots of famous computer scientists have tried to find a fast efficient parallel algorithm for the following Boolean Formula Value Problem:

INPUT: A Boolean formula F and a truth assignment A of the variables in F.

OUTPUT: 1 if A makes F true, and 0 otherwise.

Moreover, most computer scientists believe that there is no fast efficient parallel algorithm for the Boolean Value Problem. You want to find a fast efficient parallel algorithm for some new problem N. After much effort you can not find a fast efficient parallel algorithm for N, nor a proof that N does not have a fast efficient parallel algorithm. How could you give evidence that finding a fast efficient parallel algorithm for N is at least a hard of a problem as finding a fast efficient parallel algorithm for Boolean Formula Value problem? Be as specific as possible, and explain how convincing the evidence is.

Note that ``fast and efficient'' means poly-log time with a polynomial number of processors. The term ``poly-log'' means bounded by $O(\log^k n)$ for some constant k.

2.

(a)

Define ``EREW PRAM''.

(b)

Explain how to find add n numbers in time $T(n, p) = \frac{n}{p} + \log p$ on an EREW PRAM.

(c)

Formally define the efficiency of a parallel algorithm.

(d)

The algorithm that you developed in part b does not have ideal efficiency when p=n. Explain what this algorithm does that is inefficient.

3.

The input to this problem is a pair of strings $A=a_1 \ldots a_m$ and $B=b_1 \ldots b_n$. The goal is to convert A into B as cheaply as possible. A string C is initialized to A. The string C can be modified as follows:

(a)

For a cost of 4 you can delete any letter from C.

(b)

For a cost of 5 you can insert a letter in any position in C.

(c)

For a cost of 6 you can replace any letter by any other letter in C.

(d)

For a cost of 66 you can delete any suffix of C.

The conversion ends when C=B. The output should be a sequence of edits that converts A to B as cheaply as possible. Give a polynomial time algorithm for this problem.

For example, you can convert A=abcabc to B=aba via the following sequence: abcabc at a cost of 5 can be converted to abcabca, which at a cost of 66 can be converted to abc, which at cost of 6 can be converted to aba. Thus the total cost for this conversion would be 77. This conversion is clearly not optimal.

4.

Show that the following problem is NP-hard:

INPUT: A graph G with 2n vertices.

OUTPUT: 1 if G contains a simple cycle with n edges, and 0 otherwise.

Use the fact the the following problem is NP-hard:

INPUT: A graph G.

OUTPUT: 1 if G contains a simple cycle that spans G, and 0 otherwise.

Note that a cycle is simple if it doesn't visit any vertex more than once. A cycle spans G if every vertex is included in the cycle.

5.

The input to this problem is a character string C of n letters. The problem is to find the largest k such that

$$C[1] C[2] \ldots C[k] = C[n-k + 1] \ldots C[n-1] C[n]$$

That is, k is the length of the longest prefix that is also a suffix. Give a CRCW parallel algorithm that runs in constant time with a polynomial number of processors.