1.

Write a program in C to perform linear search in

an unsorted array.
#include <stdio.h>
#include <conio.h>
void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i, num ;
clrscr( ) ;
printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;
for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[i] == num )
break ;
}
if ( i == 10 )
printf ( "Number is not present in the array." ) ;
else
printf ( "The number is at position %d in the array.", i ) ;
getch( ) ;
}

Output:Enter number to search:11

The number is at position 0 in the array.

YOGESH SINGH KATHAYAT

PAGE | 1

ROLL NO-31

2. Write a program in C to perform Binary search in

a sorted array.
#include <stdio.h>
#include <conio.h>
void main( )
{
int arr[10] = { 1, 2, 3, 9, 11, 13, 17, 25, 57, 90 } ;
int mid, lower = 0 , upper = 9, num, flag = 1 ;
clrscr( ) ;
printf ( "Enter number to search: " ) ;
scanf ( "%d", &num ) ;
for ( mid = ( lower + upper ) / 2 ; lower <= upper ;
mid = ( lower + upper ) / 2 )
{
if ( arr[mid] == num )
{
printf ( "The number is at position %d in the array.", mid ) ;
flag = 0 ;
break ;
}
if ( arr[mid] > num )
upper = mid - 1 ;
else
lower = mid + 1 ;
}
if ( flag )
printf ( "Element is not present in the array." ) ;
getch( ) ;
}

Output:Enter number to search:90

The number is at position 9 in the array.

YOGESH SINGH KATHAYAT

PAGE | 2

ROLL NO-31

3. Write a program in C language to perform

Insertion Sort.
#include <stdio.h>
#include <conio.h>
void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, k, temp ;
clrscr( ) ;
printf ( "Insertion sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
for ( i = 1 ; i <= 4 ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;
for ( k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;
arr[k + 1] = temp ;
}
}
}
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
getch( ) ;
}

Output:Insertion sort:
Array before sorting:
25 17 31 13 2
Array after sorting:
2 13 17 25 31

YOGESH SINGH KATHAYAT

PAGE | 3

ROLL NO-31

4. Write a program in C language to perform

Selection sort.
#include <stdio.h>
#include <conio.h>
void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;
clrscr( ) ;
printf ( "Selection sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
getch( ) ;
}

Output:Selection sort:
Array before sorting:
25 17 31 13 2
Array after sorting:
2 13 17 25 31
YOGESH SINGH KATHAYAT
PAGE | 4

ROLL NO-31

5. Write a program in C language to perform

Bubble Sort.
#include <stdio.h>
#include <conio.h>
void main( )
{
int arr[5] = { 25, 17, 31, 13, 2 } ;
int i, j, temp ;
clrscr( ) ;
printf ( "Bubble sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = 0 ; j <= 3 - i ; j++ )
{
if ( arr[j] > arr[j + 1] )
{
temp = arr[j] ;
arr[j] = arr[j + 1] ;
arr[j + 1] = temp ;
}
}
}
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", arr[i] ) ;
getch( ) ;
}

Output:Bubble sort:Array before sorting:

25 17 31 13 2
Array after sorting:
2 13 17 25 31
YOGESH SINGH KATHAYAT
PAGE | 5

ROLL NO-31

6. Write a program in C to implement divide and

conquer approach: Merge Sort.
#include <stdio.h>
#include <conio.h>
void main( )
{
int a[5] = { 11, 2, 9, 13, 57 } ;
int b[5] = { 25, 17, 1, 90, 3 } ;
int c[10] ;
int i, j, k, temp ;
clrscr( ) ;
printf ( "Merge sort.\n" ) ;
printf ( "\nFirst array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", a[i] ) ;
printf ( "\n\nSecond array:\n" ) ;
for ( i = 0 ; i <= 4 ; i++ )
printf ( "%d\t", b[i] ) ;
for ( i = 0 ; i <= 3 ; i++ )
{
for ( j = i + 1 ; j <= 4 ; j++ )
{
if ( a[i] > a[j] )
{
temp = a[i] ;
a[i] = a[j] ;
a[j] = temp ;
}
if ( b[i] > b[j] )
{
temp = b[i] ;
b[i] = b[j] ;
b[j] = temp ;
}
}
}
for ( i = j = k = 0 ; i <= 9 ; )
YOGESH SINGH KATHAYAT
PAGE | 6

ROLL NO-31

{
if ( a[j] <= b[k] )
c[i++] = a[j++] ;
else
c[i++] = b[k++] ;
if ( j == 5 || k == 5 )
break ;
}
for ( ; j <= 4 ; )
c[i++] = a[j++] ;
for ( ; k <= 4 ; )
c[i++] = b[k++] ;
printf ( "\n\nArray after sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", c[i] ) ;
getch( ) ;
}

Output:Merge sort:
First array
11 2 9 13 57
Second array:
25 17 1 90 3
Array after sorting
1 2 3 9 11 13 17 25 57 90

7. Write a program in C to implement divide and

conquer pproach:Quick Sort.
YOGESH SINGH KATHAYAT
PAGE | 7

ROLL NO-31

#include <stdio.h>
#include <conio.h>
int split ( int*, int, int ) ;
void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
void quicksort ( int *, int, int ) ;
clrscr( ) ;
printf ( "Quick sort.\n" ) ;
printf ( "\nArray before sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
quicksort ( arr, 0, 9 ) ;
printf ( "\nArray after sorting:\n") ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
getch( ) ;
}
void quicksort ( int a[ ], int lower, int upper )
{
int i ;
if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}
int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;
p = lower + 1 ;
YOGESH SINGH KATHAYAT
PAGE | 8

ROLL NO-31

q = upper ;
i = a[lower] ;
while ( q >= p )
{
while ( a[p] < i )
p++ ;
while ( a[q] > i )
q-- ;
if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}
t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;
return q ;
}

Output:Quick sort
Array before sorting
11 2 9 13 57 25 17 1 90 3
Array after sorting
1 2 3 9 11 13 17 25 57 90

8. Write a program in C to implement Sorting: Heap

Sort.
#include <stdio.h>
#include <conio.h>
YOGESH SINGH KATHAYAT
PAGE | 9

ROLL NO-31

void makeheap ( int [ ], int ) ;

void heapsort ( int [ ], int ) ;
void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
clrscr( ) ;
printf ( "Heap Sort.\n" ) ;
makeheap ( arr, 10 ) ;
printf ( "\nBefore Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
heapsort ( arr, 10 ) ;
printf ( "\nAfter Sorting:\n" ) ;
for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;
getch( );
}
void makeheap ( int x[ ], int n )
{
int i, val, s, f ;
for ( i = 1 ; i < n ; i++ )
{
val = x[i] ;
s=i;
f=(s-1)/2;
while ( s > 0 && x[f] < val )
{
x[s] = x[f] ;
s=f;
f=(s-1)/2;
}
x[s] = val ;
}
}
void heapsort ( int x[ ], int n )
{
int i, s, f, ivalue ;
for ( i = n - 1 ; i > 0 ; i-- )
{
ivalue = x[i] ;
YOGESH SINGH KATHAYAT
PAGE | 10

ROLL NO-31

x[i] = x[0] ;
f=0;
if ( i == 1 )
s = -1 ;
else
s=1;
if ( i > 2 && x[2] > x[1] )
s=2;
while ( s >= 0 && ivalue < x[s] )
{
x[f] = x[s] ;
f=s;
s=2*f+1;
if ( s + 1 <= i - 1 && x[s] < x[s + 1] )
s++ ;
if ( s > i - 1 )
s = -1 ;
}
x[f] = ivalue ;
}
}

Output:Heap sort:
Before sorting
90 57 25 13 11 9 17 1 2 3
After sorting
1 2 3 9 11 13 17 25 57 90

9. Write a program in C to implement Sorting: radix

sort.
# include<stdio.h>
# include<malloc.h>
struct node
{
int info ;
YOGESH SINGH KATHAYAT
PAGE | 11

ROLL NO-31

struct node *link;

}*start=NULL;
main()
{
struct node *tmp,*q;
int i,n,item;
printf("Enter the number of elements in the list : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&item);
/* Inserting elements in the linked list */
tmp= malloc(sizeof(struct node));
tmp->info=item;
tmp->link=NULL;
if(start==NULL) /* Inserting first element */
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}/*End of for*/
printf("Unsorted list is :\n");
display();
radix_sort();
printf("Sorted list is :\n");
display ();
}/*End of main()*/
display()
{
struct node *p=start;
while( p !=NULL)
{
printf("%d ", p->info);
p= p->link;
YOGESH SINGH KATHAYAT
PAGE | 12

ROLL NO-31

}
printf("\n");
}/*End of display()*/
radix_sort()
{
int i,k,dig,maxdig,mindig,least_sig,most_sig;
struct node *p, *rear[10], *front[10];
least_sig=1;
most_sig=large_dig(start);
for(k = least_sig; k <= most_sig ; k++)
{
printf("PASS %d : Examining %dth digit from right ",k,k);
for(i = 0 ; i <= 9 ; i++)
{
rear[i] = NULL;
front[i] = NULL ;
}
maxdig=0;
mindig=9;
p = start ;
while( p != NULL)
{
/*Find kth digit in the number*/
dig = digit(p->info, k);
if(dig>maxdig)
maxdig=dig;
if(dig<mindig)
mindig=dig;
/*Add the number to queue of dig*/
if(front[dig] == NULL)
front[dig] = p ;
else
rear[dig]->link = p ;
rear[dig] = p ;
p=p->link;/*Go to next number in the list*/
}/*End while */
/* maxdig and mindig are the maximum amd minimum
digits of the kth digits of all the numbers*/
printf("mindig=%d maxdig=%d\n",mindig,maxdig);
/*Join all the queues to form the new linked list*/
start=front[mindig];
for(i=mindig;i<maxdig;i++)
YOGESH SINGH KATHAYAT
PAGE | 13

ROLL NO-31

{
if(rear[i+1]!=NULL)
rear[i]->link=front[i+1];
else
rear[i+1]=rear[i];
}
rear[maxdig]->link=NULL;
printf("New list : ");
display();
}/* End for */
}/*End of radix_sort*/
/* This function finds number of digits in the largest element of the list */
int large_dig()
{
struct node *p=start ;
int large = 0,ndig = 0 ;
while(p != NULL)
{
if(p ->info > large)
large = p->info;
p = p->link ;
}
printf("Largest Element is %d , ",large);
while(large != 0)
{
ndig++;
large = large/10 ;
}
printf("Number of digits in it are %d\n",ndig);
return(ndig);
} /*End of large_dig()*/
/*This function returns kth digit of a number*/
int digit(int number, int k)
{
int digit, i ;
for(i = 1 ; i <=k ; i++)
{
digit = number % 10 ;
number = number /10 ;
}
return(digit);
YOGESH SINGH KATHAYAT
PAGE | 14

ROLL NO-31

}/*End of digit()*/

Output:Enter the number of elements in the list:5

Enter elements 1- 23
Enter elements 2- 43
Enter elements 3- 12
Enter elements 4- 33
Enter elements 5- 5
Unsorted list is:
23 43 12 33 5
Largest element Is 43,number of digit in it are 2
Pass 1:examing 1th digit from right mindig=2 maxdig=5
New list: 12 23 43 33 5
Pass 2: examining 2th digit from right mindig maxdig=4
New list: 5 12 23 33 43
Sorted list is:
5 12 23 33 43

10. Write a program in C to implement Shell Sort.

#define MAX 20
void main()
{
int arr[MAX], i,j,k,n,incr;
printf("Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
YOGESH SINGH KATHAYAT
PAGE | 15

ROLL NO-31

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

printf("\nEnter maximum increment (odd value) : ");
scanf("%d",&incr);
while(incr>=1) /*Shell sort*/
{
for(j=incr;j<n;j++)
{
k=arr[j];
for(i = j-incr; i >= 0 && k < arr[i]; i = i-incr)
arr[i+incr]=arr[i];
arr[i+incr]=k;
}
printf("Increment=%d \n",incr);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
incr=incr-2; /*Decrease the increment*/
}/*End of while*/
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

Output:Enter edge 5(0 0 to quit):3

2
Enter edge 6(0 0 to quit):2
2
Enter edge 7(0 0 to quit):1
1

Enter edge 8(0 0 to quit):2

3
YOGESH SINGH KATHAYAT
PAGE | 16

ROLL NO-31

Enter edge 9(0 0 to quit):4

3
Enter edge 10(0 0 to quit):2
4

11. Write a Program to build a binary search tree

from an array.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct node
{
struct node *left ;
char data ;
struct node *right ;
};
struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;
YOGESH SINGH KATHAYAT
PAGE | 17

ROLL NO-31

char a[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
'\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
};
void main( )
{
struct node *root ;
clrscr( ) ;
root = buildtree ( 0 ) ;
printf ( "In-order Traversal:\n" ) ;
inorder ( root ) ;
getch( ) ;
}
struct node * buildtree ( int n )
{
struct node *temp = NULL ;
if ( a[n] != '\0' )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( 2 * n + 1 ) ;
temp -> data = a[n] ;
temp -> right = buildtree ( 2 * n + 2 ) ;
}
return temp ;
}
void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

Output:YOGESH SINGH KATHAYAT

PAGE | 18

ROLL NO-31

In-order traversal
DBHEAFCG

12. Write a program in C to find minimum,

maximum, Kth smallest element in given array.
I..Maximum and Minimum Element
#include<stdio.h>
int main(){
int a[50],size,i,big,small;

printf("\nEnter the size of the array: ");

scanf("%d",&size);
printf("\nEnter %d elements in to the array: ", size);
for(i=0;i<size;i++)
scanf("%d",&a[i]);
YOGESH SINGH KATHAYAT
PAGE | 19

ROLL NO-31

big=a[0];
for(i=1;i<size;i++){
if(big<a[i])
big=a[i];
}
printf("Largest element: %d\n",big);
small=a[0];
for(i=1;i<size;i++){
if(small>a[i])
small=a[i];
}
printf("Smallest element: %d\n",small);
return 0;
}
II. Kth minimum element
#include<stdio.h>
#include<conio.h>
int main()
{
int array[100],length,i,j,temp,n;
printf("Enter The length Of The Array ");
scanf("%d",&length);
printf("\nEnter The Numbers:");
for(i=0;i<length;i++)
{
scanf("%d",&array[i]);
}
YOGESH SINGH KATHAYAT
PAGE | 20

ROLL NO-31

for(i=0;i<length;i++)
{
for(j=0;j<length-1;j++)
{
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
printf("The new array is:");
for(i=0;i<length;i++)
{
printf(" %d ",array[i]);
}
printf("\nEnter Which Smallest Number You want");
scanf("%d",&n);
printf("\nThe %d th smallest number is: %d",n,array[n-1]);
getch();
return 0;

OUTPUT:ENTER the size of the array:4

Enter 4 elements in to the array:1
2
YOGESH SINGH KATHAYAT
PAGE | 21

ROLL NO-31

3
1
Largest elements:4
Smallest elements:1

13. Write a program in C to insert and delete a

node from the binary search tree.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0
struct btreenode
{
struct btreenode *leftchild ;
int data ;
struct btreenode *rightchild ;
};
void insert ( struct btreenode **, int ) ;
void delete ( struct btreenode **, int ) ;
void search ( struct btreenode **, int, struct btreenode **,struct btreenode
**, int * ) ;
void inorder ( struct btreenode * ) ;
void main( )
{
struct btreenode *bt ;
int req, i = 0, num, a[ ] = { 11, 9, 13, 8, 10, 12, 14, 15, 7 } ;
bt = NULL ; /* empty tree */
clrscr( ) ;
YOGESH SINGH KATHAYAT
PAGE | 22

ROLL NO-31

while ( i <= 8 )
{
insert ( &bt, a[i] ) ;
i++ ;
}
clrscr( ) ;
printf ( "Binary tree before deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 10 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 14 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 8 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
delete ( &bt, 13 ) ;
printf ( "\nBinary tree after deletion:\n" ) ;
inorder ( bt ) ;
}
/* inserts a new node in a binary search tree */
void insert ( struct btreenode **sr, int num )
{
if ( *sr == NULL )
{
*sr = malloc ( sizeof ( struct btreenode ) ) ;
( *sr ) -> leftchild = NULL ;
( *sr ) -> data = num ;
( *sr ) -> rightchild = NULL ;
}
else /* search the node to which new node will be attached */
{
/* if new data is less, traverse to left */
if ( num < ( *sr ) -> data )
insert ( &( ( *sr ) -> leftchild ), num ) ;
else
/* else traverse to right */
insert ( &( ( *sr ) -> rightchild ), num ) ;
}
}
/* deletes a node from the binary search tree */
void delete ( struct btreenode **root, int num )
YOGESH SINGH KATHAYAT
PAGE | 23

ROLL NO-31

{
int found ;
struct btreenode *parent, *x, *xsucc ;
/* if tree is empty */
if ( *root == NULL )
{
printf ( "\nTree is empty" ) ;
return ;
}
parent = x = NULL ;
/* call to search function to find the node to be deleted */
search ( root, num, &parent, &x, &found ) ;
/* if the node to deleted is not found */
if ( found == FALSE )
{
printf ( "\nData to be deleted, not found" ) ;
return ;
}
/* if the node to be deleted has two children */
if ( x -> leftchild != NULL && x -> rightchild != NULL )
{

parent = x ;
xsucc = x -> rightchild ;
while ( xsucc -> leftchild != NULL )
{

parent = xsucc ;
xsucc = xsucc -> leftchild ;

}
x -> data = xsucc -> data ;
x = xsucc ;
YOGESH SINGH KATHAYAT
PAGE | 24

ROLL NO-31

}
/* if the node to be deleted has no child */
if ( x -> leftchild == NULL && x -> rightchild == NULL )
{

if ( parent -> rightchild == x )

parent -> rightchild = NULL ;
else
parent -> leftchild = NULL ;
free ( x ) ;
return ;

}
/* if the node to be deleted has only rightchild */
if ( x -> leftchild == NULL && x -> rightchild != NULL )
{

if ( parent -> leftchild == x )

parent -> leftchild = x -> rightchild ;
else
parent -> rightchild = x -> rightchild ;
free ( x ) ;
return ;

}
/* if the node to be deleted has only left child */
if ( x -> leftchild != NULL && x -> rightchild == NULL )
{

if ( parent -> leftchild == x )

parent -> leftchild = x -> leftchild ;
else
parent -> rightchild = x -> leftchild ;
free ( x ) ;
return ;

}
YOGESH SINGH KATHAYAT
PAGE | 25

ROLL NO-31

}
/*returns the address of the node to be deleted, address of its parent and
whether the node is found or not */
void search ( struct btreenode **root, int num, struct btreenode **par, struct
btreenode **x, int *found )
{

struct btreenode *q ;
q = *root ;
*found = FALSE ;
*par = NULL ;
while ( q != NULL )
{

/* if the node to be deleted is found */

if ( q -> data == num )
{
*found = TRUE ;
*x = q ;
return ;
}
*par = q ;
if ( q -> data > num )
q = q -> leftchild ;
else
q = q -> rightchild ;

}
}
/* traverse a binary search tree in a LDR (Left-Data-Right) fashion */
void inorder ( struct btreenode *sr )
{

if ( sr != NULL )
{

YOGESH SINGH KATHAYAT

PAGE | 26

ROLL NO-31

inorder ( sr -> leftchild ) ;

/* print the data of the node whose leftchild is NULL or the path
has
already been traversed */
printf ( "%d\t", sr -> data ) ;
inorder ( sr -> rightchild ) ;
}
}

Output:Binary tree before delection:

7 8 9 10 11 12 13 14 15
Binary tree after delection:
7 8 9 11 12 13 14 15
Binary tree after delection:
7 8 9 11 12 13 15
Binary tree after delection:
7 9 11 12 13 15
Binary tree after delection:
7 9 11 12 15

YOGESH SINGH KATHAYAT

PAGE | 27

ROLL NO-31

14. Write a program in C of fractional knapsack

problem to implement greedy strategy of
algorithm development.
#include <stdio.h>
#include <malloc.h>
int n = 5; /* The number of objects */
int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
YOU PAY to take the object */
int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
YOU GET for taking the object */
int W = 15; /* The maximum weight you can take */
void simple_fill() {
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0; /* I have not used the ith object yet */
cur_w = W;
while (cur_w > 0) { /* while there's still room*/
/* Find the best object */
YOGESH SINGH KATHAYAT
PAGE | 28

ROLL NO-31

maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
maxi = i;
used[maxi] = 1; /* mark the maxi-th object as used */
cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
tot_v += v[maxi];
if (cur_w >= 0)
printf("Added object %d (%d$, %dKg) completly in the bag. Space left:
%d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
else {
printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 +
(float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
tot_v -= v[maxi];
tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
}
}
printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}
int main(int argc, char *argv[]) {
simple_fill();
return 0;

}
-

YOGESH SINGH KATHAYAT

PAGE | 29

ROLL NO-31

15. Write a program in C to implement minimum

spanning tree algorithm: Kruskals Algorithm.
#include<stdio.h>
#define MAX 20
struct edge
{
int u;
int v;
int weight;
struct edge *link;
}*front = NULL;
int father[MAX]; /*Holds father of each node */
struct edge tree[MAX]; /* Will contain the edges of spanning tree */
int n; /*Denotes total number of nodes in the graph */
int wt_tree=0; /*Weight of the spanning tree */
int count=0; /* Denotes number of edges included in the tree */
/* Functions */
void make_tree();
void insert_tree(int i,int j,int wt);
void insert_pque(int i,int j,int wt);
struct edge *del_pque();
main()
{
int i;
create_graph();
make_tree();
printf("Edges to be included in spanning tree are :\n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
printf("Weight of this minimum spanning tree is : %d\n", wt_tree);
}/*End of main()*/
create_graph()
{
int i,wt,max_edges,origin,destin;
printf("Enter number of nodes : ");
scanf("%d",&n);
YOGESH SINGH KATHAYAT
PAGE | 30

ROLL NO-31

max_edges=n*(n-1)/2;
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit): ",i);
scanf("%d %d",&origin,&destin);
if( (origin==0) && (destin==0) )
break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
insert_pque(origin,destin,wt);
}/*End of for*/
if(i<n-1)
{
printf("Spanning tree is not possible\n");
exit(1);
}
}/*End of create_graph()*/
void make_tree()
{
struct edge *tmp;
int node1,node2,root_n1,root_n2;
while( count < n-1) /*Loop till n-1 edges included in the tree*/
{
tmp=del_pque();
node1=tmp->u;
node2=tmp->v;
printf("n1=%d ",node1);
printf("n2=%d ",node2);
while( node1 > 0)
{
root_n1=node1;
node1=father[node1];
}
while( node2 >0 )
{
root_n2=node2;
node2=father[node2];
}
printf("rootn1=%d ",root_n1);
printf("rootn2=%d\n",root_n2);
if(root_n1!=root_n2)
{
insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
YOGESH SINGH KATHAYAT
PAGE | 31

ROLL NO-31

}
}/*End of while*/
}/*End of make_tree()*/
/*Inserting an edge in the tree */
void insert_tree(int i,int j,int wt)
{
printf("This edge inserted in the spanning tree\n");
count++;
tree[count].u=i;
tree[count].v=j;
tree[count].weight=wt;
}/*End of insert_tree()*/
/*Inserting edges in the priority queue */
void insert_pque(int i,int j,int wt)
{
struct edge *tmp,*q;
tmp = (struct edge *)malloc(sizeof(struct edge));
tmp->u=i;
tmp->v=j;
tmp->weight = wt;
/*Queue is empty or edge to be added has weight less than first edge*/
if( front == NULL || tmp->weight < front->weight )
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while( q->link != NULL && q->link->weight <= tmp->weight )
q=q->link;
tmp->link = q->link;
q->link = tmp;
if(q->link == NULL)
/*Edge to be added at the end*/
tmp->link = NULL;
}/*End of else*/
}/*End of insert_pque()*/
/*Deleting an edge from the priority queue*/
struct edge *del_pque()
{
struct edge *tmp;
tmp = front;
printf("Edge processed is %d->%d %d\n",tmp->u,tmp->v,tmp>weight);
front = front->link;
return tmp;
YOGESH SINGH KATHAYAT
PAGE | 32

ROLL NO-31

}/*End of del_pque()*/

Output:Enter weight for this edge:6

Enter edge 2(0 0 to quit): 1
2
Enter weight for this edge:3
Enter edge 3(0 0 to quit): 5
3
Enter weight for this edge:6
Invalid edge!
Enter edge 2(0 0 to quit): 1
2
Enter weight for this edge:3
Edge processed is 1->2 3
N1-1 n2=2 root1=1 root2=2
This edge inserted in the spanning tree
Edge processed is 1->2 3
N1=1 n2=2 root1=1 root2=1
Edge processed is 2-> 3 6
N1=2 n2=3 rootn1=1 root2=3
This edge inserted in the spanning tree
Edge to be include in spanning tree are:
1->2
2->3
Weight of this minimum spaning tree is 9

YOGESH SINGH KATHAYAT

PAGE | 33

ROLL NO-31

16. Write a program in C to implement minimum

spanning tree algorithm: Prims Algorithm.
#include<stdio.h>
#define MAX 10
#define TEMP 0
#define PERM 1
#define FALSE 0
#define TRUE 1
#define infinity 9999
struct node
{
int predecessor;
int dist; /*Distance from predecessor */
int status;
};
struct edge
{
int u;
int v;
};
int adj[MAX][MAX];
int n;
main()
{
int i,j;
int path[MAX];
int wt_tree,count;
struct edge tree[MAX];
create_graph();
printf("Adjacency matrix is :\n");
display();
count = maketree(tree,&wt_tree);
printf("Weight of spanning tree is : %d\n", wt_tree);
printf("Edges to be included in spanning tree are : \n");
for(i=1;i<=count;i++)
{
printf("%d->",tree[i].u);
printf("%d\n",tree[i].v);
}
}/*End of main()*/
create_graph()
{
int i,max_edges,origin,destin,wt;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1)/2;
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit) : ",i);
scanf("%d %d",&origin,&destin);
YOGESH SINGH KATHAYAT
PAGE | 34

ROLL NO-31

if((origin==0) && (destin==0))

break;
printf("Enter weight for this edge : ");
scanf("%d",&wt);
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
{
adj[origin][destin]=wt;
adj[destin][origin]=wt;
}
}/*End of for*/
if(i<n-1)
{
printf("Spanning tree is not possible\n");
exit(1);
}
}/*End of create_graph()*/
display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
int maketree(struct edge tree[MAX],int *weight)
{
struct node state[MAX];
int i,k,min,count,current,newdist;
int m;
int u1,v1;
*weight=0;
/*Make all nodes temporary*/
for(i=1;i<=n;i++)
{
state[i].predecessor=0;
state[i].dist = infinity;
state[i].status = TEMP;
}
/*Make first node permanent*/
state[1].predecessor=0;
state[1].dist = 0;
state[1].status = PERM;
/*Start from first node*/
current=1;
count=0; /*count represents number of nodes in tree */
YOGESH SINGH KATHAYAT
PAGE | 35

ROLL NO-31

while( all_perm(state) != TRUE ) /*Loop till all the nodes become

PERM*/
{
for(i=1;i<=n;i++)
{
if ( adj[current][i] > 0 && state[i].status == TEMP )
{
if( adj[current][i] < state[i].dist )
{
state[i].predecessor = current;
state[i].dist = adj[current][i];
}
}
}/*Search for temporary node with minimum distance
and make it current node*/
min=infinity;
for(i=1;i<=n;i++)
{
if(state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current=i;
}
}/*End of for*/
state[current].status=PERM;
/*Insert this edge(u1,v1) into the tree */
u1=state[current].predecessor;
v1=current;
count++;
tree[count].u=u1;
tree[count].v=v1;
/*Add wt on this edge to weight of tree
*/
*weight=*weight+adj[u1][v1];
}/*End of while*/
return (count);
}/*End of maketree()*/
int all_perm(struct node state[MAX] )
{
int i;
for(i=1;i<=n;i++)
if( state[i].status == TEMP )
return FALSE;
return TRUE;
}/*End of all_perm()*/

Output:Enter edge 5(0 0 to quit):1

YOGESH SINGH KATHAYAT
PAGE | 36

ROLL NO-31

3
Enter weight for this edge:4
Enter edge 6(0 0 to quit):5
4
Enter weight for this edge:3
Invalid edge!
Enter edge 6(0 0 to quit):4
5
Enter weight for this edge:3
Invalid edge!
Enter edge 6(0 0 to quit):2
1
Enter weight for this edge:3
Adjacency matrix is:
0
3
4
0

3
0
0
4

4
0
0
4

0
4
4
0

Weight of apaning tree is : 11

Edges to be include in apaning tree are:
1->2
1->3
2->4

17. Write a program to implement elementary

graph algorithm: Breadth first search.
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define TRUE 1
YOGESH SINGH KATHAYAT
PAGE | 37

ROLL NO-31

#define FALSE 0
#define MAX 8
struct node
{
int data ;
struct node *next ;
};
int visited[MAX] ;
int q[8] ;
int front, rear ;
void bfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void addqueue ( int ) ;
int deletequeue( ) ;
int isempty( ) ;
void del ( struct node * ) ;
void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;
clrscr( ) ;
v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = NULL ;
v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = v3 = getnode_write
v3 -> next = NULL ;
v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = v3 = getnode_write
v3 -> next = NULL ;
v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = NULL ;
v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = NULL ;
v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = NULL ;
YOGESH SINGH KATHAYAT
PAGE | 38

(3);

(4);
(5);

(6);
(7);

(8);

(8);

(8);
ROLL NO-31

v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = NULL ;
v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
v1 -> next = v2 = getnode_write
v2 -> next = v3 = getnode_write
v3 -> next = v4 = getnode_write
v4 -> next = NULL ;
front = rear = -1 ;
bfs ( 1, arr ) ;
for ( i = 0 ; i < MAX ; i++ )
del ( arr[i] ) ;
getch( ) ;

(8);

(5);
(6);
(7);

}
void bfs ( int v, struct node **p )
{
struct node *u ;
visited[v - 1] = TRUE ;
printf ( "%d\t", v ) ;
addqueue ( v ) ;
while ( isempty( ) == FALSE )
{
v = deletequeue( ) ;
u=*(p+v-1);
while ( u != NULL )
{
if ( visited [ u -> data - 1 ] == FALSE )
{
addqueue ( u -> data ) ;
visited [ u -> data - 1 ] = TRUE ;
printf ( "%d\t", u -> data ) ;
}
u = u -> next ;
}
}
}
struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}
void addqueue ( int vertex )
{
if ( rear == MAX - 1 )
{
printf ( "\nQueue Overflow." ) ;
YOGESH SINGH KATHAYAT
PAGE | 39

ROLL NO-31

exit( ) ;
}
rear++ ;
q[rear] = vertex ;
if ( front == -1 )
front = 0 ;
}
int deletequeue( )
{
int data ;
if ( front == -1 )
{
printf ( "\nQueue Underflow." ) ;
exit( ) ;
}
data = q[front] ;
if ( front == rear )
front = rear = -1 ;
else
front++ ;
return data ;
}
int isempty( )
{
if ( front == -1 )
return TRUE ;
return FALSE ;
}
void del ( struct node *n )
{
struct node *temp ;
while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;}}
Output:- 1 2 3 4 5 6 7 8

18. Write a program to implement elementary

graph algorithm: Depth First Search.
#include <stdio.h>
#include <alloc.h>
#define TRUE 1
#define FALSE 0
#define MAX 8
struct node
{
int data ;
struct node *next ;
};
YOGESH SINGH KATHAYAT
PAGE | 40

ROLL NO-31

int visited[MAX] ;
void dfs ( int, struct node ** ) ;
struct node * getnode_write ( int ) ;
void del ( struct node * ) ;
void main( )
{
struct node *arr[MAX] ;
struct node *v1, *v2, *v3, *v4 ;
int i ;
v1 = getnode_write ( 2 ) ;
arr[0] = v1 ;
v1 -> next = v2 = getnode_write ( 3 ) ;
v2 -> next = NULL ;
v1 = getnode_write ( 1 ) ;
arr[1] = v1 ;
v1 -> next = v2 = getnode_write ( 4 ) ;
v2 -> next = v3 = getnode_write ( 5 ) ;
v3 -> next = NULL ;
v1 = getnode_write ( 1 ) ;
arr[2] = v1 ;
v1 -> next = v2 = getnode_write ( 6 ) ;
v2 -> next = v3 = getnode_write ( 7 ) ;
v3 -> next = NULL ;
v1 = getnode_write ( 2 ) ;
arr[3] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;
v1 = getnode_write ( 2 ) ;
arr[4] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;
v1 = getnode_write ( 3 ) ;
arr[5] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;
v1 = getnode_write ( 3 ) ;
arr[6] = v1 ;
v1 -> next = v2 = getnode_write ( 8 ) ;
v2 -> next = NULL ;
v1 = getnode_write ( 4 ) ;
arr[7] = v1 ;
YOGESH SINGH KATHAYAT
PAGE | 41

ROLL NO-31

v1 -> next = v2 = getnode_write ( 5 ) ;

v2 -> next = v3 = getnode_write ( 6 ) ;
v3 -> next = v4 = getnode_write ( 7 ) ;
v4 -> next = NULL ;
dfs ( 1, arr ) ;
for ( i = 0 ; i < MAX ; i++ )
del ( arr[i] ) ;
getch( ) ;
}
void dfs ( int v, struct node **p )
{
struct node *q ;
visited[v - 1] = TRUE ;
printf ( "%d\t", v ) ;
q=*(p+v-1);
while ( q != NULL )
{
if ( visited[q -> data - 1] == FALSE )
dfs ( q -> data, p ) ;
else
q = q -> next ;
}
}
struct node * getnode_write ( int val )
{
struct node *newnode ;
newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
return newnode ;
}
void del ( struct node *n )
{
struct node *temp ;
while ( n != NULL )
{
temp = n -> next ;
free ( n ) ;
n = temp ;
}
}

Output:YOGESH SINGH KATHAYAT

PAGE | 42

ROLL NO-31

12485637

19. Write a program in C for topological sorting.

#include<stdio.h>
#define MAX 20
int n,adj[MAX][MAX];
int front=-1,rear=-1,queue[MAX];
main()
{
int i,j=0,k;
int topsort[MAX],indeg[MAX];
create_graph();
printf("The adjacency matrix is :\n");
display();
/*Find the indegree of each node*/
for(i=1;i<=n;i++)
{
indeg[i]=indegree(i);
if( indeg[i]==0 )
insert_queue(i);
YOGESH SINGH KATHAYAT
PAGE | 43

ROLL NO-31

}
while(front<=rear) /*Loop till queue is not empty */
{
k=delete_queue();
topsort[j++]=k; /*Add node k to topsort array*/
/*Delete all edges going fron node k */
for(i=1;i<=n;i++)
{
if( adj[k][i]==1 )
{
adj[k][i]=0;
indeg[i]=indeg[i]-1;
if(indeg[i]==0)
insert_queue(i);
}
}/*End of for*/
}/*End of while*/
printf("Nodes after topological sorting are :\n");
for(i=0;i<j;i++)
printf( "%d ",topsort[i] );
printf("\n");
}/*End of main()*/
create_graph()
{
int i,max_edges,origin,destin;
printf("Enter number of vertices : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("Enter edge %d(0 0 to quit): ",i);
scanf("%d %d",&origin,&destin);
if((origin==0) && (destin==0))
break;
if( origin > n || destin > n || origin<=0 || destin<=0)
{
printf("Invalid edge!\n");
i--;
}
else
adj[origin][destin]=1;
}/*End of for*/
}/*End of create_graph()*/
display()
{
int i,j;
YOGESH SINGH KATHAYAT
PAGE | 44

ROLL NO-31

for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%3d",adj[i][j]);
printf("\n");
}
}/*End of display()*/
insert_queue(int node)
{
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1) /*If queue is initially empty */
front=0;
rear=rear+1;
queue[rear] = node ;
}
}/*End of insert_queue()*/
delete_queue()
{
int del_item;
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
return ;
}
else
{
del_item=queue[front];
front=front+1;
return del_item;
}
}/*End of delete_queue() */
int indegree(int node)
{
int i,in_deg=0;
for(i=1;i<=n;i++)
if( adj[i][node] == 1 )
in_deg++;
return in_deg;
}/*End of indegree() */

Output:Enter edge 5(0 0 to quit):3

YOGESH SINGH KATHAYAT
PAGE | 45

ROLL NO-31

2
Enter edge 5(0 0 to quit):2
2
Enter edge 5(0 0 to quit):1
1
Enter edge 5(0 0 to quit):2
3
Enter edge 5(0 0 to quit):4
3
Enter edge 5(0 0 to quit):2
1
Enter edge 5(0 0 to quit):3
2
Enter edge 5(0 0 to quit):1
2
The adjacency matrixis :
1100
1110
0100
0010
Nodes after topological sorting are:

20. Write a program in C to find path matrix by

Warshall's algorithm.
#include<stdio.h>
// Number of vertices in the graph
#define V 4
/* Define Infinite as a large enough value. This value will be
used
for vertices not connected to each other */
#define INF 99999
// A function to print the solution matrix
void printSolution(long dist[][V]);
// Solves the all-pairs shortest path problem using Floyd
Warshall algorithm
void floydWarshell (long graph[][V])
{
/* dist[][] will be the output matrix that will finally have
the shortest
distances between every pair of vertices */
long dist[V][V], i, j, k;
YOGESH SINGH KATHAYAT
PAGE | 46

ROLL NO-31

/* Initialize the solution matrix same as input graph

matrix. Or
we can say the initial values of shortest distances are
based
on shortest paths considering no intermediate vertex. */
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
/* Add all vertices one by one to the set of intermediate
vertices.
---> Before start of a iteration, we have shortest
distances between all
pairs of vertices such that the shortest distances
consider only the
vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of a iteration, vertex no. k is added to
the set of
intermediate vertices and the set becomes {0, 1, 2, .. k}
*/
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(long dist[][V])
{
long j,i;
printf ("Following matrix shows the shortest distances"
" between every pair of vertices \n");
YOGESH SINGH KATHAYAT
PAGE | 47

ROLL NO-31

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

{
for (j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf ("%7d", dist[i][j]);
}
printf("\n");
}
}
// driver program to test above function
int main()
{
/* Let us create the following weighted graph
10
(0)------->(3)
|
/|\
5|
|
|
|1
\|/
|
(1)------->(2)
3
*/
long graph[V][V] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
// Print the solution
floydWarshell(graph);
return 0;
}

Output:
Following matrix shows the shortest distances between every pair of vertices
0
5
8
9
INF
0
3
4
YOGESH SINGH KATHAYAT
PAGE | 48

ROLL NO-31

INF
INF

INF
INF

0
INF

1
0

Time Complexity: O(V^3)

YOGESH SINGH KATHAYAT

PAGE | 49

ROLL NO-31