Algorithm design -- 2

1. Give a variation of generic merge algorithm for computing A⊖B, which is set of elements that are in A or B, but not in both. 2. Suppose that we implement the set ADT by representing each set using a balanced search tree. Describe and analyze algorithms for each of the methods in the set ADT. 3. Provide a pseudo code description for performing methods insert and remove on a set implemented with sorted sequence. 4. Let S = {a,b,c,d,e, f,g} be a collection of objects with benefit-weight values as follows: a:(12,4), b:(10,6), c:(8,5), d:(11,7), e:(14,3), f :(7,1), g:(9,6). What is an optimal solution to the fractional knapsack problem for S assuming we have a sack that can hold objects with total weight 18? Show your work. 5. Suppose we are given a set of tasks specified by pairs of the start times and finish times as T = {(1,2),(1,3),(1,4),(2,5),(3,7),(4,9),(5,6),(6,8),(7,9)}. Solve the task scheduling problem for this set of tasks. 6. Boolean matrices are matrices such that each entry is 0 or 1, and matrix multiplication is performed by using AND for · and OR for +. Suppose we are given two n × n random Boolean matrices A and B, so that the probability that any entry in either is 1, is 1/k. Show that if k is a constant, then there is an algorithm for multiplying A and B whose expected running time is O(n^2). What if k is n? 7. Show that (X-A) U (X-B) =X - (A n B),for any three sets X, A, and B.