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.