LAB EXPERIMENT RECORD

On UCS3003 Design and Analysis of Algorithms Lab

SCHOOL OF COMPUTER SCIENCE AND ENGINEERING

IILM UNIVERSITY JANUARY 2025 - JUNE 2025

Submitted to: Submitted by:

Student Name:
Semester:
Roll Number:
 List of Experiments

S. Experiment Page Date of Signature

No No Experiment
.
1 Write a program to illustrate binary search using
divide and conquer
2 Write a program to find minimum and maximum in
an array using divide and conquer approach.
3 Write a program to implement Quick Sort
algorithm using divide and conquer.
4 Write a program to implement merge sort algorithm
using divide and conquer.
5 Write a program to implement Fractional Greedy
Knapsack problem.
6 Write a program to find solution for job
sequencing with deadlines problem.
7 Write a program to find minimum cost spanning
tree using Kruskal’s Algorithm.
8 Write a program to find minimum cost spanning
tree using Prim’s Algorithm.
9 Write a program to perform Single source
shortest path problem for a given graph using
Dijkastra’s Algorithm.
10 Implement 0/1 Knapsack problem using Dynamic
Programming.
11 Implement All-Pairs Shortest Paths Problem using
Floyd's algorithm.
12 Write a program to solve Traveling salesman
problem using dynamic programming.
13 Write a program to implement N Queen's problem
using Back Tracking.
14 Write a program to implement graph coloring
using backtracking.
15 Write a program to solve travelling salesman
problem using Branch and Bound.
 Program 1

Objective: Write a program to illustrate binary search using divide and conquer

Implementation Language: C

Code:

#include <stdio.h>

// Function to perform binary search

int binarySearch(int arr[], int low, int high, int key) {
if (low <= high) {
int mid = low + (high - low) / 2; // Calculate mid to avoid overflow

// Check if the key is at the middle

if (arr[mid] == key)
return mid;

// If the key is smaller than the middle element, search the left half
if (key < arr[mid])
return binarySearch(arr, low, mid - 1, key);

// If the key is larger, search the right half

return binarySearch(arr, mid + 1, high, key);
}
// Key not found
return -1;
}

int main() {
int n, key;

// Input size of the array

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

// Declare an array and input its elements

int arr[n];
printf("Enter %d elements (sorted in ascending order):\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the element to search

printf("Enter the element to search: ");
scanf("%d", &key);

// Perform binary search

int result = binarySearch(arr, 0, n - 1, key);

// Output the result

if (result != -1)
printf("Element %d found at index %d.\n", key, result);
else
printf("Element %d not found in the array.\n", key);

return 0;
}

Output :
Enter the number of elements in the array: 5
Enter 5 elements (sorted in ascending order):
2 4 6 8 10
Enter the element to search: 8
Element 8 found at index 3.
 Program 2

Objective: Write a program to find minimum and maximum in an array using divide and
conquer approach.

Implementation Language : C

Time Complexity: The divide-and-conquer approach has a time complexity of O(n), as it

performs fewer comparisons compared to a linear approach.

Code:

#include <stdio.h>

// Function to find minimum and maximum using divide and conquer

Struct MinMax {
int min;
int max;
};

MinMax findMinMax(int arr[], int low, int high) {

MinMax result, leftResult, rightResult;

// Base case: Single element

if (low == high) {
result.min = arr[low];
result.max = arr[low];
return result;
}

// Base case: Two elements

if (high == low + 1) {
if (arr[low] < arr[high]) {
result.min = arr[low];
result.max = arr[high];
} else {
 result.min = arr[high];
result.max = arr[low];
}
return result;
}

// Divide the array into two halves

int mid = (low + high) / 2;
leftResult = findMinMax(arr, low, mid);
rightResult = findMinMax(arr, mid + 1, high);

// Combine results
result.min = (leftResult.min < rightResult.min) ? leftResult.min : rightResult.min;
result.max = (leftResult.max > rightResult.max) ? leftResult.max : rightResult.max;

return result;
}

int main() {
int n;

// Input size of the array

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

int arr[n];

// Input array elements

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

// Find minimum and maximum using divide and conquer

 MinMax result = findMinMax(arr, 0, n - 1);

// Output results
printf("Minimum element: %d\n", result.min);
printf("Maximum element: %d\n", result.max);

return 0;
}

Output :
Enter the number of elements in the array: 6
Enter 6 elements:
23 12 45 67 1 34

Minimum element: 1
Maximum element: 67
 Program 3

Objective : Write a program to implement quick sort algorithm using divide and conquer
approach.

Implementation Language : C

Time Complexity:

• Best/Average Case: O(nlogn)

• Worst Case: O(n2) (occurs when the pivot is the smallest or largest element every time).

Code:

#include <stdio.h>

// Function to partition the array

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose the last element as the pivot
int i = low - 1; // Index for elements smaller than the pivot

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

if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// Place the pivot in the correct position

int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
 return i + 1; // Return the partition index
}

// Function to implement Quick Sort

void quickSort(int arr[], int low, int high) {
if (low < high) {
// Partition the array
int pi = partition(arr, low, high);

// Recursively sort the left and right halves

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

int main() {
int n;

// Input the size of the array

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

int arr[n];

// Input the elements of the array

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

// Perform Quick Sort

quickSort(arr, 0, n - 1);

// Output the sorted array

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

return 0;
}

Output :
Enter the number of elements in the array: 6
Enter 6 elements:
34 7 23 32 5 62
Sorted array:
5 7 23 32 34 62
 Program 4

Objective : Write a program to implement merge Sort using divide and conquer approach

Implementation Language : C

Code:

#include <stdio.h>

// Function to merge two subarrays

void merge(int arr[], int low, int mid, int high) {
int n1 = mid - low + 1; // Size of the left subarray
int n2 = high - mid; // Size of the right subarray

int left[n1], right[n2];

// Copy data to temporary arrays

for (int i = 0; i < n1; i++)
left[i] = arr[low + i];
for (int j = 0; j < n2; j++)
right[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into the original array

int i = 0, j = 0, k = low;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
 // Copy remaining elements of left[], if any
while (i < n1) {
arr[k] = left[i];
i++;
k++;
}

// Copy remaining elements of right[], if any

while (j < n2) {
arr[k] = right[j];
j++;
k++;
}
}

// Function to implement Merge Sort

void mergeSort(int arr[], int low, int high) {
if (low < high) {
// Find the middle point
int mid = low + (high - low) / 2;

// Recursively sort the left and right halves

mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);

// Merge the sorted halves

merge(arr, low, mid, high);
}
}

int main() {
int n;
 // Input the size of the array
printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n];

// Input the elements of the array

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

// Perform Merge Sort

mergeSort(arr, 0, n - 1);

// Output the sorted array

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

return 0;
}

Enter the number of elements in the array: 6

Enter 6 elements:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13
 Program 5

Objective: Write a program to implement fractional Greedy Knapsack problem.

Implementation Language : C

Code:

#include <stdio.h>

// Structure to represent an item

struct Item {

int value;

int weight;

};

// Function to swap two items

void swap(struct Item* a, struct Item* b) {

struct Item temp = *a;

*a = *b;

*b = temp;

// Function to sort items by value-to-weight ratio in descending order

void sortItems(struct Item arr[], int n) {

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

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

double r1 = (double)arr[j].value / arr[j].weight;

double r2 = (double)arr[j + 1].value / arr[j + 1].weight;

if (r1 < r2) {

swap(&arr[j], &arr[j + 1]);

// Function to calculate the maximum value for the knapsack

double fractionalKnapsack(struct Item arr[], int n, int capacity) {

sortItems(arr, n);

double totalValue = 0.0;

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

if (capacity >= arr[i].weight) {

 capacity -= arr[i].weight;

totalValue += arr[i].value;

} else {

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

break;

return totalValue;

int main() {

int n, capacity;

// Input number of items and knapsack capacity

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

scanf("%d", &n);

struct Item items[n];

 printf("Enter the value and weight of each item:\n");

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

printf("Item %d - Value: ", i + 1);

scanf("%d", &items[i].value);

printf("Item %d - Weight: ", i + 1);

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

printf("Enter the capacity of the knapsack: ");

scanf("%d", &capacity);

// Calculate the maximum value for the knapsack

double maxValue = fractionalKnapsack(items, n, capacity);

printf("Maximum value that can be obtained: %.2f\n", maxValue);

return 0;

Output :
Enter the number of items: 3

Enter the value and weight of each item:

Item 1 - Value: 60

Item 1 - Weight: 10

Item 2 - Value: 100

Item 2 - Weight: 20

Item 3 - Value: 120

Item 3 - Weight: 30

Enter the capacity of the knapsack: 50

Maximum value that can be obtained: 240.00

 Program: 6

Objective : Write a program to find solution to job sequencing with deadlines problem

Implementation Language : C

Code:

#include <stdio.h>

#define MAX 100

// Structure to represent a job

struct Job {

int id; // Job ID

int deadline; // Deadline of the job

int profit; // Profit if the job is completed

};

// Function to sort jobs based on profit in descending order

void sortJobs(struct Job jobs[], int n) {

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

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

if (jobs[j].profit < jobs[j + 1].profit) {

 // Swap the jobs

struct Job temp = jobs[j];

jobs[j] = jobs[j + 1];

jobs[j + 1] = temp;

// Function to find the maximum profit sequence of jobs

void jobSequencing(struct Job jobs[], int n) {

// Sort jobs in descending order of profit

sortJobs(jobs, n);

// Find the maximum deadline to determine the number of slots

int maxDeadline = 0;

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

if (jobs[i].deadline > maxDeadline) {

maxDeadline = jobs[i].deadline;

}
}

// Array to keep track of free time slots

int slots[MAX];

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

slots[i] = -1; // Initialize all slots as free

// Array to store the job sequence

int jobSequence[MAX];

int totalProfit = 0;

int jobCount = 0;

// Assign jobs to the available slots

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

// Find a free slot for the current job (starting from the last possible slot)

for (int j = jobs[i].deadline - 1; j >= 0; j--) {

if (slots[j] == -1) { // If the slot is free

slots[j] = i; // Assign this job to the slot

totalProfit += jobs[i].profit;
 jobSequence[j] = jobs[i].id;

jobCount++;

break;

// Print the job sequence and total profit

printf("Job sequence: ");

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

if (slots[i] != -1) {

printf("Job%d ", jobSequence[i]);

printf("\nTotal profit: %d\n", totalProfit);

int main() {

int n;
 // Input the number of jobs

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

scanf("%d", &n);

struct Job jobs[n];

// Input the jobs with their ID, deadline, and profit

printf("Enter the Job ID, Deadline, and Profit for each job:\n");

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

printf("Job %d: ", i + 1);

scanf("%d %d %d", &jobs[i].id, &jobs[i].deadline, &jobs[i].profit);

// Solve the job sequencing problem

jobSequencing(jobs, n);

return 0;

Enter the number of jobs: 4

Enter the Job ID, Deadline, and Profit for each job:

Job 1: 1 4 70

Job 2: 2 1 80

Job 3: 3 1 30

Job 4: 4 1 100

Job sequence: Job4 Job1 Job2

Total profit: 250

 Program 7
Objective : Write a Program to find minimum cost spanning tree using Kruskal’s Algorithm.

Implementation Language : C

Code:

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

// Structure to represent an edge

struct Edge {
int u, v, weight;
};

// Structure to represent a subset (for Union-Find)

struct Subset {
int parent;
int rank;
};

// Function to compare two edges based on their weight (for sorting)

int compareEdges(const void *a, const void *b) {
return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Find the subset of an element (with path compression)

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

// Union of two subsets (by rank)

void unionSets(struct Subset subsets[], int xroot, int yroot) {
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++;
}
}

// Kruskal's Algorithm to find MST

void kruskal(struct Edge edges[], int V, int E) {
struct Edge result[V]; // To store the final MST
int e = 0; // Count of edges in MST
int i = 0; // Initial index of sorted edges

// Step 1: Sort all edges in non-decreasing order of their weight

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

// Create V subsets with single elements

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

// Step 2: Pick the smallest edge. Check if it forms a cycle with the MST so far.
while (e < V - 1 && i < E) {
struct Edge next_edge = edges[i++];

int x = find(subsets, next_edge.u);

int y = find(subsets, next_edge.v);

// If including this edge does not form a cycle, include it in the result
// and take the union of these two vertices
 if (x != y) {
result[e++] = next_edge;
unionSets(subsets, x, y);
}
}

// Step 3: Print the MST

printf("Edges in the Minimum Cost Spanning Tree:\n");
int minCost = 0;
for (int j = 0; j < e; j++) {
printf("%d - %d: %d\n", result[j].u, result[j].v, result[j].weight);
minCost += result[j].weight;
}
printf("\nMinimum cost of the spanning tree: %d\n", minCost);

// Free memory
free(subsets);
}

int main() {
int V, E;

// Input the number of vertices and edges

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

struct Edge edges[E];

// Input the edges (u, v, weight)

printf("Enter the edges (u, v, weight):\n");
for (int i = 0; i < E; i++) {
scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
 }

// Run Kruskal's algorithm to find MST

kruskal(edges, V, E);

return 0;
}

Output:
Enter the number of vertices: 4
Enter the number of edges: 5
Enter the edges (u, v, weight):
0 1 10
026
035
1 3 15
234
Edges in the Minimum Cost Spanning Tree:
2 - 3: 4
0 - 3: 5
0 - 1: 10

Minimum cost of the spanning tree: 19

 Program 8

Objective : Write a Program to find minimum cost spanning tree using Prim’s Algorithm.
Implementation Language : C
Code:
#include <stdio.h>
#include <limits.h>

#define MAX 100

// Function to find the vertex with the minimum key value that is not yet included in the MST
int minKey(int key[], int mstSet[], int V) {
int min = INT_MAX, minIndex;
for (int v = 0; v < V; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}

// Function to implement Prim's Algorithm to find the MST

void primMST(int graph[MAX][MAX], int V) {
int parent[V]; // Array to store the constructed MST
int key[V]; // Key values used to pick the minimum weight edge
int mstSet[V]; // To represent the set of vertices included in MST

// Initialize all key values as INFINITE

for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = 0; // Vertex i is not yet included in MST
}
 // Always include the first vertex in the MST
key[0] = 0; // Set the key value of the first vertex to 0
parent[0] = -1; // First node is the root of the MST

// The MST will have V vertices

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

// Include the picked vertex in the MST set

mstSet[u] = 1;

// Update key values and parent index of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++) {
// Update key[v] only if graph[u][v] is smaller than key[v]
if (graph[u][v] != 0 && mstSet[v] == 0 && graph[u][v] < key[v]) {
key[v] = graph[u][v];
parent[v] = u;
}
}
}

// Print the constructed MST

printf("Edge \tWeight\n");
int totalWeight = 0;
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
totalWeight += graph[i][parent[i]];
}
printf("\nTotal weight of the Minimum Spanning Tree: %d\n", totalWeight);
}

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

int graph[MAX][MAX];

// Input the adjacency matrix representing the graph

printf("Enter the adjacency matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
scanf("%d", &graph[i][j]);
}
}
// Run Prim's algorithm to find MST
primMST(graph, V);
return 0;
}

Output :
Enter the number of vertices: 5
Enter the adjacency matrix:
02060
20385
03007
68090
05700
Edge Weight
0-1 2
1-2 3
0-3 6
1-4 5

Total weight of the Minimum Spanning Tree: 16

 Program 9

Objective: Write a program to perform Single Source shortest path problem for a given graph

using Dijkastra’s Algorithm.

Implementation Language: C

Code :

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

#define MAX 100

#define INF INT_MAX

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

int minDistance(int dist[], int sptSet[], int V) {
int min = INF, minIndex;

// Find the vertex with the minimum distance value

for (int v = 0; v < V; v++) {
if (sptSet[v] == 0 && dist[v] <= min) {
min = dist[v];
minIndex = v;
}
}
return minIndex;
}

// Function to implement Dijkstra's Algorithm for Single Source Shortest Path

void dijkstra(int graph[MAX][MAX], int V, int src) {
int dist[V]; // Array to store the shortest distance from the source
int sptSet[V]; // Shortest Path Tree set to track vertices included in the MST

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

for (int i = 0; i < V; i++) {
 dist[i] = INF;
sptSet[i] = 0;
}

// Distance from the source to itself is 0

dist[src] = 0;

// Find the 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
int u = minDistance(dist, sptSet, V);

// Include the picked vertex in the shortest path tree

sptSet[u] = 1;

// Update the distance value of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++) {
// Update dist[v] if and only if the current vertex is not in the shortest path tree
// and there is an edge from u to v and the total weight of path through u is smaller
than the current distance of v
if (sptSet[v] == 0 && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] <
dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the calculated shortest distances

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

int main() {
int V, E, src;

// Input the number of vertices and edges

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

int graph[MAX][MAX] = {0}; // Initialize the graph with 0 (no edges)

// Input the graph (adjacency matrix)

printf("Enter the edges (u, v, weight):\n");
for (int i = 0; i < E; i++) {
int u, v, weight;
scanf("%d %d %d", &u, &v, &weight);
graph[u][v] = weight;
graph[v][u] = weight; // For undirected graph, we add the edge in both directions
}

// Input the source vertex

printf("Enter the source vertex: ");
scanf("%d", &src);

// Run Dijkstra's algorithm to find shortest paths

dijkstra(graph, V, src);

return 0;
}
Output:

Enter the number of vertices: 5

Enter the number of edges: 7

Enter the edges (u, v, weight):

0 1 10

0 2 20

1 2 30

1 3 40

2 3 10

2 4 50

3 4 20

Enter the source vertex: 0

Vertex Distance from Source

0 0

1 10

2 20

3 30

4 50
 Program 10

Objective: Implement 0/1 Knapsack problem using Dynamic Programming

Implementation Language : C

Code:

#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

void knapsack(int weights[], int values[], int n, int W) {
int dp[n + 1][W + 1];

// Initialize the dp table

for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0; // Base case: no items or zero capacity
} else if (weights[i - 1] <= w) {
// Include or exclude the current item
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
// Exclude the current item
dp[i][w] = dp[i - 1][w];
}
}
}

// The maximum value that can be obtained

printf("Maximum value in Knapsack = %d\n", dp[n][W]);
 // To find the items included in the knapsack
printf("Items included in the knapsack:\n");
int w = W;
for (int i = n; i > 0 && w > 0; i--) {
if (dp[i][w] != dp[i - 1][w]) {
printf("Item %d (Weight = %d, Value = %d)\n", i, weights[i - 1], values[i - 1]);
w -= weights[i - 1];
}
}
}

int main() {
int n, W;

// Input the number of items

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

int weights[n], values[n];

// Input the weights and values of the items

printf("Enter the weights of the items:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &weights[i]);
}

printf("Enter the values of the items:\n");

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

// Input the capacity of the knapsack

printf("Enter the capacity of the knapsack: ");
 scanf("%d", &W);

// Solve the 0/1 Knapsack Problem

knapsack(weights, values, n, W);

return 0;
}

Output:
Enter the number of items: 4
Enter the weights of the items:
2345
Enter the values of the items:
3456
Enter the capacity of the knapsack: 5
Maximum value in Knapsack = 7
Items included in the knapsack:
Item 2 (Weight = 3, Value = 4)
Item 1 (Weight = 2, Value = 3)
 Program 11

Objective : Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm.

Implementation Language :

Code:

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

#define MAX 100

#define INF INT_MAX

// Function to implement Floyd's Algorithm

void floydWarshall(int graph[MAX][MAX], int V) {
int dist[V][V];

// Initialize the solution matrix same as the input graph matrix

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

// Update the solution matrix for each intermediate vertex

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] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
 // Print the final shortest distance matrix
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("INF ");
} else {
printf("%d ", dist[i][j]);
}
}
printf("\n");
}
}

int main() {
int V, E;

// Input the number of vertices and edges

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

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

scanf("%d", &E);

// Initialize the graph with INF for all pairs

int graph[MAX][MAX];
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i == j) {
graph[i][j] = 0; // Distance to self is 0
} else {
graph[i][j] = INF; // No direct edge means infinite distance
}
 }
}

// Input the edges and their weights

printf("Enter the edges (u, v, weight):\n");
for (int i = 0; i < E; i++) {
int u, v, weight;
scanf("%d %d %d", &u, &v, &weight);
graph[u][v] = weight;
}

// Run Floyd's Algorithm

floydWarshall(graph, V);

return 0;
}

Output:
Enter the number of vertices: 4
Enter the number of edges: 5
Enter the edges (u, v, weight):
015
0 3 10
123
231
302
Shortest distances between every pair of vertices:
0589
INF 0 3 4
INF INF 0 1
2 7 10 0
 Program – 12
Objective: Write a program to solve travelling Salesman Problem using dynamic
Programming.
Implementation Language : C
Code :
#include <stdio.h>
#include <limits.h>

#define MAX 16
#define INF INT_MAX

int tsp(int graph[MAX][MAX], int n) {

int dp[1 << MAX][MAX]; // DP table to store minimum costs
int mask, i, j, k;

// Initialize all values to INF

for (mask = 0; mask < (1 << n); mask++) {
for (i = 0; i < n; i++) {
dp[mask][i] = INF;
}
}

// Base case: Starting at city 0

dp[1][0] = 0;

// Fill the DP table

for (mask = 0; mask < (1 << n); mask++) {
for (i = 0; i < n; i++) {
if (mask & (1 << i)) { // If city i is in the current mask
for (j = 0; j < n; j++) {
if (!(mask & (1 << j)) && graph[i][j] != INF) { // If city j is not visited
dp[mask | (1 << j)][j] =
(dp[mask][i] + graph[i][j] < dp[mask | (1 << j)][j]) ?
dp[mask][i] + graph[i][j] : dp[mask | (1 << j)][j];
 }
}
}
}
}

// Find the minimum cost to return to the starting city

int minCost = INF;
for (i = 1; i < n; i++) {
if (graph[i][0] != INF) {
minCost = (dp[(1 << n) - 1][i] + graph[i][0] < minCost) ?
dp[(1 << n) - 1][i] + graph[i][0] : minCost;
}
}

return minCost;
}

int main() {
int n;
int graph[MAX][MAX];

// Input the number of cities

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

// Input the cost matrix

printf("Enter the cost matrix (use %d for no direct path):\n", INF);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
 // Solve the TSP using Dynamic Programming
int result = tsp(graph, n);

if (result == INF) {
printf("No possible tour exists.\n");
} else {
printf("The minimum cost of the tour is: %d\n", result);
}

return 0;
}

Output:
Enter the number of cities: 4
Enter the cost matrix (use 2147483647 for no direct path):
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
The minimum cost of the tour is: 80
 Program – 13
Objective: Write a program to implement N Queen’s problem using Back Tracking
Implementation Language : C
Code :
#include <stdio.h>
#include <stdbool.h>
#define MAX 20

int board[MAX][MAX]; // Board representation

// Function to print the board configuration

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

// Function to check if a queen can be placed at board[row][col]

bool isSafe(int row, int col, int n) {
// Check the same column
for (int i = 0; i < row; i++) {
if (board[i][col]) {
return false;
}
}

// Check the upper left diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
 }
}
// Check the upper right diagonal
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j]) {
return false;
}
}
return true;
}

// Function to solve the N-Queens problem using backtracking

bool solveNQueens(int row, int n) {
// Base case: If all queens are placed, return true
if (row == n) {
printSolution(n);
return true;
}
bool res = false;
// Try placing a queen in each column for the current row
for (int col = 0; col < n; col++) {
if (isSafe(row, col, n)) {
board[row][col] = 1; // Place the queen

// Recur to place the rest of the queens

res = solveNQueens(row + 1, n) || res;

board[row][col] = 0; // Backtrack: Remove the queen

}
}

return res;
}
int main() {
int n;

// Input the size of the board

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

// Initialize the board to 0

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

// Solve the N-Queens problem

if (!solveNQueens(0, n)) {
printf("No solution exists for N = %d.\n", n);
}

return 0;
}

Output :
Enter the number of queens (N): 4
1000
0010
0100
0001

1000
0001
0100
0010
 Program – 14
Objective : Write a program to implement graph coloring using backtracking
Implementation Language : C
Code:
#include <stdio.h>
#include <stdbool.h>

#define MAX 20

int graph[MAX][MAX]; // Adjacency matrix of the graph

int color[MAX]; // Array to store colors of vertices

// Function to check if it is safe to color vertex v with color c

bool isSafe(int v, int c, int n) {
for (int i = 0; i < n; i++) {
if (graph[v][i] && color[i] == c) { // Adjacent vertex has the same color
return false;
}
}
return true;
}

// Function to solve the graph coloring problem using backtracking

bool graphColoring(int v, int n, int m) {
// If all vertices are assigned a color, return true
if (v == n) {
return true;
}

// Try assigning each color from 1 to m to vertex v

for (int c = 1; c <= m; c++) {
if (isSafe(v, c, n)) {
color[v] = c; // Assign color c to vertex v
 // Recur for the next vertex
if (graphColoring(v + 1, n, m)) {
return true;
}

// Backtrack: Remove the color assignment

color[v] = 0;
}
}

// If no color can be assigned, return false

return false;
}

int main() {
int n, m;

// Input the number of vertices

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

// Input the adjacency matrix

printf("Enter the adjacency matrix of the graph:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}

// Input the number of colors

printf("Enter the number of colors: ");
scanf("%d", &m);

// Initialize all vertices with no color (0)

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

// Solve the graph coloring problem

if (graphColoring(0, n, m)) {
printf("Solution exists. The colors assigned to the vertices are:\n");
for (int i = 0; i < n; i++) {
printf("Vertex %d -> Color %d\n", i, color[i]);
}
} else {
printf("No solution exists with %d colors.\n", m);
}

return 0;
}

Output:
Enter the number of vertices: 4
Enter the adjacency matrix of the graph:
0111
1010
1101
1010
Enter the number of colors: 3
Solution exists. The colors assigned to the vertices are:
Vertex 0 -> Color 1
Vertex 1 -> Color 2
Vertex 2 -> Color 3
Vertex 3 -> Color 2
 Program – 15
Program: Write a program to solve travelling salesman problem using Branch and Bound.
Implementation Language: C
Code:
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define MAX 20
#define INF INT_MAX

int n; // Number of cities

int graph[MAX][MAX]; // Cost matrix
int finalPath[MAX]; // Stores the final path
bool visited[MAX]; // Keeps track of visited cities
int finalCost = INF; // Stores the minimum cost

// Function to copy temporary solution to the final solution

void copyToFinal(int tempPath[]) {
for (int i = 0; i < n; i++) {
finalPath[i] = tempPath[i];
}
finalPath[n] = tempPath[0];
}

// Function to calculate the lower bound of the current path

int calculateBound(int currPath[], int level) {
int bound = 0;

// Add the edge costs to/from the visited cities

for (int i = 0; i < level; i++) {
bound += graph[currPath[i]][currPath[i + 1]];
}
 // Add the minimum cost of outgoing edges for the remaining cities
for (int i = 0; i < n; i++) {
if (!visited[i]) {
int minCost = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && i != j) {
minCost = (graph[i][j] < minCost) ? graph[i][j] : minCost;
}
}
bound += minCost;
}
}

return bound;
}

// Branch and Bound function to solve TSP

void branchAndBound(int currBound, int currCost, int level, int currPath[]) {
if (level == n) {
// Return to the starting city
currCost += graph[currPath[level - 1]][currPath[0]];
if (currCost < finalCost) {
copyToFinal(currPath);
finalCost = currCost;
}
return;
}

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

if (!visited[i] && graph[currPath[level - 1]][i]) {
int tempBound = currBound;
int tempCost = currCost + graph[currPath[level - 1]][i];

currPath[level] = i;
 visited[i] = true;

if (tempCost + calculateBound(currPath, level + 1) < finalCost) {

branchAndBound(tempBound, tempCost, level + 1, currPath);
}

visited[i] = false;
}
}
}

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

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

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

// Initialize variables
int currPath[MAX];
for (int i = 0; i < n; i++) {
visited[i] = false;
currPath[i] = -1;
}

// Start from the first city

visited[0] = true;
currPath[0] = 0;

// Calculate the initial bound and solve the TSP

 branchAndBound(0, 0, 1, currPath);

// Output the result

printf("Minimum cost: %d\n", finalCost);
printf("Path: ");
for (int i = 0; i <= n; i++) {
printf("%d ", finalPath[i]);
}
printf("\n");

return 0;
}

Output:
Enter the number of cities: 4
Enter the cost matrix (use 2147483647 for infinity):
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0
Minimum cost: 80
Path: 0 1 3 2 0