CS 1510 Midterm 2

Fall 1998

1.

Consider the following 3Clique problem:

INPUT: A undirected graph G and an integer k.

OUTPUT: 1 if G has three vertex disjoint cliques of size k, and 0 otherwise.

Show that this problem is NP-hard. Use the fact that the clique problem in NP-complete. The input to the clique problem is an undirected graph H and an integer j. The output should be 1 if H contains a clique of size j and 0 otherwise. Note that a clique is a mutually adjacent collection of vertices. Three cliques are disjoint if no vertex is in more than one clique.

2.

Show that the Vertex Cover Problem is self-reducible. The decision problem is to take a graph G and an integer k and decide if G has a vertex cover of size k or not. The optimization problem takes a graph G, and returns a smallest vertex cover in G. So you must show that if the decision problem has a polynomial time algorithm then the optimization problem also has a polynomial time algorithm. Recall that a vertex cover is a collection S of vertices with the property that every edge is incident to a vertex in S.

3.

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.

4.

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 EREW parallel algorithm that runs in $O(\log^3 n)$ time with n processors.

5.

In this problem you have n boxes $b_1, \ldots, b_n$ that you wish to load onto three trucks. You know the integral weight in kilograms w_i of each box b_i. You goal is to minimize the weight on most heavily loaded truck.

Consider the obvious greedy algorithm that considers the boxes in an arbitrary order, and always places the box under consideration into the least heavily loaded truck. Show that this algorithm guarantees that the weight on the more heavily loaded truck is at most $\frac{5}{3}$ times optimal. That is this algorithm has performance ratio $\frac{5}{3}$.