Write an algorithm for Knapsack problem using greedy approach with suitable example.

Q.1

Algorithm:

Knapsack_algo(W,n)

{

            for i:1 to n do

            {

                        if(w[i]<W)then

                        {

                                    x[i]:=1.0;

                                    W=W-w[i];

                        }

            }

            if(i<=n)then

                        x[i]:=W/w[i];

}

Example:

Consider the item along with their respective weight and values.

I={I1,I2,I3}        w={5,4,3}               v={6,5,4}

Knapsack maximum weight, W=7.

Solution:

In this fractional crieteria items are arranged by certain ratio, where the ratio is value over profit(pi).Here solution proceed from maximum ratio to the minimum ratio.

Item	Value(vi)	Weight(wi)	Pi=(vi/wi)
I1	6	5	1.2
I2	5	4	1.25
I3	4	3	1.33

Now, arranging all the items according to their profit(pi)from maximum to minimum:

Item	Value(vi)	Weight(wi)	Pi=(vi/wi)
I3	4	3	1.33
I2	5	4	1.25
I1	6	5	1.2

Maximum weight that can be inserted is 7.SO,items I3 & I2 can be easily inserted.when item I1 is inserted, overflow occurs. So, it cannot be inserted.

So, maximum profit obtained is 4+5=9.

1 Write an algorithm for job scheduling using greedy approach with suitable example.

Q.

Algorithm:

JobSceduling(d[1…n],p[1…n],N)

{

            S={1}

            for(i=2 to N)

            {

                        if(all jobs in s union i(s U {i}) Schedule by a deadline)

                        {

                                    S=S U {i}

                                    return s;

                        }

            }

}

Example:-

Problem: n jobs, S={1, 2, …, n}, each job i has a deadline di  and a profit pi . We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline.

Jobs	J 1	J 2	J 3	J 4	J 5
Profit	20	15	10	5	1
Deadline	2	1	1	3	3

Deadline 1:   {j2,j3}

                        {15,10}

Deadline 2:   {j1}

                         {20}

Deadline 3:   { j4, j5}

                        {5,1}

The optimal solution = {1, 2, 4}.

The total profit = 20 + 15 + 5 = 40

Write an algorithm for activity selection problem using greedy approach with suitable example.

Q.1 

Algorithm:

Greedy_Act_sel(S,F)

{

            Nßlength[S]

            Aß{a}

            Iß1

            for(mß2 to n)

            {

                        If(Sm>Fi)then

                                    AßA U {am}

                                    Ißm

            }

            return A;

}

Example:-consider following set of activities the set of activities sorted in ascending order.

i	1	2	3	4	5	6	7	8	9	10	11
si	1	3	0	5	3	5	6	8	8	2	12
fi	4	5	6	7	8	9	10	11	12	13	14

Step 1: Sort f_i into non decreasing order. After sorting, f₁ £ f₂ £ f₃ £ … £ f_n.

Step 2: Add the next activity i to the solution set if i is compatible with each in the solution set.

Step 3: Stop if all activities are examined. Otherwise, go to step 2.

              From the above set first of all we will select i1.the finish time of i1 is 4

                                                I1->          si=1         Fi=4

So add in the list {i1} then select the next activity whose starting time is greater than i1

                                                I4->       si=5   Fi=7

So at that way finally we get solution set is {1, 4, 8, 11}

Time complexity:  O(nlogn)

Write a program to implement sorting with Merge sort using Divide & Conquer method.

Q-2:

#include<stdio.h>

void getdata(int arr[],int n)

{

          int i;

          printf(“enter the data:");

          for(i=0;i<n;i++)

          {

                   scanf("%d",&arr[i]);

          }

}

void display(int arr[],int n)

{

          int i;

          printf("  ");

          for(i=0;i<n;i++)

          {

                   printf("%d ",arr[i]);

          }

          getchar();

}

void sort(int arr[],int low,int mid,int high)

{

 int i,j,k,l,b[20];

          l=low;

          i=low;

j=mid+1;

          while((l<=mid)&&(j<=high))

          {

                   if(arr[l]<=arr[j])

                   {

                             b[i]=arr[l];

                             l++;

                   }

                   else

                   {

                             b[i]=arr[j];

                             j++;

                   }

                  

i++;

          }

          If(l>mid)

          {

                   for(k=j;k<=high;k++)

                   {

                             b[i]=arr[k];

                             i++;

                   }

          }

          else

          {

                   for(k=l;k<=mid;k++)

                   {

                             b[i]=arr[k];

                             i++;

                   }

          }

          for(k=low;k<=high;k++)

          {

                   arr[k]=b[k];

          }

}

void partition(int arr[],int low,int high)

{

          int mid;

          if(low<high)

          {

                   mid=(low+high)/2;

                   partition(arr,low,mid);

                   partition(arr,mid+1,high);

                   sort(arr,low,mid,high);

          }

}

void main()

{

int arr[20];

          int n;

          printf("Enter number of data:");

          scanf("%d",&n);

          getdata(arr,n);

          partition(arr,0,n-1);

          display(arr,n);

          getchar();

}