Question

Q1-

Given a set S = {1, 2, . . . , n} of players, with skill levels

a₁, a₂, . . . , a_n,

we need to partition the set of players S into two teams S₁ and S₂ of equal total skill. The teams do not need to be of equal size. However, every player must be in exactly one team. In other words,

S₁ ∪ S₂ = S                                        (1)

S₁ ∩   S₂ = ∅                                                     (2)

Σ a_k= Σ a_k                                  (3)

k∈S₁   k∈S2

1. Give a brute-force algorithm to solve this problem.

Hint: You must be able to generate subsets of S. To do that, you can use a list of binary digits b = b₁b₂. . . b_nwhere setting b = 100010 means that only players 1 and 5 are in the subset represented by b.

2. Give time complexity analysis for the worst case.

Hint: How many subsets of S contain a specific element i?

Q2-

Intervals (1, 8), (6, 9), (10, 14), (7, 11), (3, 12). Maximum activity is in the interval (7, 8), where four jobs are active.

Given a set S of n open intervals on R defined by

(a₁, b₁), (a₂, b₂), . . . , (a_n, b_n)

Each a_irepresents the beginning time of a process, and b_irepresents the termination time of the process. There is an open interval (x, y) where the greatest number of processes is active. What are the x and y of such an interval. Consider the example given in Figure 1.

1. Give a brute-force algorithm to solve this problem, with a worst-case running time of Θ(n³).
2. Provide the time complexity analysis.

Answer 1

ANSWER:

Q1-

Let isSubsetSum(arr, n, sum/2) be the function that returns true if
there is a subset of S[1..n] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
a) isSubsetSum() without considering last element
(reducing n to n-1)
b) isSubsetSum considering the last element
(reducing sum/2 by S[n] and n to n-1)
If any of the above the above subproblems return true, then return true.
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
isSubsetSum (arr, n-1, sum/2 - arr[n-1])

Algorithm->

bool isSubsetSum (S[1..n], sum) //auxiliary algo

{

    // Base Cases

    if sum = 0 then return true;

    if n = 0 and sum != 0 then return false;

    // If last element is greater than sum, then

    // ignore it

    if S[n] > sum then   return isSubsetSum (S, sum);

else   return isSubsetSum (S, sum) or isSubsetSum (S,sum-S[n]);

}

bool findPartition (S[1..n]) //main algo

{

    int sum = 0;

    for i=1 to n do

    sum += S[i];

end

    // If sum is odd, there cannot be two subsets

    // with equal sum

    if sum%2 != 0 then return false;

    return isSubsetSum (S, n, sum/2);

}

Time complexity = O(2^n)

T(n) = 2T(n-1)+O(1)

using substitution or recursion tree, we get T(n) = O(2^n)

Q2)

Screenshot of code:

output:

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll s,e;
};
bool cmp(node x,node y)
{
return x.s<y.s;
}
int main()
{
ll n,i,j;
cout<<"Enter no of intervals: ";
cin>>n;
node a[n];
cout<<"Enter interval ranges: ";
for(i=0;i<n;i++)
scanf("%lld%lld",&a[i].s,&a[i].e);
sort(a,a+n,cmp);
ll gc=0;
ll gst,ge;
for(i=0;i<n;i++)
{
ll st=a[i].s;
ll ed=a[i].e;
ll cnt=1;
for(j=i+1;j<n;j++)
{
if(a[j].s<=a[i].e)
{
cnt++;
st=max(st,a[j].s);
ed=min(ed,a[j].e);
}
else
break;
}
if(cnt>gc)
{
gc=cnt;
gst=st;
ge=ed;
}
}
cout<<"Maximum no of activity is: "<<gc<<endl;
cout<<"Interval is: ("<<gst<<" "<<ge<<")"<<endl;
}

//please upvote//