DAA: PRACTICAL MANUAL: PRACTICAL 9

Experiment No: 9

1. Experiment vision:Write a program to study and implement Floyd’s algorithm.

2. OBJECTIVE: Program for computing all pairs shortest path.

3. THEORY:

 Used to find shortest paths in a weighted graph

 • Travel maps containing driving distance from one point to another – Represented by tables – Shortest distance from point A to point B given by intersection of row and column – Route may pass through other cities represented in the table

• Navigation systems All-pairs shortest-path problem • Graph G = (V, E) • Weighted and directed graph

• Problem: Find the length of the shortest path between every pair of vertices – Length of the path is strictly determined by the weight of its edges – It is not based on the number of edges traversed

4. PROGRAM:

#include<stdio.h>

#include<conio.h>

int min(int,int);

void floyds(int p[10][10],int n)

{

 int i,j,k;

 for(k=1;k<=n;k++)

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

   for(j=1;j<=n;j++)

    if(i==j)

     p[i][j]=0;

    else

     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);

}

int min(int a,int b)

{

 if(a<b)

  return(a);

 else

  return(b);

}

void main()

{

 int p[10][10],w,n,e,u,v,i,j;;

 clrscr();

 printf("\n Enter the number of vertices:");

 scanf("%d",&n);

 printf("\n Enter the number of edges:\n");

 scanf("%d",&e);

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

 {

  for(j=1;j<=n;j++)

   p[i][j]=999;

 }

 for(i=1;i<=e;i++)

 {

  printf("\n Enter the end vertices of edge%d with its weight \n",i);

  scanf("%d%d%d",&u,&v,&w);

  p[u][v]=w;

 }

 printf("\n Matrix of input data:\n");

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

 {

  for(j=1;j<=n;j++)

   printf("%d \t",p[i][j]);

  printf("\n");

 }

 floyds(p,n);

 printf("\n Transitive closure:\n");

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

 {

  for(j=1;j<=n;j++)

   printf("%d \t",p[i][j]);

  printf("\n");

 }

 printf("\n The shortest paths are:\n");

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

  for(j=1;j<=n;j++)

  {

   if(i!=j)

    printf("\n <%d,%d>=%d",i,j,p[i][j]);

  }

 getch();

}

5. OUTPUT:

------------------------------------------

------------------------------------------

6. conclusion:

Thus a C program for Floyd’s algorithm has been implemented and executed successfully.

8. Discussion Questions:

1) what is Floyd’s algorithm?

_________________________________________________________________________________________________________________________________________________________

2)   Briefly give the difference between Floyd’s algorithm and Warshall algorithm.

________________________________________________________________________________________________________________________________________________________

DAA: PRACTICAL MANUAL: PRACTICAL 8

Experiment No: 8

1. Experiment vision: Write a program to study and implement minimum spanning tree    using Prim's algorithm.

2. OBJECTIVE: Program to implement minimum spanning tree from prim’s algorithm and   connected node to each other in such way that not become a cycle.  

3. THEORY:

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a sub set of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components.

It works as follows:

• create a tree containing a single vertex, chosen arbitrarily from the graph

• create a set containing all the edges in the graph

• loop until every edge in the set connects two vertices in the tree

Ø  remove from the set an edge with minimum weight that connects a vertex in the tree   with a vertex not in the tree

Ø  Add that edge to the tree

4.  PROGRAM:

#include<stdio.h>

int a,b,u,v,n,i,j,ne=1;

int visited[10]={0},min,mincost=0,cost[10][10];

void main()

{

  printf("\n Enter the number of nodes:");

 scanf("%d",&n);

 printf("\n Enter the adjacency matrix:\n");

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

  for(j=1;j<=n;j++)

  {

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

   if(cost[i][j]==0)

    cost[i][j]=999;

  }

 visited[1]=1;

 printf("\n");

 while(ne<n)

 {

  for(i=1,min=999;i<=n;i++)

   for(j=1;j<=n;j++)

    if(cost[i][j]<min)

     if(visited[i]!=0)

     {

      min=cost[i][j];

      a=u=i;

      b=v=j;

     }

  if(visited[u]==0 || visited[v]==0)

  {

   printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);

   mincost+=min;

   visited[b]=1;

  }

  cost[a][b]=cost[b][a]=999;

 }

 printf("\n Minimun cost=%d",mincost);

 }

5. OUTPUT:

------------------------------------------

------------------------------------------

6. conclusion:

Thus a C program for prim’s algorithm has been implemented and executed successfully.

7.  REMARK:

                        In this algorithm, we find the minimum path from source to destination and measure that path. Source path must be start with first node of that graph.

8. Discussion Questions:

1) what is prims algorithm?

_________________________________________________________________________________________________________________________________________________________

2)   what is the difference between prims algorithm and kruskal algorithm.

________________________________________________________________________________________________________________________________________________________

DAA: PRACTICAL MANUAL: PRACTICAL 7

Experiment No: 07

1. Experiment vision:Write a program to study and implement Quick Sort.

2. OBJECTIVE: Program to implement quicksort in c programming.

3. THEORY:

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

The base case of the recursion are lists of size zero or one, which never need to be sorted.

4. ALGORITHM:

QuickSort(a,beg,end)            // a is Array

{

if(beg<end)

{

p=Partition(a,beg,end);         //Calling Procedure to Find Pivot

QuickSort(a,beg,p-1);               //QuickSort Calls Itself

QuickSort(a,p+1,end);           //(Divides the List into two Sub Lists)     

}

}

Procedure to Find Pivot :-

Partition(a,beg,end)

{

p=beg, pivot=a[beg];

forloc=beg+1 to end;

{

if(pivot>a[loc])

{

a[p]=a[loc];

a[loc]=a[p+1];

a[p+1]=pivot;

p=p+1;

}

}

return p;

}

4.  PROGRAM:

#include<stdio.h>

int partition(int a[], int beg, int end)          //function to find pivot point

{

int p=beg, pivot=a[beg], loc;

for(loc=beg+1;loc<=end;loc++)

{

if(pivot>a[loc])

{

a[p]=a[loc];

a[loc]=a[p+1];

a[p+1]=pivot;

p=p+1;

}

}

return p;

}

void quicksort(int a[],int beg, int end)

{

if(beg<end)

{

int p=partition(a,beg,end);                       //calling procedure to find pivot

quicksort(a,beg,p-1);                             //calls itself (recursion)

quicksort(a,p+1,end);                         //calls itself (recursion)

}

}

void main()

{

int a[100],i,n,beg,end;

printf("\n------- quick sort -------\n\n");

printf("enter the no. Of elements : ");

scanf("%d",&n);

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

{

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

}

beg=1;

end=n;

quicksort(a,beg,end);                        //calling of quicksort function

printf("\nafter sorting : \n");

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

{

printf("\n%d",a[i]);

}

}

5. OUTPUT:

------------------------------------------

------------------------------------------

6. conclusion:

Thus we studied quick sort method and executed successfully.

7. REMARK:

One of the fastest sorting algorithms.

8. Discussion Questions:

1) what is quicksort? How are they created?

_________________________________________________________________________________________________________________________________________________________

2)   What are the advantages and disadvantages of quicksort?

______________________________________________________________________________________________________________________________________________________

3)   What is the complexity of quicksort?

DAA: PRACTICAL MANUAL: PRACTICAL 6

Experiment No: 06

1. Experiment vision:Write a program to study and implement Knapsack problem.

2. OBJECTIVE: Program to implement Knapsack problem in c program.

                       

3. THEORY: The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

1. Given a set of items, each with a weight and a value.
2. Determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.
3. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

4.      PROGRAM:

# include<stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {

   float x[20], tp = 0;

   int i, j, u;

   u = capacity;

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

      x[i] = 0.0;

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

      if (weight[i] > u)

         break;

      else {

         x[i] = 1.0;

         tp = tp + profit[i];

         u = u - weight[i];

      }

   }

   if (i < n)

      x[i] = u / weight[i];

   tp = tp + (x[i] * profit[i]);

   printf("\nthe result vector is:- ");

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

      printf("%f\t", x[i]);

   printf("\nmaximum profit is:- %f", tp);

}

int main() {

   float weight[20], profit[20], capacity;

   int num, i, j;

   float ratio[20], temp;

   printf("\nenter the no. of objects:- ");

   scanf("%d", &num);

   printf("\nenter the wts and profits of each object:- ");

   for (i = 0; i < num; i++) {

      scanf("%f %f", &weight[i], &profit[i]);

   }

   printf("\nenter the capacityacity of knapsack:- ");

   scanf("%f", &capacity);

   for (i = 0; i < num; i++) {

      ratio[i] = profit[i] / weight[i];

   }

   for (i = 0; i < num; i++) {

      for (j = i + 1; j < num; j++) {

         if (ratio[i] < ratio[j]) {

            temp = ratio[j];

            ratio[j] = ratio[i];

            ratio[i] = temp;

            temp = weight[j];

            weight[j] = weight[i];

            weight[i] = temp;

            temp = profit[j];

            profit[j] = profit[i];

            profit[i] = temp;

         }

      }

   }

   knapsack(num, weight, profit, capacity);

   return(0);

}

5. OUTPUT:

------------------------------------------

------------------------------------------

6. conclusion:

Thus we studied Knapsack problem and executed successfully.

7. REMARK: The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatory, computer science, complexity theory, cryptography, applied mathematics, and daily fantasy sports.

8. Discussion Questions:

1) what is Knapsack problem?

_________________________________________________________________________________________________________________________________________________________

2)   What is Greedy methods?

________________________________________________________________________________________________________________________________________________________