PRACTICAL -1
Aim: Implementation and Time analysis of linear and binary search algorithm.
Solution (Linear Search): 
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
int arr[10],i,j;
printf("Enter the numbers in array :");
for(j=0;j<10;j++)
{
scanf("%d",&arr[j]);
}
printf("Enter numbers you want to search in array:");
scanf("%d",&i);
for(j=0;j<10;j++)
{
if(arr[j]==i)
{
  printf("Number is : %d At : %d (postion)",arr[j],j+1);
}
}
return 0;
}

Output (Screenshot-Linear Search): 
 
What is your Analysis of Linear Search?
























Best Case Complexity of Linear Search: 	 ___________________
Average Case Complexity of Linear Search:	 ___________________
Worst Case Complexity of Linear Search:	 ___________________
 
Solution (Binary Search): 
#include <stdio.h>

int binarysearch(int ar[],int x,int left,int right)
{
    int mid=left+right/2;
    if(x==ar[mid])
    {
        return mid;
    }
    if(x<ar[mid])
    {
        return binarysearch(ar,x,left,mid-1);
    }
    else
    {
        return binarysearch(ar,x,mid+1,right);
    }
}

void main()
{
int ar[10],i,j,search;
printf("Enter Element which are sorted\n\n");
printf("Enter the Element in array :");
for(i=0;i<10;i++)
{
scanf("%d",&ar[i]);
}
printf("Entered Elements in array: ");
for(i=0;i<10;i++)
{
printf("%d ",ar[i]);
}
printf("Enter the Element you want to find in array: ");
scanf("%d",&j);
search=binarysearch(ar,j,0,9);
if(search==-1)
{
printf("Invalid call");
}
else
{
       printf("Element founded on position : %d",search+1);
} }
 
Output (Screenshot-Linear Search): 






 
What is your Analysis of Binary Search?
























Best Case Complexity of Binary Search: 	 ___________________
Average Case Complexity of Binary Search:	 ___________________
Worst Case Complexity of Binary Search:	 ___________________

Signature of Faculty: __________						Date: ________
 
PRACTICAL -2
Aim: Implementation and Time analysis of sorting algorithms: Bubble sort, Selection sort, and Quicksort.
Solution (Bubble Sort): 
#include <stdio.h>
void swap(int* xp, int* yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)

		// Last i elements are already in place
		for (j = 0; j < n - i - 1; j++)
			if (arr[j] > arr[j + 1])
				swap(&arr[j], &arr[j + 1]);
}

/* Function to print an array */
void printArray(int arr[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
	int n = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, n);
	printf("Sorted array: \n");
	printArray(arr, n);
	return 0;
}
 
Output (Screenshot-Bubble Sort): 


 
What is your Analysis of Bubble Sort?
























Best Case Complexity of Bubble Sort: 	 ___________________
Average Case Complexity of Bubble Sort:	 ___________________
Worst Case Complexity of Bubble Sort:	 ___________________
 
Solution (Selection Sort): 
#include <stdio.h>
void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

	// One by one move boundary of unsorted subarray
	for (i = 0; i < n-1; i++)
	{
		// Find the minimum element in unsorted array
		min_idx = i;
		for (j = i+1; j < n; j++)
		if (arr[j] < arr[min_idx])
			min_idx = j;

		// Swap the found minimum element with the first element
		swap(&arr[min_idx], &arr[i]);
	}
}

/* Function to print an array */
void printArray(int arr[], int size)
{
	int i;
	for (i=0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

// Driver program to test above functions
int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr)/sizeof(arr[0]);
	selectionSort(arr, n);
	printf("Sorted array: \n");
	printArray(arr, n);
	return 0;
} 
Output (Screenshot-Selection Sort): 


 
What is your Analysis of Selection Sort?
























Best Case Complexity of Selection Sort: 	 ___________________
Average Case Complexity of Selection Sort:	 ___________________
Worst Case Complexity of Selection Sort:	 ___________________
 
Solution (Quick Sort): 
#include<stdio.h>

void quicksort(int number[25],int first,int last){

int i, j, pivot, temp;

if(first<last){

pivot=first;

i=first;

j=last;

while(i<j){

while(number[i]<=number[pivot]&&i<last)

i++;

while(number[j]>number[pivot])

j--;

if(i<j){

temp=number[i];

number[i]=number[j];

number[j]=temp;

}

}

temp=number[pivot];

number[pivot]=number[j];

number[j]=temp;

quicksort(number,first,j-1);

quicksort(number,j+1,last);

}

}

int main(){

int i, count, number[25];

printf("Enter some elements (Max. - 25): ");

scanf("%d",&count);

printf("Enter %d elements: ", count);

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

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

quicksort(number,0,count-1);

printf("The Sorted Order is: ");

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

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

return 0;

}

Output (Screenshot-Quick Sort): 


 
What is your Analysis of Quick Sort?
























Best Case Complexity of Quick Sort: 	 ___________________
Average Case Complexity of Quick Sort:	 ___________________
Worst Case Complexity of Quick Sort:	 ___________________

Signature of Faculty: __________						Date: ________
 
PRACTICAL -3
Aim: Implementation and Time analysis of factorial program using iterative and recursive methods.
Solution (Iterative Method):
#include<stdio.h>
int main()
{
int i,fact=1,number;
printf("Enter a number: ");
scanf("%d",&number);
for(i=1;i<=number;i++)
{
fact=fact*i;
}
printf("Factorial of %d is: %d",number,fact);
return 0;
}

Output (Iterative Method):



 
Solution (Recursive Method):
factorial(int n)
{
if (n == 0)
return 1;
else
return(n * factorial(n-1));
}
void main()
{
int number;
long fact;
printf("Enter a number: ");
scanf("%d", &number);
fact = factorial(number);
printf("Factorial of %d is %ld\n", number, fact);
}

Output (Recursive Method):


 
What is your Analysis of Factorial Using Iterative and Recursive method?









Best Case Complexity (Iterative)	: 	 ___________________
Average Case Complexity (Iterative)	:	 ___________________
Worst Case Complexity (Iterative)	:	 ___________________

Best Case Complexity (Recursive)	: 	 ___________________
Average Case Complexity(Recursive):	 ___________________
Worst Case Complexity (Recursive)	:	 ___________________






















Signature of Faculty: __________						Date: ________
 
PRACTICAL -4
Aim: Implement Prim’s algorithm.
Solution:
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#define V 5
int minKey(int key[], bool mstSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
int printMST(int parent[], int graph[V][V])
{
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V])
{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
printf("Matrix\n");
printf("{ 0, 2, 0, 6, 0 }\n");
printf("{ 2, 0, 3, 8, 5 }\n");
printf("{ 0, 3, 0, 0, 7 }\n");
printf("{ 6, 8, 0, 0, 9 }\n");
printf("{ 0, 5, 7, 9, 0 }\n\n");
primMST(graph);
return 0;
}
Output:








Signature of Faculty: __________						Date: ________
PRACTICAL -5
Aim: Implement Kruskal’s algorithm.
Solution:
#include <stdio.h>
#define MAX 30
typedef struct edge {
  int u, v, w;
} edge;
typedef struct edge_list {
  edge data[MAX];
  int n;
} edge_list;
edge_list elist;
int Graph[MAX][MAX], n;
edge_list spanlist;
void kruskalAlgo();
int find(int belongs[], int vertexno);
void applyUnion(int belongs[], int c1, int c2);
void sort();
void print();
// Applying Krushkal Algo
void kruskalAlgo() {
  int belongs[MAX], i, j, cno1, cno2;
  elist.n = 0;
  for (i = 1; i < n; i++)
    for (j = 0; j < i; j++) {
      if (Graph[i][j] != 0) {
        elist.data[elist.n].u = i;
        elist.data[elist.n].v = j;
        elist.data[elist.n].w = Graph[i][j];
        elist.n++;
      }
    }
  sort();
  for (i = 0; i < n; i++)
    belongs[i] = i;
  spanlist.n = 0;
  for (i = 0; i < elist.n; i++) {
    cno1 = find(belongs, elist.data[i].u);
    cno2 = find(belongs, elist.data[i].v);
    if (cno1 != cno2) {
      spanlist.data[spanlist.n] = elist.data[i];
      spanlist.n = spanlist.n + 1;
      applyUnion(belongs, cno1, cno2);
    }
  }
}
int find(int belongs[], int vertexno) {
  return (belongs[vertexno]);
}
void applyUnion(int belongs[], int c1, int c2) {
  int i;
  for (i = 0; i < n; i++)
    if (belongs[i] == c2)
      belongs[i] = c1;
}
// Sorting algo
void sort() {
  int i, j;
  edge temp;

  for (i = 1; i < elist.n; i++)
    for (j = 0; j < elist.n - 1; j++)
      if (elist.data[j].w > elist.data[j + 1].w) {
        temp = elist.data[j];
        elist.data[j] = elist.data[j + 1];
        elist.data[j + 1] = temp;
      }
}
// Printing the result
void print() {
  int i, cost = 0;
  for (i = 0; i < spanlist.n; i++) {
    printf("\n%d - %d : %d", spanlist.data[i].u, spanlist.data[i].v, spanlist.data[i].w);
    cost = cost + spanlist.data[i].w;
  }
  printf("\nSpanning tree cost: %d", cost);
}
int main() {
  int i, j, total_cost;
  n = 6;
  Graph[0][0] = 0;
  Graph[0][1] = 4;
  Graph[0][2] = 4;
  Graph[0][3] = 0;
  Graph[0][4] = 0;
  Graph[0][5] = 0;
  Graph[0][6] = 0;

  Graph[1][0] = 4;
  Graph[1][1] = 0;
  Graph[1][2] = 2;
  Graph[1][3] = 0;
  Graph[1][4] = 0;
  Graph[1][5] = 0;
  Graph[1][6] = 0;

  Graph[2][0] = 4;
  Graph[2][1] = 2;
  Graph[2][2] = 0;
  Graph[2][3] = 3;
  Graph[2][4] = 4;
  Graph[2][5] = 0;
  Graph[2][6] = 0;

  Graph[3][0] = 0;
  Graph[3][1] = 0;
  Graph[3][2] = 3;
  Graph[3][3] = 0;
  Graph[3][4] = 3;
  Graph[3][5] = 0;
  Graph[3][6] = 0;

  Graph[4][0] = 0;
  Graph[4][1] = 0;
  Graph[4][2] = 4;
  Graph[4][3] = 3;
  Graph[4][4] = 0;
  Graph[4][5] = 0;
  Graph[4][6] = 0;

  Graph[5][0] = 0;
  Graph[5][1] = 0;
  Graph[5][2] = 2;
  Graph[5][3] = 0;
  Graph[5][4] = 3;
  Graph[5][5] = 0;
  Graph[5][6] = 0;
  kruskalAlgo();
  print();
}
Output:
















Signature of Faculty: __________						Date: ________ 
PRACTICAL -6
Aim: Implementation of a knapsack problem using dynamic programming.
Solution: 
#include<stdio.h>  int max(int a, int b)  
{  return (a > b)? a : b;  
}  
int knapSack(int W, int wt[], int val[], int n)  
{  int i, w;  
int K[n+1][W+1];  for (i = 0; i <= n; i++)  
{  
for (w = 0; w <= W; w++)  
{  if (i==0 || w==0)  
K[i][w] = 0;  else if (wt[i-1] <= w)  
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], 
K[i-1][w]);  else  
K[i][w] = K[i-1][w];  }  
}  return K[n][W];  
}  int main()  
{  int i, n, val[20], wt[20], W;  
printf("Enter number of items:");  
scanf("%d", &n);  
printf("Enter value and weight of items:\n");  
for(i = 0;i < n; ++i)  
{  
scanf("%d%d", &val[i], &wt[i]);  
}  
printf("Enter size of knapsack:");  scanf("%d", &W);  
printf("%d", knapSack(W, wt, val, n));  
return 0;  
}
Output: 










Signature of Faculty: __________						Date: ________
PRACTICAL -7
Aim: Implementation of matrix chain multiplication using dynamic programming.
Solution:

 #include<stdio.h>  #include<limits.h>  
int MatrixChainMultiplication(int p[], int n)  
{  int m[n][n];  
int i, j, k, L, q;  for (i=1; i<n; i++)  m[i][i] = 0;  
 
for (L=2; L<n; L++)  
{  for (i=1; i<n-L+1; i++)  
{  j = i+L-1;  m[i][j] = INT_MAX;  for (k=i; k<=j-1; k++)  
{ q = m[i][k] +m[k+1][j] + p[i-1]*p[k]*p[j];  if (q < m[i][j])  
{  m[i][j] = q;  
}  
}  
}  
}  return m[1][n-1]; 
} 
 
int main() 
{ 
 	int n,i;  	 
printf("Enter number of matrices :- \n");  
scanf("%d",&n);  
n++;  int arr[n];  
printf("\nEnter dimensions :- \n");  for(i=0;i<n;i++)  
{  printf("Enter d%d :- ",i);  
scanf("%d",&arr[i]);  
}  
int size = sizeof(arr)/sizeof(arr[0]);  
printf("Minimum number of multiplications is :- %d ", 
MatrixChainMultiplication(arr, size));  return 0;  
} 

Output:





Signature of Faculty: __________						Date: ________
PRACTICAL -8
Aim: Implementation of making a change problem using dynamic programming.
Solution:
#include<stdio.h>
int count( int S[], int m, int n )
{
if (n == 0)
return 1;
if (n < 0)
return 0;
if (m <=0 && n >= 1)
return 0;
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int main()
{
int i, j;
int arr[] = {2, 5, 8};
int m = sizeof(arr)/sizeof(arr[0]);
printf("%d \n", count(arr, m, 10));
return 0;
}

Output:

















Signature of Faculty: __________						Date: ________
PRACTICAL -9
Aim: Implementation of Graph and Searching (DFS and BFS).
Solution (DFS):
 #include <stdio.h>
#include <stdlib.h>
#define MAX 10
int i, visited[MAX];
char vertex[MAX];
int graph[MAX][MAX] = {{0,1,0,1,0},
{1,0,1,0,0},
{0,1,0,0,0},
{1,0,0,0,1},
{0,0,0,1,0}};
void dfs(int currentVertex)
{
printf("%c ",vertex[currentVertex]);
visited[currentVertex] = 1;
for(i=0; i<MAX; i++ )
{
if(visited[i] == 0)
{
//Recursive calling dfs() i.e implementing stack
dfs(i);
}
}
}

int main()
{
vertex[0] = 'A';
vertex[1] = 'B';
vertex[2] = 'C';
vertex[3] = 'D';
vertex[4] = 'E';
dfs(0);
return 0;
}

Output (DFS):




 
Solution (BFS):

#include<stdio.h>
int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
void bfs(int v)
{ for(i = 1; i <= n; i++)
if(a[v][i] && !visited[i])
q[++r] = i; if(f <= r)
{
visited[q[f]] = 1;
bfs(q[f++]);
}
}
void main()
{
int v;
printf("\n Enter the number of vertices:");
scanf("%d", &n);
for(i=1; i <= n; i++)
{
q[i] = 0;
visited[i] = 0;
}
printf("\n Enter graph data in matrix form:\n");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
scanf("%d", &a[i][j]);
}
}
printf("\n Enter the starting vertex:");
scanf("%d", &v); bfs(v);
printf("\n The node which are reachable are:\n");
for(i=1; i <= n; i++)
{
if(visited[i])
printf("%d\t", i);
else
{
printf("\n Bfs is not possible. Not all nodes are reachable");
break;
}
}
}
 
Output (BFS):











































Signature of Faculty: __________						Date: ________
PRACTICAL -10
Aim: Implement LCS problem.
Solution:

#include <stdio.h>
#include <string.h>

int i, j, m, n, LCS_table[20][20];
char S1[20] = "ACADB", S2[20] = "CBDA", b[20][20];

void lcsAlgo() {
m = strlen(S1);
n = strlen(S2);

// Filling 0's in the matrix
for (i = 0; i <= m; i++)
LCS_table[i][0] = 0;
for (i = 0; i <= n; i++)
LCS_table[0][i] = 0;

// Building the mtrix in bottom-up way
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (S1[i - 1] == S2[j - 1]) {
LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1;
} else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1]) {
LCS_table[i][j] = LCS_table[i - 1][j];
} else {
LCS_table[i][j] = LCS_table[i][j - 1];
}
}

int index = LCS_table[m][n];
char lcsAlgo[index + 1];
lcsAlgo[index] = '\0';

int i = m, j = n;
while (i > 0 && j > 0) {
if (S1[i - 1] == S2[j - 1]) {
lcsAlgo[index - 1] = S1[i - 1];
i--;
j--;
index--;
}
else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])
i--;
else
j--;
}
// Printing the sub sequences
printf("S1 : %s \nS2 : %s \n", S1, S2);
printf("LCS: %s", lcsAlgo);
}
int main() {
lcsAlgo();
printf("\n");
}

Output :

































Signature of Faculty: __________						Date: ________