THE NATIONAL INSTITUTE OF ENGINEERING
MANANDAVADI ROAD, MYSURU-08
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Laboratory Manual
for
ANALYSIS AND DESIGN OF ALGORITHMS LABORATORY
(CS4L01)
ACADEMIC YEAR- 2019-20
Analysis and Design of Algorithms Laboratory CS4L01
Algorithms Laboratory (CS4L01)
Course Outcomes
At the end of this course the student will be able to
1. Implement the basic techniques of analyzing the algorithms using space and time complexity,
asymptotic notations..
2. Implement divide and conquer method and analyze the different algorithms like merge sort,
quick sort etc.
3. Apply the greedy strategy to design different algorithms like 0 /1 knapsack Problem, closest pair
of points etc.
4. Implement the dynamic programming method to solve the different problems like All pair
Shortest Path Problem, Non Crossing subset of Nets etc..
5. Implement the Backtracking method to solve many classic problems like N-Queens Problem,
DFS,BFS etc.
Evaluation Pattern
Evaluation Marks
Continuous Internal Evaluation 25
SET 25
Total 50
Dept of CS&E, NIE Page 2
Analysis and Design of Algorithms Laboratory CS4L01
Sl.No CO TITLE OF PROGRAMS
CO1 Implement Recursive Linear search and determine the time taken to search an
1. element. Repeat the experiment for different values of n.
CO1 Sort a given set of elements using Rank sort and Repeat the experiment for different
2. values of n, the number of elements in the list to be sorted
CO1 Sort a given set of elements using Insertion sort method and Repeat the experiment
3. for different values of n, the number of elements in the list to be sorted
CO1 Sort a given set of elements using Selection sort and hence find the time required to
sort elements. Repeat the experiment for different values of n, the number of
4.
elements in the list to be sorted and plot a graph of the time taken versus n.
CO2 Implement Recursive Binary search determine the time taken to search an element.
5. Repeat the experiment for different values of n.
CO2 Sort a given set of elements using Merge sort method and determine the time taken
6.
to sort the elements. Repeat the experiment for different values of n.
CO2 Sort a given set of elements using Quick sort method. Repeat the experiment for
7.
different values of n.
CO3 Obtain the Topological ordering of vertices in a given digraph.
8.
CO3 From a given vertex in a weighted connected graph, find shortest paths to other
9.
vertices using Dijkstra's algorithm.
CO3 Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's
10. algorithm
CO3 Find Minimum Cost Spanning Tree of a given undirected graph using Prims
11.
algorithm.
12. CO4 Implement All Pair Shortest paths problem using Floyd’s algorithm.
CO4 Implement 0/1 Knapsack problem using dynamic programming.
13.
CO4 Find the Binomial Co-efficient using Dynamic Programming.
14.
CO5 Print all the nodes reachable from a given starting node in a digraph using Breadth
15.
First Search method.
CO5 Check whether a given graph is connected or not using DFS method.
16.
17. CO5 Implement N Queen's problem using Back Tracking
List of Programs
Dept of CS&E, NIE Page 3
Analysis and Design of Algorithms Laboratory CS4L01
1. Implement Linear search and determine the time taken to search an element. Repeat the
experiment for different values of n.
#include <stdio.h>
int main()
{
int array[100], search, c, n;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search) /* If required element is found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
printf(“Time complexity:%d”,c);
if (c == n)
printf("%d isn't present in the array.\n", search);
return 0;
}
Output: Pass-2
Pass-1
Enter number of elements in array Enter number of elements in array
5 5
Enter 5 integer(s) Enter 5 integer(s)
4 4
3 3
2 2
7 7
8 8
Enter a number to search Enter a number to search
4 1
4 is present at location 1 1 isn’t present in the array
Time Complexity=1 Time Complexity=5
Dept of CS&E, NIE Page 4
Analysis and Design of Algorithms Laboratory CS4L01
2. Sort a given set of elements using Rank sort and Repeat the experiment for different values of
n, the number of elements in the list to be sorted
#include<stdio.h>
void Rank(int a[], int n, int r[])
{
int C=0;
for (int i=0;i<n;i++)
r[i]=0; //initialize rank array
for(int i=1;i<n;i++)
{
for (int j=0; j<i; j++)
{ C++;
if(a[j]<=a[i]) r[i]++;
else r[j]++;
}
}
printf(“Time complexity=%d”, C);
}
void Rearrange(int a[], int n, int r[])
{
int u[20];
for (int i=0;i<n;i++)
u[r[i]]=a[i];
for(int i =0;i<n;i++)
a[i]=u[i];
int main( )
{
int a[100], n, i, r[100];
printf(“Enter the value of n\n”);
scanf(“%d”, &n);
printf(“ Enter %d integers\n”,n);
for (i=0; i<n; i++)
scanf(“%d”,&a[i]);
Rank( a, n, r);
Rearrange(a, n, r);
printf(“The array elements after sorting are\n”);
Dept of CS&E, NIE Page 5
Analysis and Design of Algorithms Laboratory CS4L01
for (i=0; i<n; i++)
printf(“%d\n”, a[i]);
return 0;
}
Output:
Pass-1
Enter the value of n
5
Enter 5 integers
45
35
10
25
15
Time complexity = 10
The array elements after sorting are
10
15
25
35
45
Dept of CS&E, NIE Page 6
Analysis and Design of Algorithms Laboratory CS4L01
3. Sort a given set of elements using Insertion sort method and Repeat the experiment for
different values of n, the number of elements in the list to be sorted
#include<stdio.h>
void InsertionSort(int a[],int n) ;
int main()
{
int a[20],i,n;
printf(" Enter number of elements in array : ");
scanf("%d",&n);
// Inputting elements
printf("Enter %d numbers: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
// Displaying Elements before insertion sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
//Applying insertion sort
InsertionSort(a,n);
// Displaying elements after insertion sort
printf("\nElements after insertion sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
void InsertionSort(int a[],int n)
{
Dept of CS&E, NIE Page 7
Analysis and Design of Algorithms Laboratory CS4L01
int i,key,j, C=0;
for(i=1;i<n;i++)
{
key=a[i];
j=i-1;
C++;
// Finding appropriate position to insert key
while((key<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
C++;
}
// Inserting key
a[j+1]=key;
}
printf(“Time Complexity:%d\n”,C);
}
Output: Pass-2
Pass-1
Enter number of elements in array : Enter number of elements in array :
6 6
Enter 6 numbers: Enter 6 numbers:
123456 10 9 7 8 6 5
Items in the array are : Items in the array are :
12345 6 10 9 7 8 5 6
Time Complexity: 6 Time Complexity:
Elements after insertion sort : Elements after insertion sort :
123456 5 6 7 8 9 10
Dept of CS&E, NIE Page 8
Analysis and Design of Algorithms Laboratory CS4L01
4. Sort a given set of elements using Selection sort and hence find the time required to sort
elements. Repeat the experiment for different values of n, the number of elements in the list to be
sorted and plot a graph of the time taken versus n.
#include<stdio.h>
int main()
{
int n, i, j, temp, min;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for (i = 0; i < n - 1; i++)
{
// Finding the minimum element in unsorted array
min = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min])
min = j;
// Swaping the found minimum element with the first element
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
Output:
4 (Number of elements)
33 76 21 2
2 21 33 76
Dept of CS&E, NIE Page 9
Analysis and Design of Algorithms Laboratory CS4L01
5. Implement Recursive Binary search determine the time taken to search an element. Repeat
the experiment for different values of n.
#include <stdio.h>
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if (arr[mid] == x) return mid;
// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present in array
return -1;
}
int main(void)
{
int arr[], n, x,i;
printf (“enter the number of elements\n”);
scanf(“%d”,&n);
printf(“Enter the %d integers in ascending order\n”,n);
for( i=0;i<n;i++)
scanf(“%d”, &arr[i])
printf(“Enter the key\n”);
scanf(“%d”,&key);
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Output:
Pass-1: Pass-2
enter the number of elements enter the number of elements
Dept of CS&E, NIE Page 10
Analysis and Design of Algorithms Laboratory CS4L01
5 5
Enter the %d integers in ascending order Enter the %d integers in ascending order
10 10
20 20
30 30
40 40
50 50
Enter the key Enter the key
40 7
Element is present at index 3 Element is not present in array
6. Sort a given set of elements using Merge sort method and determine the time taken to sort the
elements. Repeat the experiment for different values of n.
#include<stdio.h>
void mergesort(int a[],int i, int j);
void merge(int a[],int p , int q, int r1);
int count=0;
int main()
{
int a[20],i,n,item;
printf("Enter number of elements in array : ");
scanf("%d",&n);
// Inputting elements
for(i=0;i<n;i++)
{
printf("Enter number %d: ",i+1);
scanf("%d",&a[i]);
}
// Displaying Elements before merge sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
//Applying merge sort
mergesort(a,0,n-1);
// Displaying elements after merge sort
printf("\nElements after merge sort : ");
Dept of CS&E, NIE Page 11
Analysis and Design of Algorithms Laboratory CS4L01
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf(“Time complexity : %d\n”,count);
return 0;
}
void mergesort(int a[],int i, int j)
{
int mid;
if(i>=j)
return;
else
{
mid=(i+j)/2;
count++;
mergesort(a,i,mid);
mergesort(a,mid+1,j);
merge(a,i,mid,j);
}
}
void merge(int a[],int p , int q, int r)
{
int n1=q-p+1;
int n2=r-q;
int left[n1+1];
int right[n2+1];
int i=0;
int j=0;
int k=0;
for(i=0;i<n1;i++)
{
left[i]=a[p+i];
}
for(i=0;i<n2;i++)
{
right[i]=a[q+i+1];
}
left[n1]=9999;
right[n2]=9999;
Dept of CS&E, NIE Page 12
Analysis and Design of Algorithms Laboratory CS4L01
i=0;
j=0;
for(k=p;k<=r;k++)
{
if(left[i]<right[j])
{
a[k]=left[i];
i++;
}
else
{
a[k]=right[j];
j++;
}
}
}
Output:
Enter number of elements in array :
5
25
34
15
63
45
Elements after merge sort :
15 25 34 45 63
Time complexity: 4
7. Sort a given set of elements using Quick sort method. Repeat the experiment for different values
of n.
#include<stdio.h>
void quicksort(int a[],int p, int r);
int partition(int a[],int p, int r);
int Count=0;
int main()
{
int a[20],i,n;
printf("Enter number of elements in array : ");
Dept of CS&E, NIE Page 13
Analysis and Design of Algorithms Laboratory CS4L01
scanf("%d",&n);
// Inputting elements
printf("Enter %d number: ",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
// Displaying Elements before quick sort
printf("Items in the array are : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
//Applying quick sort
quicksort(a,0,n-1);
// Displaying elements after quick sort
printf("\nElements after quick sort : ");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf(“Time complexity: Count=%d”, Count);
return 0;
}
void quicksort(int a[],int p, int r)
{
int q;
if(p<r)
{
// q - index at which pivot element lies
Count++;
q=partition(a,p,r);
// Sorting sub-array recursively
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
int partition(int a[],int p, int r)
{
int temp;
int i=p-1;
Dept of CS&E, NIE Page 14
Analysis and Design of Algorithms Laboratory CS4L01
int j;
// pivot element around which partition is done
int x=a[r];
for(j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return (i+1);
}
Output : Output :
Pass-1: Pass-2:
Enter number of elements in array : Enter number of elements in array :
5 6
Enter 5 numbers Enter 5 numbers
12345 30 10 40 60 20 50
Elements after quick sort : Elements after quick sort :
12345 10 20 30 40 50
Time complexity: Count= 15 Time complexity: Count=
8. Obtain the Topological ordering of vertices in a given digraph.
#include <stdio.h>
int main(){
int i, j, k, n, a[10][10], indeg[10], flag[10], count=0;
printf("Enter the no of vertices:\n");
scanf("%d",&n);
printf("Enter the adjacency matrix:\n");
for(i=0;i<n;i++){
printf("Enter row %d\n",i+1);
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
Dept of CS&E, NIE Page 15
Analysis and Design of Algorithms Laboratory CS4L01
}
for(i=0;i<n;i++){
indeg[i]=0;
flag[i]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
indeg[i]=indeg[i]+a[j][i];
printf("\nThe topological order is:");
while(count<n){
for(k=0;k<n;k++){
if((indeg[k]==0) && (flag[k]==0)){
printf("%d ",(k+1));
flag [k]=1;
}
for(i=0;i<n;i++){
if(a[i][k]==1)
indeg[k]--;
}
}
count++;
}
return 0;
}
Output
Enter the no of vertices:
4
Enter the adjacency matrix:
Enter row 1
0110
Enter row 2
0001
Enter row 3
0001
Enter row 4
0000
The topological order is:1 2 3 4
Dept of CS&E, NIE Page 16
Analysis and Design of Algorithms Laboratory CS4L01
9. From a given vertex in a weighted connected graph, find shortest paths to other vertices using
Dijkstra's algorithm.
#include<stdio.h>
main ()
{
int n, cost[15][15], i, j, s[15], v, u, w, dist[15],
num, min;
clrscr();
printf ("Enter the vertices please\n");
scanf ("%d", &n);
printf ("Enter the cost of the edges please\n");
printf ("Enter 999 if the edgeis not present or for the
self loop\n");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
scanf ("%d", &cost[i][j]);
printf ("Enter the Source vertex please\n");
scanf ("%d", &v);
for (i = 1; i <= n; i++)
{
s[i] = 0;
dist[i] = cost[v][i];
}
s[v] = 1;
dist[v] = 0;
for (num = 2; num <= n - 1; num++)
{
min = 999;
for (w = 1; w <= n; w++)
if (s[w] == 0 && dist[w] < min)
{
min = dist[w];
u = w;
}
s[u] = 1;
for (w = 1; w <= n; w++)
{
if (s[w] == 0)
{
if (dist[w] > (dist[u] + cost[u][w]))
dist[w] = (dist[u] + cost[u][w]);
Dept of CS&E, NIE Page 17
Analysis and Design of Algorithms Laboratory CS4L01
}
}
}
printf ("VERTEX\tDESTINATION\tCOST\n");
for (i = 1; i <= n; i++)
printf (" %d\t %d\t\t %d\n", v, i, dist[i]);
getch();
}
OUTPUT
Enter the vertices please
n=5
Enter the cost of the edges please
Enter 999 if the edge is not present or for the self loop
The cost of the edges are :
999 1 2 999 999
1 999 3 4 999
2 3 999 5 6
999 4 5 999 6
999 999 6 6 999
Enter the Source vertex please : 1
VERTEX DESTINATION COST
1 1 0
1 2 1
1 3 2
1 4 5
1 5 8
10. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
clrscr();
printf("\n\tImplementation of Kruskal's algorithm\n");
Dept of CS&E, NIE Page 18
Analysis and Design of Algorithms Laboratory CS4L01
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost 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;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
getch();
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
Dept of CS&E, NIE Page 19
Analysis and Design of Algorithms Laboratory CS4L01
{
parent[j]=i;
return 1;
}
return 0;
}
Output:
Implementation of Kruskal's algorithm
Enter the no. of vertices:
4
Enter the cost adjacency matrix
999 1 5 2
1 999 999 999
5 999 999 3
2 999 3 999
The edges of Minimum Cost Spanning Tree are
1 ---> 2 = 1
1 ---> 4 = 2
3 ---> 4 = 3
Minimum Cost= 6
11. Find Minimum Cost Spanning Tree of a given undirected graph using Prims algorithm.
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
int main()
clrscr();
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
Dept of CS&E, NIE Page 20
Analysis and Design of Algorithms Laboratory CS4L01
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;
Dept of CS&E, NIE Page 21
Analysis and Design of Algorithms Laboratory CS4L01
visited[b]=1;
cost[a][b]=cost[b][a]=999;
printf("\n Minimun cost=%d",mincost);
return 0;
}
Output:
Enter the number of nodes
4
Enter the adjacency matrix
999 1 5 2
1 999 999 999
5 999 999 3
2 999 3 999
Minimum Cost= 6
12. Implement All Pair Shortest paths problem using Floyd’s algorithm.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],a[10][10];
void all_paths(int [10][10],int [10][10],int);
int min1(int,int);
void main()
{
int i,j,n;
clrscr();
printf("\n enter the number of vertices\n");
scanf("%d",&n);
printf("\n enter the adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
Dept of CS&E, NIE Page 22
Analysis and Design of Algorithms Laboratory CS4L01
scanf("%d",&cost[i][j]);
all_paths(cost,a,n);
printf("\n\t the shortest path obtained is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\t %d",a[i][j]);
printf("\n");
}
getch();
}
void all_paths(int cost[10][10],int a[10][10],int n)
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=cost[i][j];
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min1(a[i][j],a[i][k]+a[k][j]);
}
int min1(int a,int b)
{
return(a<b)?a:b;
}
Output:
enter the number of vertices
4
enter the adjacency matrix
999 999 3 999
2 999 999 999
999 7 999 1
6 999 999 999
The shortest path obtained is
10 10 3 4
2 12 5 6
7 7 10 1
6 16 9 10
13. Implement 0/1 Knapsack problem using dynamic programming.
Dept of CS&E, NIE Page 23
Analysis and Design of Algorithms Laboratory CS4L01
#include<stdio.h>
#include<conio.h>
int v[20][20];
int max1(int a,int b)
{
return(a>b)?a:b;
}
void main()
{
int i,j,p[20],w[20],n,max;
clrscr();
printf("\n enter the number of items\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("\n enter the weight and profit of the
item %d:",i);
scanf("%d %d",&w[i],&p[i]);
}
printf("\n enter the capacity of the knapsack");
scanf("%d",&max);
for(i=0;i<=n;i++)
v[i][0]=0;
for(j=0;j<=max;j++)
v[0][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=max;j++)
{
if(w[i]>j)
v[i][j]=v[i-1][j];
else
v[i][j]=max1(v[i-1][j],v[i-1][j-w[i]]+p[i]);
}
printf("\n\nThe table is\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=max;j++)
printf("%d\t",v[i][j]);
printf("\n");
}
printf("\nThe maximum profit is %d",v[n][max]);
printf("\nThe most valuable subset is:{");
j=max;
Dept of CS&E, NIE Page 24
Analysis and Design of Algorithms Laboratory CS4L01
for(i=n;i>=1;i--)
if(v[i][j]!=v[i-1][j])
{
printf("\t item %d:",i);
j=j-w[i];
}
printf("}");
getch();
}
OUTPUT:
enter the number of items
4
enter the weight and profit of the item 1:2 12
enter the weight and profit of the item 2:1 10
enter the weight and profit of the item 3:3 20
enter the weight and profit of the item 4:2 15
enter the capacity of the knapsack5
The table is
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37
The maximum profit is 37
The most valuable subset is:{ item 4: item 2: item 1:}
14. Find the Binomial Co-efficient using Dynamic Programming.
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,k,n,c[50][50];
clrscr();
printf("\n enter the value of n & k\n");
scanf("%d%d",&n,&k);
for(i=0;i<=n;i++)
Dept of CS&E, NIE Page 25
Analysis and Design of Algorithms Laboratory CS4L01
for(j=0;j<=k;j++)
c[i][j]=0;
for(i=0;i<=n;i++)
{
c[i][0]=1;
c[i][i]=1;
}
for(i=2;i<=n;i++)
for(j=1;j<=i-1;j++)
c[i][j]=c[i-1][j-1]+c[i-1][j];
printf("\n The table for valuation is\n");
for(i=0;i<=n;i++)
{
for(j=0;j<=k;j++)
if(c[i][j]!=0)
printf("\t%d",c[i][j]);
printf("\n");
}
printf("\n\t The binomial coefficient of C(%d,%d) is %d\n",n,k,c[n][k]);
getch();
}
OUTPUT:
enter the value of n & k
6 3
The table for valuation is
1
1 1
1 2 1
1 3 3 1
1 4 6 4
1 5 10 10
1 6 15 20
The binomial coefficient of C(6,3) is 20
Dept of CS&E, NIE Page 26
Analysis and Design of Algorithms Laboratory CS4L01
15. Print all the nodes reachable from a given starting node in a digraph using Breadth First
Search method.
#include<stdio.h>
int s[20], source;
void BFS( int A[20][20], int n)
{
int f, r, q[20], u, v, i;
for(i=0; i<n; i++)
s[i]=0;
f = r = 0;
q[20]=source;
s[source]=1;
while( f<=r)
{
u=q[f++];
for(v=1;v<=n;v++)
{
if (A[u][v] ==1 && s[v]==0)
{
s[v]=1;
q[++r]=v;
}
}
}
}
int main( )
{
int n, A[20[20], i, j;
printf(“ Enter the number of nodes\n”);
scanf(“%d”,&n);
printf(“ Enter the Adjacency Matrix\n”);
for(i =0;i<n; i++)
{
for( j=0; j<n; j++)
scanf(“%d”,&A[i][j]);
}
printf(“Enter the source\n”);
scanf(“%d”, &source);
BFS(A,n);
for( i=0;i<n;i++)
Dept of CS&E, NIE Page 27
Analysis and Design of Algorithms Laboratory CS4L01
{
if(s[i]==0)
printf(“ Node %d is not reachable\n”,i);
else
printf(“Node %d is reachable\n”,i);
}
return 0;
}
Output:
Enter the number of nodes:
4
Enter the adjacency matrix
0111
0001
0000
0010
Enter the source
0
Node 0 is reachable
Node 1 is reachable
Node 2 is reachable
Node 3 is reachable
16. Check whether a given graph is connected or not using DFS method.
#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n; //n is no of vertices and graph is sorted in array G[10][10]
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
//read the adjacency matrix
printf("\nEnter adjacency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
//visited is initialized to zero
for(i=0;i<n;i++)
Dept of CS&E, NIE Page 28
Analysis and Design of Algorithms Laboratory CS4L01
visited[i]=0;
DFS(0);
for(i =0; i<n; i++)
{
if(visited[i]==0)
{
printf(“Graph is not connected\n”);
exit(0);
}
}
printf(“ Graph is connected\n”);
return 0;
void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
Output: Pass 2:
Pass 1:
Enter number of vertices: Enter number of vertices:
4 4
enter the adjacency matrix enter the adjacency matrix
0001 1111
0000 1111
0010 1111
0001 1111
Graph is not connected Graph is connected
17. Implement N Queen’s problem using Backtracking.
#include<stdio.h>
int a[30],count=0;
int place(int pos) {
Dept of CS&E, NIE Page 29
Analysis and Design of Algorithms Laboratory CS4L01
int i;
for (i=1;i<pos;i++) {
if((a[i]==a[pos])||((abs(a[i]-a[pos])==abs(i-pos))))
return 0;
}
return 1;
}
void print_sol(int n) {
int i,j;
count++;
printf("\n\nSolution #%d:\n",count);
for (i=1;i<=n;i++) {
for (j=1;j<=n;j++) {
if(a[i]==j)
printf("Q\t"); else
printf("*\t");
}
printf("\n");
}
}
void queen(int n) {
int k=1;
a[k]=0;
while(k!=0) {
a[k]=a[k]+1;
while((a[k]<=n)&&!place(k))
a[k]++;
if(a[k]<=n) {
if(k==n)
print_sol(n); else {
k++;
a[k]=0;
}
} else
k--;
}
}
void main() {
int i,n;
clrscr();
printf("Enter the number of Queens\n");
scanf("%d",&n);
queen(n);
printf("\nTotal solutions=%d",count);
getch();
}
Output:
Dept of CS&E, NIE Page 30
Analysis and Design of Algorithms Laboratory CS4L01
Enter the number of Queens
4
Solution #1:
X QX X
X X X Q
Q X X X
X X Q X
Solution #2:
X X QX
Q X X X
X X XQ
X Q X X
Total solutions=2
Dept of CS&E, NIE Page 31
