1.

Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Kruskal's algorithm
#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge in the graph

struct Edge {
int src, dest, weight;
};

// Structure to represent a subset for union-find

struct Subset {
int parent, rank;
};

// Function prototypes
void addEdge(struct Edge* edges, int src, int dest, int weight);
int find(struct Subset subsets[], int i);
void Union(struct Subset subsets[], int x, int y);
int compareEdges(const void* a, const void* b);
void KruskalMST(struct Edge* edges, int V);

int main() {
int V, E;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &V, &E);

struct Edge* edges = (struct Edge*)malloc(E * sizeof(struct Edge));

printf("Enter the source, destination, and weight of each edge:\n");

for (int i = 0; i < E; ++i) {
int src, dest, weight;
scanf("%d %d %d", &src, &dest, &weight);
addEdge(edges, src, dest, weight);
}

KruskalMST(edges, V);

free(edges);

return 0;
}

// Function to add an edge to the graph

void addEdge(struct Edge* edges, int src, int dest, int weight) {
edges->src = src;
edges->dest = dest;
edges->weight = weight;
edges++;
}

// Utility function to find set of an element i

int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}

// Utility function to perform union of two subsets

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++;
}
}

// Function to find Minimum Spanning Tree using Kruskal's algorithm

void KruskalMST(struct Edge* edges, int V) {
// Step 1: Sort all the edges in non-decreasing order of their weight
qsort(edges, V, sizeof(struct Edge), 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;
}

// Number of edges to be taken is equal to V-1

struct Edge result[V];
int e = 0; // Index variable used for result[]
int i = 0; // Index variable used for sorted edges
while (e < V - 1) {
// Step 2: Pick the smallest edge and increment the index for next iteration
struct Edge next_edge = edges[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);

// If including this edge does not cause cycle, include it in result and increment the index
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}

// Print the Minimum Spanning Tree

printf("Minimum Spanning Tree:\n");
 int minCost = 0;
for (i = 0; i < e; i++) {
printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
minCost += result[i].weight;
}
printf("Total minimum cost: %d\n", minCost);

free(subsets);
}

// Comparison function for sorting edges by weight

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;
}

2. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given connected
undirected graph using Prim's algorithm
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define V 5 // Maximum number of vertices in the graph

// Function to find the vertex with minimum key value

int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;

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

if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
min_index = v;
}
}

return min_index;
}

// Function to print the Minimum Spanning Tree

void printMST(int parent[], int graph[V][V]) {
printf("Edge Weight\n");
for (int i = 1; i < V; i++)
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
}

// Function to find Minimum Cost Spanning Tree using Prim's algorithm

void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge in cut
int mstSet[V]; // To represent set of vertices not yet included in MST
 // Initialize all keys as INFINITE
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}

// Always include first vertex in MST.

key[0] = 0;
parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the set of vertices
// not yet included in MST
int u = minKey(key, mstSet);

// Add the picked vertex to the MST set

mstSet[u] = 1;

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

// of the picked vertex. Consider only those vertices which are
// not yet included in MST
for (int v = 0; v < V; v++) {
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

// Print the constructed MST

printMST(parent, graph);
}

int main() {
/* Let us create the following graph
23
(0)--(1)--(2)
|/\|
6| 8/ \5 |7
|/ \|
(3)-------(4)
9 */

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}};
 // Print the solution
primMST(graph);

return 0;
}

3a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's algorithm.

#include <stdio.h>

#include <limits.h>

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

// Function to print the solution matrix

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

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] == INT_MAX)

printf("INF\t");

else

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

printf("\n");

// Function to solve All-Pairs Shortest Paths problem using Floyd's algorithm

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

int dist[V][V];

// Initialize the solution matrix same as input graph matrix

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

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

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

// Update dist[][] with the shortest path using all vertices as intermediates

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

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

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

// If vertex k is on the shortest path from i to j, then update the value of dist[i][j]

if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {

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

// Print the shortest distances

printSolution(dist);

int main() {

/* Let us create the following weighted graph

10

(0)------->(3)

| /|\

5| |

| |1

\|/ |

(1)------->(2)

3 */

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

{INT_MAX, 0, 3, INT_MAX},
 {INT_MAX, INT_MAX, 0, 1},

{INT_MAX, INT_MAX, INT_MAX, 0}};

// Solve All-Pairs Shortest Paths problem

floydWarshall(graph);

return 0;

3b. Design and implement C Program to find the transitive closure using Warshal's algorithm.

#include <stdio.h>

#include <stdbool.h>

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

// Function to print the transitive closure matrix

void printTransitiveClosure(bool reach[][V]) {

printf("Transitive Closure of the graph:\n");

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

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

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

printf("\n");

// Function to find the transitive closure using Warshall's algorithm

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

// Initialize the transitive closure matrix to the given graph

bool reach[V][V];

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

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

reach[i][j] = graph[i][j];
 }

// Update reach[][] to include all vertices that are reachable through intermediate vertices

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

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

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

// If vertex k is on a path from vertex i to vertex j, then mark reach[i][j] as true

reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

// Print the transitive closure matrix

printTransitiveClosure(reach);

int main() {

/* Let us create the following directed graph

1 4

(0)--->(3)

/|\ /|\

| |

2| |5

| |

\/ \/

(1)--->(2)

*/

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

{0, 1, 1, 0},

{0, 0, 1, 1},

{0, 0, 0, 1}};
 // Find the transitive closure of the given graph

transitiveClosure(graph);

return 0;

4.Design and implement C/C++ Program to find shortest paths from a given vertex in a weighted connected
graph to other vertices using Dijkstra's algorithm

#include <stdio.h>

#include <stdbool.h>

#include <limits.h>

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

// Function to find the vertex with the minimum distance value, from the set of vertices not yet included in
the shortest path tree

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

int min = INT_MAX, min_index;

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

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

min = dist[v];

min_index = v;

return min_index;

// Function to print the constructed distance array

void printSolution(int dist[]) {

printf("Vertex \t Distance from Source\n");

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

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

// Function to implement Dijkstra's algorithm for a given graph represented as an adjacency matrix graph[V]
[V]

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

int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is included in the shortest path tree or shortest distance
from src to i is finalized

// Initialize all distances as INFINITE and sptSet[] as false

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

dist[i] = INT_MAX;

sptSet[i] = false;

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

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

// Pick the minimum distance vertex from the set of vertices not yet processed.

// u is always equal to src in the first iteration.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex

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

// Update dist[v] only if is not in sptSet, there is an edge from u to v, and total weight of path from src
to v through u is smaller than current value of dist[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];

// Print the constructed distance array

printSolution(dist);

int main() {

/* Let us create the following weighted graph

4 8

(0)----->(1)----->(2)

| /|\ |

2| / | \ |7

| / |3 \ |

\/ / \/ \/ \/

(3)<------(4)----->(5)

| 6| /

9| |2 4|

| \/ \/

\------->(6)----->(7)----->(8)

2 1 5

*/

int graph[V][V] = {{0, 4, 0, 2, 0, 0, 0, 0, 0},

{0, 0, 8, 0, 3, 0, 0, 0, 0},

{0, 0, 0, 0, 0, 7, 0, 0, 0},

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

{0, 0, 0, 0, 0, 0, 0, 6, 0},

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

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

{0, 0, 0, 0, 0, 0, 0, 0, 0}};

int src = 0; // Source vertex

dijkstra(graph, src);

return 0;

Design and implement C/C++ Program to obtain the Topological ordering of vertices in a given digraph

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_VERTICES 100

// Structure to represent a graph node

struct GraphNode {

int vertex;

struct GraphNode* next;

};

// Structure to represent a graph

struct Graph {

int numVertices;

struct GraphNode** adjLists;

bool* visited;

};

// Function to create a new graph node

struct GraphNode* createNode(int v) {

struct GraphNode* newNode = (struct GraphNode*)malloc(sizeof(struct GraphNode));

newNode->vertex = v;
 newNode->next = NULL;

return newNode;

// Function to create a graph with given number of vertices

struct Graph* createGraph(int vertices) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->numVertices = vertices;

graph->adjLists = (struct GraphNode**)malloc(vertices * sizeof(struct GraphNode*));

graph->visited = (bool*)malloc(vertices * sizeof(bool));

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

graph->adjLists[i] = NULL;

graph->visited[i] = false;

return graph;

// Function to add an edge to a directed graph

void addEdge(struct Graph* graph, int src, int dest) {

struct GraphNode* newNode = createNode(dest);

newNode->next = graph->adjLists[src];

graph->adjLists[src] = newNode;

// Function to perform Depth First Search (DFS)

void DFS(struct Graph* graph, int vertex, bool visited[], int* stack, int* index) {

visited[vertex] = true;

struct GraphNode* adjNode = graph->adjLists[vertex];

while (adjNode != NULL) {

 int adjVertex = adjNode->vertex;

if (!visited[adjVertex]) {

DFS(graph, adjVertex, visited, stack, index);

adjNode = adjNode->next;

stack[(*index)++] = vertex;

// Function to perform topological sorting using Depth First Search (DFS)

void topologicalSort(struct Graph* graph) {

int stack[MAX_VERTICES];

int index = 0;

bool visited[MAX_VERTICES];

for (int i = 0; i < graph->numVertices; i++) {

visited[i] = false;

for (int i = 0; i < graph->numVertices; i++) {

if (!visited[i]) {

DFS(graph, i, visited, stack, &index);

// Print the topological order

printf("Topological ordering of vertices:\n");

for (int i = index - 1; i >= 0; i--) {

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

printf("\n");
}

int main() {

int vertices, edges;

printf("Enter the number of vertices and edges: ");

scanf("%d %d", &vertices, &edges);

struct Graph* graph = createGraph(vertices);

printf("Enter the edges (source destination):\n");

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

int src, dest;

scanf("%d %d", &src, &dest);

addEdge(graph, src, dest);

topologicalSort(graph);

return 0;

Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic Programming method.

#include <stdio.h>

// Function to find the maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;

// Function to solve the 0/1 Knapsack problem using Dynamic Programming

int knapsack(int W, int wt[], int val[], int n) {

int i, w;
 int K[n + 1][W + 1];

// Build K[][] array in bottom-up manner

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];

// K[n][W] contains the maximum value that can be obtained

return K[n][W];

int main() {

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};

int W = 50;

int n = sizeof(val) / sizeof(val[0]);

printf("Maximum value that can be obtained: %d\n", knapsack(W, wt, val, n));

return 0;

7.Design and implement C/C++ Program to solve discrete Knapsack and continuous Knapsack problems using
greedy approximation method.

#include <stdio.h>

// Item structure for the knapsack problems

typedef struct {

int weight;

int value;

} Item;

// Function to solve the discrete knapsack problem using a greedy approach

int discreteKnapsack(Item items[], int n, int capacity) {

int totalValue = 0;

int remainingCapacity = capacity;

// Sort items by value per unit weight (value/weight ratio)

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

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

double ratio1 = (double)items[j].value / items[j].weight;

double ratio2 = (double)items[j + 1].value / items[j + 1].weight;

if (ratio1 < ratio2) {

// Swap items

Item temp = items[j];

items[j] = items[j + 1];

items[j + 1] = temp;

// Fill the knapsack greedily

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

if (items[i].weight <= remainingCapacity) {

totalValue += items[i].value;

remainingCapacity -= items[i].weight;

} else {

// If item doesn't fit completely, take fraction of it

totalValue += items[i].value * ((double)remainingCapacity / items[i].weight);

 break;

return totalValue;

// Function to solve the continuous knapsack problem using a greedy approach

double continuousKnapsack(Item items[], int n, int capacity) {

double totalValue = 0.0;

// Sort items by value per unit weight (value/weight ratio)

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

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

double ratio1 = (double)items[j].value / items[j].weight;

double ratio2 = (double)items[j + 1].value / items[j + 1].weight;

if (ratio1 < ratio2) {

// Swap items

Item temp = items[j];

items[j] = items[j + 1];

items[j + 1] = temp;

// Fill the knapsack greedily

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

if (items[i].weight <= capacity) {

totalValue += items[i].value;

capacity -= items[i].weight;

} else {

// If item doesn't fit completely, take fraction of it

 totalValue += items[i].value * ((double)capacity / items[i].weight);

break;

return totalValue;

int main() {

// Example usage

Item items[] = {{10, 60}, {20, 100}, {30, 120}};

int n = sizeof(items) / sizeof(items[0]);

int capacity = 50;

printf("Discrete Knapsack Value: %d\n", discreteKnapsack(items, n, capacity));

printf("Continuous Knapsack Value: %.2lf\n", continuousKnapsack(items, n, capacity));

return 0;

8 Design and implement C/C++ Program to find a subset of a given set S = {sl , s2,.....,sn} of n positive integers
whose sum is equal to a given positive integer d.

#include <stdio.h>

#define MAX_SIZE 100

// Function to find subsets with the given sum using backtracking

void findSubsets(int set[], int n, int sum, int subset[], int subsetSize, int index, int targetSum) {

if (sum == targetSum) {

// Print the subset

printf("Subset found: ");

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

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

 }

printf("\n");

return;

if (index == n || sum > targetSum) {

return;

// Include the current element in the subset

subset[subsetSize] = set[index];

findSubsets(set, n, sum + set[index], subset, subsetSize + 1, index + 1, targetSum);

// Exclude the current element from the subset and try next element

findSubsets(set, n, sum, subset, subsetSize, index + 1, targetSum);

// Function to initialize the subset finding process

void subsetSum(int set[], int n, int targetSum) {

int subset[MAX_SIZE];

findSubsets(set, n, 0, subset, 0, 0, targetSum);

int main() {

int set[] = {3, 4, 5, 2};

int n = sizeof(set) / sizeof(set[0]);

int targetSum = 7;

printf("Subsets with sum %d:\n", targetSum);

subsetSum(set, n, targetSum);

return 0;
}

Design and implement C/C++ Program to sort a given set of n integer elements using Selection Sort method
and compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to
sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using
the random number generator.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to perform selection sort

void selectionSort(int arr[], int n) {

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

int min_index = i;

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

if (arr[j] < arr[min_index]) {

min_index = j;

// Swap arr[i] and arr[min_index]

int temp = arr[i];

arr[i] = arr[min_index];

arr[min_index] = temp;

int main() {

// Variables for time measurement

clock_t start, end;

double cpu_time_used;

// File pointer to read elements from file

FILE *file;

// You can also generate random numbers instead of reading from a file

// For example: int arr[] = {5, 2, 7, 1, 9, 3};

// int n = sizeof(arr) / sizeof(arr[0]);

// Open the file containing integer elements

file = fopen("input.txt", "r");

if (file == NULL) {

printf("Error opening file.\n");

return 1;

// Read the number of elements from the file

int n;

fscanf(file, "%d", &n);

// Allocate memory for the array

int *arr = (int *)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed.\n");

return 1;

// Read elements from the file

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

fscanf(file, "%d", &arr[i]);

// Close the file

fclose(file);

// Measure the time taken to sort using selection sort

 start = clock();

selectionSort(arr, n);

end = clock();

cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

// Print the sorted array

printf("Sorted array:\n");

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

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

printf("\n");

// Print the time taken

printf("Time taken for sorting (n=%d): %f seconds\n", n, cpu_time_used);

// Free dynamically allocated memory

free(arr);

return 0;

Design and implement C/C++ Program to sort a given set of n integer elements using Quick Sort method and
compute its time complexity. Run the program for varied values of n> 5000 and record the time taken to sort.
Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the
random number generator.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Function to partition the array for quick sort

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1;
 for (int j = low; j <= high - 1; j++) {

if (arr[j] <= pivot) {

i++;

// Swap arr[i] and arr[j]

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

// Swap arr[i + 1] and arr[high] (or pivot)

int temp = arr[i + 1];

arr[i + 1] = arr[high];

arr[high] = temp;

return (i + 1);

// Function to perform quick sort

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

int main() {

// Variables for time measurement

clock_t start, end;

double cpu_time_used;
// File pointer to read elements from file

FILE *file;

// You can also generate random numbers instead of reading from a file

// For example: int arr[] = {5, 2, 7, 1, 9, 3};

// int n = sizeof(arr) / sizeof(arr[0]);

// Open the file containing integer elements

file = fopen("input.txt", "r");

if (file == NULL) {

printf("Error opening file.\n");

return 1;

// Read the number of elements from the file

int n;

fscanf(file, "%d", &n);

// Allocate memory for the array

int *arr = (int *)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed.\n");

return 1;

// Read elements from the file

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

fscanf(file, "%d", &arr[i]);

// Close the file

fclose(file);
 // Measure the time taken to sort using quick sort

start = clock();

quickSort(arr, 0, n - 1);

end = clock();

cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

// Print the sorted array

printf("Sorted array:\n");

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

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

printf("\n");

// Print the time taken

printf("Time taken for sorting (n=%d): %f seconds\n", n, cpu_time_used);

// Free dynamically allocated memory

free(arr);

return 0;

Design and implement C/C++ Program to sort a given set of n integer elements using Merge Sort method and
compute its time complexity. Run the program for varied values of n> 5000, and record the time taken to
sort. Plot a graph of the time taken versus n. The elements can be read from a file or can be generated using
the random number generator.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

// Merge two subarrays of arr[]

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

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

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

// Create temporary arrays

int L[n1], R[n2];

// Copy data to temporary arrays L[] and R[]

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

L[i] = arr[l + i];

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

R[j] = arr[m + 1 + j];

// Merge the temporary arrays back into arr[l..r]

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++;

// Copy the remaining elements of L[], if any

while (i < n1) {

 arr[k] = L[i];

i++;

k++;

// Copy the remaining elements of R[], if any

while (j < n2) {

arr[k] = R[j];

j++;

k++;

// l is for left index and r is right index of the sub-array of arr to be sorted

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

if (l < r) {

// Same as (l+r)/2, but avoids overflow for large l and r

int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

// Merge the sorted halves

merge(arr, l, m, r);

int main() {

// Variables for time measurement

clock_t start, end;

double cpu_time_used;
// File pointer to read elements from file

FILE *file;

// You can also generate random numbers instead of reading from a file

// For example: int arr[] = {5, 2, 7, 1, 9, 3};

// int n = sizeof(arr) / sizeof(arr[0]);

// Open the file containing integer elements

file = fopen("input.txt", "r");

if (file == NULL) {

printf("Error opening file.\n");

return 1;

// Read the number of elements from the file

int n;

fscanf(file, "%d", &n);

// Allocate memory for the array

int *arr = (int *)malloc(n * sizeof(int));

if (arr == NULL) {

printf("Memory allocation failed.\n");

return 1;

// Read elements from the file

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

fscanf(file, "%d", &arr[i]);

// Close the file

fclose(file);
 // Measure the time taken to sort using merge sort

start = clock();

mergeSort(arr, 0, n - 1);

end = clock();

cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

// Print the sorted array

printf("Sorted array:\n");

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

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

printf("\n");

// Print the time taken

printf("Time taken for sorting (n=%d): %f seconds\n", n, cpu_time_used);

// Free dynamically allocated memory

free(arr);

return 0;

Design and implement C/C++ Program for N Queen's problem using Backtracking

#include <stdio.h>

#include <stdbool.h>

#define N 8 // Change this value for different board sizes

// Function to print the solution

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");

// Function to check if it's safe to place a queen at board[row][col]

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

int i, j;

// Check this row on left side

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

if (board[row][i])

return false;

// Check upper diagonal on left side

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

if (board[i][j])

return false;

// Check lower diagonal on left side

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

if (board[i][j])

return false;

return true;

}
// Recursive function to solve N Queen problem

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

// If all queens are placed, return true

if (col >= N)

return true;

// Consider this column and try placing this queen in all rows one by one

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

// Check if the queen can be placed on board[i][col]

if (isSafe(board, i, col)) {

// Place the queen in board[i][col]

board[i][col] = 1;

// Recur to place the rest of the queens

if (solveNQUtil(board, col + 1))

return true;

// If placing queen in board[i][col] doesn't lead to a solution, backtrack

board[i][col] = 0;

// If the queen can't be placed in any row in this column, return false

return false;

// Wrapper function to solve N Queen problem

void solveNQ() {

int board[N][N] = { {0, 0, 0, 0, 0, 0, 0, 0},

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

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

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

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

{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;

printSolution(board);

int main() {

solveNQ();

return 0;