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?

________________________________________________________________________________________________________________________________________________________

DAA PRACTICAL MANUAL : PRACTICAL 5

Experiment No: 05

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

2. OBJECTIVE: Program to implement an array of object in C and to find the specific 

                        element.  

3. THEORY: In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also implemented, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.

4.  PROGRAM:

#include<stdio.h>

#define MAX 10

#include<stdlib.h>

void insert(int queue[],int *rear,int front,int value)

 {

   *rear=(*rear+1);

   if(*rear==front)

     {

       printf("the queue is full can not insert a value\n");

       exit(0);

     }

   queue[*rear]=value;

 }

void delete(int queue[],int *front,int rear,int * value)

 {

   if(*front==rear)

     {

       printf("the queue is empty can not delete a value\n");

       exit(0);

     }

   *front=(*front+1);

   *value=queue[*front];

 }

void main()

 {

   int queue[MAX];

   int front,rear;

   int n,value;

   front =0;

   rear=0;

   do

     {

       do

           {

            printf("enter the element to be inserted\n");

            scanf("%d",&value);

            insert(queue,&rear,front,value);

            printf("enter 1 to continue\n");

            scanf("%d",&n);

           }while(n==1);

       printf("enter 1 to delete an element\n");

       scanf("%d",&n);

       while(n==1)

           {

             delete(queue,&front,rear,&value);

             printf("the value deleted is %d\n",value);

             printf("enter 1 to delete an element\n");

             scanf("%d",&n);

           }

       printf("enter 1 to continue\n");

       scanf("%d",&n);

    }while(n==1);

 }

5. OUTPUT:------------------------------------------

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

6. conclusion:

Thus a C program of queue has been executed successfully.

7. REMARK:

In the queue, how the element added and remove. We understood all the procedure through this program.

8. Discussion Questions:

1) what is Queue?

_________________________________________________________________________________________________________________________________________________________

2) How is queue working, explain with example? (diagrammatically)

________________________________________________________________________________________________________________________________________________________

3)   What are the types of queue?