Algorithm design -- 2

Completed Posted Apr 13, 2015 Paid on delivery
Completed Paid on delivery

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.

Algorithm C++ Programming Java

Project ID: #7474910

About the project

2 proposals Remote project Active Apr 13, 2015

Awarded to:

akpv1

Hello Currently involved in machine intelligence research at IIT Bombay. Senior CS undergrad. Have done multiple courses on Algorithms and DS, and completed over 400 spoj problems. This shouldn't take more than a fe More

$80 USD in 0 days
(3 Reviews)
1.4

2 freelancers are bidding on average $90 for this job

nani01029x

A proposal has not yet been provided

$100 USD in 2 days
(131 Reviews)
5.8