Analysis & Design of Algorithms Lab (BCSL404)

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>
#define MAX 10
#define INF 999 // Represents no connection or very high cost

int cost[MAX][MAX]; // Graph as cost adjacency matrix

int n; // Number of vertices

// Function to find the root of a vertex

int find(int parent[], int vertex) {
while (parent[vertex] != -1)
vertex = parent[vertex];
return vertex;
}

// Function to apply Kruskal's Algorithm

void kruskal() {
int parent[MAX]; // Used to track sets (for cycle detection)
int totalCost = 0; // Total cost of MST
int edgeCount = 0; // Number of edges in MST

// Initially, no vertices are connected

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

printf("\nEdges selected for the Minimum Spanning Tree:\n");

// Loop until we include (n - 1) edges in the MST

while (edgeCount < n - 1) {
int min = INF;
int u = -1, v = -1;

// Find the edge with the minimum cost

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cost[i][j] < min) {
min = cost[i][j];
u = i;
v = j;
}
}
}

Page 1
 Analysis & Design of Algorithms Lab (BCSL404)

// Find roots (to detect cycle)

int rootU = find(parent, u);
int rootV = find(parent, v);

// If they belong to different sets, include the edge

if (rootU != rootV) {
printf("Edge %d: (%d - %d) Cost = %d\n", edgeCount + 1, u, v, min);
parent[rootV] = rootU; // Union the sets
totalCost += min;
edgeCount++;
}

// Mark this edge as used

cost[u][v] = cost[v][u] = INF;
}

printf("\nTotal Cost of Minimum Spanning Tree = %d\n", totalCost);

}

// Main function
int main() {
printf("Enter the number of vertices: ");
scanf("%d", &n);

printf("Enter the cost adjacency matrix:\n");

printf("(Enter %d if no edge exists between two vertices)\n", INF);

// Read the cost matrix

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}

// Call the function to compute MST

kruskal();

return 0;
}

OUTPUT:

Enter the number of vertices: 4

Enter the cost adjacency matrix:
Page 2
 Analysis & Design of Algorithms Lab (BCSL404)

(Enter 999 if no edge exists between two vertices)

999
10
6
5
10
999
999
15
6
999
999
4
5
15
4
999

Edges selected for the Minimum Spanning Tree:

Edge 1: (2 - 3) Cost = 4
Edge 2: (0 - 3) Cost = 5
Edge 3: (0 - 1) Cost = 10

Total Cost of Minimum Spanning Tree = 19

Page 3
 Analysis & Design of Algorithms Lab (BCSL404)

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>

#define MAX 10 // Maximum number of vertices

#define INF 9999 // A large value to represent infinity (no connection)

int cost[MAX][MAX]; // Adjacency matrix to store the graph

int n; // Number of vertices

// Function to implement Prim's Algorithm

void prim() {
int selected[MAX] = {0}; // Array to mark selected (visited) vertices
int edgeCount = 0; // Number of edges in MST
int minCost = 0; // Total cost of MST

selected[0] = 1; // Start from the first vertex (vertex 0)

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

// Repeat until we include (n - 1) edges in the MST

while (edgeCount < n - 1) {
int min = INF;
int u = -1, v = -1;

// Search for the smallest edge connecting selected and unselected vertices
for (int i = 0; i < n; i++) {
if (selected[i]) { // If vertex 'i' is already selected
for (int j = 0; j < n; j++) {
// Find the edge with the smallest cost
if (!selected[j] && cost[i][j] < min) {
min = cost[i][j];
u = i;
v = j;
}
}
}
}

// If a valid edge is found, include it in the MST

if (u != -1 && v != -1) {
printf("Edge %d: (%d - %d) cost = %d\n", edgeCount + 1, u, v, min);
selected[v] = 1; // Mark the new vertex as selected
minCost += min; // Add the edge cost to the total cost
edgeCount++; // Increment edge count
Page 4
 Analysis & Design of Algorithms Lab (BCSL404)

// Mark this edge as used by setting its cost to INF

cost[u][v] = cost[v][u] = INF;
}

// Display total cost of MST

printf("\nTotal cost of Minimum Spanning Tree = %d\n", minCost);
}

// Main function to read input and call Prim's algorithm

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

printf("Enter the cost adjacency matrix:\n");

printf("(Use %d to represent no direct connection between vertices)\n", INF);

// Read the cost adjacency matrix

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}

// Call the Prim's algorithm function

prim();

return 0;
}

OUTPUT:

Enter the number of vertices: 6

Enter the cost adjacency matrix:
(Use 9999 to represent no direct connection between vertices)
0
60
10
9999
9999
9999
60
Page 5
 Analysis & Design of Algorithms Lab (BCSL404)

0
9999
20
40
70
10
9999
9
0
9999
9999
50
9999
20
9999
0
9999
80
9999
40
9999
9999
0
30
9999
70
50
80
30
0

Edges in the Minimum Spanning Tree:

Edge 1: (0 - 2) cost = 10
Edge 2: (2 - 5) cost = 50
Edge 3: (5 - 4) cost = 30
Edge 4: (4 - 1) cost = 40
Edge 5: (1 - 3) cost = 20

Total cost of Minimum Spanning Tree = 150

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

#include <stdio.h>
Page 6
 Analysis & Design of Algorithms Lab (BCSL404)

#define INF 99999 // A large value representing infinity

// Function to find the minimum of two numbers

int min(int a, int b) {
return (a < b ? a : b);
}

// Function to implement Floyd's Algorithm

void floydWarshall(int dist[][10], int n) {
// Applying Floyd's algorithm
for (int k = 0; k < n; k++) { // k is the intermediate vertex
for (int i = 0; i < n; i++) { // i is the source vertex
for (int j = 0; j < n; j++) {// j is the destination vertex
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}

// Main function
int main() {
int n, cost[10][10];

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

scanf("%d", &n);

printf("Enter the cost adjacency matrix (Use %d for INF):\n", INF);

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &cost[i][j]);
}
}

// Run Floyd-Warshall algorithm

floydWarshall(cost, n);

// Output the result

printf("\nAll Pairs Shortest Path Matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (cost[i][j] == INF)
printf("INF ");
else
printf("%3d ", cost[i][j]);
Page 7
 Analysis & Design of Algorithms Lab (BCSL404)

}
printf("\n");
}

return 0;
}

OUTPUT:

Enter the number of vertices: 4

Enter the cost adjacency matrix (Use 99999 for INF):
0
99999
3
99999
2
0
99999
99999
99999
7
0
1
6
99999
99999
0

All Pairs Shortest Path Matrix:

0 10 3 4
2 0 5 6
7 7 0 1
6 16 9 0

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

#include <stdio.h>

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

Page 8
 Analysis & Design of Algorithms Lab (BCSL404)

void warshall(int A[][10], int n) {

for (int k = 0; k < n; k++) { // Intermediate vertex
for (int i = 0; i < n; i++) { // Source vertex
for (int j = 0; j < n; j++) {// Destination vertex
A[i][j] = A[i][j] || (A[i][k] && A[k][j]);
}
}
}
}

int main() {
int n, adj[10][10];

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

scanf("%d", &n);

printf("Enter the adjacency matrix (0 or 1):\n");

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
}
}

// Apply Warshall's algorithm

warshall(adj, n);

// Display the transitive closure

printf("\nTransitive Closure of the given graph is:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", adj[i][j]);
}
printf("\n");
}

return 0;
}

OUTPUT:
Enter the number of vertices: 4
Enter the adjacency matrix (0 or 1):
0
1
0
0
0
Page 9
 Analysis & Design of Algorithms Lab (BCSL404)

0
0
1
0
0
0
0
1
0
1
0

Transitive Closure of the given graph is:

1111
1111
0000
1111

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>

#define INF 999 // Represents infinity or no direct path

#define MAX 10 // Maximum number of vertices

Page 10
 Analysis & Design of Algorithms Lab (BCSL404)

// Function to implement Dijkstra’s Algorithm

void dijkstra(int cost[MAX][MAX], int n, int source, int distance[MAX]) {
int visited[MAX]; // To mark visited vertices
int i, j, u, min;

// Step 1: Initialize distances and visited flags

for (i = 1; i <= n; i++) {
distance[i] = cost[source][i]; // Initial distance from source
visited[i] = 0; // No vertex is visited yet
}

visited[source] = 1; // Mark source as visited

// Step 2: Loop to find shortest paths for all vertices

for (i = 1; i < n; i++) {
min = INF;
u = -1;

// Step 3: Find the unvisited vertex with the smallest distance

for (j = 1; j <= n; j++) {
if (!visited[j] && distance[j] < min) {
min = distance[j];
u = j;
}
}

visited[u] = 1; // Mark this vertex as visited

// Step 4: Update distances of neighboring unvisited vertices

for (j = 1; j <= n; j++) {
if (!visited[j] && distance[u] + cost[u][j] < distance[j]) {
distance[j] = distance[u] + cost[u][j];
}
}
}
}

// Main function to input data and display output

int main() {
int cost[MAX][MAX], distance[MAX];
int n, source, i, j;

// Input: Number of vertices

printf("Enter the number of vertices: ");
scanf("%d", &n);

Page 11
 Analysis & Design of Algorithms Lab (BCSL404)

// Input: Cost adjacency matrix

printf("Enter the cost adjacency matrix (use %d for no edge):\n", INF);
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
}
}

// Input: Source vertex

printf("Enter the source vertex (1 to %d): ", n);
scanf("%d", &source);

// Run Dijkstra’s algorithm

dijkstra(cost, n, source, distance);

// Output: Shortest distances from source to all other vertices

printf("\nShortest distances from vertex %d:\n", source);
for (i = 1; i <= n; i++) {
printf("To vertex %d = %d\n", i, distance[i]);
}

return 0;
}

OUTPUT:
Enter the number of vertices: 6
Enter the cost adjacency matrix (use 999 for no edge):
0
15
10
999
45
999
999
0
15
999
20
999
20
999
0
20
999
999
999
Page 12
 Analysis & Design of Algorithms Lab (BCSL404)

10
999
0
35
999
999
999
999
30
0
999
999
999
999
4
999
0
Enter the source vertex (1 to 6): 5

Shortest distances from vertex 5:

To vertex 1 = 75
To vertex 2 = 40
To vertex 3 = 55
To vertex 4 = 30
To vertex 5 = 0
To vertex 6 = 999

5. Design and implement C/C++ Program to obtain the Topological ordering of

vertices in a given digraph.

#include <stdio.h>

int cost[10][10], n, in_degree[10];

void calculate_in_degree() {
for (int j = 0; j < n; j++) {
in_degree[j] = 0;
for (int i = 0; i < n; i++) {
in_degree[j] += cost[i][j]; //in_degree[j] = in_degree[j] + cost[i][j]
Page 13
 Analysis & Design of Algorithms Lab (BCSL404)

}
}
}

void source_removal() {
int select[10] = {0};
printf("Topological ordering is: ");

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

calculate_in_degree();

int found = 0;
for (int j = 0; j < n; j++) {
if (select[j] == 0 && in_degree[j] == 0) {
printf("%d ", j);
select[j] = 1;

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

cost[j][k] = 0;
}

found = 1;
break;
}
}

if (!found) {
printf("\nCycle detected! Topological sorting not possible.\n");
return;
}
}
}

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

printf("Enter adjacency matrix:\n");

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &cost[i][j]);

source_removal();
return 0;
}

Page 14
 Analysis & Design of Algorithms Lab (BCSL404)

OUTPUT:

Enter number of vertices: 6

Enter adjacency matrix:
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
Topological ordering is: 0 1 2 3 4 5

Page 15
 Analysis & Design of Algorithms Lab (BCSL404)

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

#include <stdio.h>

int n, m; // n = number of items, m = capacity of knapsack

int w[100], p[100]; // weight and profit arrays

int max(int a, int b) {

return (a > b) ? a : b;
}

void knapsack_DP() {
int V[100][100]; // DP table
int i, j;
Page 16
 Analysis & Design of Algorithms Lab (BCSL404)

// Build the DP table

for(i = 0; i <= n; i++) {
for(j = 0; j <= m; j++) {
if(i == 0 || j == 0)
V[i][j] = 0;
else if(w[i - 1] <= j)
V[i][j] = max(V[i - 1][j], p[i - 1] + V[i - 1][j - w[i - 1]]);
else
V[i][j] = V[i - 1][j];
}
}

// Display the DP table

printf("\nKnapsack DP Table:\n");
for(i = 0; i <= n; i++) {
for(j = 0; j <= m; j++) {
printf("%3d ", V[i][j]);
}
printf("\n");
}

// Print maximum profit

printf("\nMaximum Profit: %d\n", V[n][m]);

// Traceback to find items included

printf("\nItems included:\n");
i = n; j = m;
while(i > 0 && j > 0) {
if(V[i][j] != V[i - 1][j]) {
printf("Item %d (Weight = %d, Profit = %d)\n", i, w[i - 1], p[i - 1]);
j -= w[i - 1];
}
i--;
}
}

int main() {
int i;

printf("Enter number of items: ");

scanf("%d", &n);

printf("Enter weights of items:\n");

for(i = 0; i < n; i++)
scanf("%d", &w[i]);
Page 17
 Analysis & Design of Algorithms Lab (BCSL404)

printf("Enter profits of items:\n");

for(i = 0; i < n; i++)
scanf("%d", &p[i]);

printf("Enter capacity of knapsack: ");

scanf("%d", &m);

knapsack_DP();

return 0;
}

OUTPUT:

enter number of items: 4

Enter weights of items:
2
1
3
2
Enter profits of items:
12
10
20
15
Enter capacity of knapsack: 5

Knapsack DP Table:
0 0 0 0 0 0
0 0 12 12 12 12
0 10 12 22 22 22
0 10 12 22 30 32
0 10 15 25 30 37

Maximum Profit: 37

Items included:
Item 4 (Weight = 2, Profit = 15)
Item 2 (Weight = 1, Profit = 10)
Item 1 (Weight = 2, Profit = 12)

Page 18
 Analysis & Design of Algorithms Lab (BCSL404)

7. Design and implement C/C++ Program to solve discrete Knapsack and

continuous
Knapsack problems using greedy approximation methods.

#include <stdio.h>

#define MAX 50

int profit[MAX], weight[MAX], n, capacity;

float ratio[MAX], fraction[MAX];

// Function for Continuous (Fractional) Knapsack

void continuousKnapsack() {
int i, j;
float totalProfit = 0;
int remaining = capacity;

// Calculate profit/weight ratio

Page 19
 Analysis & Design of Algorithms Lab (BCSL404)

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

ratio[i] = (float)profit[i] / weight[i];
}

// Sort items by ratio (highest first)

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

// Swap profits
int tempP = profit[i];
profit[i] = profit[j];
profit[j] = tempP;

// Swap weights
int tempW = weight[i];
weight[i] = weight[j];
weight[j] = tempW;
}
}
}

// Initialize fractions
for (i = 0; i < n; i++) {
fraction[i] = 0.0;
}

// Pick items into knapsack

for (i = 0; i < n; i++) {
if (weight[i] <= remaining) {
fraction[i] = 1.0;
totalProfit += profit[i];
remaining -= weight[i];
} else {
fraction[i] = (float)remaining / weight[i];
totalProfit += fraction[i] * profit[i];
break;
}
}

// Output result
printf("\n--- Continuous (Fractional) Knapsack ---\n");
Page 20
 Analysis & Design of Algorithms Lab (BCSL404)

printf("Total Profit: %.2f\n", totalProfit);

printf("Fractions of items included:\n");
for (i = 0; i < n; i++) {
printf("Item %d: %.2f\n", i + 1, fraction[i]);
}
}

// Function for Discrete (0/1) Knapsack

void discreteKnapsack() {
int i, j;
int totalProfit = 0;
int remaining = capacity;

// Items are already sorted by ratio in previous function

// Initialize fractions
for (i = 0; i < n; i++) {
fraction[i] = 0.0;
}

// Pick items into knapsack

for (i = 0; i < n; i++) {
if (weight[i] <= remaining) {
fraction[i] = 1.0; // Take whole item
totalProfit += profit[i];
remaining -= weight[i];
}
}

// Output result
printf("\n--- Discrete (0/1) Knapsack ---\n");
printf("Total Profit: %d\n", totalProfit);
printf("Items included (1: included, 0: not included):\n");
for (i = 0; i < n; i++) {
printf("Item %d: %.0f\n", i + 1, fraction[i]);
}
}

int main() {
int i;

printf("Enter number of items: ");

scanf("%d", &n);

printf("Enter weights:\n");
for (i = 0; i < n; i++)
Page 21
 Analysis & Design of Algorithms Lab (BCSL404)

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

printf("Enter profits:\n");
for (i = 0; i < n; i++)
scanf("%d", &profit[i]);

printf("Enter knapsack capacity: ");

scanf("%d", &capacity);

// First solve continuous knapsack

continuousKnapsack();

// Then solve discrete knapsack

discreteKnapsack();

return 0;
}

OUTPUT:

Enter number of items: 1 6 3

Enter weights:
10
20
30
Enter profits:
60
100
120
Enter knapsack capacity: 50

--- Continuous (Fractional) Knapsack ---

Total Profit: 240.00
Fractions of items included:
Item 1: 1.00
Item 2: 1.00
Item 3: 0.67

--- Discrete (0/1) Knapsack ---

Total Profit: 160
Items included (1: included, 0: not included):
Item 1: 1
Item 2: 1
Item 3: 0
Page 22
 Analysis & Design of Algorithms Lab (BCSL404)

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 100 // Maximum size of the array
int subset[MAX]; // Array to store the subset

void findSubset(int arr[], int n, int sum, int index, int subsetSize) {
if (sum == 0)
{ // Base case: subset found
printf("Subset found: ");
for (int i = 0; i < subsetSize; i++) {
printf("%d ", subset[i]);
}
printf("\n");
return;
}

if (index == n || sum < 0) { // No subset possible

return;
}

Page 23
 Analysis & Design of Algorithms Lab (BCSL404)

// Include the current element

subset[subsetSize] = arr[index];
findSubset(arr, n, sum - arr[index], index + 1, subsetSize + 1);

// Exclude the current element and move to the next

findSubset(arr, n, sum, index + 1, subsetSize);
}

int main() {
int n, sum;

printf("Enter the number of elements in the array: ");

scanf("%d", &n);

int arr[MAX];

printf("Enter the elements of the array: ");

for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

printf("Enter the target sum: ");

scanf("%d", &sum);

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

findSubset(arr, n, sum, 0, 0)
return 0;
}

OUTPUT:

Enter the number of elements in the array: 5

Enter the elements of the array: 1
2
5
6
8
Enter the target sum: 9
Subsets with sum 9 are:
Subset found: 1 2 6
Subset found: 1 8

Page 24
 Analysis & Design of Algorithms Lab (BCSL404)

9.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>

void selsort(int a[], int n)

{
int i, j, min, pos, temp;
for (j = 0; j < n - 1; j++)
{
min = a[j];
pos = j;
for (i = j + 1; i < n; i++)
{
if (a[i] < min)
{
min = a[i];
pos = i;
}
Page 25
 Analysis & Design of Algorithms Lab (BCSL404)

}
temp = a[j];
a[j] = min;
a[pos] = temp;
}
}

int main()
{
int a[1000], i, n;
clock_t start, end;
double dura;

printf("\nEnter the number of elements (n): ");

scanf("%d", &n);

srand(time(0)); // Seed the random number generator

// Generate random numbers and fill the array

printf("\nGenerated Random Array: ");
for (i = 0; i < n; i++)
{
a[i] = rand() % 1000; // Generate numbers between 0 and 999
printf("%d ", a[i]);
}

start = clock();
selsort(a, n);
end = clock();

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

printf("\n\nTime taken for sorting: %f seconds", dura);

printf("\nSorted Array: ");

for (i = 0; i < n; i++)
printf("%d ", a[i]);

printf("\n");
return 0;
}

OUTPUT:

Enter the number of elements (n): 6

Page 26
 Analysis & Design of Algorithms Lab (BCSL404)

Generated Random Array: 288 576 566 705 768 163

Time taken for sorting: 0.000004 seconds

Sorted Array: 163 288 566 576 705 768

10.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>

void quicksort(int arr[], int low, int high)

{
if (low < high)
{
int pivot = arr[high]; // Choosing the last element as pivot
int i = (low - 1), temp;

for (int j = low; j < high; j++)

{
if (arr[j] < pivot)
{
i++;
// Swap arr[i] and arr[j]
temp = arr[i];
arr[i] = arr[j];
Page 27
 Analysis & Design of Algorithms Lab (BCSL404)

arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (pivot)
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

int pi = i + 1; // Partition index

quicksort(arr, low, pi - 1);

quicksort(arr, pi + 1, high);
}
}

int main()
{
int *a, i, n;
clock_t start, end;
double dura;

printf("\nEnter the number of elements (n): ");

scanf("%d", &n);

// Allocate memory dynamically

a = (int*)malloc(n * sizeof(int));
if (a == NULL)
{
printf("Memory allocation failed!\n");
return 1;
}

srand(time(0)); // Seed random number generator

// Generate random numbers and fill the array

printf("\nGenerated Random Array: ");
for (i = 0; i < n; i++)
{
a[i] = rand() % 1000; // Generate numbers between 0 and 999
printf("%d ", a[i]);
}

start = clock();
quicksort(a, 0, n - 1);
end = clock();

Page 28
 Analysis & Design of Algorithms Lab (BCSL404)

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

printf("\n\nTime taken for sorting: %f seconds", dura);

printf("\nSorted Array: ");

for (i = 0; i < n; i++)
printf("%d ", a[i]);

printf("\n");

// Free allocated memory

free(a);

return 0;
}

OUTPUT:

Enter the number of elements (n): 5

Generated Random Array: 820 675 694 523 366

Time taken for sorting: 0.000001 seconds

Sorted Array: 366 523 675 694 820

Page 29
 Analysis & Design of Algorithms Lab (BCSL404)

11.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>

void quicksort(int arr[], int low, int high)

{
if (low < high)
{
int pivot = arr[high]; // Choosing the last element as pivot
int i = (low - 1), temp;

for (int j = low; j < high; j++)

{
if (arr[j] < pivot)
{
i++;
// Swap arr[i] and arr[j]
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Page 30
 Analysis & Design of Algorithms Lab (BCSL404)

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

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

int pi = i + 1; // Partition index

quicksort(arr, low, pi - 1);

quicksort(arr, pi + 1, high);
}
}

int main()
{
int a[1000], i, n;
clock_t start, end;
double dura;

printf("\nEnter the number of elements (n): ");

scanf("%d", &n);

srand(time(0)); // Seed random number generator

// Generate random numbers and fill the array

printf("\nGenerated Random Array: ");
for (i = 0; i < n; i++)
{
a[i] = rand() % 1000; // Generate numbers between 0 and 999
printf("%d ", a[i]);
}

start = clock();
quicksort(a, 0, n - 1);
end = clock();

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

printf("\n\nTime taken for sorting: %f seconds", dura);

printf("\nSorted Array: ");

for (i = 0; i < n; i++)
printf("%d ", a[i]);

printf("\n");
return 0;
}

Page 31
 Analysis & Design of Algorithms Lab (BCSL404)

OUTPUT:

Enter the number of elements (n): 6

Generated Random Array: 654 618 564 940 993 681

Time taken for sorting: 0.000001 seconds

Sorted Array: 564 618 654 681 940 993

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

#include <stdio.h>
#include <stdlib.h> // For abs() function
#include <math.h>

// Function to check if the queen can be placed at position (row, col)

int isSafe(int board[], int row) {
for (int i = 1; i < row; i++) {
if (board[i] == board[row] || abs(board[i] - board[row]) == abs(i - row)) {
return 0; // Conflict found
}
}
return 1; // Safe position
}

// Function to solve N-Queens using backtracking

void printSolution(int board[], int n, int *count) {
printf("\nSolution %d:\n", ++(*count));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
printf("%c ", j == board[i] ? 'Q' : 'X');
}
printf("\n");
}
}

int solveNQueens(int n) {
int board[10], row = 1, count = 0;
Page 32
 Analysis & Design of Algorithms Lab (BCSL404)

board[row] = 0; // Start placing queens

while (row > 0) { // Continue until all rows are processed

board[row]++; // Move to next column

while (board[row] <= n && !isSafe(board, row)) {

board[row]++; // Find a valid column
}

if (board[row] <= n) { // If valid position found

if (row == n) { // All queens placed successfully
printSolution(board, n, &count);
} else {
row++; // Move to the next row
board[row] = 0; // Reset column index
}
} else {
row--; // Backtrack if no valid column found
}
}
return count;
}

int main() {
int n;
printf("Enter the size of chessboard: ");
scanf("%d", &n);
printf("\nThe number of solutions: %d\n", solveNQueens(n));
return 0;
}

OUTPUT:

Enter the size of chessboard: 4

Solution 1:
XQXX
XXXQ
QXXX
XXQX

Solution 2:
XXQX
QXXX
XXXQ
Page 33
 Analysis & Design of Algorithms Lab (BCSL404)

XQXX

The number of solutions: 2

Page 34