20CS472001  Design and Analysis of Algorithms II  Winter 2011 


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 endpointWhat is the complexity of this algorithm (measurement is on the number of executions of the most frequently executed statement?
Instance: A set S={a_{1},a_{2},...,a_{n}} 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(n^{2}) time. Observe, the algorithm may sometimes fail but usually does not!!!