Program No.

- 07
Problem Statement: Implement Stassen’s matrix multiplication.
Description:
Strassen's Matrix Multiplication is a divide and conquer approach to solve the
matrix multiplication problems. In the ordinary matrix multiplication, it used to
take O(n3) T.C. Strassen’s method was introduced to reduce the time complexity
from O(n3) to O(n2.81), which is a significant time reduction.
Algorithm :
FUNCTION StrassenMatrixMultiply(A, B)
IF size(A) == 1 THEN
RETURN A[0][0] * B[0][0] // Base case: single element multiplication
// Divide matrices into

submatrices n = size(A)

/2

A11 = A[0:n, 0:n]

A12 = A[0:n, n:2n]
A21 = A[n:2n, 0:n]
A22 = A[n:2n, n:2n]

B11 = B[0:n, 0:n]

B12 = B[0:n, n:2n]
B21 = B[n:2n, 0:n]
B22 = B[n:2n, n:2n]

// Compute M1 to M7
M1 = StrassenMatrixMultiply(A11 + A22, B11 + B22)
 M2 = StrassenMatrixMultiply(A21 + A22, B11)
M3 = StrassenMatrixMultiply(A11, B12 - B22)
M4 = StrassenMatrixMultiply(A22, B21 - B11)
M5 = StrassenMatrixMultiply(A11 + A12, B22)
M6 = StrassenMatrixMultiply(A21 - A11, B11 + B12)
M7 = StrassenMatrixMultiply(A12 - A22, B21 + B22

// Combine results into submatrices of C

C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6

// Combine submatrices into result matrix C

C = [[C11, C12], [C21, C22]]
RETURN C

Program:
#include <stdio.h> void main() { printf("Name- Shalini Vashishtha \nRoll

no.-2200970100152\nProgram no – 07 \n");

// Define two 2x2 matrices

int a[2][2] = {{2, 2}, {2, 7}};

int b[2][2] = {{1, 2}, {2, 3}};

int c[2][2]; // Resultant

matrix
 // Temporary variables for calculations int s[11];

// Store intermediate values s[0] = b[1][0] - b[0][0];

// s0 s[1] = a[0][0] + a[0][1]; // s1 s[2] = a[1][0] +

a[1][1]; // s2 s[3] = b[1][0] - b[0][0]; // s3 (same as

s0, likely a mistake) s[4] = a[0][0] + a[1][1]; // s4

s[5] = b[0][0] + b[1][1]; // s5 s[6] = a[0][1] - a[1][1];

// s6 s[7] = b[1][0] + b[1][1]; // s7 s[8] = a[0][0] -

a[1][0]; // s8

s[9] = b[0][0] + b[0][1]; // s9

int p[8]; // Store the products M1 to

M7 p[0] = a[0][0] * s[0]; // M1

p[1] = s[1] * b[1][1]; // M2 p[2] =

s[2] * b[0][0]; // M3 p[3] = a[1][1] *

s[3]; // M4 p[4] = s[4] * s[5]; //

M5 p[5] = s[6] * s[7]; // M6 p[6]

= s[8] * s[9]; // M7 // Calculate

the resulting matrix c c[0][0] = p[4] +

p[3] - p[1] + p[5]; // C11 c[0][1] =

p[0] + p[1]; // C12 c[1][0] =

p[2] + p[3]; // C21 c[1][1] =

p[4] + p[0] - p[2] - p[6]; // C22

// Print the resultant matrix

printf("Resultant Matrix:\n");
 for (int i = 0; i < 2; i++) {

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

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

printf("\n");
}

Output :
 Program No. - 08
Problem Statement: Implement Fractional knapsack (Greedy knapsack)
Description:
The greedy approach of the knapsack problem is to calculate the ratio of
profit/weight for each item and sort the item based on this ratio. Then take the
item with the highest ratio and add them as much as we can (can be the whole
element or a fraction of it). This will always give the maximum profit because in
each step, it adds an element such that this is the maximum possible profit for
that much weight. Time Complexity=O(nlogn) dominated by the sorting process.
Algorithm :
Greedy Knapsack(m,n)

//p(1,n) and w(1,n) contain profit & weight respectively of object ordered so that p[i]/w[i]
> p[i+1]/w[i+1]
//m is knapsack size an x(1,n) is solution vector

For i=1 to n do x[i] = 0.0

If(w[i] > u) then break;
X[i] = 1.0
U = u-w[i]

If(i<=n) then x[i] = u/w[i]

}

Program:
#include <stdio.h> int main() {

printf("Name- Shalini Vashishtha\nRoll no.- 2200970100152\nProgram 08

\n");float ratio[3], Totalvalue = 0, temp, capacity;

int n, i, j;
 float weight[3] = {18, 15, 10};
float profit[3] = {25, 24, 15}; n=

sizeof(weight)/sizeof(weight[0]);
capacity = 20;

// Calculate the ratio of profit to weight

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

ratio[i] = profit[i] / weight[i];

// Sort items based on their ratio (greedy step)

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

for (j = i + 1; j < n; j++)
if (ratio[i] < ratio[j]) {
// Swap ratios

temp= ratio[j];

ratio[j] =ratio[i];
ratio[i] =temp;

// Swap weights
temp =weight[j];
weight[j]= weight[i];

weight[i] = temp;

// Swap profitstemp =
profit[j];

profit[j] = profit[i];
profit[i] = temp;
}
 printf("Knapsack problem solution using Greedy approach:\n");

// Greedily select items to maximize profit

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

if (weight[i] > capacity)

break;
else {
Totalvalue += profit[i];
capacity -= weight[i];

}
}

// If there is remaining capacity, take a fraction of the next item

if (i < n)
Totalvalue += (ratio[i] * capacity); printf("\nThe
maximum value(profit) is : %f\n", Totalvalue);
return 0;

Output :
 Program No. - 09
Problem Statement: Implement 0/1 knapsack problem(Dynamic Programming)
Description:
The 0/1 Knapsack Problem is a classic optimization problem where you need to
determine the maximum value that can be carried in a knapsack of a given
capacity, where each item can either be included in the knapsack or excluded
(hence the term 0/1). This problem can be efficiently solved using dynamic
programming.
Algorithm :
FUNCTION Knapsack(weights, values, capacity, n)

// Create a 2D array to store the maximum value for each subproblem

DECLARE dp[n+1][capacity+1]

// Initialize the first row and column FOR i

FROM 0 TO n dp[i][0] = 0 // If capacity is 0,

max value is 0

END FOR

FOR j FROM 0 TO capacity dp[0][j] = 0 // If

there are no items, max value is 0

END FOR

// Fill the dp array

FOR i FROM 1 TO n

FOR j FROM 1 TO capacity

IF weights[i-1] <= j THEN

// Item can be included, take max of including or excluding

dp[i][j] = MAX(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i-1]]) ELSE

// Item cannot be included

dp[i][j] = dp[i-1][j]

END IF

END FOR
END FOR
 RETURN dp[n][capacity] // The maximum value for n items and given capacity

Program:
#include <stdio.h>
// Function to solve the 0/1 Knapsack problem

int knapsack(int weights[], int values[], int capacity, int n) {

// Create a 2D array to store the maximum value for each subproblem

int dp[n + 1][capacity + 1]; //

Initialize the first row and column

for (int i = 0; i <= n; i++) { dp[i][0] = 0; // If
capacity is 0, max value is 0

for (int j = 0; j <= capacity; j++) { dp[0][j] = 0; // If

there are no items, max value is 0
}
// Fill the dp array for (int i = 1;

i <= n; i++) { for (int j = 1; j <=

capacity; j++) { if (weights[i -
1] <= j) {

// Item can be included, take max of including or excluding

dp[i][j] = (dp[i - 1][j] > values[i - 1] + dp[i - 1][j - weights[i - 1]]) ?

dp[i - 1][j] :

values[i - 1] + dp[i - 1][j - weights[i - 1]];

} else {

// Item cannot be included

dp[i][j] = dp[i - 1][j];

}
}
 }
return dp[n][capacity]; // The maximum value for n items and given capacity

int main() { int weights[] = {1, 2, 3}; // Weights of the items

int values[] = {10, 15, 40}; // Values of the items int capacity =
6; // Maximum capacity of the knapsack int n = sizeof(weights)
/ sizeof(weights[0]); // Number of items

int maxValue = knapsack(weights, values, capacity, n); // Call the knapsack function
printf("Shalini Vashishtha \n 2200970100152 Program 9\n"); printf("Maximum value
inBinary Knapsack = %d\n", maxValue); // Print the result

return 0;

Output :
 Program No. - 10
Problem Statement: Find Minimum Cost Spanning Tree using
a.Kruskal`s Algorithm
b.Prims Algorithm

Description:
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph.
The main target of the algorithm is to find the subset of edges by using which we can traverse
every vertex of the graph. It follows the greedy approach that finds an optimum solution at every
stage instead of focusing on a global optimum. O(E log E) is the Time complexity.

Algorithm :
Step 1: Create a forest F in such a way that every vertex of the graph is a separate
tree.
Step 2: Create a set E that contains all the edges of the graph.

Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
Step 4: Remove an edge from E with minimum weight
Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to

the forest F (for combining two trees into one tree).

ELSE
Discard the edge
Step 6: END

Program:
#include <stdio.h> #include <stdlib.h> struct Edge { int src, dest, weight;
};

struct Graph {
int V, E;
struct Edge* edges;

};
struct Subset {
int parent; int
rank;

};
struct Graph* createGraph(int V, int E) { struct Graph* graph =
(struct Graph*)malloc(sizeof(struct Graph)); graph->V = V;
graph->E = E; graph->edges = (struct Edge*)malloc(E *
sizeof(struct Edge)); return graph;
}
int find(struct Subset subsets[], int i) { if

(subsets[i].parent != i) subsets[i].parent =
find(subsets, subsets[i].parent); return
subsets[i].parent;

}
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x); int yroot =
find(subsets, y); if (subsets[xroot].rank <

subsets[yroot].rank) subsets[xroot].parent =
yroot; else if (subsets[xroot].rank >
subsets[yroot].rank) subsets[yroot].parent =
xroot;

else {

subsets[yroot].parent = xroot;
subsets[xroot].rank++;

}
}
int compareEdges(const void* a, const void* b) {
struct Edge* edge1 = (struct Edge*)a; struct
Edge* edge2 = (struct Edge*)b; return edge1-

>weight - edge2->weight;
}

void KruskalMST(struct Graph* graph) {

int V = graph->V;

struct Edge result[V];

int e = 0, i = 0;

qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
for (int v = 0; v < V; v++) {
subsets[v].parent = v; subsets[v].rank
= 0;
}

while (e < V - 1 && i < graph->E) { struct

Edge nextEdge = graph->edges[i++]; int x

= find(subsets, nextEdge.src); int y =

find(subsets, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;

Union(subsets, x, y);

printf("Edges in the Minimum Spanning Tree:\n");

int totalWeight = 0;
 for (i = 0; i < e; i++) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);

totalWeight += result[i].weight;
}

printf("Total weight of the MST: %d\n", totalWeight);

free(subsets);
}

int main() {

printf("Name- Shalini Vashishtha \nRoll no.-

2200970100152");int V = 4, E = 5;

struct Graph* graph = createGraph(V, E); graph->edges[0].src = 0; graph-

>edges[0].dest = 1; graph->edges[0].weight = 2; graph->edges[1].src = 0;
graph->edges[1].dest = 2; graph->edges[1].weight = 9; graph->edges[2].src =
0; graph->edges[2].dest = 3; graph->edges[2].weight = 6; graph->edges[3].src
= 1; graph->edges[3].dest = 3; graph->edges[3].weight = 1; graph-
>edges[4].src = 2; graph->edges[4].dest = 3; graph->edges[4].weight = 3;
KruskalMST(graph); free(graph->edges); free(graph); return 0;

Output :
Prims Algorithm

Description:
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning
tree from a graph. Prim's algorithm finds the subset of edges that includes every
vertex of the graph such that the sum of the weights of the edges can be
minimized. O((V + E) log V) is the time complexity.

Algorithm:
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe vertices
Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has
minimum weight
Step 4: Add the selected edge and the vertex to the minimum spanning tree T
[END OF LOOP]

Step 5: EXIT

Program:
#include <stdio.h>

#include <limits.h>

#define V 5

// Function to find the vertex with the minimum key value

int findMinVertex(int key[], int included[]) { int min =

INT_MAX, minIndex; for (int v = 0; v < V; v++) { if

(!included[v] && key[v] < min) { min = key[v];

minIndex = v;

return minIndex;
}

// Function to implement Prim's Minimum Spanning Tree algorithm

void primMST(int graph[V][V]) { int parent[V]; // Array to store

the constructed MST int key[V]; // Key values used to pick

minimum weight edge int included[V]; // Track vertices included

in MST

// Initialize all keys as infinite and included as false

for (int i = 0; i < V; i++) { key[i] = INT_MAX;

included[i] = 0;

key[0] = 0; // Start with the first vertex

parent[0] = -1; // First node is always the root

// The MST will have V - 1 edges for (int count = 0; count < V - 1;

count++) { int u = findMinVertex(key, included); // Find the

minimum vertex included[u] = 1; // Include it in the MST

// Update key values and parent index of the adjacent vertices

for (int v = 0; v < V; v++) { if (graph[u][v] &&

!included[v] && graph[u][v] < key[v]) { parent[v] = u;

key[v] = graph[u][v];

}
}

// Print the edges of the Minimum Spanning Tree

printf("Edge \tWeight\n");

for (int i = 1; i < V; i++) { printf("%d - %d \t%d\n",

parent[i], i, graph[i][parent[i]]);

}}

int main() { printf("Name- Shalini Vashishtha \nRoll no.-

2200970100152");int graph[V][V] = {

{0, 2, 0, 8, 0},

{2, 0, 4, 8, 5},

{0, 3, 0, 0, 9},

{6, 5, 0, 0, 9},

{0, 5, 7, 9, 0}

};

primMST(graph); // Call the function to find MST

return 0;
}

Output :
 Program No. - 11
Problem Statement: a given vertex in a weighted connected graph, find shortest paths to
other vertices using Dijkstra’s algorithm.

Description: Dijkstra's Algorithm. Dijkstra's Algorithm is a Graph algorithm that finds the
shortest path from a source vertex to all other vertices in the Graph (single source shortest
path). It is a type of Greedy Algorithm that only works on Weighted Graphs having positive
weights. The time complexity of Dijkstra's Algorithm is O(V2) with the help of the adjacency
matrix representation of the graph. This time complexity can be reduced to O((V + E) log V) with
the help of an adjacency list representation of the graph, where V is the number of vertices and
E is the number of edges in the graph.

Algorithm:
Step 1: First, we will mark the source node with a current distance of 0 and set the rest of the

nodes to INFINITY.

Step 2: We will then set the unvisited node with the smallest current distance as the current

node, suppose X.

Step 3: For each neighbor N of the current node X: We will then add the current distance of X

with the weight of the edge joining X-N. If it is smaller than the current distance of N, set it as

the new current distance of N.

Step 4: We will then mark the current node X as visited.

Step 5: We will repeat the process from 'Step 2' if there is any node unvisited left in the graph.

Program:

#include <stdio.h>

#include <limits.h>

#define V 5 // Number of vertices in the graph

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

{ int min = INT_MAX, minIndex;

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

if (!visited[v] && dist[v] < min) {

min = dist[v]; minIndex =

v;}

return minIndex;

void dijkstra(int graph[V][V], int src) { int dist[V];

// Distance from source to each vertex int

visited[V]; // Track visited vertices int

parent[V]; // To store shortest path tree

// Initialize distances as infinite and visited as

false for (int i = 0; i < V; i++) { dist[i] =

INT_MAX; visited[i] = 0; parent[i] = -1; //

Initialize parent of each vertex as -1

}
 dist[src] = 0; // Distance from source to itself is

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

int u = findMinDistance(dist, visited);

visited[u] = 1; for (int v = 0; v < V; v++) { if

(!visited[v] && graph[u][v] && dist[u] != INT_MAX &&

dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] +

graph[u][v]; parent[v] = u;

// Print the results printf("Vertex \t

Distance from Source \t Path\n");

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

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

int temp = i; while (temp != -

1) { printf("%d ", temp);

temp = parent[temp];

printf("\n");

int main() { printf("Name- Shalini Vashishtha\nRoll no.- 2200970100152");

 int graph[V][V] = {

{0, 10, 20, 0, 0},

{10, 0, 0, 50, 10},

{20, 0, 0, 20, 33},

{0, 50, 20, 0, 2},

{0, 10, 33, 2, 0}

};

dijkstra(graph, 0);

return 0;

Output :
 Program No. - 12
Problem Statement: Implement All Pairs Shortest Paths problem using Floyd’s algorithm
Description: The Floyd-Warshall algorithm is a dynamic programming algorithm used to
discover the shortest paths in a weighted graph, which includes negative weight cycles. The
algorithm works with the aid of computing the shortest direction between every pair of vertices
within the graph, the usage of a matrix of intermediate vertices to keep music of the
exceptional-recognized route thus far.

Algorithm:
FloydWarshall(graph)

Input: graph[][] - adjacency matrix of the graph

graph[i][j] = weight of edge from vertex i to j, or INF if no edge

exists n = number of vertices in the graph

Output: dist[][] - matrix containing shortest path distances between all pairs of
vertices

1. Initialize:

Let dist[][] = graph[][]

2. For k from 0 to n-1:

For i from 0 to n-

1: For j from 0

to n-1:

dist[i][j] = min(dist[i][j], dist[i][k] +

dist[k][j]) 3. Return dist[][]

Program:
#include <stdio.h>
#define V 4

#define INF 99999

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

int dist[V][V];

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

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

dist[i][j] = graph[i][j];

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

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

0; j < V; j++) { if (dist[i][k] +

dist[k][j] < dist[i][j]) {

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

printf("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() { printf("Name- Shalini Vashishtha \nRoll no.-

2200970100152");int graph[V][V] = {

{0, 7, INF, 1},

{5, 0, 2, INF},

{5, INF, 3, 1},

{2, INF, INF, 0}

};

floydWarshall(graph);

return 0;

}
Output:
 Program No – 13
Problem Statement: Write program to Implement Travelling Sales problem using Dynamicprogramming.

Description: The traveling salesman problems abide by a salesman and a set of cities. The
salesman has to visit every one of the cities starting from a certain one (e.g., the hometown)
and to return to the same city. The challenge of the problem is that the traveling salesman
needs to minimize the total length of the trip.

Algorithm:
Step 1: Firstly, we will consider City 1 as the starting and ending point. Since the route is cyclic,

any point can be considered a starting point.

Step 2: As the second step, we will generate all the possible permutations of the cities, which are

(n-1)!

Step 3: After that, we will find the cost of each permutation and keep a record of the minimum

cost permutation.

Step 4: At last, we will return the permutation with minimum cost.

Program:

#include<stdio.h>

#include<limits.h>

#define V 4

#define INF INT_MAX

int dp[1 << V][V]; int

dist[V][V]; int tsp(int

mask, int pos) { if

(mask == (1 << V) - 1)

{ return

dist[pos][0];

if (dp[mask][pos] != -1) {

return dp[mask][pos];

int ans = INF; for (int city = 0; city < V; city++) {

if ((mask & (1 << city)) == 0) { int newAns =

dist[pos][city] + tsp(mask | (1 << city), city);

ans = (ans < newAns) ? ans : newAns;

return dp[mask][pos] = ans;

int main() { printf("Name- Shalini Vashishtha \nRoll

no.-2200970100152n");

// Modified graph with different

distances int graph[V][V] = {

{0, 10, 15, 20},

 {10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0}

};

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

{ for (int j = 0; j < V;

j++) { dist[i][j] =

graph[i][j];}}

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

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

V; j++) { dp[i][j] = -1;

}}

int result = tsp(1, 0); printf("The minimum cost of

visiting all cities is: %d\n", result); return 0;

Output :
 Program No. – 14

Problem Statement: Design and implement to find a subset of a given set S = {s1,s2,…,sn} of
n positive integer whose SUM is equal to a given positive integer d.
For example, if S = {1,2,5,6,8} and d = 9 there are two solutions {1,2,6}. Display a suitable
message, if the given problem instance doesn’t have solution.
Description: The set cover problem is to find the smallest sub-collection of S whose union
equals the universe given a set of elements 1, 2,..., n (referred to as the universe) and a
collection S of m sets. For instance, take the universe U = 1, 2, 3, 4, 5 and the group of sets S =
1, 2, 3, 2, 4, 3, and 4. The merger of S is undoubtedly U. The following lesser number of sets,
however, may accommodate all elements: 1, 2, 3, and 4.

Program:
#include <stdio.h> int

findSubset(int S[], int n, int

d) { int dp[n + 1][d + 1];

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

for (int j = 0; j <= d; j++) {

if (j == 0) { dp[i][j]

= 1; } else if (i == 0) {

dp[i][j] = 0;

} else if (S[i - 1] <= j) {

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - S[i - 1]];

} else {

dp[i][j] = dp[i - 1][j];

}
 }

if (dp[n][d] == 0) {

printf("No solution

exists\n"); return 0;

int subset[n], index = 0;

int j = d; for (int i = n; i

> 0 && j > 0; i--) { if

(dp[i][j] != dp[i - 1][j]) {

subset[index++] = S[i - 1];

j -= S[i - 1];

printf("Subset with sum %d:

{", d); for (int i = 0; i <

index; i++) { printf("%d",

subset[i]); if (i < index - 1)

{ printf(", ");

printf("}\n");

return 1;
}

int main() {

printf("Name- Shalini Vashishtha \nRoll no.-

2200970100152");

int S[] = {3, 34, 4, 12, 5,

2}; int d = 9; int n =

sizeof(S) / sizeof(S[0]);

findSubset(S, n, d);

return 0;

Output:
 Program No. – 15
Problem Statement: Design and implement to find all Hamiltonian Cycles in a connected
undirected Graph G of n vertices using backtracking principle.

Description: A Hamiltonian Cycle (or Hamiltonian Circuit) in a graph is a cycle that visits each
vertex exactly once and returns to the starting vertex. This problem involves determining if such
a cycle exists in a given graph.

Program:
#include<stdio.h>

#include<stdlib.h> #define V 5 void

printSolution(int path[]); int isSafe(int v,

int graph[V][V], int path[], int pos) { if

(graph[path[pos-1]][v] == 0) return

0; for (int i = 0; i < pos; i++) if

(path[i] == v) return 0; return 1;

int hamCycleUtil(int graph[V][V], int path[],

int pos) { if (pos == V) { if

(graph[path[pos-1]][path[0]] == 1)

return

1; else

return 0;

}
 for (int v = 1; v < V; v++) { if

(isSafe(v, graph, path, pos)) {

path[pos] = v; if

(hamCycleUtil(graph, path, pos + 1) == 1)

return 1;

path[pos] = -1;

return 0;

int hamCycle(int graph[V][V]) {

int *path = (int *)malloc(V *

sizeof(int)); if (path == NULL) {

printf("Memory allocation

failed\n"); return 0;

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

path[i] = -1; path[0] = 0; if

(hamCycleUtil(graph, path, 1) ==

0) { printf("\nSolution does

not exist"); free(path);

return 0;
 }

printSolution(path

); free(path);

return 1;

void printSolution(int path[]) { printf("Solution

Exists: Following is one Hamiltonian Cycle \n");

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

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

printf(" %d ", path[0]);

printf("\n");

int main() { printf("Name- Shalini Vashishtha \nRoll

no.-2200970100152");

int graph1[V][V] = {{0, 1, 1, 0, 1},

{1, 0, 1, 1, 1},

{1, 1, 0, 1, 0},

{0, 1, 1, 0,

1}, {1, 1, 0,

1, 0},

};
 hamCycle(graph1); int

graph2[V][V] = {{0, 1, 0, 1,

0},

{1, 0, 1, 1, 0},

{0, 1, 0, 0, 1},

{1, 1, 0, 0,

0}, {0, 0, 1,

0, 0},

};

hamCycle(graph2);

return 0;

Output:
 Program No. – 16
Problem Statement: Implement n-Queen Problem.

Description: In N-Queen problem, we are given an NxN chessboard and we have to place
N number of queens on the board in such a way that no two queens attack each other. A queen
will attack another queen if it is placed in horizontal, vertical or diagonal points in its way. The
most popular approach for solving the N Queen puzzle is Backtracking.

Algorithm:
• Place the first queen in the top-left cell of the chessboard.

• After placing a queen in the first cell, mark the position as a part of the solution and then
recursively check if this will lead to a solution.

• Now, if placing the queen doesn’t lead to a solution. Then go to the first step and place queens
in other cells. Repeat until all cells are tried.

• If placing queen returns a lead to solution return TRUE.

• If all queens are placed return TRUE.

• If all rows are tried and no solution is found, return FALSE.

Program:
#include<stdio.h>
#define BOARD_SIZE 6 // Modified board

size void displayChess(int

chBoard[BOARD_SIZE][BOARD_SIZE]) { for

(int row = 0; row < BOARD_SIZE; row++) {

for (int col = 0; col < BOARD_SIZE; col++)

printf("%d ", chBoard[row][col]);

printf("\n");

}
}
int isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
for (int i = 0; i <

crntCol; i++)if

(chBoard[crntRow][i])

return 0; for (int i =

crntRow, j = crntCol; i >=

0 && j >= 0; i--, j--)

if (chBoard[i][j])

return 0; for (int i =

crntRow, j = crntCol; j >=

0 && i < BOARD_SIZE;

i++, j--)

if

(chBoard[i][j])

return 0;

return 1;

}
int solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
if (crntCol >= BOARD_SIZE)

return 1; for (int i = 0; i <

BOARD_SIZE; i++) { if

(isQueenPlaceValid(chBoard, i,

crntCol)) {

chBoard[i][crntCol] = 1; if
(solveProblem(chBoard, crntCol +

1))

return 1;

chBoard[i][crntCol] = 0;

}
}

return

0;

}
int displaySolution() { int

chBoard[BOARD_SIZE][BOARD_

SIZE]; for(int i = 0; i <

BOARD_SIZE; i++) for(int j

= 0; j < BOARD_SIZE; j++)

chBoard[i][j] = 0; if

(solveProblem(chBoard, 0) ==

0) { printf("Solution

does not exist\n"); return

0;

displayChess(chBoard);

return 1;

}
int main() { printf("Name- Shalini Vashishtha \nRoll

no.-2200970100152");

displaySolution();

return 0;

Output :
 Program No. – 17

Problem Statement: Implement Graph Coloring Algorithms

Description: In its simplest form, it is a way of coloring the vertices of a graph such that no
two adjacent vertices are of the same color; this is called vertex coloring.

Algorithm:
Input a graph with V vertices (represented by an adjacency matrix graph[V][V]) and an integer m
for the maximum number of colors. Initialize a color array
color [] of size V, setting all values to 0 (no color). For each vertex v, try assigning
each color from 1 to m. Check if the color is safe (no adjacent vertex has the same color). If the
color is safe, assign it to the vertex and move to the next vertex. If all
vertices are successfully colored, print the solution. If a color can't be assigned to a vertex,
backtrack to the previous vertex and try a different color. If a valid coloring is found, output the
colors; otherwise, print "Solution does not exist."
Program:
#include <stdio.h>

#include <stdlib.h>

#define V 5 // Modified number of vertices void

printSolution(int color[]) { printf("Solution Exists:

Following are the assigned colors\n");

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

printf("Vertex %d -> Color %d\n", i,

color[i]);

}
int isSafe(int v, int graph[V][V], int

color[], int c) { for (int i = 0; i < V; i++)

{ if (graph[v][i] && color[i] == c) {

return 0;

return 1;

int graphColoringUtil(int graph[V][V], int m, int color[], int v) {

if (v == V) {

return 1;

for (int c = 1; c <= m; c++) { if

(isSafe(v, graph, color, c)) { color[v]

= c; if (graphColoringUtil(graph, m,

color, v + 1)) {

return 1;

color[v] = 0;

return 0;

}
int graphColoring(int graph[V][V],

int m) { int* color =

(int*)malloc(V * sizeof(int)); for

(int i = 0; i < V; i++) { color[i] =

0;

if (graphColoringUtil(graph, m, color, 0)

== 0) { printf("Solution does not

exist\n"); free(color);

return 0;

printSolution(colo

r); free(color);

return 1;

int main() { printf("Name- Shalini Vashishtha\nRoll

no.-2200970100152");

int graph[V][V] = {

{0, 1, 1, 0, 0},

{1, 0, 1, 1, 0},

{1, 1, 0, 1, 1},
 {0, 1, 1, 0, 1},

{0, 0, 1, 1, 0}

};

int m = 3; // Number of colors

if (!graphColoring(graph, m)) {

printf("Solution does not

exist.\n");

return 0;

Output: