20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

## Divide and Conquer

Due: xxx, 2011

1. Design a divide-and-conquer algorithm for the vertex cover problem which is stated as follows:
```       Instance:  a graph G=(V,E)
Find:      a minimum sized subset S of V such that every edge in E
contains at least one vertex in S as an endpoint
```
What is the complexity of this algorithm (measurement is on the number of executions of the most frequently executed statement?

2. Consider the following problem which we call SS:

Instance: A set S={a1,a2,...,an} of n integers, each having value between 1 and given number m, and a number B.

Question: Find a subset S' of S such that the sum of all the numbers in S' is B or verify that no such subset exists.

Produce a Divide and Conquer algorithm for this problem. What is its worst case complexity?

Suppose B is one half the sum of all numbers in S, suppose the numbers of S are distributed uniformly over 1 to m, and suppose m is a lot less than n. Come up with an algorithm that exploits this case and finds a solution (S') with very high probability in O(n2) time. Observe, the algorithm may sometimes fail but usually does not!!!

3. Show that the median of five in a list of n numbers can be computing using six comparisons.