[TOC]

Write a C program of Binary Search

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
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;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 1 Binary.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

Element is present at index 3
C:\Users\Ankit Rauthan \code\daa file>
Write a C Program of Merge short

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)

{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

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

L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)

{
if (l < r) {
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)

{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 2 merge sort.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Quicksort Algorithm

#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("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 1 quick short.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

Enter 3 elements: 5
9
2
Order of Sorted elements: 2 5 9
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Strassen’s Matrix Multiplication

#include<stdio.h>

int main(){

int a[2][2], b[2][2], c[2][2], i, j;

int m1, m2, m3, m4 , m5, m6, m7;

printf("Enter the 4 elements of first matrix: ");

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

for(j = 0;j < 2; j++)

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

printf("Enter the 4 elements of second matrix: ");

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

for(j = 0;j < 2; j++)

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

printf("\nThe first matrix is\n");

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

printf("\n");

for(j = 0; j < 2; j++)

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

printf("\nThe second matrix is\n");

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

printf("\n");
 for(j = 0;j < 2; j++)

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

m1= (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);

m2= (a[1][0] + a[1][1]) * b[0][0];

m3= a[0][0] * (b[0][1] - b[1][1]);

m4= a[1][1] * (b[1][0] - b[0][0]);

m5= (a[0][0] + a[0][1]) * b[1][1];

m6= (a[1][0] - a[0][0]) * (b[0][0]+b[0][1]);

m7= (a[0][1] - a[1][1]) * (b[1][0]+b[1][1]);

c[0][0] = m1 + m4- m5 + m7;

c[0][1] = m3 + m5;

c[1][0] = m2 + m4;

c[1][1] = m1 - m2 + m3 + m6;

printf("\nAfter multiplication using Strassen's algorithm \n");

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

printf("\n");

for(j = 0;j < 2; j++)

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

return 0;

}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 9 station matrix.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

Enter the 4 elements of first matrix: 1
3 9 7
Enter the 4 elements of second matrix: 3 7 2 6

The first matrix is

1 3
9 7
The second matrix is

3 7
2 6
After multiplication using Strassen's algorithm

9 25
41 105
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Kruskal algorithm

#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) {
[Link][elist.n].u = i;
[Link][elist.n].v = j;
[Link][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, [Link][i].u);
cno2 = find(belongs, [Link][i].v);
 if (cno1 != cno2) {
[Link][spanlist.n] = [Link][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 ([Link][j].w > [Link][j + 1].w) {
temp = [Link][j];
[Link][j] = [Link][j + 1];
[Link][j + 1] = temp;
}
}

// Printing the result

void print() {
int i, cost = 0;

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

printf("\n%d - %d : %d", [Link][i].u, [Link][i].v,
[Link][i].w);
cost = cost + [Link][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();
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 8 kruskl.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

2 - 1 : 2
5 - 2 : 2
3 - 2 : 3
4 - 3 : 3
1 - 0 : 4
Spanning tree cost: 14
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of prim's algorithm

#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 } };
primMST(graph);
 return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc p6.c

C:\Users\Ankit Rauthan \code\daa file>[Link]

Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Dijkstra algorithm in c

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>

#define V 9

int minDistance(int dist[], bool sptSet[])

{
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;

return min_index;
}

void printSolution(int dist[])

{
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t\t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[V][V], int src)

{
int dist[V];

bool sptSet[V];

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

dist[i] = INT_MAX, sptSet[i] = false;

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

int u = minDistance(dist, sptSet);

sptSet[u] = true;
 for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v]

&& dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

printSolution(dist);
}

int main()
{
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

dijkstra(graph, 0);

return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 7 Dijkstra.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Floyd warshall algorithm

#include <stdio.h>

#define V 4

#define INF 99999

void printSolution(int dist[][V]);

void floydWarshall(int dist[][V])

{
int i, j, k;

for (k = 0; k < V; k++) {

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

for (j = 0; j < V; j++) {

if (dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

printSolution(dist);
}

void printSolution(int dist[][V])

{
printf(
"The following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}

int main()
{

int graph[V][V] = { { 0, 5, INF, 10 },

{ INF, 0, 3, INF },
 { INF, INF, 0, 1 },
{ INF, INF, INF, 0 } };

floydWarshall(graph);
return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 5 n Q problem.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

The following matrix shows the shortest distances between every pair of vertices
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of n queen problem

#define N 4
#include <stdbool.h>
#include <stdio.h>

void printSolution(int board[N][N])

{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}

bool isSafe(int board[N][N], int row, int col)

{
int i, j;

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

if (board[row][i])
return false;

for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])
return false;

for (i = row, j = col; j >= 0 && i < N; i++, j--)

if (board[i][j])
return false;

return true;
}

bool solveNQUtil(int board[N][N], int col)

{

if (col >= N)
return true;

for (int i = 0; i < N; i++) {

if (isSafe(board, i, col)) {
board[i][col] = 1;

if (solveNQUtil(board, col + 1))

return true;
 board[i][col] = 0; // BACKTRACK
}
}

return false;
}

bool solveNQ()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };

if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}

printSolution(board);
return true;
}

int main()
{
solveNQ();
return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 5 n Q problem.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
C:\Users\Ankit Rauthan \code\daa file>
Write a C program of Sum of Subset

#include <stdio.h>
#include <stdlib.h>

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

static int total_nodes;

// prints subset found

void printSubset(int A[], int size)
{
for(int i = 0; i < size; i++)
{
printf("%*d", 5, A[i]);
}

printf("\n");
}

// qsort compare function

int comparator(const void *pLhs, const void *pRhs)
{
int *lhs = (int *)pLhs;
int *rhs = (int *)pRhs;

return *lhs > *rhs;

}

void subset_sum(int s[], int t[],

int s_size, int t_size,
int sum, int ite,
int const target_sum)
{
total_nodes++;

if( target_sum == sum )

{
// We found sum
printSubset(t, t_size);

// constraint check
if( ite + 1 < s_size && sum - s[ite] + s[ite+1] <= target_sum )
{
// Exclude previous added item and consider next candidate
subset_sum(s, t, s_size, t_size-1, sum - s[ite], ite + 1, target_sum);
}
return;
}
else
 {
// constraint check
if( ite < s_size && sum + s[ite] <= target_sum )
{
// generate nodes along the breadth
for( int i = ite; i < s_size; i++ )
{
t[t_size] = s[i];

if( sum + s[i] <= target_sum )

{
// consider next level node (along depth)
subset_sum(s, t, s_size, t_size + 1, sum + s[i], i + 1,
target_sum);
}
}
}
}
}

// Wrapper that prints subsets that sum to target_sum

void generateSubsets(int s[], int size, int target_sum)
{
int *tuplet_vector = (int *)malloc(size * sizeof(int));

int total = 0;

// sort the set

qsort(s, size, sizeof(int), &comparator);

for( int i = 0; i < size; i++ )

{
total += s[i];
}

if( s[0] <= target_sum && total >= target_sum )

{

subset_sum(s, tuplet_vector, size, 0, 0, 0, target_sum);

free(tuplet_vector);
}

int main()
{
int weights[] = {15, 22, 14, 26, 32, 9, 16, 8};
int target = 53;

int size = ARRAYSIZE(weights);

 generateSubsets(weights, size, target);

printf("Nodes generated %d\n", total_nodes);

return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 4 sum of sub set.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

8 9 14 22
8 14 15 16
15 16 22
Nodes generated 68
C:\Users\Ankit Rauthan \code\daa file>
Write a C program Knapsack greedy algorithm

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int knapSack(int W, int wt[], int val[], int n)

{
if (n == 0 || W == 0)
return 0;

if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

int main()
{
int val[] = { 60, 100, 120 };
int wt[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 3 Knapsack.c"

C:\Users\Ankit Rauthan \code\daa file>[Link]

220
C:\Users\Ankit Rauthan \code\daa file>
Write a Program of Traveling sales person problem

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define V 4

// implementation of traveling Salesman Problem

int travllingSalesmanProblem(int graph[][V], int s)
{
// store all vertex apart from source vertex
vector<int> vertex;
for (int i = 0; i < V; i++)
if (i != s)
vertex.push_back(i);

// store minimum weight Hamiltonian Cycle.

int min_path = INT_MAX;
do {

// store current Path weight(cost)

int current_pathweight = 0;

// compute current path weight

int k = s;
for (int i = 0; i < [Link](); i++) {
current_pathweight += graph[k][vertex[i]];
k = vertex[i];
}
current_pathweight += graph[k][s];

// update minimum
min_path = min(min_path, current_pathweight);

} while (
next_permutation([Link](), [Link]()));

return min_path;
}

// Driver Code
int main()
{
// matrix representation of graph
int graph[][V] = { { 0, 10, 15, 20 },
{ 10, 0, 35, 25 },
{ 15, 35, 0, 30 },
{ 20, 25, 30, 0 } };
int s = 0;
cout << travllingSalesmanProblem(graph, s) << endl;
 return 0;
}
Microsoft Windows [Version 10.0.22000.1219]
(c) Microsoft Corporation. All rights reserved.

C:\Users\Ankit Rauthan \code\daa file>gcc "program 12 Travelling Salesman [Link]" -

lstdc++

C:\Users\Ankit Rauthan \code\daa file>[Link]

80
C:\Users\Ankit Rauthan \code\daa file>