Bellman Ford:

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

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

void printArray(int *arr, char *name, int n)

{
printf("For %s\n", name);
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}

int main()
{
int n, source, edges, s, d;
printf("Enter number of vertices: ");
scanf("%d", &n);
int dist[n], pred[n], w[n][n];
printf("Enter source vertex: ");
scanf("%d", &source);

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

{
dist[i] = 999;
pred[i] = -1;
}

dist[0] = 0;
pred[0] = 0;

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

{
for(int j = 0; j < n; j++)
{
w[i][j] = 0;
}
}

printf("Enter number of edges: ");

scanf("%d", &edges);

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

{
printf("Enter source edge: ");
scanf("%d", &s);
printf("Enter destination edge: ");
scanf("%d", &d);
printf("Enter weight: ");
scanf("%d", &w[s][d]);
}

for(int i = 0; i < n - 1; i++)

{
for(int j = 0; j < edges; j++)
{
 for(int k = 0; k < edges; k++)
{

if((w[i][j] > 0) && (dist[j] > dist[i] + w[i][j]))

{
dist[j] = dist[i] + w[i][j];
pred[j] = i;
}
}
}
}

int check = 1;

for(int j = 0; j < edges; j++)

{

for(int k = 0; k < edges; k++)

{
if(dist[j] > dist[n-1] + w[n-1][j])
{
printf("Bellman ford has failed.\n");
check = 0;
break;
}
}
if(!check)
break;
}

printArray(dist,"Distance", n);
printArray(pred, "Predecessor", n);

return 0;
}

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

KMP:
-------------------------------------------------------------------------------

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

void prefixTable(int *arr, char *str, int len)

{
int i = 1, j = 0;
arr[0] = 0;

while(i < len)

{
if(str[i] == str[j])
{
arr[i] = j + 1;
i++;
j++;
}
else if(j > 0)
 j = arr[j - 1];
else
{
arr[i] = 0;
i++;
}
}
}

int kmp(char *str1, char *str2, int *prefix2, int a_len, int b_len)
{
int i = 0, j = 0;

while(i < a_len)

{
if(str1[i] == str2[j])
{
if(j == b_len - 1)
return i - j;
else
{
i++;
j++;
}
}
else if(j>0)
j = prefix2[j-1];
else
i++;
}
return -1;
}

void printArray(int *arr, int len)

{
printf("\n");

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

{
printf("%d ", arr[i]);
}
printf("\n");
}

int main()
{
char str1[20], str2[20];

printf("Enter main string: ");

scanf("%s", str1);
printf("Enter the pattern to be compared: ");
scanf("%s", str2);

int a_len = strlen(str1), b_len = strlen(str2);

int prefix1[a_len], prefix2[b_len];

prefixTable(prefix2, str2, b_len);

 printArray(prefix2, b_len);

int ans = kmp(str1, str2, prefix2, a_len, b_len);

if(ans == -1)
printf("No match found\n");
else
printf("There was a match found at index %d\n", ans);

return 0;
}

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

LCS:

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

int main()
{
char str1[20], str2[20];
int a_len, b_len;
printf("Enter string A: ");
scanf("%s", str1);
fflush(stdin);
printf("Enter string B: ");
scanf("%s", str2);

a_len = strlen(str1);
b_len = strlen(str2);

int s[a_len + 1][b_len + 1];

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

{
s[0][i] = 0;
}
for(int i = 0; i <= a_len; i++)
{
s[i][0] = 0;
}

for(int r = 1; r <= a_len; r++)

{
for(int c = 1; c <= b_len; c++)
{
if(str1[r-1] == str2[c-1])
{
s[r][c] = s[r-1][c-1] + 1;
}
else
{
if(s[r-1][c] > s[r][c-1])
s[r][c] = s[r-1][c];
else
s[r][c] = s[r][c-1];
}
}
 }

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

printf("\nThe length of the longest common subsequence is %d\n", s[a_len]

[b_len]);

return 0;
}

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

SUM OF SUBSETS:
-----------------------------------------------------------------------------------
-----

#include<stdio.h>

int numbers, sum;

void bubble_sort(int *arr)

{
int swapped = 1, temp;
for(int i = 0; (i < numbers - 1 && swapped == 1); i++)
{
swapped = 0;
for(int j = 0; j < numbers - 1 - i; j++)
{
if(arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1;
}
}
}
}

int promising(int l, int wsf, int tpl, int w[numbers])

{
if(l == numbers - 1)
return 0;

if((wsf + w[l+1] <= sum) && (wsf + tpl >= sum))

return 1;
else
return 0;
}
void sum_of_subsets(int l, int wsf, int tpl, int sol_vec[numbers], int w[numbers])
{
if(l == numbers)
return;

if(wsf == sum)
{
printf("The solution vector is as follows\n");
for(int i = 0; i < numbers; i++)
{
printf("%d ", sol_vec[i]);
}
printf("\n");
}
else
{
if(promising(l, wsf, tpl, w))
{
sol_vec[l+1] = 1;
sum_of_subsets(l + 1, wsf + w[l+1], tpl - w[l+1], sol_vec, w);
sol_vec[l+1] = 0;
sum_of_subsets(l + 1, wsf, tpl - w[l+1], sol_vec, w);
}
}
}

int main()
{
int sum_array = 0;
printf("Enter the number of numbers: ");
scanf("%d", &numbers);

int numbers_arr[numbers], sol_vec[numbers];

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

{
printf("Enter number %d: ", i + 1);
scanf("%d", &numbers_arr[i]);
sum_array += numbers_arr[i];
}

bubble_sort(numbers_arr);

printf("Enter sum: ");

scanf("%d", &sum);

sum_of_subsets(-1, 0, sum_array, sol_vec, numbers_arr);

return 0;
}

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

GRAPH COLOURING:
----------------------------------------------------------------------------------

#include<stdio.h>

int colors, nodes;

int canColor(int node, int color, int sol_vec[colors], int adj[nodes][nodes])
{
for(int i = 0; i < node; i++)
{
if(adj[node][i] == 1 && sol_vec[i] == color)
{
return 0;
}
}
return 1;
}

void mcolor(int node, int sol_vec[colors], int adj[nodes][nodes])

{
for(int c = 0; c < colors; c++)
{
if(canColor(node, c, sol_vec, adj))
{
sol_vec[node] = c;

if(node == nodes - 1)
{
for(int i = 0; i < nodes; i++)
{
printf("Node %d is coloured with colour no %d\n", i,
sol_vec[i]);
}
printf("\n");
}
else
mcolor(node + 1, sol_vec, adj);
}
}
}

int main()
{
int c, edges, start, end, path;

printf("Enter number of nodes: ");

scanf("%d", &nodes);

int adj[nodes][nodes];
int sol_vec[nodes];

printf("Enter the number of colors: ");

scanf("%d", &colors);

printf("Enter number of edges: ");

scanf("%d", &edges);

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

{
for(int j = 0; j < nodes; j++)
{
adj[i][j] = 0;
}
}
 for(int i = 0; i < edges; i++)
{
printf("Enter start vertex: ");
scanf("%d", &start);

printf("Enter end vertex: ");

scanf("%d", &end);

adj[start][end] = 1;
adj[end][start] = 1;
}

mcolor(0, sol_vec, adj);

return 0;
}

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

N QUEEN:
-------------------------------------------------------------------------------

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

int queens;

int place(int queen, int c, int sol_vec[queens])

{
for(int i = 0; i < queen; i++)
{
if(sol_vec[i] == c || abs(queen - i) == abs(sol_vec[i] - c))
return 0;
}
return 1;
}

void nQueen(int queen,int sol_vec[queens])

{

for(int c = 0; c < queens; c++)

{
if(place(queen, c, sol_vec))
{
sol_vec[queen] = c;

if( queen == (queens - 1))

{
printf("The queens will be placed in the following columns\n");
for(int i = 0; i < queens; i++)
{
printf("Queen No %d is placed in column %d\n", i + 1,
sol_vec[i]);
}
printf("\n");
}
else
nQueen(queen + 1, sol_vec);
 }
}
}

int main()
{
int c;
printf("Enter number of queens: ");
scanf("%d", &queens);

c = queens;

int sol_vec[queens];

nQueen(0, sol_vec);

return 0;
}

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

FLOYD MARSHALL:
----------------------------------------------------------------------------------

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

int nodes;

void print2D(int arr[nodes][nodes])

{

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

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

int main()
{
int edges, start, end, weight;
printf("Enter number of nodes: ");
scanf("%d", &nodes);

int cost[nodes][nodes], dist[nodes][nodes];

printf("Enter number of edges: ");

scanf("%d", &edges);

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

{
for(int j = 0; j < nodes; j++)
{
if(i == j)
 {
cost[i][j] = -1;
dist[i][j] = -1;
continue;
}
cost[i][j] = 0;
dist[i][j] = 0;
}
}

// Weights for only those vertices which have are adjacent to each other
for(int i = 0; i < edges; i++)
{
printf("Enter start vertex: ");
scanf("%d", &start);
printf("Enter ending vertex: ");
scanf("%d", &end);
printf("Enter weight: ");
scanf("%d", &weight);

cost[start][end] = weight;
dist[start][end] = weight;
cost[end][start] = weight;
dist[end][start] = weight;
}

// if not an edge then dist is infinity

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

{
for(int j = 0; j < nodes; j++)
{
if(dist[i][j] == 0)
{
dist[i][j] = 999;
cost[i][j] = 999;
}
}
}

print2D(dist);

for(int k = 0; k < nodes; k++)

{
for(int i = 0; i < nodes; i++)
{
for(int j = 0; j < nodes; j++)
{
if(k == i || k == j || i == j)
continue;

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

dist[i][j] = dist[i][k] + dist[k][j];
}
}
printf("\n\nFor k = %d\n\n", k);
print2D(dist);

}
 return 0;
}

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

PRIMS:
-----------------------------------------------------------------------------------
-

#include<stdio.h>

int V;

int minimum(int dist[], int visited[])

{
int min = 999, index = -1;

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

{
if((dist[i] < min) && (visited[i] == 0))
{
min = dist[i];
index = i;
}
}

return index; // vertec which is at min distance from source

}

void printMST(int pred[], int graph[][V])

{
printf("\nThe Minimum Spanning tree is as follows\n\n");
for(int i = 1; i < V; i++)
{
printf("%d - %d | %d\n", pred[i], i, graph[i][pred[i]]);
}
printf("\n");
}

void prims(int graph[V][V]) {

int pred[V], visited[V], dist[V], source, u;

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

{
dist[i] = 1000;
visited[i] = 0;
}

printf("Enter source vertex: ");

scanf("%d", &source);
pred[source] = -1;
dist[source] = 0;

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

{
u = minimum(dist,visited);
visited[u] = 1;
 for(int i = 0; i < V; i++)
{
if((graph[u][i]) != 0 && (visited[i] == 0) && (graph[u][i] < dist[i]) )
{
pred[i] = u;
dist[i] = graph[u][i];
}

}
}

printMST(pred, graph);
// for(int i = 1; i < V; i++)
// {
// printf("%d - %d | %d\n", pred[i], i, graph[i][pred[i]]);
// }
}

int main()
{
int edges, source, destination, weight;
printf("Enter number of vertices: ");
scanf("%d", &V);
int graph[V][V];
for(int i = 0; i < V; i++)
{
for(int j = 0; j < V; j++)
{
graph[i][j] = 0;
}
}
printf("Enter number of edges: ");
scanf("%d", &edges);
for(int i = 0; i < edges ; i++)
{
printf("Enter source: ");
scanf("%d", &source);
printf("Enter destination: ");
scanf("%d", &destination);
printf("Enter weight: ");
scanf("%d", &weight);

graph[source][destination] = weight;
graph[destination][source] = weight;
}

prims(graph);
return 0;
}

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

DJIKSTRA: (run it on online gdb)

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

#include<stdio.h>
#include<stdlib.h>
int n;

void printArray(int arr[])

{
printf("array is as follows\n");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}

int minimumIndex(int dist[], int visited[])

{
int min = 999, index;
for(int i = 0; i < n; i++)
{
if(dist[i] < min && visited[i] == 0)
{
min = dist[i];
index = i;
}
}

return index;
}

void djikstra(int graph[n][n])

{
int visited[n], dist[n], pred[n], u, source, i;

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

{
visited[i] = 0;
dist[i] = 999;
}

printf("Enter the starting vertex: ");

scanf("%d", &source);

pred[source] = -1;
dist[source] = 0;

for( i = 0; i < n - 1; i++)

{
u = minimumIndex(dist, visited);
visited[u] = 1;
for(int j = 0; j < n; j++)
{
if((graph[u][j] != 0) && (visited[j] == 0) && (dist[u] != 999) &&
(dist[u] + graph[u][j] < dist[j]))
{
dist[j] = dist[u] + graph[u][j];
pred[j] = u;
}
}
}
 printArray(dist);
printArray(pred);
}

int main()
{
int edges, source, destination, weight, i;
printf("Enter number of vertices: ");
scanf("%d", &n);

int graph[n][n];

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

{
for(int j = 0; j < n; j++)
{
graph[i][j] = 0;
}
}

printf("Enter number of edges: ");

scanf("%d", &edges);

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

{
printf("Enter source vertex: ");
scanf("%d", &source);
printf("Enter destination vertex: ");
scanf("%d", &destination);

printf("Enter weight: ");

scanf("%d", &weight);

graph[source][destination] = weight;
graph[destination][source] = weight;

}
djikstra(graph);
return 0;
}

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

0/1 KNAPSACK:
-----------------------------------------------------------------------------------
----

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

int capacity;

int max(int a, int b)

{
if(a > b)
return a;
else
 return b;
}

void print2D(int arr[][capacity+1], int r, int c)

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

int main()
{
int items;
printf("Enter number of items: ");
scanf("%d", &items);

int weight[items + 1];

int profit[items + 1];
printf("Enter capacity: ");
scanf("%d", &capacity);

weight[0] = 0;
profit[0] = 0;

for(int i = 1; i <= items; i++)

{
printf("Enter weight for item %d: ", i);
scanf("%d", &weight[i]);
printf("Enter profit for item %d: ", i);
scanf("%d", &profit[i]);
}

int u[items + 1][capacity + 1];

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

{
u[0][i] = u[i][0] = 0;
}

for(int i = 1; i <= items; i++)

{
for(int w = 1; w <= capacity; w++)
{
if (weight[i] > w)
{
u[i][w] = u[i-1][w];
}
else {
u[i][w] = max((u[i-1][w]), (profit[i] + u[i-1][ w -
weight[i] ] ) );
}
}
}
 print2D(u, items + 1, capacity + 1);

printf("\nThe maximum profit is %d\n", u[items][capacity]);

int i = items;
int w = capacity;

printf("The items in the knapsack are ");

while(i > 0 || w > 0)
{
if(u[i][w] != u[i-1][w])
{
if(i>-1)
printf("%d ", i);
w = w - weight[i];
i = i - 1;
}
else
i = i - 1;
}
return 0;
}

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